Liberating TFHE: Programmable bootstrapping with general quotient polynomials

Fully homomorphic encryption (FHE) allows operations to be performed directly on encrypted data, with bootstrapping serving as a crucial technique to manage the inherent noise in ciphertexts, which increases during operations but is essential for security. In TFHE, bootstrapping, and its programmable extension, is notably efficient, primarily through polynomial multiplications evaluated in the Fourier domain using either the fast Fourier transform (FFT) or its discrete counterpart, the number-theoretic variant (NTT). While NTT offers exact results, it restricts the choice of modulus, typically requiring NTT-friendly moduli. The work presented at WAHC 2022 proposes an alternative by altering the quotient polynomial, expanding the programmable bootstrapping framework to encompass a polynomial ring $(ℤ/qℤ)[X]/(Φ(X))$ with a cyclotomic polynomial $Φ(X)$, advantageous when modulus $q$ is a power of two. The paper includes example parameters to illustrate this approach.