Skip to content

Leveraging Discrete CKKS to Bootstrap in High Precision

Authors: Hyeongmin Choe; Jaehyung Kim; Damien Stehlé; Elias Suvanto
Year: 2025
Venue: IACR ePrint 2025/1786

type: scheme collection: catalogue, schemes status: auto

Links: DOI · ePrint 2025/1786

Summary

Auto-extracted summary (unreviewed)

The paper presents a non-iterative high-precision CKKS bootstrapping whose cost is almost independent of the target precision and whose modulus consumption grows much more slowly than classical bootstrapping, by improving EvalRound bootstrapping with recent techniques for handling discrete data in CKKS (bootstrapping only the small integer I rather than the full high-precision plaintext). Implemented in HEaaN, it gives the first 80-bit-precise single-shot bootstrap at ring degree N = 2^16 with 494 bits of modulus left for computation, and 64% higher throughput than Meta-BTS at 80-bit precision, which matters for IND-CPA-D security, threshold FHE and circuit privacy that need noise flooding.

Abstract

The CKKS fully homomorphic encryption (FHE) scheme enables computations on vectors of approximate complex numbers. A moderate precision of ≈20 bits often suffices but, in many applications, a higher precision is required for functionality and/or security. Indeed, to obtain IND-CPA-D security [Li-Micciancio; Eurocrypt’21], secure threshold-FHE [Asharov et al; Eurocrypt’12] and circuit privacy [Gentry; STOC’09], all known approaches require a precision that supports noise flooding. This may lead to a precision of ≈80 bits, or more. High-precision CKKS is hard to achieve, notably because of bootstrapping. The main difficulty is modulus consumption: every homomorphic multiplication consumes some, out of an overall modulus budget. Unfortunately, in high precision, most known bootstrapping algorithms consume so much modulus that one needs to increase the parameters to increase the budget. The state-of-the-art approach, Meta-BTS [Bae et al; CCS’22], performs moderate-precision bootstrapping several times to enable highprecision bootstrapping, with similar modulus consumption as the base bootstrapping it builds upon. It however damages latency. We introduce a new approach for high-precision CKKS bootstrapping, whose cost is almost independent of the precision (as opposed to Meta-BTS) and whose modulus consumption increases significantly more slowly than with classical bootstrapping algorithms. Our design relies on the EvalRound bootstrapping [Kim et al; Asiacrypt’22], which we improve in the high-precision context by leveraging and improving recent techniques for handling discrete data with CKKS. We obtain for the first time a non-iterative 80bit precise bootstrapping algorithm which can be run in ring degree 𝑁= 216, with 494 bits of remaining modulus for computations. In terms of throughput, and for 80-bit precision, our implementation shows an acceleration of 64% compared to Meta-BTS.
Source: pdf

Extracted details

Field Value Source Confidence
contribution High-precision CKKS bootstrapping with cost almost independent of precision llm 0.85
contribution Improved EvalRound bootstrapping leveraging discrete-CKKS techniques for the integer part I llm 0.85
contribution First non-iterative 80-bit precise bootstrap at N = 2^16 with 494 bits of remaining modulus llm 0.85
contribution Implementation in HEaaN with grafting and comparison against Meta-BTS and EvalRound+ llm 0.85
schemes CKKS llm 0.85
libraries HEaaN llm 0.85
tasks high-precision CKKS bootstrapping llm 0.85
tasks enabling IND-CPA-D security, threshold FHE and circuit privacy via noise flooding llm 0.85
hardware Apple M4 Pro CPU (single thread, 32 GiB RAM) llm 0.85
security level 128-bit (RLWE, lattice estimator); bootstrapping failure probability about 2^-128 llm 0.85
interaction non-interactive FHE llm 0.85
code url https://github.com/tuneinsight/lattigo (URL found in the full text) regex 0.50
limitations Implementation is experimental code whose efficiency can likely be improved llm 0.85
limitations Meta-BTS timings are estimated from the authors' own implementation, with one row extrapolated llm 0.85
limitations EvalRound+ comparison not timed because it uses a different, less efficient code base llm 0.85
llm relevance low llm 0.85
key result bootstrap precision / remaining modulus: 81 bits / 494 bits (Direct3Cln81 parameter set, N = 2^16) llm 0.85
key result bootstrap latency: 20.9 s (Direct3Cln81 (81-bit), single-thread Apple M4 Pro, HEaaN) llm 0.85
key result bootstrap latency (baseline): 34.0 s (Meta-BTS x4 (about 80-bit precision), 490 bits remaining modulus, extrapolated) llm 0.85
key result throughput gain over Meta-BTS: +64% (80-bit precision) llm 0.85
key result bootstrap latency (moderate precision): 14.3 s (19-bit) and 17.9 s (38-bit) (Direct2Cln19 / Direct2Cln38, N = 2^16) llm 0.85
key result baseline CKKS bootstrap: 8.5 s, 21-bit precision, 550 bits remaining (FGb parameter set, same code base)* llm 0.85

System card: Discrete CKKS for high-precision bootstrapping

Group 2. CKKS core and variants
Family CKKS bootstrapping
Arithmetic Approximate real, very high precision
Interaction Non-interactive
Model scale -
Status Active SOTA
Relation to the SoK Reaches about 80+ bit precision needed for noise flooding.
Note Relevant to IND-CPA-D security and threshold CKKS.
Systems page Discrete CKKS for high-precision bootstrapping

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: CKKS 89 [p.1], BFV 5 [p.5], Threshold HE 2 [p.5], MPC 2 [p.13]
  • library: HEaaN (library) 3 [p.2], Lattigo 3 [p.12], OpenFHE 1 [p.13]
  • hardware: Apple silicon 1 [p.11]
  • technique: Bootstrapping 113 [p.1], Rescaling 20 [p.2], Relinearization 8 [p.4], RNS 7 [p.1], SIMD packing 5 [p.5], Noise flooding 5 [p.1], Polynomial approximation 3 [p.3], Rotations 3 [p.5], Key switching 2 [p.2], Paterson-Stockmeyer 2 [p.8], NTT 2 [p.6]
  • assumption: RLWE 13 [p.2], IND-CPA 10 [p.1], IND-CPA-D 8 [p.1], LWE 7 [p.2], Lattice-based 4 [p.11]
  • task: Language modeling / generation 3 [p.11]
  • topic: Homomorphic encryption 18 [p.1], Open source 2 [p.13]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/2-130_leveraging-discrete-ckks-to-bootstrap-in-high-precision.pdf catalogue 15 810.6 KB 3d1e2277a4a6
references/schemes/s05-1_eprint-2025-1786.pdf schemes 15 810.6 KB 3d1e2277a4a6 byte-identical to references/catalogue/2-130_leveraging-discrete-ckks-to-bootstrap-in-high-precision.pdf

Database key: leveraging-discrete-ckks-to-bootstrap-in-high-precision · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set leveraging-discrete-ckks-to-bootstrap-in-high-precision COLUMN VALUE