In exploring post-quantum cryptography algorithms like Kyber and Falcon, I've come across their utilization of Discrete Fourier Transform (DFT) and Number Theoretic Transform (NTT), but I'm seeking clarity on why the choice of transform matters.

While Falcon employs DFT in its algorithm and NTT in the verification phase, Kyber seems to rely primarily on NTT. What factors influence this choice between DFT and NTT? Are there specific computational or security advantages to one over the other?

My understanding is that these transforms are utilized to accelerate polynomial multiplication, but I'm curious if there are deeper implications or considerations at play. Could someone provide insights into the significance of DFT and NTT in these post-quantum cryptography schemes, and how their selection impacts the overall effectiveness and security?

I appreciate any clarification or guidance on this topic!

  • 2
    $\begingroup$ Related and maybe dupe Difference between FFT and NTT $\endgroup$
    – kelalaka
    Commented Jan 30 at 20:58
  • $\begingroup$ Albert, can you check the link and indicate if that contains the info you are looking for? If not please indicate what is missing from the answers on that question. $\endgroup$
    – Maarten Bodewes
    Commented Jan 31 at 10:50
  • $\begingroup$ It is not exactly what I would like to understand. For example, why the signature generation of falcon uses dft instead ntt? The falcon verification uses ntt, I do not understand why this difference. Is it about the ring? $\endgroup$
    – albert
    Commented Feb 7 at 20:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.