Bootstrapping for Approximate Homomorphic Encryption with Negligible Failure-Probability by Using Sparse-Secret Encapsulation¶
Authors: Bossuat, Troncoso-Pastoriza, Hubaux
Year: 2022
Venue: ACNS 2022
type: scheme collection: schemes status: auto
Links: ePrint 2022/24 · link
Visual lesson: Sparse-secret encapsulation CKKS · Scheme table row: Sparse-secret encapsulation CKKS
Summary¶
Auto-extracted summary (unreviewed)
Presents a CKKS bootstrapping procedure that encapsulates a dense main secret with a sparse ephemeral secret, so that homomorphic capacity is set by a dense-secret parameterization while bootstrapping cost stays that of a sparse secret with a large security margin. This makes it easy to parameterize the EvalMod step for negligible failure probability; implemented in Lattigo, it bootstraps a C^32768 plaintext in 20.2 s with 32.11 bits of precision, 285 bits of remaining modulus and failure probability 2^-138.7 at 128-bit security.
Abstract¶
Bootstrapping parameters for the approximate homomorphicencryption scheme of Cheon et al., CKKS (Asiacrypt 17), are usually instantiated using sparse secrets to be efficient. However, using sparse secrets constrains the range of practical parameters within a tight interval, as they must support a large enough depth for the bootstrapping circuit but also be secure with respect to the sparsity of their secret. We present a bootstrapping procedure for the CKKS scheme that combines both dense and sparse secrets. Our construction enables the use of parameters for which the homomorphic capacity is based on a dense secret, yet with a bootstrapping complexity that remains the one of a sparse secret and with a large security margin. Moreover, this also enables us to easily parameterize the bootstrapping circuit so that it has a negligible failure probability that, to the best of our knowledge, has never been achieved for the CKKS scheme. When using the parameters of previous works, our bootstrapping procedures enables a faster procedure with an increased precision and lower failure probability. For example we are able to bootstrap a plaintext of C32768 in 20.2 sec, with 32.11 bits of precision, 285 bits of modulus remaining, a failure probability of 2−138.7 and 128 bit security.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | sparse-secret encapsulation combining dense and sparse secrets in CKKS bootstrapping | llm | 0.90 |
| contribution | first CKKS bootstrapping with negligible failure probability | llm | 0.90 |
| contribution | higher precision and smaller EvalMod interpolant at the same parameters as prior work | llm | 0.90 |
| contribution | security analysis of the ephemeral sparse secret | llm | 0.90 |
| contribution | implementation in the Lattigo library | llm | 0.90 |
| schemes | CKKS | llm | 0.90 |
| libraries | Lattigo | llm | 0.90 |
| tasks | FHE bootstrapping | llm | 0.90 |
| hardware | Intel i5-6600K 3.50 GHz, 32 GB RAM, single-threaded (Windows 10) | llm | 0.90 |
| security level | 128-bit (ephemeral secret about 141-168-bit) | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| code url | https://github.com/ldsec/lattigo (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/ldsec/lattigo/tree/btp_eprint (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/ldsec/lattigo/tree/btp_eprint | llm | 0.90 |
| limitations | with the Han-Ki interpolation method, K = 16 is the largest range achievable with a depth-5 interpolant | llm | 0.90 |
| limitations | noise from a denser main secret dominates once ciphertext multiplications are involved | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
| key result | bootstrapping latency: 20.2 s (plaintext in C^32768, 128-bit security) | llm | 0.90 |
| key result | bootstrapping precision: 32.11 bits (Set II parameters, K = 16) | llm | 0.90 |
| key result | remaining modulus after bootstrapping: 285 bits (C^32768 plaintext) | llm | 0.90 |
| key result | failure probability: 2^-138.7 (vs 2^-15.58 in Bossuat et al.) (n = 2^15 slots, K = 16, same parameters as prior work) | llm | 0.90 |
Scheme card: Sparse-secret encapsulation CKKS¶
| Group | 1. CKKS and its variants |
| Kind | Variant |
| Hardness assumption | RLWE |
| Plaintext type | Approximate real/complex |
| SIMD packing | Yes |
| Bootstrapping | Yes, faster with dense secrets |
| Post-quantum | Yes |
| Status | Active |
| Fit for LLM inference | Gets fast bootstrapping without weakening the main secret key. |
| Libraries | Lattigo |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 36 [p.1]
- library: Lattigo 2 [p.15]
- technique: Bootstrapping 138 [p.1], Key switching 9 [p.7], Polynomial approximation 6 [p.3], RNS 6 [p.3], Rescaling 3 [p.2], Rotations 3 [p.6], Minimax approximation 2 [p.3], Taylor expansion 2 [p.13]
- assumption: LWE 16 [p.1], RLWE 12 [p.1], Lattice-based 2 [p.21], 128-bit security 2 [p.11]
- topic: Homomorphic encryption 9 [p.21], Open source 3 [p.3]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s04-0_bootstrapping-for-approximate-homomorphic-encryption-with-ne.pdf |
schemes | 22 | 488.2 KB | 37863df80532 |
Database key: bootstrapping-for-approximate-homomorphic-encryption-with-negligible · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set bootstrapping-for-approximate-homomorphic-encryption-with-negligible COLUMN VALUE