IFFT and Bit reversal

Library Questions
1

Hello,
In Encode, why do we do the bit reversal before the IFFT? Since OpenFHE uses the GS in the IFFT which expects the inputs in BO and outputs in NO, wouldn’t it make more sense to perform the Bit Reversal before the IFFT ? Then, we perform the Bit Reversal just before the FFT in the Decode, since it uses the CT butterfly it would expect in NO and output in BO. Wouldn’t it make more sense again to perform the Bit Reversal after the FFT ? Am I missing something?
Thank you

2

The first questions look confusing. First you wrote

In Encode, why do we do the bit reversal before the IFFT?

Then

Since OpenFHE uses the GS in the IFFT which expects the inputs in BO and outputs in NO, wouldn’t it make more sense to perform the Bit Reversal before the IFFT ?

Do you mean “after” in the second case?

At a high level, FFTSpecialInv takes the data input, applies FFT, which is in BO, and then switches it to NO. FFTSpecial does the opposite. Of course, the order can be switched (as is done in some FFT variants). Not sure what your specific question is.

3

Hello,

Sorry for the confusion. I thought that the “inv” in “FFTSpecialInv” meant Inverse as in Inverse FFT, but looks like it is for the BO input, so now it makes more sense. That explains why we do the Bit Reversal before the FFTSpecialInv. So, if I understood correctly, we use the FFT in both Encode (not the IFFT) and Decode, right?

4

FFTSpecialInv is used for Encoding and FFTSpecial is used for Decoding (as defined in the original CKKS paper)

5

Yes, but they are both implementations of FFT, right? The Inverse FFT is not used either for encoding or decoding.

6

The implementations are two different datapaths of FFT. They consume the twiddle factors in reverse order (which is similar to reading twiddle factors from the inverse “FFT” matrix). So, FFTSpecialInv computes an inverse of a special DFT.

7

FFTSpecialInv is used for encoding: openfhe-development/src/pke/lib/encoding/ckkspackedencoding.cpp at v1.1.2 · openfheorg/openfhe-development · GitHub

FFTSpecial is used for decoding: openfhe-development/src/pke/lib/encoding/ckkspackedencoding.cpp at v1.1.2 · openfheorg/openfhe-development · GitHub

Please see the code at openfhe-development/src/core/lib/math/dftransform.cpp at v1.1.2 · openfheorg/openfhe-development · GitHub to see the differences between FFTSpecialInv and FFTSpecial