Hubbry Logo
NTRUNTRUMain
Open search
NTRU
Community hub
NTRU
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
NTRU
NTRU
NTRU
View on Wikipedia
from Wikipedia

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]

History

[edit]

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 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.

Performance

[edit]

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

[edit]

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

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

Implementations

[edit]

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:

  • OpenSSH by default uses NTRU combined with the X25519 ECDH key exchange since August 2022, included in version 9.0.[19]
  • The GPL-licensed reference implementation[18]
  • A BSD-licensed library[16]
  • bouncycastle[20]
  • Lokinet[21] was the first onion router implementing NTRU algorithm for its intraweb and End-2-End Encrypted events.
  • GoldBug Messenger[22] 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.[23]
  • Additionally, wolfSSL provides support for NTRU cipher suites in a lightweight C implementation.[24]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

NTRU

View on Grokipedia
from Grokipedia
NTRU is a lattice-based public-key cryptosystem introduced in 1996 by Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman, designed for efficient encryption and decryption using polynomial arithmetic in the ring Z/(xN−1)\mathbb{Z}/(x^N - 1) modulo two coprime integers pp and qq. It operates by generating keys through random polynomials ff and gg that satisfy invertibility conditions, with the public key hh computed as the convolution product h=f−1⋅g(modq)h = f^{-1} \cdot g \pmod{q}, while encryption adds a blinded message e=p⋅r⋅h+m(modq)e = p \cdot r \cdot h + m \pmod{q} using a random polynomial rr, and decryption recovers the message via multiplication by the private key and modular reduction. The system's security stems from the computational difficulty of lattice problems, such as finding short vectors in NTRU lattices, providing resistance to both classical and quantum attacks, including Shor's algorithm. Developed as an alternative to slower systems like RSA and , NTRU offers advantages in speed and , with , , and decryption operations scaling at O(N2)O(N^2) complexity for parameter NN, enabling its use on resource-constrained devices. Typical parameters include NN around 100–500, p=3p=3, and qq as a power of 2 (e.g., 64 or 128), balancing security levels from 2502^{50} to over 22002^{200} bits against known attacks like . Its mathematical foundation in the shortest vector problem (SVP) within rings has made it a prominent candidate in efforts, though variants like NTRU Prime were not selected in NIST's standardization rounds, which finalized algorithms such as CRYSTALS-Kyber and CRYSTALS-Dilithium instead. NTRU has evolved through variants including for encryption and NTRUSign for digital signatures, with parameter sets refined for enhanced security against side-channel and algebraic attacks. It was standardized in IEEE 1363.1 in 2008 and has been implemented in protocols like TLS for experimental post-quantum hybrid schemes, such as Google's CECPQ2 in Chrome. Despite not achieving NIST standardization, ongoing research supports its viability, with software implementations available for benchmarking and deployment in quantum-resistant applications.

Fundamentals

Overview

NTRU is an open-source lattice-based public-key cryptosystem designed for secure encryption and digital signatures, consisting of two primary algorithms: NTRUEncrypt for encryption and NTRUSign for signatures. It operates within the broader paradigm of lattice-based cryptography, relying on the hardness of lattice problems for security. The system performs key generation, encryption, and decryption using arithmetic on polynomials in quotient rings, enabling efficient handling of structured data without relying on factoring or discrete logarithm problems. A core strength of NTRU lies in its performance characteristics, including high-speed operations and compact key sizes, which make it suitable for resource-constrained environments compared to classical systems like RSA. Additionally, its lattice foundation provides inherent resistance to quantum attacks, positioning it as a viable option for post-quantum security. NTRUEncrypt entered the public domain in 2017 under a Creative Commons CC0 license, eliminating patent barriers for its implementation, while NTRUSign remains available under the GNU General Public License (GPL) for compatible software. Despite not being selected among the finalists in NIST's 2024 post-quantum cryptography standardization process, NTRU continues to influence research and deployments in quantum-resistant protocols. The system's parameters are chosen to balance security and efficiency, typically including a ring dimension NN such as 251 or 347, a modulus qq like 2048, and ternary polynomials for private keys with coefficients restricted to {−1,0,1}\{-1, 0, 1\}.

Mathematical Basis

The NTRU cryptosystem operates over the polynomial ring R=Z/(xN−1)R = \mathbb{Z} / (x^N - 1), where NN is a prime integer representing the degree of the polynomials, and elements are polynomials of degree less than NN with integer coefficients. Operations in RR include addition and multiplication modulo xN−1x^N - 1, which corresponds to circular convolution of coefficient vectors. To support modular arithmetic, the quotient ring Rq=(Z/qZ)/(xN−1)R_q = (\mathbb{Z}/q\mathbb{Z}) / (x^N - 1) is used, where qq is a small prime power (typically q=2kq = 2^k); coefficients in RqR_q are represented in the balanced range [−(q−1)/2,(q−1)/2][-(q-1)/2, (q-1)/2] to minimize wrapping effects during computations. Small polynomials ff and gg (used in key generation) have ternary coefficients drawn from a centered binomial distribution, which generates values in {−1,0,1}\{-1, 0, 1\} by summing η\eta independent random variables each taking values +1+1 or −1-1 with probability 1/21/2, then taking the result modulo 3 (or equivalently, using a direct probability assignment of 5/165/16 for ±1\pm 1 and 6/166/16 for 0 when η=2\eta = 2). This distribution ensures the polynomials are "short" in the ℓ2\ell_2-norm sense, with expected norm approximately Nη/2\sqrt{N \eta / 2}
Add your contribution
Related Hubs
User Avatar
No comments yet.