NTRU: History, Design, and Security

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.

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.

Key generation selects two small polynomials f and g with coefficients in {-1, 0, 1}. The polynomial f must be invertible modulo both p (small prime, typically 3) and q (larger prime, typically 2048). The public key is h = f_q^{-1} * g mod q, where f_q is the inverse of f modulo q. The private key is the pair (f, g).

To encrypt a message polynomial m with small coefficients, the sender picks a random small blinding polynomial r and computes c = r * h + m mod q. The ciphertext c is a polynomial in the same ring. The random r prevents any two encryptions of the same message from looking identical, achieving semantic security.

Decryption computes a = f * c mod q, choosing coefficients in the range (-q/2, q/2]. Then a mod p recovers f_p * m mod p, and multiplying by fp = f^{-1} mod p gives m. The small error structure ensures the coefficients of f * c are small enough that the mod q and mod p operations interact correctly to recover the message without noise failure.

Modern NTRU has two standardized parameter families: NTRU-HPS (Hoffstein-Pipher-Silverman) and NTRU-HRSS (Hulsing-Rijneveld-Schanck-Schwabe). NTRU-HPS uses trinary message polynomials while NTRU-HRSS uses a randomized encoding for better decryption failure rates. Both appeared as NIST PQC round 3 finalists, with parameter sets targeting 128, 192, and 256-bit security.

No polynomial-time attack against properly parameterized NTRU is known. The best attacks reduce to finding a short vector in an NTRU lattice, which is an instance of the approximate SVP problem. The NTRU lattice has a specific structure (circulant blocks) that makes it slightly easier to attack than a random lattice, so parameters are chosen with a security margin accounting for this structure.

NTRU was heavily patented by NTRU Cryptosystems Inc. (later Security Innovation). The original patents were filed in 1996 and 1998. This patent protection hindered widespread adoption and open-source implementations for two decades. The core NTRU patents expired around 2017, after which open implementations proliferated and NTRU entered the NIST PQC standardization competition.

NTRU was a round 3 finalist in the NIST PQC competition alongside Kyber, Classic McEliece, and SABER. NIST ultimately chose Kyber (ML-KEM) as the primary KEM standard, citing its simpler security analysis and cleaner design. NTRU was not standardized but remains a viable alternative, and its analysis contributed to understanding of lattice security.

NTRUPrime, developed by Bernstein, Chuengsatiansup, Lange, and van Vredendaal, deliberately removes the ring structure X^N - 1 and replaces it with X^N - X - 1, a prime-degree polynomial. This eliminates potential weaknesses from the cyclic ring structure that some cryptanalysts believe could be exploited. NTRUPrime was also a NIST PQC alternate candidate.

NTRU predates LWE-based schemes and does not have a formal worst-case hardness reduction like Regev's LWE reduction. However, NTRU is faster in key generation and has smaller ciphertext sizes than many LWE schemes for equivalent security levels. The trade-off is a less formal security foundation, relying on decades of cryptanalytic experience rather than a reduction proof.

In NTRU, what is the public key derived from?

NTRU is a pioneering lattice-based cryptosystem based on polynomial ring arithmetic. Key generation uses small polynomials f and g, with public key h = f^{-1}*g mod q. Encryption uses random blinding; decryption exploits the small-coefficient structure of f. NTRU has no formal worst-case reduction but has withstood decades of cryptanalysis. Its patents expired in 2017 and it was a NIST PQC round 3 finalist.