Exact Error Bootstrapping and Comb Bootstrapping in FHEW/TFHE
Abstract
In FHEW and TFHE, bootstrapping evaluates the decryption function via a blind rotation, whose resolution limits the message space. We propose instead to bootstrap the error. By rounding the ciphertext at a resolution that is a multiple of the message modulus, we preserve the message exactly. Reduction modulo a small integer then yields a noise-free encryption of the error, which a single blind rotation lifts exactly before it is subtracted. The message modulus is thus constrained solely by the noise and can be much larger than in standard TFHE. Since the error takes far fewer distinct values than the ring degree, a single blind rotation can also refresh several ciphertexts simultaneously. We call this procedure the comb bootstrap. Between refreshes, an integer remains encrypted in a single ciphertext, allowing additions modulo the message modulus and multiplications without programmable bootstrapping. Built on TFHE-rs, for 8-bit integers on a single thread, our refresh is 3.5 times faster than that of TFHE-rs, and 9.1 times faster with the comb bootstrap; multiplication is 6.5 times faster. In a residue number system, multiplication of integers modulo P ≥ 2^32 is 19 times faster than in TFHE-rs. The error bootstrap serves exclusively to refresh ciphertexts; evaluating any other function still requires programmable bootstrapping.
Related
- An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB
- The Exact Second Generalized Covering Radius of Binary Primitive Triple-Error-Correcting BCH Codes
- Corrections to ``The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms
- Binary Quantum Hypothesis Testing with a Rejection Option: The Exact Error-Exponent Trade-off
- An Exact Tail Condition for the Largest Error in Estimating a Rank-One Direction
BibTeX
@misc{chartier2026exact,
title = {{Exact Error Bootstrapping and Comb Bootstrapping in FHEW/TFHE}},
author = {Philippe Chartier and Mohammed Lemou},
howpublished = {HAL},
year = {2026},
month = oct,
url = {https://hal.science/hal-05849119v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact Error Bootstrapping and Comb Bootstrapping in FHEW/TFHE
AU - Philippe Chartier
AU - Mohammed Lemou
PY - 2026
DA - 2026/10/31
PB - HAL
UR - https://hal.science/hal-05849119v1
AB - In FHEW and TFHE, bootstrapping evaluates the decryption function via a blind rotation, whose resolution limits the message space. We propose instead to bootstrap the error. By rounding the ciphertext at a resolution that is a multiple of the message modulus, we preserve the message exactly. Reduction modulo a small integer then yields a noise-free encryption of the error, which a single blind rotation lifts exactly before it is subtracted. The message modulus is thus constrained solely by the noise and can be much larger than in standard TFHE. Since the error takes far fewer distinct values than the ring degree, a single blind rotation can also refresh several ciphertexts simultaneously. We call this procedure the comb bootstrap. Between refreshes, an integer remains encrypted in a single ciphertext, allowing additions modulo the message modulus and multiplications without programmable bootstrapping. Built on TFHE-rs, for 8-bit integers on a single thread, our refresh is 3.5 times faster than that of TFHE-rs, and 9.1 times faster with the comb bootstrap; multiplication is 6.5 times faster. In a residue number system, multiplication of integers modulo P ≥ 2^32 is 19 times faster than in TFHE-rs. The error bootstrap serves exclusively to refresh ciphertexts; evaluating any other function still requires programmable bootstrapping.
ER -