META-BTS: Bootstrapping Precision Beyond the Limit¶
Authors: Bae, Cheon, Cho, Kim, Kim
Year: 2022
Venue: CCS 2022
type: technique collection: catalogue, schemes status: auto
Links: ePrint 2022/1167
Visual lesson: META-BTS (iterative CKKS bootstrapping) · Scheme table row: META-BTS (iterative CKKS bootstrapping)
Summary¶
Auto-extracted summary (unreviewed)
Meta-BTS is a CKKS bootstrapping strategy that repeats an existing bootstrapping algorithm k times so that the precision of the result is essentially multiplied by k, overcoming the precision ceiling imposed by the rescale operation. A proof-of-concept C++ implementation reaches the theoretical maximum of 420-bit precision at N=2^17 with 14 iterations (903 s), and yields 48-bit and 255-bit high-precision parameter sets for N=2^15 and N=2^16; the authors also propose a parameter set III' whose Meta-BTS bootstrapping takes about 46 s while doubling the usable multiplicative depth.
Abstract¶
Bootstrapping, which enables the full homomorphic encryption scheme that can perform an infinite number of operations by restoring the modulus of the ciphertext with a small modulus, is an essential step in homomorphic encryption. However, bootstrapping is the most time and memory consuming of all homomorphic operations. As we increase the precision of bootstrapping, a large amount of computational resources is required. Specifically, for any of the previous bootstrap designs, the precision of bootstrapping is limited by rescaling precision. In this paper, we propose a new bootstrapping algorithm of the Cheon-Kim-Kim-Song (CKKS) [11] scheme to use a known bootstrapping algorithm repeatedly, so called Meta-BTS. By repeating the original bootstrapping operation twice, one can obtain another bootstrapping with its precision essentially doubled; it can be generalized to be 𝑘-fold bootstrapping operations for some 𝑘> 1 while the ciphertext size is large enough. Our algorithm overcomes the precision limitation given by the rescale operation.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Meta-BTS: repeating a base CKKS bootstrapping to double or k-fold its precision | llm | 0.85 |
| contribution | overcomes the precision limit imposed by the rescaling operation | llm | 0.85 |
| contribution | high-precision parameter constructions for N=2^15, 2^16 and 2^17 with implementation results | llm | 0.85 |
| contribution | improved parameter set III' (based on Bossuat et al.) with Meta-BTS as default bootstrapping | llm | 0.85 |
| schemes | CKKS | llm | 0.85 |
| security level | 128-bit | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| limitations | bootstrapping time grows roughly linearly with the number of Meta-BTS iterations | llm | 0.85 |
| limitations | implementation issues increased the maximum ciphertext level, making the 14-iteration run slower than expected (903 s vs 719.6 s) | llm | 0.85 |
| limitations | k-fold bootstrapping requires the ciphertext modulus to be large enough | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | maximum bootstrapping precision: 420 bits (N=2^17, 14 Meta-BTS iterations (theoretical maximum reached)) | llm | 0.85 |
| key result | bootstrapping time: 903 s (base bootstrapping 51.4 s) (N=2^17, 14 iterations; expected 719.6 s) | llm | 0.85 |
| key result | bootstrapping precision: 48 bits (N=2^15 high-precision parameter set (base boot time 6.43 s)) | llm | 0.85 |
| key result | bootstrapping precision: 255 bits (N=2^16 high-precision parameter set (base boot time 16.3 s)) | llm | 0.85 |
| key result | bootstrapping time: about 46 s (proposed parameter set III', twice the time of Set I but with doubled multiplicative depth (10)) | llm | 0.85 |
Scheme card: META-BTS (iterative CKKS bootstrapping)¶
| Group | 1. CKKS and its variants |
| Kind | Variant |
| Hardness assumption | RLWE |
| Plaintext type | Approximate, high precision |
| SIMD packing | Yes |
| Bootstrapping | Yes, iterated |
| Post-quantum | Yes |
| Status | Active |
| Fit for LLM inference | Raises precision for deep circuits such as many-layer LLMs. |
System card: META-BTS¶
| Group | 3. CKKS bootstrapping and operation advances |
| Family | CKKS bootstrapping |
| Arithmetic | - |
| Interaction | - |
| Model scale | - |
| Status | Active |
| Relation to the SoK | Iterative bootstrapping that doubles precision. |
| Note | Trades extra bootstrapping for precision. Useful when deep models accumulate error. |
| Systems page | META-BTS |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 32 [p.1], TFHE 3 [p.1], FHEW 2 [p.1]
- library: HEaaN (library) 1 [p.9], Lattigo 1 [p.3]
- hardware: Intel Xeon 1 [p.9]
- technique: Bootstrapping 214 [p.1], Rescaling 23 [p.1], Polynomial approximation 7 [p.1], SIMD packing 4 [p.1], RNS 4 [p.5], Minimax approximation 3 [p.8], Rotations 3 [p.1], Remez 2 [p.8]
- assumption: LWE 5 [p.11], RLWE 4 [p.9], Lattice-based 2 [p.9], 128-bit security 2 [p.9]
- task: Language modeling / generation 3 [p.4]
- topic: Homomorphic encryption 30 [p.1]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/3-037_meta-bts-bootstrapping-precision-beyond-the-limit.pdf |
catalogue | 12 | 804.8 KB | cd7d94609025 |
|
references/schemes/s06-0_meta-bts-bootstrapping-precision-beyond-the-limit.pdf |
schemes | 12 | 804.8 KB | cd7d94609025 |
byte-identical to references/catalogue/3-037_meta-bts-bootstrapping-precision-beyond-the-limit.pdf |
Database key: meta-bts-bootstrapping-precision-beyond-the-limit · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set meta-bts-bootstrapping-precision-beyond-the-limit COLUMN VALUE