Skip to content

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