Short answer: NTRU is a public key cryptosystem presented in 1996 by Hoffstein, Pipher and Silverman, built on polynomial algebra and reduction modulo two numbers, p and q. A book chapter describes it as resistant to quantum attacks and categorizes it as a post-quantum cryptosystem, while a survey notes that confidence in the hardness of its underlying problems has been a long-standing concern. The sources here are the original paper and two academic texts, not a standards document.
Where it comes from
The original NTRU paper describes a new public key cryptosystem with reasonably short, easily created keys, high speed and low memory requirements. Encryption uses a mixing system based on polynomial algebra and reduction modulo p and q, while decryption uses an unmixing system whose validity depends on elementary probability theory. The paper says the security comes from the interaction of the polynomial mixing system with the independence of reduction modulo p and q, and also relies on the experimentally observed fact that for most lattices it is very difficult to find extremely short, as opposed to moderately short, vectors.
A book chapter by Nitaj says NTRU was first introduced in the rump session at Crypto 1996 and later published at the ANTS-III conference. It says NTRU offers encryption and a signature scheme, NTRUSign, and calls it more efficient than RSA, ECC and El Gamal. That efficiency claim is the chapter's characterization.
Why quantum computers matter here
The chapter explains that the security of RSA, ECC and El Gamal rests on factoring or discrete logarithms, and that Shor showed in 1997 that quantum computers can solve both in polynomial time. It concludes that those systems would be easily breakable with a quantum computer, and says some cryptosystems, such as NTRU, are believed to be resistant to quantum attacks. A survey of NTRU says classical systems have been shown to be insecure in the presence of quantum computing. The word "believed" matters: this is a hardness assumption, not a proof.
The confidence question
A survey of NTRU's security and applications says one troubling issue since its introduction has been a lack of confidence in the hardness of its underlying computational problems. It reviews a result of Stehle and Steinfeld showing a variant of NTRU whose security can be proved based on the worst-case quantum hardness of natural lattice problems over ideal lattices defined over certain polynomial rings. The survey cautions that the hardness of those problems is not guaranteed, but says the result shows that any efficient attack against the variant implies a significant advance in computational algebraic number theory. It also says the survey introduces Fourier analysis tools now common in lattice-based cryptography.
Extensions
The survey reviews two novel variants that add functionality to the basic system. The first is an NTRU-based fully homomorphic encryption scheme. The text we reviewed does not go further, so this article does not describe the second.
What this does not tell you
These sources do not give key sizes, speeds or security levels for any current NTRU parameter set, and they do not say whether any standards body has selected NTRU. The efficiency statements come from the authors of the papers. Check current specifications before relying on any parameter.
FAQ
What is NTRU?
A public key cryptosystem from 1996 based on polynomial algebra and reduction modulo two numbers, p and q.
Is NTRU quantum-resistant?
A book chapter describes it as resistant to quantum attacks and as a post-quantum cryptosystem. It rests on a hardness assumption, not a proof.
What does its security rely on?
The interaction of polynomial mixing with reduction modulo p and q, and the observed difficulty of finding extremely short lattice vectors, per the original paper.
What did Stehle and Steinfeld show?
A survey says they showed a variant whose security can be proved from the worst-case quantum hardness of lattice problems over ideal lattices.
Does NTRU do more than encryption?
The chapter says it also offers a signature scheme, NTRUSign, and the survey reviews a fully homomorphic encryption variant.
All field notes