# NTT or FFT in TFHE and CKKS scheme?

**URL:** <https://openfhe.discourse.group/t/ntt-or-fft-in-tfhe-and-ckks-scheme/982>\
**Category:** FHE Questions\
**Created:** [December 21, 2023, 1:02pm UTC](https://openfhe.discourse.group/t/ntt-or-fft-in-tfhe-and-ckks-scheme/982 "2023-12-21T13:02:33Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![damionfan](https://avatars.discourse-cdn.com/v4/letter/d/278dde/32.png) [@damionfan](https://openfhe.discourse.group/u/damionfan)\
**Post date:** [December 21, 2023, 1:02pm UTC](https://openfhe.discourse.group/t/ntt-or-fft-in-tfhe-and-ckks-scheme/982/1 "2023-12-21T13:02:33Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ypolyakov](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/ypolyakov/32/47_2.png) [@ypolyakov](https://openfhe.discourse.group/u/ypolyakov)\
**Post date:** [December 22, 2023, 9:59pm UTC](https://openfhe.discourse.group/t/ntt-or-fft-in-tfhe-and-ckks-scheme/982/2 "2023-12-22T21:59:57Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![damionfan](https://avatars.discourse-cdn.com/v4/letter/d/278dde/32.png) [@damionfan](https://openfhe.discourse.group/u/damionfan)\
**Post date:** [December 24, 2023, 1:33pm UTC](https://openfhe.discourse.group/t/ntt-or-fft-in-tfhe-and-ckks-scheme/982/3 "2023-12-24T13:33:45Z")

</div>

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?"

---

<div class="post-metadata">

**Author:** ![ypolyakov](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/ypolyakov/32/47_2.png) [@ypolyakov](https://openfhe.discourse.group/u/ypolyakov)\
**Post date:** [December 27, 2023, 9:27pm UTC](https://openfhe.discourse.group/t/ntt-or-fft-in-tfhe-and-ckks-scheme/982/4 "2023-12-27T21:27:50Z")

</div>

In OpenFHE, the [HomomorphicEncryption.org security guidelines](https://homomorphicencryption.org/wp-content/uploads/2018/11/HomomorphicEncryptionStandardv1.1.pdf) 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](https://github.com/openfheorg/openfhe-development/blob/v1.1.2/src/binfhe/lib/binfhecontext.cpp#L123)

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).