Skip to content

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