NTRU

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.{{cite web |url=https://grouper.ieee.org/groups/802/15/pub/Patent_Letters/15.3/ntru%2015.3.pdf |title=RE: NTRU Public Key Algorithms IP Assurance Statement for 802.15.3 |last1=Robertson |first1=Elizabeth D. |date=August 1, 2002 |publisher=IEEE |access-date=February 4, 2013}} 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.{{cite web |url=https://www.brown.edu/Administration/George_Street_Journal/vol25/25GSJ01e.html |title=Math professors patent computer security system |last1=Kerlin |first1=Janet |date=September 1, 2000 |periodical=George Street Journal |publisher=Brown University |archive-url=https://web.archive.org/web/20010125192900/http://www.brown.edu/Administration/George_Street_Journal/vol25/25GSJ01e.html |archive-date=January 25, 2001 }} In 2009, the company was acquired by Security Innovation, a software security corporation.{{cite press release |last=Robinson |first=Maureen |title=Security Innovation acquires NTRU Cryptosystems, a leading security solutions provider to the embedded security market |date=July 22, 2009 |publisher=Security Innovation |location=Wilmington, MA |url=https://www.securityinnovation.com/company/news-and-events/press-releases/acquires-ntru.html |access-date=February 4, 2013 |archive-url=https://web.archive.org/web/20131217073347/https://www.securityinnovation.com/company/news-and-events/press-releases/acquires-ntru.html |archive-date=December 17, 2013 }} 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,{{cite web |title=NTRU Prime |author=D. J. Bernstein |author2=C. Chuengsatiansup |author3=T. Lange |author4=C. van Vredendaal |date=2016-05-12 |url=https://ntruprime.cr.yp.to/ntruprime-20160511.pdf |website=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.

At equivalent cryptographic strength, NTRU performs costly private-key operations much faster than RSA does.{{cite web |url=https://tbuktu.github.io/ntru/ |title=NTRU: Quantum-Resistant High Performance Cryptography}} 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 {{val|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."{{cite book |last1=Hermans |first1=Jens |last2=Vercauteren |first2=Frederik |last3=Preneel |first3=Bart |title=Topics in Cryptology - CT-RSA 2010 |chapter=Speed Records for NTRU |year=2010 |volume=5985 |series=Lecture Notes in Computer Science |pages=73–88 |location=San Francisco, CA |publisher=Springer Berlin Heidelberg |editor1-first=Josef |editor1-last=Pieprzyk |isbn=978-3-642-11924-8 |issn=0302-9743 |doi=10.1007/978-3-642-11925-5_6 |access-date=February 4, 2013 |chapter-url=https://lirias.kuleuven.be/handle/123456789/280752}}

Unlike RSA and elliptic-curve cryptography, NTRU is not known to be vulnerable to attacks on 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".{{cite book |last1=Perlner |first1=Ray A. |last2=Cooper |first2=David A. |title=Proceedings of the 8th Symposium on Identity and Trust on the Internet |chapter=Quantum resistant public key cryptography |year=2009 |pages=85–93 |location=New York, NY |publisher=ACM |editor1-first=Kent |editor1-last=Seamons |editor2-first=Neal |editor2-last=McBurnett |editor3-first=Tim |editor3-last=Polk |isbn=978-1-60558-474-4 |doi=10.1145/1527017.1527028 |s2cid=12214601 |access-date=February 3, 2013 |chapter-url=http://middleware.internet2.edu/idtrust/2009/papers/07-perlner-quantum.pdf |archive-url=https://web.archive.org/web/20120514004113/http://middleware.internet2.edu/idtrust/2009/papers/07-perlner-quantum.pdf |archive-date=May 14, 2012 }} 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.{{Cite web |url = http://pqcrypto.eu/docs/initial-recommendations.pdf |title = Initial recommendations of long-term secure post-quantum systems |date = 1 March 2015 |access-date = 18 January 2015 |website = PQCRYPTO.EU |publisher = Horizon 2020 ICT-645622 |last = Lange |first = Tanja}} However the Stehle–Steinfeld version of NTRU is "significantly less efficient than the original scheme".{{Cite web |first1 = Damien |last1 = Stehlé |first2 = Ron |last2 = Steinfeld |title = Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices |url = https://eprint.iacr.org/2013/004 |website = Cryptology ePrint Archive |access-date = 2016-01-18}}

• The standard IEEE Std 1363.1, issued in 2008, standardizes lattice-based public-key cryptography, especially NTRUEncrypt.{{cite web |url=http://grouper.ieee.org/groups/1363/ |title=IEEE P1363: Standard Specifications For Public Key Cryptography |publisher=IEEE |access-date=7 December 2014 |archive-url=https://web.archive.org/web/20081119061833/http://grouper.ieee.org/groups/1363/ |archive-date=19 November 2008 }}
• The standard X9.98 standardizes lattice-based public-key cryptography, especially NTRUEncrypt, as part of the [http://www.x9.org/ X9] standards for the financial services industry.{{cite web |url=http://www.businesswire.com/news/home/20110411005309/en/Security-Innovation%E2%80%99s-NTRUEncrypt-Adopted-X9-Standard-Data |title=Security Innovation's NTRUEncrypt Adopted as X9 Standard for Data Protection |date=11 April 2011 |publisher=Business Wire |access-date=7 December 2014}}
• The PQCRYPTO project of the European Commission is considering standardization of the provably secure Stehle–Steinfeld version of NTRU.

Originally, NTRU was only available as a proprietary, for-pay library, and open-source authors were threatened with legal action.{{cite web |url=https://groups.google.com/d/msg/sci.crypt/OWSK-Dq1iBs/sF2iBuqRlj0J |title=Statement by the libtomcrypt (LTC) author }}{{cite web|url=http://pastebin.com/bENihzyD |title=Email exchange between Security Innovation and a software author }} 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{{cite web |url=https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/FOSS%20Exception.md |title=FOSS Exception |website=GitHub |access-date=2014-12-15 |archive-date=2019-02-14 |archive-url=https://web.archive.org/web/20190214045302/https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/FOSS%20Exception.md }} and released an NTRU reference implementation under the GPL v2.

Implementations:

• OpenSSH by default uses NTRU combined with the X25519 ECDH key exchange since August 2022, included in version 9.0.{{cite web |url=https://www.openssh.com/txt/release-9.0 |title=Changes since OpenSSH 8.9 (OpenSSH 9.0 release notes) |publisher=OpenBSDs OpenSSH developers |date=2022-04-08}}
• The GPL-licensed reference implementation{{cite web |url=https://github.com/NTRUOpenSourceProject/ntru-crypto |title=Open Source NTRU Public Key Cryptography and Reference Code |website=GitHub |access-date=2014-12-08 |archive-date=2018-03-31 |archive-url=https://web.archive.org/web/20180331010135/https://github.com/NTRUOpenSourceProject/ntru-crypto }}
• A BSD-licensed library{{cite web |url=https://tbuktu.github.io/ntru/ |title=NTRU: Quantum-Resistant cryptography |last=Buktu |first=Tim |publisher=Independent / not affiliated with NTRU Cryptosystems, Inc. |access-date=February 4, 2013}}
• bouncycastle{{cite web |url=http://www.bouncycastle.org/latest_releases.html |title=-ext- |publisher=Independent / not affiliated with NTRU Cryptosystems, Inc. |access-date=February 13, 2016}}
• Lokinet{{cite web |url=https://github.com/oxen-io/lokinet/commit/186bd7d573c4f260a98b3b4a3b7d5fade605627f|title=GitHub Commit in the lokinet repository showing NTRU implementation |author=majestrate |website=GitHub Pages |date=2018 }} was the first onion router implementing NTRU algorithm for its intraweb and End-2-End Encrypted events.
• GoldBug Messenger{{cite web |url=https://compendio.github.io/goldbug-manual/ |title=GoldBug-manual. Manual of the GoldBug Crypto Messenger |author=Scott Edwards |website=GitHub Pages |date=2018 }} 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.{{cite news

|title=Spot-On Encryption Suite with NTRU: Democratization of Multiple & Exponential Encryption

|url=https://textbrowser.github.io/spot-on/

|date=2016-12-20

|publisher=Spot-On

|isbn=978-3-7494-3506-7

}}

• Additionally, wolfSSL provides support for NTRU cipher suites in a lightweight C implementation.{{Cite news |url=https://www.wolfssl.com/products/wolfssl/ |title=wolfSSL Embedded SSL/TLS Library |website=wolfSSL Products |access-date=2018-10-09 |language=en-US}}

{{Reflist}}

• [https://ntru.org/ NTRU NIST submission]
• [https://ntruprime.cr.yp.to/ NTRU Prime NIST submission]

Category:Lattice-based cryptography

Category:Post-quantum cryptography

Category:1996 introductions