## 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