NTRU

NTRU is an asymmetric (public/private key) 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^[1].

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 n³ whereas NTRU's decrease at n².

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." ^[2]

Resistance to quantum-computer-based attacks

Unlike RSA or ECC, NTRU is currently not known to be vulnerable to quantum computer 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." ^[3]

Standardization

• The standard IEEE Std 1363.1, issued in 2008, standardizes lattice-based public key cryptography, especially NTRUEncrypt. ^[4]
• The standard X9.98 standardizes lattice-based public key cryptography, especially NTRUEncrypt, as part of the X9 standards for the financial services industry. ^[5].

Implementations

NTRU is available as an open source Java library^[6] and as for-pay, closed source^[7].

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. Silverman). In 1996 these mathematicians together with D. Lieman founded the NTRU Cryptosystems, Inc. and were given a patent on the cryptosystem.^[8]

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.^[9]

References

1. ^ http://ntru.sf.net/
2. ^ http://homes.esat.kuleuven.be/~fvercaut/papers/ntru_gpu.pdf
3. ^ http://middleware.internet2.edu/idtrust/2009/papers/07-perlner-quantum.pdf
4. ^ http://grouper.ieee.org/groups/1363/
5. ^ http://www.businesswire.com/news/home/20110411005309/en/Security-Innovation%E2%80%99s-NTRUEncrypt-Adopted-X9-Standard-Data
6. ^ http://ntru.sf.net/
7. ^ http://www.securityinnovation.com/products/encryption-libraries/ntru-cryptography.html
8. ^ http://grouper.ieee.org/groups/802/15/pub/Patent_Letters/15.3/ntru%2015.3.pdf
9. ^ Security Innovation acquires NTRU Cryptosystems, a leading security solutions provider to the embedded security market