Number-Theoretic Transform
Description
The number-theoretic transform (NTT) is a generalization of the discrete Fourier transform over a ring or finite field. In a similar fashion to the FFT algorithm, the NNT efficiently computes the circular convolution of an integer sequence. An application of the NTT is the multiplication of two polynomials over a finite field, which is often used in cryptosystems based on lattices like CRYSTALS-KYBER.
Tasks:
- Understand the NTT and inverse NTT and how it relates to the FFT,
- study applications of NTT in post-quantum cryptosystems using the paper provided
Main papers:
Number Theoretic Transform and Its Applications in Lattice-based Cryptosystems: A Survey
Conceptual Review on Number Theoretic Transform and Comprehensive Review on Its Implementations
A nice primer on the NTT with examples can also be found in this blog
Contact
anna.baumeister@tum.de