Skip to content

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]

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