Jump to content

NTRU: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
added reference to PQCrypto evaluation of the provably secure version of NTRU
mNo edit summary
Line 11: Line 11:
== Resistance to quantum-computer-based attacks ==
== Resistance to quantum-computer-based attacks ==
Unlike [[RSA (algorithm)|RSA]] and [[Elliptic Curve Cryptography]], NTRU is not known to be vulnerable to [[quantum computer]] based attacks. 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 “[of] the various lattice based cryptographic schemes that have been developed, the NTRU family of cryptographic algorithms appears to be the most practical".<ref>{{cite journal |last=Perlner |first=Ray A. |last2=Cooper |first2=David A. |year=2009 |title=Quantum resistant public key cryptography: a survey |journal=Proceedings of the 8th Symposium on Identity and Trust on the Internet |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 |format=PDF |isbn=978-1-60558-474-4 |doi=10.1145/1527017.1527028 |accessdate=February 3, 2013 |url=http://middleware.internet2.edu/idtrust/2009/papers/07-perlner-quantum.pdf}}</ref> 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.<ref>{{Cite web|url = http://pqcrypto.eu/docs/initial-recommendations.pdf|title = Initial recommendations of long-term secure post-quantum
Unlike [[RSA (algorithm)|RSA]] and [[Elliptic Curve Cryptography]], NTRU is not known to be vulnerable to [[quantum computer]] based attacks. 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 “[of] the various lattice based cryptographic schemes that have been developed, the NTRU family of cryptographic algorithms appears to be the most practical".<ref>{{cite journal |last=Perlner |first=Ray A. |last2=Cooper |first2=David A. |year=2009 |title=Quantum resistant public key cryptography: a survey |journal=Proceedings of the 8th Symposium on Identity and Trust on the Internet |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 |format=PDF |isbn=978-1-60558-474-4 |doi=10.1145/1527017.1527028 |accessdate=February 3, 2013 |url=http://middleware.internet2.edu/idtrust/2009/papers/07-perlner-quantum.pdf}}</ref> 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.<ref>{{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}}</ref> However the Stehle-Steinfeld version of NTRU is "signi�ficantly less efficient than the original scheme."<ref name=":0">{{Cite web|title = Cryptology ePrint Archive: Report 2013/004|url = https://eprint.iacr.org/2013/004|website = eprint.iacr.org|access-date = 2016-01-18}}</ref>
systems|date = 1 March 2015|access-date = 18 January 2015|website = PQCRYPTO.EU|publisher = Horizon 2020 ICT-645622|last = Lange|first = Tanja}}</ref> However the Stehle-Steinfeld version of NTRU is "significantly less efficient than the original scheme."<ref name=":0">{{Cite web|title = Cryptology ePrint Archive: Report 2013/004|url = https://eprint.iacr.org/2013/004|website = eprint.iacr.org|access-date = 2016-01-18}}</ref>


== Standardization ==
== Standardization ==

Revision as of 20:50, 18 January 2016

NTRU is a patented and 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 and its performance has been shown to be significantly better.

History

The first version of the system, which was called NTRU, was developed in 1996 by mathematicians de [Jeffrey Hoffstein], Jill Pipher, and Joseph H. Silverman. That same year, the developers of NTRU joined with Daniel Lieman and founded the NTRU Cryptosystems, Inc., and were given a patent on the cryptosystem.[1] In 2009, the company was acquired by Security Innovation, a software security company.[2]

Performance

At equivalent cryptographic strength, NTRU performs costly private key operations much faster than RSA.[3] As key sizes increase, RSA's operations per second decrease cubicly, whereas NTRU's operations per second decrease quadratically.

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

Resistance to quantum-computer-based attacks

Unlike RSA and Elliptic Curve Cryptography, NTRU is not known to be vulnerable to quantum computer based attacks. 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 “[of] the various lattice based cryptographic schemes that have been developed, the NTRU family of cryptographic algorithms appears to be the most practical".[5] 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.[6] However the Stehle-Steinfeld version of NTRU is "significantly less efficient than the original scheme."[7]

Standardization

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

Implementations

Two open-source NTRU implementations exist; there is a BSD-licensed library [10] and a GPL-licensed library,[11] each available in Java and C.

Originally, NTRU was only available as a proprietary, for-pay library and open source authors were threatened with legal action.[12][13] It was not until 2011 that the first open-source implementation appeared.[10] In 2013, Security Innovation exempted open source projects from having to get a patent license,[14] and released an NTRU reference implementation under the GPL v2.[11] The proprietary, for-pay option is still offered by Security Innovation.[15]

References

  1. ^ Robertson, Elizabeth D. (August 1, 2002). "RE: NTRU Public Key Algorithms IP Assurance Statement for 802.15.3" (PDF). IEEE. Retrieved February 4, 2013.
  2. ^ Robinson, Maureen (July 22, 2009). "Security Innovation acquires NTRU Cryptosystems, a leading security solutions provider to the embedded security market" (Press release). Wilmington, MA: Security Innovation. Retrieved February 4, 2013.
  3. ^ "NTRU: Quantum-Resistant High Performance Cryptography".
  4. ^ Hermans, Jens; Vercauteren, Frederik; Preneel, Bart (2010). Pieprzyk, Josef (ed.). "Speed Records for NTRU" (PDF). Topics in Cryptography - CT-RSA 2010. Lecture Notes in Computer Science. 5985. San Francisco, CA: Springer Berlin Heidelberg: 73–88. doi:10.1007/978-3-642-11925-5_6. ISBN 978-3-642-11924-8. ISSN 0302-9743. Retrieved February 4, 2013.
  5. ^ Perlner, Ray A.; Cooper, David A. (2009). Seamons, Kent; McBurnett, Neal; Polk, Tim (eds.). "Quantum resistant public key cryptography: a survey" (PDF). Proceedings of the 8th Symposium on Identity and Trust on the Internet. New York, NY: ACM: 85–93. doi:10.1145/1527017.1527028. ISBN 978-1-60558-474-4. Retrieved February 3, 2013.
  6. ^ Lange, Tanja (1 March 2015). "Initial recommendations of long-term secure post-quantum systems" (PDF). PQCRYPTO.EU. Horizon 2020 ICT-645622. Retrieved 18 January 2015. {{cite web}}: line feed character in |title= at position 57 (help)
  7. ^ a b "Cryptology ePrint Archive: Report 2013/004". eprint.iacr.org. Retrieved 2016-01-18.
  8. ^ "IEEE P1363: Standard Specifications For Public Key Cryptography". Grouper.ieee.org. Retrieved 7 December 2014.
  9. ^ "Security Innovation's NTRUEncrypt Adopted as X9 Standard for Data Protection - Business Wire". Businesswire.com. Retrieved 7 December 2014.
  10. ^ a b Buktu, Tim. "NTRU: Quantum-Resistant cryptography". Independent / not affiliated with NTRU Cryptosystems, Inc. Retrieved February 4, 2013.
  11. ^ a b "Open Source NTRU Public Key Cryptography and Reference Code".
  12. ^ "Statement by the libtomcrypt (LTC) author".
  13. ^ "Email exchange between Security Innovation and a software author".
  14. ^ "FOSS Exception".
  15. ^ "Security Innovation - NTRU Cryptography".
Retrieved from "https://en.wikipedia.org/w/index.php?title=NTRU&oldid=700492080"