NTRU: History, Design, and Security
Study NTRU's polynomial ring structure, its key generation, and its long security track record.
NTRU Origins
NTRU was invented by Hoffstein, Pipher, and Silverman in 1996, making it one of the oldest post-quantum public-key systems still considered secure. Unlike RSA and ECC which rely on number-theoretic hardness, NTRU's security is based on the difficulty of finding short vectors in a specific lattice derived from polynomial rings. NTRU was commercialized and deployed in several security products before post-quantum cryptography became mainstream.
The NTRU Polynomial Ring
NTRU operates in the truncated polynomial ring Z[X]/(X^N - 1), where N is a prime. Polynomials in this ring are of degree at most N-1 and multiplication wraps around (convolution). The choice of ring and the structure of small-coefficient polynomials are central to both NTRU's efficiency and its security properties.
All lessons in this course
- Learning With Errors: The Hard Problem
- NTRU: History, Design, and Security
- Ring-LWE and Module Lattices
- Security Proofs and Reductions in Lattice Schemes