NTRU

Last updated

NTRU is an 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. NTRUEncrypt was patented, but it was placed in the public domain in 2017. NTRUSign is patented, but it can be used by software under the GPL. [1] [2]

Contents

History

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. [3] 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. [4] In 2009, the company was acquired by Security Innovation, a software security corporation. [5] In 2013, Damien Stehle and Ron Steinfeld created a provably secure version of NTRU, [6] which is being studied by a post-quantum crypto group chartered by the European Commission. [7]

In May 2016, Daniel Bernstein, Chitchanok Chuengsatiansup, Tanja Lange and Christine van Vredendaal released NTRU Prime, [8] which adds defenses against potential attack to NTRU by eliminating algebraic structure they considered worrisome. However, after more than 20 years of scrutiny, no concrete approach to attack the original NTRU 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.

Performance

At equivalent cryptographic strength, NTRU performs costly private-key operations much faster than RSA does. [9] 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 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." [10]

Resistance to quantum-computer-based attacks

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". [11] 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. [7] However the Stehle–Steinfeld version of NTRU is "significantly less efficient than the original scheme". [6]

Standardization

Implementations

Originally, NTRU was only available as a proprietary, for-pay library, and open-source authors were threatened with legal action. [14] [15] It was not until 2011 that the first open-source implementation appeared, [16] and in 2013, Security Innovation exempted open-source projects from having to get a patent license [17] and released an NTRU reference implementation under the GPL v2. [18]

Implementations:

Related Research Articles

Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys to provide equivalent security, compared to cryptosystems based on modular exponentiation in Galois fields, such as the RSA cryptosystem and ElGamal cryptosystem.

<span class="mw-page-title-main">Public-key cryptography</span> Cryptographic system with public and private keys

Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic algorithms based on mathematical problems termed one-way functions. Security of public-key cryptography depends on keeping the private key secret; the public key can be openly distributed without compromising security.

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem, one of the oldest widely used for secure data transmission. The initialism "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly in 1973 at Government Communications Headquarters (GCHQ), the British signals intelligence agency, by the English mathematician Clifford Cocks. That system was declassified in 1997.

Articles related to cryptography include:

The NTRUEncrypt public key cryptosystem, also known as the NTRU encryption algorithm, is an NTRU lattice-based alternative to RSA and elliptic curve cryptography (ECC) and is based on the shortest vector problem in a lattice.

There are a number of standards related to cryptography. Standard algorithms and protocols provide a focus for study; standards for popular applications attract a large amount of cryptanalysis.

IEEE P1363 is an Institute of Electrical and Electronics Engineers (IEEE) standardization project for public-key cryptography. It includes specifications for:

NTRUSign, also known as the NTRU Signature Algorithm, is an NTRU public-key cryptography digital signature algorithm based on the GGH signature scheme. The original version of NTRUSign was Polynomial Authentication and Signature Scheme (PASS), and was published at CrypTEC'99. The improved version of PASS was named as NTRUSign, and was presented at the rump session of Asiacrypt 2001 and published in peer-reviewed form at the RSA Conference 2003. The 2003 publication included parameter recommendations for 80-bit security. A subsequent 2005 publication revised the parameter recommendations for 80-bit security, presented parameters that gave claimed security levels of 112, 128, 160, 192 and 256 bits, and described an algorithm to derive parameter sets at any desired security level. NTRU Cryptosystems, Inc. have applied for a patent on the algorithm.

Cryptographic primitives are well-established, low-level cryptographic algorithms that are frequently used to build cryptographic protocols for computer security systems. These routines include, but are not limited to, one-way hash functions and encryption functions.

Homomorphic encryption is a form of encryption that allows computations to be performed on encrypted data without first having to decrypt it. The resulting computations are left in an encrypted form which, when decrypted, result in an output that is identical to that produced had the operations been performed on the unencrypted data. Homomorphic encryption can be used for privacy-preserving outsourced storage and computation. This allows data to be encrypted and outsourced to commercial cloud environments for processing, all while encrypted.

In cryptography, Curve25519 is an elliptic curve used in elliptic-curve cryptography (ECC) offering 128 bits of security and designed for use with the Elliptic-curve Diffie–Hellman (ECDH) key agreement scheme. It is one of the fastest curves in ECC, and is not covered by any known patents. The reference implementation is public domain software.

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions support important standards of post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.

<span class="mw-page-title-main">Cryptography</span> Practice and study of secure communication techniques

Cryptography, or cryptology, is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others. Core concepts related to information security are also central to cryptography. Practical applications of cryptography include electronic commerce, chip-based payment cards, digital currencies, computer passwords, and military communications.

DNSCurve is a proposed secure protocol for the Domain Name System (DNS), designed by Daniel J. Bernstein. It encrypts and authenticates DNS packets between resolvers and authoritative servers.

The following outline is provided as an overview of and topical guide to cryptography:

Post-quantum cryptography (PQC), sometimes referred to as quantum-proof, quantum-safe, or quantum-resistant, is the development of cryptographic algorithms that are thought to be secure against a cryptanalytic attack by a quantum computer. Most widely-used public-key algorithms rely on the difficulty of one of three mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems could be easily solved on a sufficiently powerful quantum computer running Shor's algorithm or even faster and less demanding alternatives.

wolfSSL is a small, portable, embedded SSL/TLS library targeted for use by embedded systems developers. It is an open source implementation of TLS written in the C programming language. It includes SSL/TLS client libraries and an SSL/TLS server implementation as well as support for multiple APIs, including those defined by SSL and TLS. wolfSSL also includes an OpenSSL compatibility interface with the most commonly used OpenSSL functions.

