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