Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys¶
Authors: Bossuat, Mouchet, Troncoso-Pastoriza, Hubaux
Year: 2021
Venue: EUROCRYPT 2021
type: technique collection: catalogue status: auto
Links: ePrint 2020/1203
Summary¶
Auto-extracted summary (unreviewed)
The paper presents a bootstrapping procedure for full-RNS CKKS that works with dense (non-sparse) secret keys and is therefore 128-bit secure under recent attacks on sparse R-LWE secrets. It contributes a level-optimal homomorphic polynomial evaluation that accounts for approximate rescaling, an optimized key-switch with a double-hoisting technique for linear transformations, and a systematic parameterization method with an explicit failure-probability estimate. Implemented in Lattigo, bootstrapping a C^32768 plaintext takes 18 s with 19.1 bits of mean precision and failure probability 2^-15.58, a 14.1x throughput gain and 468x lower failure probability than prior work.
Abstract¶
We present a bootstrapping procedure for the full-RNS variant of the approximate homomorphic-encryption scheme of Cheon et al., CKKS (Asiacrypt 17, SAC 18). Compared to the previously proposed procedures (Eurocrypt 18 & 19, CT-RSA 20), our bootstrapping procedure is more precise, more efficient (in terms of CPU cost and number of consumed levels), and is more reliable and 128-bit-secure. Unlike the previous approaches, it does not require the use of sparse secret-keys. Therefore, to the best of our knowledge, this is the first procedure that enables a highly efficient and precise bootstrapping with a low probability of failure for parameters that are 128-bit-secure under the most recent attacks on sparse R-LWE secrets. We achieve this efficiency and precision by introducing three novel contributions: (i) We propose a generic algorithm for homomorphic polynomialevaluation that takes into account the approximate rescaling and is optimal in level consumption. (ii) We optimize the key-switch procedure and propose a new technique for linear transformations (double hoisting). (iii) We propose a systematic approach to parameterize the bootstrapping, including a precise way to assess its failure probability. We implemented our improvements and bootstrapping procedure in the open-source Lattigo library. For example, bootstrapping a plaintext in C32768 takes 18 seconds, has an output coefficient modulus of 505 bits, a mean precision of 19.1 bits, and a failure probability of 2−15.58. Hence, we achieve 14.1× improvement in bootstrapped throughput (plaintextbit per second), with respect to the previous best results, and we have a failure probability 468× smaller and ensure 128-bit security.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | generic homomorphic polynomial evaluation algorithm optimal in level consumption under approximate rescaling | llm | 0.90 |
| contribution | optimized key-switch procedure and double-hoisting technique for linear transformations | llm | 0.90 |
| contribution | systematic bootstrapping parameterization including a precise failure-probability estimate | llm | 0.90 |
| contribution | first open-source bootstrapping for full-RNS CKKS with dense keys (in Lattigo) | llm | 0.90 |
| schemes | CKKS | llm | 0.90 |
| libraries | Lattigo | llm | 0.90 |
| tasks | CKKS bootstrapping | llm | 0.90 |
| hardware | Intel i5-6600k 3.5 GHz, 32 GB RAM, single-threaded | llm | 0.90 |
| security level | 128-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/snucrypto/HEAAN (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/Microsoft/SEAL (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/ldsec/lattigo | llm | 0.90 |
| limitations | comparison with prior works relies on their reported numbers because their implementations were not publicly released | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
| key result | bootstrapping latency: 18 s (plaintext in C^32768, single-threaded) | llm | 0.90 |
| key result | output coefficient modulus: 505 bits (C^32768 bootstrapping) | llm | 0.90 |
| key result | mean output precision: 19.1 bits (C^32768 bootstrapping) | llm | 0.90 |
| key result | failure probability: 2^-15.58 (468x smaller than prior best) (C^32768 bootstrapping) | llm | 0.90 |
| key result | bootstrapping throughput improvement: 14.1x (plaintext-bits per second vs previous best results) | llm | 0.90 |
System card: Non-sparse-key bootstrapping (Bossuat et al.)¶
| Group | 3. CKKS bootstrapping and operation advances |
| Family | CKKS bootstrapping |
| Arithmetic | - |
| Interaction | - |
| Model scale | - |
| Status | Widely used |
| Relation to the SoK | Secure, precise bootstrapping implemented in Lattigo. |
| Note | Removes the sparse-key assumption that weakened security. |
| Code | https://github.com/tuneinsight/lattigo |
| Systems page | Non-sparse-key bootstrapping (Bossuat et al.) |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 55 [p.1], BFV 5 [p.16], BGV 3 [p.13], RSA 3 [p.1]
- library: Lattigo 8 [p.1], Microsoft SEAL 5 [p.7], HElib 3 [p.31]
- model: CNN 1 [p.29]
- technique: Bootstrapping 134 [p.1], Rotations 54 [p.3], RNS 37 [p.1], Rescaling 23 [p.1], NTT 19 [p.2], Chebyshev 12 [p.6], Convolution 4 [p.4], Relinearization 2 [p.5], Polynomial approximation 2 [p.25]
- assumption: LWE 11 [p.1], RLWE 6 [p.1], 128-bit security 4 [p.1], Lattice-based 3 [p.1]
- task: Language modeling / generation 9 [p.6]
- topic: Homomorphic encryption 15 [p.1], Open source 8 [p.1], Benchmark 2 [p.26]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/3-035_efficient-bootstrapping-for-approximate-homomorphic-encrypti.pdf |
catalogue | 46 | 1.5 MB | 3b53cf70c8cd |
Database key: efficient-bootstrapping-for-approximate-homomorphic-encryption-with-non · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set efficient-bootstrapping-for-approximate-homomorphic-encryption-with-non COLUMN VALUE