Post-Quantum Cryptography Standardization is a program and competition by NIST to update their standards to include post-quantum cryptography. It was announced at PQCrypto 2016. 23 signature schemes and 59 encryption/KEM schemes were submitted by the initial submission deadline at the end of 2017 of which 69 total were deemed complete and proper and participated in the first round. Seven of these, of which 3 are signature schemes, have advanced to the third round, which was announced on July 22, 2020.

<span class="mw-page-title-main">Hugo Krawczyk</span> Argentine Israeli cryptographer

Hugo Krawczyk is an Argentine-Israeli cryptographer best known for co-inventing the HMAC message authentication algorithm and contributing in fundamental ways to the cryptographic architecture of central Internet standards, including IPsec, IKE, and SSL/TLS. In particular, both IKEv2 and TLS 1.3 use Krawczyk’s SIGMA protocol as the cryptographic core of their key exchange procedures. He has also contributed foundational work in the areas of threshold and proactive cryptosystems and searchable symmetric encryption, among others.

Kyber is a key encapsulation mechanism (KEM) designed to be resistant to cryptanalytic attacks with future powerful quantum computers. It is used to establish a shared secret between two communicating parties without an (IND-CCA2) attacker in the transmission system being able to decrypt it. This asymmetric cryptosystem uses a variant of the learning with errors lattice problem as its basic trapdoor function. It won the NIST competition for the first post-quantum cryptography (PQ) standard. NIST calls its draft standard Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM).

References

  1. ↑ "Security Innovation Makes NTRUEncrypt Patent-Free". 2017-03-28. Archived from the original on 2019-02-18.
  2. ↑ "Ntru-crypto". GitHub . 25 November 2021.
  3. ↑ Robertson, Elizabeth D. (August 1, 2002). "RE: NTRU Public Key Algorithms IP Assurance Statement for 802.15.3" (PDF). IEEE. Retrieved February 4, 2013.
  4. ↑ Kerlin, Janet (September 1, 2000). "Math professors patent computer security system". George Street Journal. Brown University. Archived from the original on January 25, 2001.
  5. ↑ 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. Archived from the original on December 17, 2013. Retrieved February 4, 2013.
  6. 1 2 3 Stehlé, Damien; Steinfeld, Ron. "Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices". Cryptology ePrint Archive. Retrieved 2016-01-18.
  7. 1 2 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.
  8. ↑ D. J. Bernstein; C. Chuengsatiansup; T. Lange; C. van Vredendaal (2016-05-12). "NTRU Prime" (PDF). NTRU Prime.
  9. ↑ "NTRU: Quantum-Resistant High Performance Cryptography".
  10. ↑ Hermans, Jens; Vercauteren, Frederik; Preneel, Bart (2010). "Speed Records for NTRU". In Pieprzyk, Josef (ed.). Topics in Cryptology - CT-RSA 2010. Lecture Notes in Computer Science. Vol. 5985. San Francisco, CA: Springer Berlin Heidelberg. pp. 73–88. doi:10.1007/978-3-642-11925-5_6. ISBN   978-3-642-11924-8. ISSN   0302-9743 . Retrieved February 4, 2013.
  11. ↑ Perlner, Ray A.; Cooper, David A. (2009). "Quantum resistant public key cryptography" (PDF). In Seamons, Kent; McBurnett, Neal; Polk, Tim (eds.). Proceedings of the 8th Symposium on Identity and Trust on the Internet. New York, NY: ACM. pp. 85–93. doi:10.1145/1527017.1527028. ISBN   978-1-60558-474-4. S2CID   12214601. Archived from the original (PDF) on May 14, 2012. Retrieved February 3, 2013.
  12. ↑ "IEEE P1363: Standard Specifications For Public Key Cryptography". IEEE. Archived from the original on 19 November 2008. Retrieved 7 December 2014.
  13. ↑ "Security Innovation's NTRUEncrypt Adopted as X9 Standard for Data Protection". Business Wire. 11 April 2011. Retrieved 7 December 2014.
  14. ↑ "Statement by the libtomcrypt (LTC) author".
  15. ↑ "Email exchange between Security Innovation and a software author".
  16. 1 2 Buktu, Tim. "NTRU: Quantum-Resistant cryptography". Independent / not affiliated with NTRU Cryptosystems, Inc. Retrieved February 4, 2013.
  17. ↑ "FOSS Exception". GitHub . Archived from the original on 2019-02-14. Retrieved 2014-12-15.
  18. 1 2 "Open Source NTRU Public Key Cryptography and Reference Code". GitHub . Archived from the original on 2018-03-31. Retrieved 2014-12-08.
  19. ↑ "Changes since OpenSSH 8.9 (OpenSSH 9.0 release notes)". OpenBSDs OpenSSH developers. 2022-04-08.
  20. ↑ "-ext-". Independent / not affiliated with NTRU Cryptosystems, Inc. Retrieved February 13, 2016.
  21. ↑ majestrate (2018). "GitHub Commit in the lokinet repository showing NTRU implementation". GitHub Pages.
  22. ↑ Scott Edwards (2018). "GoldBug-manual. Manual of the GoldBug Crypto Messenger". GitHub Pages.
  23. ↑ "Spot-On Encryption Suite with NTRU: Democratization of Multiple & Exponential Encryption". Spot-On. 2016-12-20. ISBN   978-3-7494-3506-7.
  24. ↑ "wolfSSL Embedded SSL/TLS Library". wolfSSL Products. Retrieved 2018-10-09.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.