Liberating TFHE: Programmable Bootstrapping with General Quotient Polynomials

Marc Joye; Michael Walter

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.

Note: Added more detailed analysis on noise growth.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. WAHC 2022
DOI: 10.1145/3560827.3563376
Keywords: Number-theoretic transform Polynomial multiplication Blind rotation FHE Programmable bootstrapping
Contact author(s): marc @ zama ai
michael walter @ zama ai
History: 2023-02-17: revised; 2022-09-08: received; See all versions
Short URL: https://ia.cr/2022/1177
License: 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},
      doi = {10.1145/3560827.3563376},
      url = {https://eprint.iacr.org/2022/1177}
}