Liberating TFHE: Programmable bootstrapping with general quotient polynomials
Fully homomorphic encryption (FHE) enables operating directly on encrypted data. Bootstrapping is a technique used to reduce the noise of ciphertexts: indeed, in all known FHE schemes, ciphertexts contain a small amount of random noise, necessary for security reasons. When operations are carried out on noisy ciphertexts, the noise tends to increase. The bootstrapping operation is therefore an essential ingredient in FHE implementations.
Compared to other schemes, bootstrapping in TFHE, as well as its programmable extension, is relatively fast. At its core, it makes use of a series of polynomial multiplications in $(ℤ/qℤ)[X]/(X^N+1)$. For better efficiency, these polynomial multiplications are evaluated in the Fourier domain. Two options are available: the fast Fourier transform (FFT) over the complex numbers or its number-theoretic variant (NTT). The NTT presents the advantage of being purely discrete and, thus, produces exact results. It, however, imposes restrictions on the choice of modulus $q$. Current implementations assume so-called NTT-friendly moduli $q$.
In this work to be presented at WAHC 2022 (10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Los Angeles, CA, USA on November 7, 2022), we take a different route. Rather than modifying the modulus, we change the quotient polynomial. We explain how to adapt the programmable bootstrapping in the general setting of a polynomial ring of the form $(ℤ/qℤ)[X]/(Φ(X))$ for some cyclotomic polynomial $Φ(X)$. Our extended setting is particularly useful when modulus $q$ is a power of two, like $2^{32}$ or $2^{64}$. Example parameters are further provided in the paper.
