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 3rd round of the 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 compared to non-EC cryptography to provide equivalent security.

<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, that is widely used for secure data transmission. The acronym "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) 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.

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 out-sourced to commercial cloud environments for processing, all while encrypted.

In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently. It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.

Dual_EC_DRBG is an algorithm that was presented as a cryptographically secure pseudorandom number generator (CSPRNG) using methods in elliptic curve cryptography. Despite wide public criticism, including the public identification of the possibility that the National Security Agency put a backdoor into a recommended implementation, it was for seven years one of four CSPRNGs standardized in NIST SP 800-90A as originally published circa June 2006, until it was withdrawn in 2014.

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 are currently important candidates for 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.

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

In cryptography, post-quantum cryptography (PQC) refers to cryptographic algorithms that are thought to be secure against a cryptanalytic attack by a quantum computer. The problem with currently popular algorithms is that their security relies on one of three hard 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.

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.

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.

SM9 is a Chinese national cryptography standard for Identity Based Cryptography issued by the Chinese State Cryptographic Authority in March 2016. It is represented by the Chinese National Cryptography Standard (Guomi), GM/T 0044-2016 SM9. The standard contains the following components:

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.

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.{{cite book}}: CS1 maint: date and year (link)
  12. ↑ "IEEE P1363: Standard Specifications For Public Key Cryptography". Grouper.ieee.org. 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. ↑ Scott Edwards (2018). "GoldBug-manual. Manual of the GoldBug Crypto Messenger". GitHub Pages.
  22. ↑ "Spot-On Encryption Suite with NTRU: Democratization of Multiple & Exponential Encryption". Spot-On. 2016-12-20. ISBN   978-3-7494-3506-7.
  23. ↑ "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.