NTRUEncrypt
Encyclopedia
The NTRUEncrypt public key cryptosystem, also known as the NTRU encryption algorithm, is a lattice-based alternative to RSA and ECC
and is based on the shortest vector problem
in a lattice (i.e. is not breakable using quantum computers). Operations are based on objects in a truncated polynomial ring
with convolution multiplication and all polynomials in the ring have integer
coefficient
s and degree at most N-1:
NTRU is actually a parameterised family of cryptosystems; each system is specified by three integer parameters (N, p, q) which represent the maximal degree
for all polynomials in the truncated ring R, a small modulus and a large modulus, respectively, where it is assumed that N is prime
, q is always larger than p, and p and q are coprime
; and four sets of polynomials
and 
(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 
.
It relies on the presumed difficulty of factoring
certain polynomials in such rings 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
(solving the closest vector problem) in certain 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, El Gamal
and elliptic curve cryptography
. However, NTRUEncrypt has not yet undergone a comparable amount of cryptographic analysis.
A related algorithm is the NTRUSign
digital signature
algorithm.
The first version of the system, which was simply called NTRU, was developed around 1996 by three mathematicians (J. Hoffstein, J.Pipher and J.H. Silverman
). In 1996 these mathematicians together with D. Lieman founded the NTRU Cryptosystems, Inc.
and were given a patent on the cryptosystem.
At first the cryptosystem sometimes failed to decrypt a message back to the original message even though the message was encrypted correctly. Even though the system sometimes failed to decrypt, the developers considered it a public key cryptosystem and thereby based their security claims on the assumption that this system was a public key 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 focussed on speeding up the process, rather than fixing the problem of incorrect decryption. 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.
and with coefficients in {-1,0,1} are required. They can be considered as representations of the residue classes of polynomials modulo 
in R. The polynomial 
must satisfy the additional requirement that the inverses modulo q and modulo p (computed using the Euclidean algorithm
) exist, which means that
and 
must hold.
So when the chosen f is not invertible, Bob has to go back and try another f.
Both f and
are Bob’s 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 system parameters (N, p, q) are known to everybody. 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
After creating the message polynomial, Alice chooses randomly a polynomial r with small coefficients (not restricted to the set {-1,0,1}), that is meant to obscure the message.
With Bob’s public key h the encrypted message e is computed:
This ciphertext hides Alice’s messages and can be sent safely to Bob.
Example:
Assume that Alice wants to send a message that can be written as polynomial
and that the randomly chosen ‘blinding value’ can be expressed as
The ciphertext e that represents her encrypted message to Bob will look like
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]. This implies that all coefficients of
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.
The next step will be to calculate a modulo p:
because
.
Knowing b Bob can use the other part of his private key
to recover Alice’s message by multiplication of b and 
because the property
was required for 
.
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.
Reducing the coefficients of a mod p results in
which equals
.
In the last step the result is multiplied with
from Bob’s private key to end up with the original message m
Which indeed is the original message Alice has sent to Bob!
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
. If it has small coefficients it might be the secret key f, and Eve can test if f´ is the secret key by using it to decrypt a message she encrypted herself.
Eve could also try values of g and test if
has small values.
It is possible to mount a the meet-in-the-middle attack
which is more powerful. It can cut the search time by square root. The attack is based on the property that
.
Eve wants to find
and 
such that 
holds and such that they have the property
If f has d one’s and N-d zero’s, then Eve creates all possible
and 
in which they both have length 
(e.g. 
covers the 
lowest coefficients of f and 
the highest)
with d/2 one’s. Then she computes
for all 
and orders them in bins based on the first k coordinates. After that she computes all 
and orders them in bins not only based on the first k coordinates, but also based on what happens if you add 1 to the first k coordinates. Then you check the bins that contain both 
and 
and see if the property 
holds.
The lattice reduction attack is one of the best known and one of the most practical methods to break the NTRUEncrypt. In a way it can be compared to the factorization of the modulus in RSA. The most used algorithm for the lattice reduction attack is the Lenstra-Lenstra-Lovàsz algorithm.
Because the public key h contains both f and g one can try to obtain them from h. It is however too hard to find the secret key when the NTRUEncrypt parameters are chosen secure enough. The lattice reduction attack becomes harder if the dimension of the lattice gets bigger and the shortest vector gets longer.
The chosen ciphertext attack is also a method which recovers the secret key f and thereby results in a total break. In this attack Eve tries to obtain her own message from the ciphertext and thereby tries to obtain the secret key. In this attack Eve doesn’t have any interaction with Bob.
How it works:
First Eve creates a cipher text
such that 
and 
When Eve writes down the steps to deciphers e (without actually calculating the values since she does not know f) she finds
:
In which
such that
Example:
Then K becomes
.
Reducing the coefficients of polynomials a mod p really reduces the coefficients of
. After multiplication with 
, Eve finds:
Because c was chosen to be a multiple of p, m can be written as
Which means that
.
Now if f and g have few coefficients which are the same at the same factors, K has few non zero coefficients and is thereby small. By trying different values of K the attacker can recover f.
By encrypting and decrypting a message according to the NTRUEncrypt the attacker can check whether the function f is the correct secret key or not.
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
, in which F is a small polynomial (i.e. coefficients {-1,0, 1}). By constructing f this way, f is invertible mod p. In fact 
, which means that Bob does not have to actually calculate the inverse and that Bob does not have to conduct the second step of decryption. 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 
but f is still hard to recover.
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.
Second, f can be written as the product of multiple polynomials, such that the polynomials have many zero coefficients. This way fewer calculations have to be conducted.
In most commercial applications of the NTRUEncrypt, the parameter N=251 is used. To avoid lattice attacks, brute force attacks and meet-in-the-middle attacks, f and g should have about 72 non-zero coefficients.
According to the latest research the following parameters are considered secure:
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
and is based on the shortest vector problem
Lattice problems
In computer science, lattice problems are a class of optimization problems on lattices. The conjectured intractability of such problems is central to construction of secure lattice-based cryptosystems...
in a lattice (i.e. is not breakable using quantum computers). Operations are based on objects in a truncated polynomial ring
Polynomial ring
In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the Hilbert basis theorem, to the construction of...
with convolution multiplication and all polynomials in the ring have integerInteger
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
coefficient
Coefficient
In mathematics, a coefficient is a multiplicative factor in some term of an expression ; it is usually a number, but in any case does not involve any variables of the expression...
s and degree at most N-1:
NTRU is actually a parameterised family of cryptosystems; each system is specified by three integer parameters (N, p, q) which represent the maximal degree
for all polynomials in the truncated ring R, a small modulus and a large modulus, respectively, where it is assumed that N is primePrime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
, q is always larger than p, and p and q are coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
; and four sets of polynomials
and (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 .It relies on the presumed difficulty of factoring
Factorization
In mathematics, factorization or factoring is the decomposition of an object into a product of other objects, or factors, which when multiplied together give the original...
certain polynomials in such rings 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
Lattice reduction
In mathematics, the goal of lattice basis reduction is given an integer lattice basis as input, to find a basis with short, nearly orthogonal vectors. This is realized using different algorithms, whose running time is usually at least exponential in the dimension of the lattice.-Nearly...
(solving the closest vector problem) in certain lattice
Lattice (group)
In mathematics, especially in geometry and group theory, a lattice in Rn is a discrete subgroup of Rn which spans the real vector space Rn. Every lattice in Rn can be generated from a basis for the vector space by forming all linear combinations with integer coefficients...
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, El Gamal
ElGamal encryption
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1984. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of...
and elliptic curve cryptography
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
. However, NTRUEncrypt has not yet undergone a comparable amount of cryptographic analysis.
A related algorithm is the NTRUSign
NTRUSign
NTRUSign, also known as the NTRU Signature Algorithm, is a public key cryptography digital signature algorithm based on the GGH signature scheme. It was first presented at the rump session of Asiacrypt 2001 and published in peer-reviewed form at the RSA Conference 2003. The 2003 publication...
digital signature
Digital signature
A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...
algorithm.
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 (J. Hoffstein, J.Pipher and J.H. Silverman
Joseph H. Silverman
Joseph Hillel Silverman is currently a professor of mathematics at Brown University. Joseph Silverman received an Sc.B. from Brown University in 1977 and a Ph.D. from Harvard University in 1982 under the direction of John Tate. He taught at M.I.T...
). In 1996 these mathematicians together with D. Lieman founded the NTRU Cryptosystems, Inc.
NTRU Cryptosystems, Inc.
Ntru Cryptosystems, Inc. is a provider of embedded security solutions. It was founded in 1996 by Joseph H. Silverman, Jeffrey Hoffstein, Jill Pipher and Daniel Lieman, four mathematicians at Brown University...
and were given a patent on the cryptosystem.
At first the cryptosystem sometimes failed to decrypt a message back to the original message even though the message was encrypted correctly. Even though the system sometimes failed to decrypt, the developers considered it a public key cryptosystem and thereby based their security claims on the assumption that this system was a public key 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 focussed on speeding up the process, rather than fixing the problem of incorrect decryption. 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
IEEE P1363
IEEE P1363 is an Institute of Electrical and Electronics Engineers standardization project for public-key cryptography. It includes specifications for:* Traditional public-key cryptography...
).
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 coefficients much smaller than q, with degree at most and with coefficients in {-1,0,1} are required. They can be considered as representations of the residue classes of polynomials modulo in R. The polynomial must satisfy the additional requirement that the inverses modulo q and modulo p (computed using the Euclidean algorithmEuclidean algorithm
In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
) exist, which means that
and must hold.So when the chosen f is not invertible, Bob has to go back and try another f.
Both f and
are Bob’s private key. The public key h is generated computing the quantityExample:
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 system parameters (N, p, q) are known to everybody. 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
Encryption
Alice, who wants to send a secret message to Bob, puts her message in the form of a polynomial m with coefficients {-1,0,1}. In modern applications of the encryption, the message polynomial can be translated in a binary or ternary representation.After creating the message polynomial, Alice chooses randomly a polynomial r with small coefficients (not restricted to the set {-1,0,1}), that is meant to obscure the message.
With Bob’s public key h the encrypted message e is computed:
This ciphertext hides Alice’s messages and can be sent safely to Bob.
Example:
Assume that Alice wants to send a message that can be written as polynomial
and that the randomly chosen ‘blinding value’ can be expressed as
The ciphertext e that represents her encrypted message to Bob will look like
Decryption
Anybody knowing r could compute the message m; so r must not be revealed by Alice. 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]. This implies that all coefficients of
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.The next step will be to calculate a modulo p:
because
.Knowing b Bob can use the other part of his private key
to recover Alice’s message by multiplication of b and because the property
was required for .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.
Reducing the coefficients of a mod p results in
which equals
.In the last step the result is multiplied with
from Bob’s private key to end up with the original message mWhich indeed is the original message Alice has sent to Bob!
Attacks
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
Brute force attack
In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...
by trying all values for f. When Eve wants to know whether f´ is the secret key, she simply calculates
. If it has small coefficients it might be the secret key f, and Eve can test if f´ is the secret key by using it to decrypt a message she encrypted herself.Eve could also try values of g and test if
has small values.It is possible to mount a the meet-in-the-middle attack
Meet-in-the-middle attack
The meet-in-the-middle attack is a cryptographic attack which, like the birthday attack, makes use of a space-time tradeoff. While the birthday attack attempts to find two values in the domain of a function that map to the same value in its range, the meet-in-the-middle attack attempts to find a...
which is more powerful. It can cut the search time by square root. The attack is based on the property that
.Eve wants to find
and such that holds and such that they have the propertyIf f has d one’s and N-d zero’s, then Eve creates all possible
and in which they both have length (e.g. covers the lowest coefficients of f and the highest)with d/2 one’s. Then she computes
for all and orders them in bins based on the first k coordinates. After that she computes all and orders them in bins not only based on the first k coordinates, but also based on what happens if you add 1 to the first k coordinates. Then you check the bins that contain both and and see if the property holds.The lattice reduction attack is one of the best known and one of the most practical methods to break the NTRUEncrypt. In a way it can be compared to the factorization of the modulus in RSA. The most used algorithm for the lattice reduction attack is the Lenstra-Lenstra-Lovàsz algorithm.
Because the public key h contains both f and g one can try to obtain them from h. It is however too hard to find the secret key when the NTRUEncrypt parameters are chosen secure enough. The lattice reduction attack becomes harder if the dimension of the lattice gets bigger and the shortest vector gets longer.
The chosen ciphertext attack is also a method which recovers the secret key f and thereby results in a total break. In this attack Eve tries to obtain her own message from the ciphertext and thereby tries to obtain the secret key. In this attack Eve doesn’t have any interaction with Bob.
How it works:
First Eve creates a cipher text
such that and When Eve writes down the steps to deciphers e (without actually calculating the values since she does not know f) she finds
:In which
such thatExample:
Then K becomes
.Reducing the coefficients of polynomials a mod p really reduces the coefficients of
. After multiplication with , Eve finds:Because c was chosen to be a multiple of p, m can be written as
Which means that
.Now if f and g have few coefficients which are the same at the same factors, K has few non zero coefficients and is thereby small. By trying different values of K the attacker can recover f.
By encrypting and decrypting a message according to the NTRUEncrypt the attacker can check whether the function f is the correct secret key or not.
Security and performance improvements
Using the latest suggested parameters (see below) the NTRUEncrypt public key cryptosystem is secure to most attacks. There continues however to be a struggle between performance and security. 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
, in which F is a small polynomial (i.e. coefficients {-1,0, 1}). By constructing f this way, f is invertible mod p. In fact , which means that Bob does not have to actually calculate the inverse and that Bob does not have to conduct the second step of decryption. 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 but f is still hard to recover.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.
Second, f can be written as the product of multiple polynomials, such that the polynomials have many zero coefficients. This way fewer calculations have to be conducted.
In most commercial applications of the NTRUEncrypt, the parameter N=251 is used. To avoid lattice attacks, brute force attacks and meet-in-the-middle attacks, f and g should have about 72 non-zero coefficients.
According to the latest research the following parameters are considered secure:
Table 1: Parameters
| N | q | p | |
|---|---|---|---|
| Moderate Security | 167 | 128 | 3 |
| Standard Security | 251 | 128 | 3 |
| High Security | 347 | 128 | 3 |
| Highest Security | 503 | 256 | 3 |
External links
- NTRU Cryptosystems's technical website
- The IEEE P1363 Home Page
- NTRU Cryptosystems, Inc.
- A Java implementation of NTRUEncrypt
- CyaSSL - Embedded SSL Library offering cipher suites utilizing NTRUCyaSSLCyaSSL is a small, portable, embedded SSL programming library targeted for use by embedded systems developers. It is an open source, implementation of SSL built in the C language. It includes SSL client libraries and an SSL server implementation as well as support for multiple API's, including...