Get Ready for NTT

Within lattice cryptography, such as in areas of post-quantum cryptography (PQC), Zero Knowledge Proofs (ZKPs) and homomorphic encryption, we have the core concept of a Number-Theoretic Transform (NTT). Overall, in these fields, NTTs can account for over 90% of the FHE (Fully Homomorphic Encryption) computation time [1] and for ZKPs for over 80% of the processing time. With NTT, we have inputs of x_0, x_1 … x_{n-1} and outputs of y_0, y_1 … y_{n-1}, and where the values range from 0 to m-1. alpha_n is the n-th primitive root of unity:

Jung [2] outlines the parameters of HEAAN HE for the Arithmetic of Approximate Numbers method, and also known as CKKS [3]:

• L is the level and is the number of multiplications that can be applied before we lose data.
• p is the rescaling factor.
• Q is the maximum ciphertext modulus.
• N is a power-of-two integer.

Overall, we have a ciphertext which has a modulus of Q and which is two polynomials of c.ax and c.bx. These are in a ring of x^N+1. We can then perform a multiplication and then a rescaling process. For ciphertexts of c1 and c2, it is relatively simple to add the coefficients of the polynomials. With multiplication, we compute a tensor product (Figure 1):

c3.ax = c1.ax · c2.ax, c3.cx = c1.bx · c2.bx,
c3.bx = c1.ax · c2.bx +…