New publication: “Fast amortized bootstrapping with small keys and polynomial noise overhead”
New publication: “Fast amortized bootstrapping with small keys and polynomial noise overhead”
Antonio Guimarães from the IMDEA Software Institute and Hilder V. L. Pereira from UNICAMP have co-authored “Fast amortized bootstrapping with small keys and polynomial noise overhead,” a 2025 ePrint now listed by the authors as to appear at ACM CCS 2025, presenting an amortized FHE bootstrapping method with smaller keys and polynomial noise overhead suitable for multi-message processing.
The paper targets the concrete inefficiency of prior amortized bootstrapping methods that either require very large evaluation keys or incur high asymptotic constants. It introduces three main elements:
Sparse-secret design:
The scheme instantiates LWE and RLWE with secrets of Hamming weight h. The resulting amortized cost per message is O(h) homomorphic operations, and the noise overhead scales as O(h·log(N/h)) for ring dimension N under typical spacing of nonzero secret components.
GSW-friendly sparse-by-dense multiplication (MPmul):
A homomorphic monomial-by-polynomial multiplication routine evaluates “in the exponent” using only external products and automorphisms, running in O(N · log B) where B bounds the monomial degree. MPmul limits the noise growth to a low-degree polynomial and avoids ciphertext-ciphertext products.
Nested decryption circuit with external products only:
The LWE decryption linear form is re-expressed so that the summation over secret indices becomes a sequence of nested MPmul steps. Each step uses a fresh encryption of a monomial exponent from the bootstrapping key and cleartext subtractions, eliminating the need for RLWE-by-RLWE multiplications and keeping the modulus small.
Together, these choices enable amortized bootstrapping across O(λ) messages while preserving polynomial noise growth, with key sizes and runtime competitive in practice.
Packing and message model:
Messages mi ∈ ℤt are packed into a single RLWE ciphertext encrypting the polynomial m(X) = ∑i mi Xi. The scheme then evaluates a function fi per slot and extracts refreshed LWE ciphertexts. The packing stage admits time-noise tradeoffs by tuning internal parameters.
Complexity and noise:
- Homomorphic operations per message: O(h).
- Noise overhead: O(h · log(N / h)) using the monomial-spacing argument; more generally O(h) up to a logarithmic factor from MPmul.
- Key size: quasilinear in h with log-factors from automorphisms, substantially below earlier amortized approaches that required large GSW parameter inflation.
Reported performance and sizes
Measured on the authors’ implementation, the paper reports:
-
2-bit messages, 2 048 slots: 4.0 ms amortized per message with a 17.1 MB bootstrapping key.
-
6-bit messages, 8 192 slots: 4.4 ms amortized per message with a 16.9 MB key.
-
8-bit messages, 8 192 slots: 28.5 ms amortized per message with a 70.1 MB key.
Compared to TFHE-rs and the GPvL23 amortized implementation, speedups range from 2.5× to 38.7× while using significantly smaller bootstrapping keys.
Relation to earlier amortized bootstrapping
The approach contrasts with ring-packing plus DFT-like pipelines that require GSW multiplication at nontrivial depth. By relying on external products and a nested form of the decryption, the method reduces practical constants and key sizes while keeping polynomial noise. For background on prior asymptotic improvements and their practical limits, see ICALP 2018 and follow-on work, as well as the authors’ earlier study on simpler, asymptotically faster amortized bootstrapping.
How this supports CONFIDENTIAL6G
CONFIDENTIAL6G investigates cryptographic and systems mechanisms for secure data processing across heterogeneous 6G environments. Practical amortized bootstrapping helps reduce FHE latency and memory footprint for edge and network-embedded computations. It aligns with the project’s pillars on post-quantum cryptography and confidential computation, and can be integrated with other work on secure data in use and in transit described in the action description.