Hello,
The functions FFTSpecialInv and FFTSpecial from DiscreteFourierTransform perform the inverse and the normal Fast Fourier Transform, respectively, correct ?
In Encode we call the FFTSpecialInv. At the end of Encode, we switch from COEFF to EVAL format by calling (among other functions) ForwardTransformToBitReverseInPlace from ChineseRemainderTransformFTTNat, which from my understanding applies the FFT.
My question is, how can we apply the inverse of the FFT before we apply the FFT itself? What is the logic behind these steps?
Thank you and sorry if my question is confusing
Without getting into gory details, here is the high-level idea.
Suppose you have a set of points (x_i, y_i) and you are asked to find a polynomial a (with the lowest possible degree) that passes through these points, that is, y_i=a(x_i), \forall i. You can do this using polynomial interpolation methods. If the x_i's are certain values with nice properties, such as roots of unity, you can use IDFT- and DFT-like linear transforms to do the interpolation and the inverse of interpolation, which is evaluating a given polynomial at certain points, respectively.
In CKKS packed encoding, the input values we want to encode correspond to the y_i's in the example above, and the x_i's are pre-known powers of an M-th root of unity, where M is the underlying cyclotomic polynomial index. The SpecialIFFT is an IDFT-like linear transform that interpolates these points (x_i,y_i) to give the polynomial a which encodes them in CKKS plaintext space.
Note that the FFT-like transform is called in decoding, basically to evaluate the encoded polynomial (a) at x_i's and return y_i's in the example above, that is, computing a(x_i), \forall i.
One last thing to note is that evaluating IDFT- and FFT-like linear transforms is quite efficient with quasi-linear computational complexity in the length of the transform.
1 Like
Oh okay, I think I’ve got it. Thank you. So, when performing the EVAL to COEFF we are really applying the FFT to go the NTT domain, whereas in the Encode when we apply FFTSpecialInv we are using it as a polynomial interpolator to encode our plaintext and taking advantage of the roots of unity’s properties. Is this the correct rationale? Appreciate the help!
Yes, that is the gist of it.
1 Like