Paper 2022/1177

Liberating TFHE: Programmable Bootstrapping with General Quotient Polynomials

Marc Joye, Zama
Michael Walter, Zama
Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. WAHC 2022
Keywords
Number-theoretic transform Polynomial multiplication Blind rotation FHE Programmable bootstrapping
Contact author(s)
marc @ zama ai
michael walter @ zama ai
History
2022-09-09: approved
2022-09-08: received
See all versions
Short URL
https://ia.cr/2022/1177
License
Creative Commons Attribution
CC BY

BibTeX

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