Skip to content

On the Security of Homomorphic Encryption on Approximate Numbers

Authors: B. Li; D. Micciancio
Year: 2021
Venue: EUROCRYPT 2021

type: scheme collection: catalogue, sok-references status: auto

Links: ePrint 2020/1533

Summary

Auto-extracted summary (unreviewed)

Presents a passive, polynomial-time key-recovery attack on CKKS that exploits the fact that decryption returns the message plus the encryption noise, so an adversary who sees decrypted approximate results can recover the secret key. The attack is implemented against HEAAN, PALISADE, SEAL, HElib and RNS-HEAAN on common ML computations (variance, logistic and exponential series) and succeeds in seconds for most parameters; the paper then defines IND-CPA^D security for approximate encryption, proves relations among variants, and discusses countermeasures.

Abstract

We present passive attacks against CKKS, the homomorphic encryption scheme for arithmetic on approximate numbers presented at Asiacrypt 2017. The attack is both theoretically efficient (running in expected polynomial time) and very practical, leading to complete key recovery with high probability and very modest running times. We implemented and tested the attack against major open source homomorphic encryption libraries, including HEAAN, SEAL, HElib and PALISADE, and when computing several functions that often arise in applications of the CKKS scheme to machine learning on encrypted data, like mean and variance computations, and approximation of logistic and exponential functions using their Maclaurin series. The attack shows that the traditional formulation of IND-CPA security (or indistinguishability against chosen plaintext attacks) achieved by CKKS does not adequately capture security against passive adversaries when applied to approximate encryption schemes, and that a different, stronger definition is required to evaluate the security of such schemes. We provide a solid theoretical basis for the security evaluation of homomorphic encryption on approximate numbers (against passive attacks) by proposing new definitions, that naturally extend the traditional notion of IND-CPA security to the approximate computation setting. We propose both indistinguishability-based and simulation-based variants, as well as restricted versions of the definitions that limit the order and number of adversarial queries (as may be enforced by some applications). We prove implications and separations among different definitional variants, and discuss possible modifications to CKKS that may serve as a countermeasure to our attacks.
Source: pdf

Extracted details

Field Value Source Confidence
contribution linear key-recovery attack on CKKS from decryption results llm 0.90
contribution attack implementation against HEAAN, PALISADE, SEAL, HElib and RNS-HEAAN llm 0.90
contribution IND-CPA^D security definitions (indistinguishability and simulation based) for approximate HE llm 0.90
contribution implications and separations among definitional variants llm 0.90
contribution discussion of countermeasures for CKKS llm 0.90
schemes CKKS llm 0.90
libraries HEAAN llm 0.90
libraries PALISADE llm 0.90
libraries SEAL llm 0.90
libraries HElib llm 0.90
libraries RNS-HEAAN llm 0.90
tasks key recovery attack llm 0.90
tasks variance computation llm 0.90
tasks logistic and exponential function approximation llm 0.90
threat model passive adversary who observes ciphertexts and decrypted approximate results (IND-CPA^D) llm 0.90
interaction non-interactive FHE llm 0.90
code url https://github.com/ucsd-crypto/CKKSKeyRecovery.21 (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/homenc/HElib (URL found in the full text) regex 0.50
code url https://github.com/ucsd-crypto/CKKSKeyRecovery llm 0.90
limitations lattice-based variant of the attack not implemented (needs lattice reduction in very large dimension) llm 0.90
limitations proposed countermeasures are simple mitigations; a provably IND-CPA^D-secure solution is left open llm 0.90
llm relevance low llm 0.90
key result key recovery success: attack always recovered sk for most (scaling factor, magnitude) settings over 100 runs per library (variance of 2^15 complex numbers; HEAAN 2.1, PALISADE 1.10.4, SEAL 3.5, HElib 1.1.0) llm 0.90
key result attack running time: a few seconds (even for large security parameters) llm 0.90

System card: IND-CPA-D attack on CKKS

Group 2. CKKS core and variants
Family Security analysis
Arithmetic -
Interaction -
Model scale -
Status Foundational
Relation to the SoK Shows CKKS decryptions leak the secret key if shared.
Note Motivates the SoK's assumption that the client never shares decrypted outputs with the server.
Systems page IND-CPA-D attack on CKKS

SoK reference [55]

B. Li and D. Micciancio, “On the security of homomorphic encryption on approximate numbers,” in Advances in Cryptology – EUROCRYPT 2021, Part I, ser. Lecture Notes in Computer Science, A. Canteaut and F.-X. Standaert, Eds., vol. 12696. Zagreb, Croatia: Springer, Cham, Switzerland, Oct. 17–21, 2021, pp. 648–677.

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 81 [p.1], GSW 2 [p.4], MPC 2 [p.2]
  • library: HElib 21 [p.1], PALISADE 15 [p.1], Microsoft SEAL 14 [p.1], Lattigo 2 [p.24], EVA / CHET 2 [p.26], nGraph-HE 1 [p.2]
  • model: Logistic regression 4 [p.2]
  • technique: RNS 18 [p.4], Bootstrapping 12 [p.1], Rescaling 8 [p.7], Compiler 4 [p.2], Encrypted training 2 [p.2]
  • assumption: IND-CPA-D 73 [p.2], IND-CPA 48 [p.1], Lattice-based 44 [p.1], LWE 25 [p.3], RLWE 4 [p.19]
  • task: Language modeling / generation 8 [p.8], Medical / healthcare 4 [p.4], Clustering 2 [p.2]
  • topic: Homomorphic encryption 58 [p.1], Open source 6 [p.21]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/2-025_on-the-security-of-homomorphic-encryption-on-approximate-num.pdf catalogue 27 507.1 KB 1e695e93051e
references/sok-references/055_on-the-security-of-homomorphic-encryption-on-approximate-num.pdf sok-references 27 507.1 KB 1e695e93051e byte-identical to references/catalogue/2-025_on-the-security-of-homomorphic-encryption-on-approximate-num.pdf

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