NTRU

Key takeaways

NTRU belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect NTRU to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of NTRU from memory before moving on to harder problems.

Reference excerpt

NTRU is an open-source public-key cryptosystem that uses lattice-based cryptography to encrypt and decrypt data. It consists of two algorithms: NTRUEncrypt, which is used for encryption, and NTRUSign, which is used for digital signatures. Unlike other popular public-key cryptosystems, it is resistant to attacks using Shor's algorithm. NTRUEncrypt was patented, but it was placed in the public domain in 2017. NTRUSign is patented, but it can be used by software under the GPL.

History The first version of the system, which was called NTRU, was developed in 1996 by mathematicians Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. That same year, the developers of NTRU joined with Daniel Lieman and founded the company NTRU Cryptosystems, Inc., and were given a patent on the cryptosystem. The name "NTRU", chosen for the company and soon applied to the system as well, was originally derived from the pun Number Theorists 'R' Us or, alternatively, stood for Number Theory Research Unit. In 2009, the company was acquired by Security Innovation, a software security corporation. In 2013, Damien Stehle and Ron Steinfeld created a provably secure version of NTRU, which is being studied by a post-quantum crypto group chartered by the European Commission. In May 2016, Daniel Bernstein, Chitchanok Chuengsatiansup, Tanja Lange and Christine van Vredendaal released NTRU Prime, which adds defenses against a potential attack on NTRU by eliminating algebraic structure they considered worrisome. However, after more than 20 years of scrutiny, no concrete approach to attack the original NTRU by exploiting its algebraic structure has been found so far. NTRU became a finalist in the third round of NIST's Post-Quantum Cryptography Standardization project, whereas NTRU Prime became an alternate candidate.

Performance At equivalent cryptographic strength, NTRU performs costly private-key operations much faster than RSA does. The time of performing an RSA private operation increases as the cube of the key size, whereas that of an NTRU operation increases quadratically. In 2010, the Department of Electrical Engineering, University of Leuven, noted that "[using] a modern GTX280 GPU, a throughput of up to 200000 encryptions per second can be reached at a security level of 256 bits. Comparing this to a symmetric cipher (not a very common comparison), this is only around 20 times slower than a recent AES implementation."

Resistance to quantum-computer-based attacks Unlike RSA and elliptic-curve cryptography, NTRU is not known to be vulnerable to attacks from quantum computers. The National Institute of Standards and Technology wrote in a 2009 survey that "[there] are viable alternatives for both public key encryption and signatures that are not vulnerable to Shor's Algorithm" and that "[of] the various lattice based cryptographic schemes that have been developed, the NTRU family of cryptographic algorithms appears to be the most practical". The European Union's PQCRYPTO project (Horizon 2020 ICT-645622) is evaluating the provably secure Stehle–Steinfeld version of NTRU (not original NTRU algorithm itself) as a potential European standard. However the Stehle–Steinfeld version of NTRU is "significantly less efficient than the original scheme".

Standardization The standard IEEE Std 1363.1, issued in 2008, standardizes lattice-based public-key cryptography, especially NTRUEncrypt. The standard X9.98 standardizes lattice-based public-key cryptography, especially NTRUEncrypt, as part of the X9 standards for the financial services industry. The PQCRYPTO project of the European Commission is considering standardization of the provably secure Stehle–Steinfeld version of NTRU.

Implementations Originally, NTRU was only available as a proprietary, for-pay library, and open-source authors were threatened with legal action. It was not until 2011 that the first open-source implementation appeared, and in 2013, Security Innovation exempted open-source projects from having to get a patent license and released an NTRU reference implementation under the GPL v2. Implementations:

OpenSSH by default uses NTRU Prime combined with the X25519 ECDH key exchange since August 2022, included in version 9.0. The GPL-licensed reference implementation A BSD-licensed library bouncycastle Lokinet was the first onion router implementing NTRU algorithm for its intraweb and End-2-End Encrypted events. GoldBug Messenger was the first chat and E-mail client with NTRU algorithm under open-source license, which is based on the Spot-On Encryption Suite Kernels. Additionally, wolfSSL provides support for NTRU cipher suites in a lightweight C implementation.

References

External links NTRU NIST submission NTRU Prime NIST submission

Worked examples

Example 1 — a first encounter with NTRU

Start with the simplest possible case. Write down what NTRU claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to NTRU before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about NTRU ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of NTRU

In research: NTRU appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses NTRU in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: NTRU is common in secondary-school and first-year university syllabi. It links to neighbouring topics 1996 introductions, Lattice-based cryptography, Post-quantum cryptography, so understanding it makes those chapters shorter.
In everyday life: Look for NTRU outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study NTRU in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what NTRU means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain NTRU out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is NTRU in simple terms?

NTRU is an open-source public-key cryptosystem that uses lattice-based cryptography to encrypt and decrypt data. It consists of two algorithms: NTRUEncrypt, which is used for encryption, and NTRUSign, which is used for digital signatures.

Why does NTRU matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study NTRU?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on NTRU.