NTRU
Encyclopedia
NTRU is an asymmetric cryptosystem. It has two characteristics that make it interesting as an alternative to RSA and Elliptic Curve Cryptography
; speed and quantum computing resistance. There are two NTRU based algorithms: NTRUEncrypt
and NTRUSign
. An open source implementation of NTRU is available.
Most asymmetric algorithms cannot be compared to the performance of symmetric algorithms; symmetric algorithms are so much faster. However, according to the Department of Electrical Engineering, University of Leuven, "Using a modern GTX280 GPU a throughput of up to 200 000 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. This is using the speed-optimized parameter sets from a recent version of 1363.1 -- unfortunately those parameter sets have since changed but the overall result still holds: NTRU is extremely fast on parallelizable processors."
based attacks. A working, full-scale quantum computer running the process known as Shor's algorithm
would be able to break RSA or ECC of any practical key size in negligible time. In contrast, there is no known quantum attack on NTRU that significantly reduces its security. The National Institute of Standards and Technology (NIST), wrote in a 2009 survey: "There are viable alternatives for both public key encryption and signatures that are not vulnerable to Shor’s Algorithm” and “Of the various lattice based cryptographic schemes that have been developed, the NTRU family of cryptographic algorithms appears to be the most practical...smallest key size...highest performance."
). In 1996 these mathematicians together with D. Lieman founded the NTRU Cryptosystems, Inc.
and were given a patent on the cryptosystem.
During the last ten years people have been working on improving the cryptosystem. Since the first presentation of the cryptosystem, some changes were made to improve both the performance of the system and its security. In 2009, the company was acquired by Security Innovation -- a software security company.
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
; speed and quantum computing resistance. There are two NTRU based algorithms: NTRUEncrypt
NTRUEncrypt
The NTRUEncrypt public key cryptosystem, also known as the NTRU encryption algorithm, is a lattice-based alternative to RSA and ECC and is based on the shortest vector problem in a lattice...
and NTRUSign
NTRUSign
NTRUSign, also known as the NTRU Signature Algorithm, is a public key cryptography digital signature algorithm based on the GGH signature scheme. It was first presented at the rump session of Asiacrypt 2001 and published in peer-reviewed form at the RSA Conference 2003. The 2003 publication...
. An open source implementation of NTRU is available.
Speed
Because it is based on different mathematics (lattice-based cryptography) from RSA and ECC, the NTRU algorithm has different cryptographic properties. At comparable cryptographic strength, NTRU performs costly private key operations much much faster than RSA. In addition, NTRU's comparative performance increases with the level of security required. As key sizes increase by n, RSA's operations/second decrease at n3 whereas NTRU's decrease at n2.Most asymmetric algorithms cannot be compared to the performance of symmetric algorithms; symmetric algorithms are so much faster. However, according to the Department of Electrical Engineering, University of Leuven, "Using a modern GTX280 GPU a throughput of up to 200 000 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. This is using the speed-optimized parameter sets from a recent version of 1363.1 -- unfortunately those parameter sets have since changed but the overall result still holds: NTRU is extremely fast on parallelizable processors."
Resistance to quantum-computer-based attacks
Unlike RSA or ECC, NTRU is currently not known to be vulnerable to quantum computerQuantum computer
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
based attacks. A working, full-scale quantum computer running the process known as Shor's algorithm
Shor's algorithm
Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994...
would be able to break RSA or ECC of any practical key size in negligible time. In contrast, there is no known quantum attack on NTRU that significantly reduces its security. The National Institute of Standards and Technology (NIST), wrote in a 2009 survey: "There are viable alternatives for both public key encryption and signatures that are not vulnerable to Shor’s Algorithm” and “Of the various lattice based cryptographic schemes that have been developed, the NTRU family of cryptographic algorithms appears to be the most practical...smallest key size...highest performance."
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. .
Implementations
NTRU is available as an open source Java library and as for-pay, closed source.History
The first version of the system, which was simply called NTRU, was developed around 1996 by three mathematicians (J. Hoffstein, J.Pipher and J.H. SilvermanJoseph H. Silverman
Joseph Hillel Silverman is currently a professor of mathematics at Brown University. Joseph Silverman received an Sc.B. from Brown University in 1977 and a Ph.D. from Harvard University in 1982 under the direction of John Tate. He taught at M.I.T...
). In 1996 these mathematicians together with D. Lieman founded the NTRU Cryptosystems, Inc.
NTRU Cryptosystems, Inc.
Ntru Cryptosystems, Inc. is a provider of embedded security solutions. It was founded in 1996 by Joseph H. Silverman, Jeffrey Hoffstein, Jill Pipher and Daniel Lieman, four mathematicians at Brown University...
and were given a patent on the cryptosystem.
During the last ten years people have been working on improving the cryptosystem. Since the first presentation of the cryptosystem, some changes were made to improve both the performance of the system and its security. In 2009, the company was acquired by Security Innovation -- a software security company.