Securing Approximate Homomorphic Encryption Using Differential Privacy¶
Authors: Li, Micciancio, Schultz, Sorrell
Year: 2022
Venue: CRYPTO 2022
type: scheme collection: catalogue, schemes status: auto
Links: ePrint 2022/816
Visual lesson: IND-CPA-D secure CKKS (noise flooding) · Scheme table row: IND-CPA-D secure CKKS (noise flooding)
Summary¶
Auto-extracted summary (unreviewed)
Building on the Li-Micciancio key-recovery attack on CKKS, this paper shows how to turn any IND-CPA-secure approximate homomorphic encryption scheme into an IND-CPA^D-secure one by post-processing decryption with a differentially private mechanism whose noise is calibrated to the worst-case error of the homomorphic computation. For CKKS, adding Gaussian noise suffices, and nearly matching bounds show that kappa/2 + O~(1) bits of noise are sufficient while kappa/4 - Omega~(1) bits are necessary for kappa-bit IND-CPA^D security; a finer-grained (computational c, statistical s) bit-security notion yields smaller practical noise. The authors also prove that 'dynamic' noise estimates tailored to a given ciphertext are vulnerable to IND-CPA^D attacks, and propose parameters for the countermeasures adopted by open-source CKKS libraries.
Abstract¶
Recent work of Li and Micciancio (Eurocrypt 2021) has shown that the traditional formulation of indistinguishability under chosen plaintext attack (IND-CPA) is not adequate to capture the security of approximate homomorphic encryption against passive adversaries, and identi- fied a stronger IND-CPAD security definition (IND-CPA with decryption oracles) as the appropriate security target for approximate encryption schemes. We show how to transform any approximate homomorphic encryption scheme achieving the weak IND-CPA security definition, into one which is provably IND-CPAD secure, offering strong guarantees against realistic passive attacks. The method works by postprocessing the output of the decryption function with a mechanism satisfying an appropriate notion of differential privacy (DP), adding an amount of noise tailored to the worst-case error growth of the homomorphic computation. We apply these results to the approximate homomorphic encryption scheme of Cheon, Kim, Kim, and Song (CKKS, Asiacrypt 2017), proving that adding Gaussian noise to the output of CKKS decryption suffices to achieve IND-CPAD security. We precisely quantify how much Gaussian noise must be added by proving nearly matching upper and lower bounds, showing that one cannot hope to significantly reduce the amount of noise added in this post-processing step. As an additional contribution, we present and use a finer grained definition of bit security that distinguishes between a computational security parameter (c) and a statistical one (s). Based on our upper and lower bounds, we propose parameters for the counter-measures recently adopted by open-source libraries implementing CKKS. Lastly, we investigate the plausible claim that smaller DP noise parameters might suffice to achieve IND-CPAD-security for schemes supporting more accurate (dynamic, key dependent) estimates of ciphertext noise during decryption. Perhaps surprisingly, we show that this claim is false, and that DP mechanisms with noise parameters tailored to the error present in a given ciphertext, rather than worst-case error, are vulnerable to IND-CPAD attacks. ⋆Research supported by Global Research Cluster program of Samsung Advanced Institute of Technology and NSF Award 1936703. 2 B. Li et al.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Generic transformation from IND-CPA to IND-CPA^D security for approximate HE via differentially private post-processing of decryption | llm | 0.85 |
| contribution | Proof that Gaussian noise added to CKKS decryption achieves IND-CPA^D security, with nearly matching upper and lower bounds on the noise | llm | 0.85 |
| contribution | Finer-grained bit-security definition separating computational (c) and statistical (s) security parameters | llm | 0.85 |
| contribution | Concrete parameter proposals for countermeasures adopted by open-source CKKS libraries | llm | 0.85 |
| contribution | Attack showing that DP mechanisms with dynamic (ciphertext-specific) noise estimates are insecure | llm | 0.85 |
| schemes | CKKS | llm | 0.85 |
| schemes | differential privacy | llm | 0.85 |
| libraries | HElib | llm | 0.85 |
| libraries | Lattigo | llm | 0.85 |
| libraries | PALISADE | llm | 0.85 |
| tasks | IND-CPA^D security of approximate homomorphic encryption | llm | 0.85 |
| security level | kappa-bit IND-CPA^D; (c, s) computational/statistical bit security | llm | 0.85 |
| threat model | passive adversary with access to decryption oracle (IND-CPA^D) | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| code url | https://github.com/ucsd-crypto/DynamicEstimationAttack (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/homenc/HElib (URL found in the full text) | regex | 0.50 |
| code url | http://github.com/ldsec/lattigo (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/ucsd-crypto/DynamicEstimationAttack | llm | 0.85 |
| limitations | Countermeasure requires FHE libraries supporting 128-bit precision; 64-bit-precision libraries may only support low-precision applications or aggressive parameters | llm | 0.85 |
| limitations | Exact scaling (kappa/4 vs kappa/2) of the required noise remains open | llm | 0.85 |
| limitations | Results on dynamic error estimation are negative; weaker security notions for it are not ruled out | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | sufficient added noise: kappa/2 + O~(1) bits (kappa-bit IND-CPA^D for CKKS with static error estimates (Theorem 3)) | llm | 0.85 |
| key result | necessary added noise: kappa/4 - Omega~(1) bits (kappa-bit IND-CPA^D for CKKS (Theorem 4)) | llm | 0.85 |
| key result | sufficient added noise under relaxed notion: s/2 + O~(1) bits ((c, s)-bit q-IND-CPA^D security (Theorem 5)) | llm | 0.85 |
Scheme card: IND-CPA-D secure CKKS (noise flooding)¶
| Group | 1. CKKS and its variants |
| Kind | Variant |
| Hardness assumption | RLWE |
| Plaintext type | Approximate real/complex |
| SIMD packing | Yes |
| Bootstrapping | Yes |
| Post-quantum | Yes |
| Status | Active |
| Fit for LLM inference | Needed when decrypted results go back to the server or other parties. Fixes the Li–Micciancio key-recovery attack (EUROCRYPT 2021). |
| Follow-ups | Discrete-CKKS high-precision bootstrapping (2025/1786) supports the large precision noise flooding needs. |
| Libraries | OpenFHE |
| Follow-up papers in the archive | Leveraging Discrete CKKS to Bootstrap in High Precision |
System card: IND-CPA-D secure CKKS (noise flooding / DP)¶
| Group | 2. CKKS core and variants |
| Family | CKKS + noise flooding |
| Arithmetic | Approximate real/complex |
| Interaction | Non-interactive |
| Model scale | - |
| Status | Active |
| Relation to the SoK | Hardened CKKS decryption for threshold or shared-output settings. |
| Note | Implemented as NOISE_FLOODING_DECRYPT in OpenFHE. Costs some precision. |
| Code | https://github.com/openfheorg/openfhe-development |
| Systems page | IND-CPA-D secure CKKS (noise flooding / DP) |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 96 [p.1]
- library: PALISADE 10 [p.4], HElib 6 [p.4], Lattigo 4 [p.22], Microsoft SEAL 2 [p.30], Concrete (Zama) 1 [p.21]
- model: SVM 1 [p.30], Logistic regression 1 [p.29]
- technique: Rescaling 3 [p.24], Bootstrapping 2 [p.28]
- assumption: IND-CPA-D 91 [p.1], IND-CPA 45 [p.1], Lattice-based 12 [p.2], LWE 3 [p.2], RLWE 2 [p.18]
- task: Language modeling / generation 3 [p.24]
- topic: Homomorphic encryption 83 [p.1], Open source 7 [p.1]
Related papers¶
- Leveraging Discrete CKKS to Bootstrap in High Precision follow up of this paper — follow-up listed for scheme "IND-CPA-D secure CKKS (noise flooding)"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/2-026_securing-approximate-homomorphic-encryption-using-differenti.pdf |
catalogue | 38 | 556.9 KB | 5b185f2a5ee8 |
|
references/schemes/s05-0_securing-approximate-homomorphic-encryption-using-differenti.pdf |
schemes | 38 | 556.9 KB | 5b185f2a5ee8 |
byte-identical to references/catalogue/2-026_securing-approximate-homomorphic-encryption-using-differenti.pdf |
Database key: securing-approximate-homomorphic-encryption-using-differential-privacy · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set securing-approximate-homomorphic-encryption-using-differential-privacy COLUMN VALUE