Open Source NTRU Public Key Cryptography Algorithm and Reference Code

Key Contacts:

• Dr. William Whyte
• Dr. Mark Etzel
• Mr. Peter Jenney

Contacts may be reached by sending mail to [email protected]

Security Innovation, Inc., the owner of the NTRU public key cryptography system, made the intellectual property and a sample implementation available under the Gnu Public License (GPL) in 2013 with the goal of enabling more widespread adoption of this superior cryptographic technology. The system is also available for commercial use under the terms of the Security Innovation Commercial License.

NTRU represents a significant improvement in the Public Key cryptography world—it’s faster, stronger and smaller than virtually any other system in use and it’s quantum computer resistant, making it the best choice for current projects with lifetimes that extend into the post quantum computer age.

For additional overview information click https://www.securityinnovation.com/products/encryption-libraries/ntru-cryptography.html

NTRU is an asymmetric (public/private key) cryptosystem. It is a leading alternative to RSA and ECC as it is faster and quantum resistant. There are two NTRU based algorithms: NTRU Encrypt and NTRU Sign. Both cryptosystems are being released under GPL. The portable C/C++ & Java implementation in this project is also available under GPL.

Because it is based on different math from RSA and ECC, the NTRU algorithm has different cryptographic properties. At comparable cryptographic strength, NTRU performs costly private key operations much faster than RSA or ECC. In addition, NTRU's comparative performance increases with the level of security required. As key sizes increase by a factor of n, RSA's operations/second decrease by about n3 whereas NTRU's decrease at n2.

NTRU is currently not known to be vulnerable to algorithms based on quantum computers, unlike RSA or its other challenger, Elliptic Curve Cryptography. 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 size in negligible time. In contrast, NTRU’s security is reduced only slightly by quantum computers. This has been validated by external reviewers such as the National Institute of Standards and Technology (NIST), who in a 2009 survey referenced NTRU as justification for the statement that “there are viable alternatives for both public key encryption and signatures that are not vulnerable to Shor’s Algorithm”.

NTRU was invented in 1996 based on a completely different mathematical problems from RSA and Elliptic Curve called the “Approximate close lattice vector problem.” It has been published, reviewed in scholarly journals, and presented at Crypto, Eurocrypt, RSA. The NTRU approach to lattice-based cryptography, which uses a particular type of lattice known as an “ideal lattice”, has been a catalyst for the development of other efficient lattice-based cryptographic primitives, most notably Gentry’s approach to fully homomorphic encryption.

At comparable cryptographic strength, NTRU performs the costly private key operations much faster than RSA.

Security  NTRU Key Size     ECC   RSA     NTRU Ops/Sec.   ECC   RSA
Level     Std.    Opt.       Key Size     Std.    Opt.     Ops/Sec.
112       5951	  4411	    224	  2048	  2284	  10638	  951	  156
128	      6743	  4829	    256	  4096	  1896	  9901	  650	  12
192	      9757	  6523	    384	  7680	  1034	  6849	  285	  8
256	      12881	  8173	    512	  15360	  638     5000	  116	  1

Much of the performance impact in SSL comes from the use of public key cryptography, which is used to initiate new sessions (session “handshakes”). During session handshakes, the main public key activity consuming server resources is decryption of the session key provided by each client. Performance increases in decryption have a significant impact on server performance. At current levels of activity, for a server using NTRU, the server time spent peforming public key cryptography will become negligible. CyaSSL+NTRU, a product that uses the algoritm runs 20x to 200x faster than openSSL RSA.

Yes. The Department of Electrical Engineering at the University of Leuven released a report entitled Speed records for NTRU. in which they write: "NTRU is extremely fast on parallelizable processors."

Yes. NTRU has been adopted in two standards. By IEEE and the Financial industries X9 standards. (i) IEEE P1363 Working Group for Standards In Public Key Cryptography. This working group, active since 1992, has standardized many different techniques in public key cryptography. The standard IEEE Std 1363.1, issued in 2008, standardizes lattice-based public key cryptography, especially NTRUEncrypt. Other projects include or have included RSA, discrete log, elliptic curve discrete log, strong password-based techniques, and cryptography based on pairings. IEEE 1363 Working Group Home Page

Yes. The patents will still be enforced but may be used under the GPL, i.e. under the condition that any work that uses them is also made available under the GPL. The patents and the code implementations are also available under standard commercial terms.

Go to https://www.securityinnovation.com/security-lab/crypto.html which is where we’ve collected a boatload of content on NTRU including NIST reports, the math and other very useful stuff.