Homomorphic Encryption for Arithmetic of Approximate Numbers¶
Authors: Jung Hee Cheon; Andrey Kim; Miran Kim; Yongsoo Song
Year: 2017
Venue: ASIACRYPT 2017
type: scheme collection: catalogue, schemes, sok-references status: auto
Links: DOI · ePrint 2016/421 · Semantic Scholar
Visual lesson: CKKS · Scheme table row: CKKS
Summary¶
Auto-extracted summary (unreviewed)
This paper introduces the CKKS scheme for homomorphic approximate arithmetic on real and complex numbers: a rescaling procedure truncates the ciphertext modulus to round the plaintext, treating encryption noise as part of the approximation error, and a batching technique based on the complex canonical embedding packs N/2 slots without amplifying errors. The ciphertext modulus grows only linearly with circuit depth and precision loss is bounded by the depth (at most one bit worse than floating point); the NTL/GMP implementation at 80-bit security evaluates x^1024 over 2^14 slots in 7.46 s (0.43 ms amortized) and supports multiplicative inverse, exponential, logistic function and DFT.
Abstract¶
We suggest a method to construct a homomorphic encryption scheme for approximate arithmetic. It supports an approximate addition and multiplication of encrypted messages, together with a new rescaling procedure for managing the magnitude of plaintext. This procedure truncates a ciphertext into a smaller modulus, which leads to rounding of plaintext. The main idea is to add a noise following significant figures which contain a main message. This noise is originally added to the plaintext for security, but considered to be a part of error occurring during approximate computations that is reduced along with plaintext by rescaling. As a result, our decryption structure outputs an approximate value of plaintext with a predetermined precision. We also propose a new batching technique for a RLWE-based construction. A plaintext polynomial is an element of a cyclotomic ring of characteristic zero and it is mapped to a message vector of complex numbers via complex canonical embedding map, which is an isometric ring homomorphism. This transformation does not blow up the size of errors, therefore enables us to preserve the precision of plaintext after encoding. In our construction, the bit size of ciphertext modulus grows linearly with the depth of the circuit being evaluated due to rescaling procedure, while all the previous works either require an exponentially large size of modulus or expensive computations such as bootstrapping or bit extraction. One important feature of our method is that the precision loss during evaluation is bounded by the depth of a circuit and it exceeds at most one more bit compared to unencrypted approximate arithmetic such as floating-point operations. In addition to the basic approximate circuits, we show that our scheme can be applied to the efficient evaluation of transcendental functions such as multiplicative inverse, exponential function, logistic function and discrete Fourier transform.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | homomorphic encryption scheme for approximate arithmetic with a rescaling procedure | llm | 0.90 |
| contribution | batching via the complex canonical embedding (N/2 complex slots per ciphertext) | llm | 0.90 |
| contribution | ciphertext modulus linear in circuit depth; precision loss bounded by depth | llm | 0.90 |
| contribution | homomorphic evaluation of transcendental functions (multiplicative inverse, exp, logistic, DFT) | llm | 0.90 |
| contribution | open-source HEAAN implementation | llm | 0.90 |
| schemes | CKKS | llm | 0.90 |
| libraries | HEAAN | llm | 0.90 |
| libraries | NTL | llm | 0.90 |
| libraries | GMP | llm | 0.90 |
| tasks | approximate arithmetic on encrypted real/complex numbers | llm | 0.90 |
| tasks | evaluation of multiplicative inverse, exponential, logistic function and discrete Fourier transform | llm | 0.90 |
| hardware | Intel Core i5 2.9 GHz CPU | llm | 0.90 |
| security level | 80-bit | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| code url | https://github.com/kimandrik/HEAAN (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/snucrypto/HEAAN | llm | 0.90 |
| limitations | scheme is leveled, not fully homomorphic: bootstrapping is left as the primary open problem | llm | 0.90 |
| limitations | implementation does not yet use NTT for polynomial multiplication | llm | 0.90 |
| limitations | experiments use 80-bit security parameters | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
| key result | latency of x^1024: 7.46 s total, 0.43 ms amortized per slot (N=2^15, log q=620, log p=56, 36-bit input precision, 2^14 slots, 80-bit security) | llm | 0.90 |
| key result | latency of x^16: 0.31 s total, 0.07 ms amortized (N=2^13, log q=155, log p=30, 14-bit precision) | llm | 0.90 |
| key result | latency of multiplicative inverse (degree-8 polynomial): 0.45 s total, 0.11 ms amortized (N=2^13) | llm | 0.90 |
| key result | latency of exp(x) (degree-8 Taylor): 0.65 s total, 0.16 ms amortized (N=2^13) | llm | 0.90 |
| key result | precision loss: < 4.1 bits at depth 4; < 10.1 bits at depth 10 (x^16 and x^1024 experiments) | llm | 0.90 |
Scheme card: CKKS¶
| Group | 1. CKKS and its variants |
| Kind | Scheme |
| Hardness assumption | RLWE |
| Plaintext type | Approximate real/complex fixed point |
| SIMD packing | Yes, N/2 complex slots |
| Bootstrapping | Yes; expensive, consumes many levels |
| Post-quantum | Yes |
| Status | Widely used (baseline) |
| Fit for LLM inference | The SoK's baseline. Native SIMD real arithmetic suits linear layers. Non-linear layers need polynomial approximation and bootstrapping dominates latency. |
| Follow-ups | Bootstrapping: Cheon et al. EUROCRYPT 2018; Chen–Chillotti–Song EUROCRYPT 2019; Bossuat et al. EUROCRYPT 2021; Lee et al. EUROCRYPT 2021. |
| Libraries | OpenFHE, SEAL, Lattigo, HEaaN, HElib, Phantom, FIDESlib, HEonGPU, Liberate.FHE |
System card: CKKS (HEAAN)¶
| Group | 2. CKKS core and variants |
| Family | RLWE, leveled + bootstrapping |
| Arithmetic | Approximate fixed-point real/complex, SIMD |
| Interaction | Non-interactive |
| Model scale | Llama-3-8B (via frameworks below) |
| Status | Foundational |
| Relation to the SoK | Baseline scheme of the SoK. |
| Note | De facto scheme for private LLM inference. Native SIMD over N/2 slots, but non-linear functions need polynomial approximation. |
| Code | https://github.com/snucrypto/HEAAN |
| Systems page | CKKS (HEAAN) |
SoK reference [5]¶
J. H. Cheon, A. Kim, M. Kim, and Y. S. Song, “Homomorphic encryption for arithmetic of approximate numbers,” in Advances in Cryptology – ASIACRYPT 2017, Part I, ser. Lecture Notes in Computer Science, T. Takagi and T. Peyrin, Eds., vol. 10624. Hong Kong, China: Springer, Cham, Switzerland, Dec. 3–7, 2017, pp. 409–437.
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: BGV 6 [p.2], Leveled / somewhat HE 5 [p.9], CKKS 3 [p.4], NTRU 2 [p.3], RSA 2 [p.20], MPC 2 [p.21]
- library: Concrete (Zama) 1 [p.10]
- model: Logistic regression 4 [p.18]
- dataset: Diabetes (Pima) 3 [p.18]
- technique: Rescaling 20 [p.1], Bootstrapping 5 [p.1], Modulus switching 3 [p.3], Taylor expansion 2 [p.4], SIMD packing 2 [p.8]
- assumption: RLWE 19 [p.1], LWE 12 [p.3], Lattice-based 2 [p.8]
- task: Language modeling / generation 9 [p.3], Medical / healthcare 6 [p.1], Genomics 3 [p.1]
- topic: Homomorphic encryption 51 [p.1], Open source 2 [p.4]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/2-021_homomorphic-encryption-for-arithmetic-of-approximate-numbers.pdf |
catalogue | 23 | 463.0 KB | 2d84c504e428 |
|
references/schemes/s00-0_homomorphic-encryption-for-arithmetic-of-approximate-numbers.pdf |
schemes | 23 | 463.0 KB | 2d84c504e428 |
byte-identical to references/catalogue/2-021_homomorphic-encryption-for-arithmetic-of-approximate-numbers.pdf |
references/sok-references/005_homomorphic-encryption-for-arithmetic-of-approximate-numbers.pdf |
sok-references | 23 | 463.0 KB | 2d84c504e428 |
byte-identical to references/catalogue/2-021_homomorphic-encryption-for-arithmetic-of-approximate-numbers.pdf |
Database key: homomorphic-encryption-for-arithmetic-of-approximate-numbers · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set homomorphic-encryption-for-arithmetic-of-approximate-numbers COLUMN VALUE