Skip to content

On the precision loss in approximate homomorphic encryption

Authors: A. Costache; B. R. Curtis; E. Hales; S. Murphy; T. Ogilvie; R. Player
Year: 2024

type: theory collection: sok-references status: auto

Links: ePrint 2022/162

Summary

Auto-extracted summary (unreviewed)

Gives a comprehensive noise analysis of CKKS that accounts for both encoding and homomorphic-operation noise, introducing the first average-case (CLT) analysis and refining prior worst-case canonical-embedding bounds, for both textbook and RNS CKKS. Experiments in HEAAN and FullRNS-HEAAN show the new heuristics shrink the heuristic-to-practical gap from roughly 6-8 bits to under 1 bit, but they sometimes slightly underestimate the observed noise, pointing to the need for implementation-specific noise analyses.

Abstract

Since its introduction at Asiacrypt 2017, the CKKS approximate homomorphic encryption scheme has become one of the most widely used and implemented homomorphic encryption schemes. Due to the approximate nature of the scheme, application developers using CKKS must ensure that the evaluation output is within a tolerable error of the corresponding plaintext computation. Choosing appropriate parameters requires a good understanding of how the noise will grow through the computation. A strong understanding of the noise growth is also necessary to limit the performance impact of mitigations to the attacks on CKKS presented by Li and Micciancio (Eurocrypt 2021). In this work we present a comprehensive noise analysis of CKKS, that considers noise coming both from the encoding and homomorphic operations. Our main contribution is the first average-case analysis for CKKS noise, and we also introduce refinements to prior worst-case noise analyses. We develop noise heuristics both for the original CKKS scheme and the RNS variant presented at SAC 2018. We then evaluate these heuristics by comparing the predicted noise growth with experiments in the HEAAN and FullRNS-HEAAN libraries, and by comparing with a worst-case noise analysis as done in prior work. Our findings show mixed results: while our new analyses lead to heuristic estimates that more closely model the observed noise growth than prior approaches, the new heuristics sometimes slightly underestimate the observed noise growth. This evidences the need for implementation-specific noise analyses for CKKS, which recent work has shown to be effective for implementations of similar schemes.
Source: pdf

Extracted details

Field Value Source Confidence
contribution first average-case noise analysis for CKKS llm 0.90
contribution refined worst-case canonical embedding noise bounds llm 0.90
contribution noise heuristics for textbook CKKS and the RNS variant llm 0.90
contribution experimental validation against HEAAN and FullRNS-HEAAN llm 0.90
schemes CKKS llm 0.90
schemes RNS-CKKS llm 0.90
libraries HEAAN llm 0.90
libraries FullRNS-HEAAN llm 0.90
tasks noise analysis and parameter selection llm 0.90
interaction non-interactive FHE llm 0.90
code url https://github.com/bencrts/CKKS_noise.Experimental (URL found in the full text) regex 0.50
code url https://github.com/KyoohyungHan/FullRNS-HEAAN (URL found in the full text) regex 0.50
code url https://github.com/snucrypto/HEAAN (URL found in the full text) regex 0.50
code url https://github.com/bencrts/CKKS_noise llm 0.90
limitations new heuristics sometimes slightly underestimate the observed noise llm 0.90
limitations observed noise jump at log N = 14 in the RNS variant is not captured by any heuristic llm 0.90
limitations a refined theory of CKKS noise and implementation-specific analyses are needed llm 0.90
llm relevance low llm 0.90
key result heuristic-to-practical noise gap: reduced from about 8 bits to under 1 bit (textbook CKKS plaintext space, CLT vs prior canonical embedding, HEAAN, 1000 trials) llm 0.90
key result heuristic-to-practical noise gap: reduced from about 6 bits to under 1 bit (RNS variant, FullRNS-HEAAN) llm 0.90
key result underestimate of message-space noise: 3 to 7 bits (CLT and CE approaches, textbook CKKS message space) llm 0.90

SoK reference [66]

A. Costache, B. R. Curtis, E. Hales, S. Murphy, T. Ogilvie, and R. Player, “On the precision loss in approximate homomorphic encryption,” in SAC 2023: 30th Annual International Workshop on Selected Areas in Cryptography, ser. Lecture Notes in Computer Science, C. Carlet, K. Mandal, and V. Rijmen, Eds., vol. 14201. Fredericton, Canada: Springer, Cham, Switzerland, Aug. 14-18, 2024, pp. 325–345.

Listed on the reference page of the site.

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: CKKS 131 [p.1], BFV 9 [p.2], BGV 8 [p.2], RSA 5 [p.26], TFHE 2 [p.2], Leveled / somewhat HE 2 [p.26]
  • library: HElib 4 [p.21], Microsoft SEAL 2 [p.28], PALISADE 1 [p.28], Lattigo 1 [p.27], Zama 1 [p.1]
  • model: Logistic regression 1 [p.27]
  • technique: RNS 65 [p.1], Rescaling 29 [p.5], Key switching 8 [p.6], Bootstrapping 4 [p.26]
  • assumption: LWE 9 [p.2], RLWE 6 [p.5], IND-CPA-D 6 [p.4], Lattice-based 3 [p.27], IND-CPA 2 [p.25]
  • task: Language modeling / generation 11 [p.4]
  • topic: Homomorphic encryption 20 [p.1], Open source 9 [p.2]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/sok-references/066_on-the-precision-loss-in-approximate-homomorphic-encryption.pdf sok-references 38 591.5 KB a4ee82afaeed

Database key: on-the-precision-loss-in-approximate-homomorphic-encryption · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set on-the-precision-loss-in-approximate-homomorphic-encryption COLUMN VALUE