I'm looking at document of SEAL and openFHE, and they both use $\mathrm{NTT}^{\mathrm{CT}, \psi_{rev}}[\text{no to bo}]$ and $\mathrm{INTT}^{\mathrm{GS}, \psi_{rev}}[\text{bo to no}]$, 2 kinds of butterflies. $[\text{no to bo}]$ means natural order to bit-reversal order, similar to the other one.
I'm quite confused because they are pretty similar so why can't we just use one of them, like $\mathrm{NTT}^{\mathrm{CT}, \psi_{rev}}[\text{no to bo}]$ and $\mathrm{INTT}^{\mathrm{CT}, \psi_{rev}}[\text{bo to no}]$? Is this just some terminology confusion?
Also, since originally, CT is decimation-in-time (which will take bo as input) and GS is decimation-in-frequency (will take no as input), why we don't just use $\mathrm{NTT}^{\mathrm{GS}}[\text{no to bo}]$ and $\mathrm{INTT}^{\mathrm{CT}}[\text{bo to no}]$? Why bother adjust both of them to perform the current algorithms?
For reference, I'm reading these two papers:
- Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography
(This one is cited in both SEAL and openFHE)
- High-Performance Ideal Lattice-Based Cryptography on 8-bit ATxmega Microcontrollers
(1 cited 2)
