# NTT or FFT in TFHE and CKKS scheme?

The CKKS scheme employs the Number Theoretic Transform (NTT) to expedite polynomial multiplication, as the elements of the CKKS polynomial are integers with a prime modulus. On the other hand, the multiplication between polynomials in the TFHE scheme can be perplexing, as the elements of polynomials in TFHE can be either integers or floats. Some researchers utilize the Fast Fourier Transform (FFT) to accelerate this process, while others opt for NTT. In cases where NTT is chosen to accelerate polynomial multiplication in TFHE, the question arises: how does one determine the suitable prime for this purpose

For NTTs used in TFHE/FHE, OpenFHE supports any prime modulus that is congruent to 1 mod 2N, where N is the ring dimension. The high-level idea is to iterate through integers congruent to 1 mod 2N (for a given bit size) until a prime is found. This is implemented using FirstPrime and LastPrime methods in OpenFHE.

To my knowledge, TFHE uses q=2^{32} or 2^{64}. Are you selecting the prime number closest to this value? Could this selection potentially introduce additional errors?"

In OpenFHE, the HomomorphicEncryption.org security guidelines are also used for TFHE. In other words, the error distribution parameter \sigma is set to 3.19 and the ring dimension is chosen based on the desired security work factor (using the lattice estimator). You can see the parameters used in v1.1.2 at openfhe-development/src/binfhe/lib/binfhecontext.cpp at v1.1.2 · openfheorg/openfhe-development · GitHub

In classical TFHE, 32-bit and 64-bit moduli are used for convenience (to leverage complex-number FFT) and higher values of distribution parameters are used as \log q/\sigma can approximately be treated as one parameter in estimating the work factor. In the NTT case, we often use 27-bit moduli (for ternary uniform secrets) or 28-bit moduli (for Gaussian secrets).