Paper 2022/1177

Liberating TFHE: Programmable Bootstrapping with General Quotient Polynomials

Marc Joye, Zama
Michael Walter, Zama

All known instantiations for fully homomorphic encryption (FHE) produce noisy ciphertexts and rely on a technique called bootstrapping to reduce the noise so as to enable an arbitrary number of homomorphic operations. Bootstrapping is the main performance bottleneck and arguably the biggest obstacle to widespread adoption of FHE. Among the FHE schemes, TFHE and its variations present the appealing property of having a bootstrapping procedure---as well as its extension to programmable bootstrapping---that is relatively light-weight. The essential operations consist of a series of multiplications in $(Z/qZ)[X]/(X^N+1)$. While the NTT is seemingly the natural candidate for evaluating these multiplications in a fast and exact way, it restricts the possible choices for $q$ and $N$. To the authors' knowledge, all current implementations of TFHE with $q$ a power of two actually employ the FFT over the complex numbers instead. This introduces real numbers to the otherwise purely discrete algorithms, including all the drawbacks of the need to approximate them using finite precision. This work studies the avenues available to apply the NTT in the context of TFHE-like schemes. In particular, it considers various combinations of coefficient rings and quotient polynomials that are compatible with the requirements of the underlying scheme. Importantly, this work provides methods for adapting the (programmable) bootstrapping to quotient polynomials beyond power-of-two cyclotomics. As a side effect, it also demonstrates how this may enhance the programmability of the bootstrapping.

Note: Added more detailed analysis on noise growth.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. WAHC 2022
Number-theoretic transformPolynomial multiplicationBlind rotationFHEProgrammable bootstrapping
Contact author(s)
marc @ zama ai
michael walter @ zama ai
2023-02-17: revised
2022-09-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marc Joye and Michael Walter},
      title = {Liberating TFHE: Programmable Bootstrapping with General Quotient Polynomials},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1177},
      year = {2022},
      doi = {10.1145/3560827.3563376},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.