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