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]
Related papers¶
- this paper follow up of Securing Approximate Homomorphic Encryption Using Differential Privacy — follow-up listed for scheme "IND-CPA-D secure CKKS (noise flooding)"
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