Editing NTRUEncrypt (section)

{{Short description|Lattice-based public key cryptosystem}}
{{More footnotes needed|date=April 2013}}
The '''NTRUEncrypt''' [[public key cryptosystem]], also known as the '''NTRU encryption algorithm''', is an [[NTRU]] [[lattice-based cryptography|lattice-based]] alternative to [[RSA (algorithm)|RSA]] and [[elliptic curve cryptography]] (ECC) and is based on the [[lattice problems|shortest vector problem]] in a lattice (which is not known to be breakable using [[quantum computers]]).

It relies on the presumed difficulty of [[factorization|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 [[lattice (group)|lattice]]s. 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 encryption|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 <math> \ R=\mathbb{Z}[X]/(X^N-1) </math> with convolution multiplication and all polynomials in the ring have [[integer]] [[coefficient]]s and degree at most ''N''-1:

:<math>  \textbf{a} = a_0 + a_1 X + a_2 X^2 + \cdots + a_{N-2} X^{N-2} + a_{N-1} X^{N-1} </math>

That <math> X^N = 1 </math> in this ring has the effect that multiplying a polynomial by <math>X</math> [[circular shift|rotates]] the coefficients of the polynomial. A map of the form <math> f \mapsto fg </math> for a fixed <math> g \in R </math> thus produces a new polynomial <math> fg </math> where every coefficient depends on as many coefficients from <math>f</math> as there are nonzero coefficients in <math>g</math>.

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 number|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. 
<!-- Not sure what to do with these phrases:
four sets of polynomials <math> \ \mathcal{L}_f, \mathcal{L}_g, \mathcal{L}_m </math> and <math> \ \mathcal{L}_r </math> (a polynomial part of the private key, a polynomial for generation of the public key, the message and a blinding value, respectively), all of degree at most <math> \ N-1 </math>. -->