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).
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.
Specifically, NTRU operations are based on objects in a truncated polynomial ring
with convolution multiplication and all polynomials in the ring have integer coefficients and degree at most N-1: That
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.
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).
Since the first presentation of the cryptosystem, some changes were made to improve both the performance of the system and its security.
[further explanation needed] Up till 2005 literature can be found that describes the decryption failures of the NTRUEncrypt.
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)[dubious – discuss], 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.
[2] Sending a secret message from Alice to Bob requires the generation of a public and a private key.
The public key h is generated computing the quantity Example: In this example the parameters (N, p, q) will have the values N = 11, p = 3 and q = 32 and therefore the polynomials f and g are of degree at most 10.
The polynomials are randomly chosen, so suppose they are represented by Using the Euclidean algorithm the inverse of f modulo p and modulo q, respectively, is computed Which creates the public key h (known to both Alice and Bob) computing the product Alice, who wants to send a secret message to Bob, puts her message in the form of a polynomial m with coefficients in
In modern applications of the encryption, the message polynomial can be translated in a binary or ternary representation.
In addition to the publicly available information, Bob knows his own private key.
Here is how he can obtain m: First he multiplies the encrypted message e and part of his private key f By rewriting the polynomials, this equation is actually representing the following computation: Instead of choosing the coefficients of a between 0 and q – 1 they are chosen in the interval [-q/2, q/2] to prevent that the original message may not be properly recovered since Alice chooses the coordinates of her message m in the interval [-p/2, p/2].
already lie within the interval [-q/2, q/2] because the polynomials r, g, f and m and prime p all have coefficients that are small compared to q.
This means that all coefficients are left unchanged during reducing modulo q and that the original message may be recovered properly.
Example: The encrypted message e from Alice to Bob is multiplied with polynomial f where Bob uses the interval [-q/2, q/2] instead of the interval [0, q – 1] for the coefficients of polynomial a to prevent that the original message may not be recovered correctly.
Since the proposal of NTRU several attacks on the NTRUEncrypt public key cryptosystem have been introduced.
Most attacks are focused on making a total break by finding the secret key f instead of just recovering the message m. If f is known to have very few non-zero coefficients Eve can successfully mount a brute force attack by trying all values for f. When Eve wants to know whether f´ is the secret key, she simply calculates
The lattice reduction attack is one of the best known and one of the most practical methods to break the NTRUEncrypt.
The chosen ciphertext attack is also a method which recovers the secret key f and thereby results in a total break.
When Eve writes down the steps to decipher e (without actually calculating the values since she does not know f) she finds
Using the latest suggested parameters (see below) the NTRUEncrypt public key cryptosystem is secure to most attacks.
It is hard to improve the security without slowing down the speed, and vice versa.
One way to speed up the process without damaging the effectiveness of the algorithm, is to make some changes in the secret key f. First, construct f such that
Therefore, constructing f this way saves a lot of time but it does not affect the security of the NTRUEncrypt because it is only easier to find
In this case f has coefficients different from -1, 0 or 1, because of the multiplication by p. But because Bob multiplies by p to generate the public key h, and later on reduces the ciphertext modulo p, this will not have an effect on the encryption method.