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 (which is not known to be breakable using quantum computers). It relies on the presumed difficulty of factoring certain polynomials in a truncated polynomial ring into a quotient of two polynomials having very small coefficients. Breaking the cryptosystem is strongly related, though not equivalent, to the algorithmic problem of lattice reduction in certain lattices. Careful choice of parameters is necessary to thwart some published attacks. Since both encryption and decryption use only simple polynomial multiplication, these operations are very fast compared to other asymmetric encryption schemes, such as RSA, ElGamal and elliptic curve cryptography. However, NTRUEncrypt has not yet undergone a comparable amount of cryptographic analysis in deployed form. A related algorithm is the NTRUSign digital signature algorithm. Specifically, NTRU operations are based on objects in a truncated polynomial ring R = Z [ X ] / ( X N − 1 ) {\displaystyle \ R=\mathbb {Z} [X]/(X^{N}-1)} with convolution multiplication and all polynomials in the ring have integer coefficients and degree at most N-1:
a = a 0 + a 1 X + a 2 X 2 + ⋯ + a N − 2 X N − 2 + a N − 1 X N − 1 {\displaystyle {\textbf {a}}=a_{0}+a_{1}X+a_{2}X^{2}+\cdots +a_{N-2}X^{N-2}+a_{N-1}X^{N-1}}
That X N = 1 {\displaystyle X^{N}=1} in this ring has the effect that multiplying a polynomial by X {\displaystyle X} rotates the coefficients of the polynomial. A map of the form f ↦ f g {\displaystyle f\mapsto fg} for a fixed g ∈ R {\displaystyle g\in R} thus produces a new polynomial f g {\displaystyle fg} where every coefficient depends on as many coefficients from f {\displaystyle f} as there are nonzero coefficients in g {\displaystyle g} . NTRU has three integer parameters (N, p, q), where N is the polynomial degree bound, p is called the small modulus, and q is called the large modulus; it is assumed that N is prime, q is always (much) larger than p, and p and q are coprime. Plaintext messages are polynomials modulo p but ciphertext messages are polynomials modulo q. Concretely the ciphertext consists of the plaintext message plus a randomly chosen multiple of the public key, but the public key may itself be regarded as a multiple of the small modulus p, which allows the holder of the private key to extract the plaintext from the ciphertext.
History The NTRUEncrypt Public Key Cryptosystem is a relatively new cryptosystem. The first version of the system, which was simply called NTRU, was developed around 1996 by three mathematicians (Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman). In 1996 these mathematicians together with Daniel Lieman founded the NTRU Cryptosystems, Inc. and were given a patent (now expired) on the cryptosystem. During the last ten years people have been working on improving the cryptosystem. Since the first presentation of the cryptosystem, some changes were made to improve both the performance of the system and its security. Most performance improvements were focused on speeding up the process. Up till 2005 literature can be found that describes the decryption failures of the NTRUEncrypt. As for security, since the first version of the NTRUEncrypt, new parameters have been introduced that seem secure for all currently known attacks and reasonable increase in computation power. Now the system is fully accepted to IEEE P1363 standards under the specifications for lattice-based public-key cryptography (IEEE P1363.1). Because of the speed of the NTRUEncrypt Public Key Cryptosystem (see http://bench.cr.yp.to for benchmarking results) and its low memory use (see below), it can be used in applications such as mobile devices and Smart-cards. In April 2011, NTRUEncrypt was accepted as a X9.98 Standard, for use in the financial services industry.
Public key generation Sending a secret message from Alice to Bob requires the generation of a public and a private key. The public key is known by both Alice and Bob and the private key is only known by Bob. To generate the key pair two polynomials f and g, with degree at most N − 1 {\displaystyle \ N-1} and with coefficients in {-1,0,1} are required. They can be considered as representations of the residue classes of polynomials modulo X N − 1 {\displaystyle \ X^{N}-1} in R. The polynomial f ∈ L f {\displaystyle {\textbf {f}}\in L_{f}} must satisfy the additional requirement that the inverses modulo q and modulo p (computed using the Euclidean algorithm) exist, which means that
… excerpt ends here. Continue reading the full article.
