Quantum Cryptanalysis of NTRU

Abstract

This paper explores some attacks that someone with a Quantum Computer may be able to perform against NTRUEncrypt, and in particular NTRUEncrypt as implemented by the publicly available library from Security Innovation. We show four attacks that an attacker with a Quantum Computer might be able to perform against encryption performed by this library. Two of these attacks recover the private key from the public key with less effort than expected; in one case taking advantage of how the published library is implemented, and the other, an academic attack that works against four of the parameter sets defined for NTRUEncrypt. In addition, we also show two attacks that are able to recover plaintext from the ciphertext and public key with less than expected effort. This has potential implications on the use of NTRU within TOR, as suggested by Whyte and Schanck(John Schanck 2015)

Introduction

NTRUEncrypt(Hoffstein 1998) is a public key encryption system designed by Jeffrey Hoffstein, Jill Pipher and Joseph Silverman. It has several attractive features, one of which is that it is immune to attacks by Shor’s algorithm (as it does not rely on a factorization or discrete log hard problem). Hence, it looks to be a logical component as a part of a Quantum-Resistant cryptosystem.

NTRU does appear to be immune to Shor’s algorithm (which allows the attacker to quickly factor large integers and compute discrete logarithms). However, a Quantum Computer also allows an attacker to run Grover’s algorithm(Grover 1996), which is able to find a \(n\) bit solution to a problem in \(2^{n/2}\) time. The question we would like to look at is ’how can Grover’s algorithm be used to advantage in attacking NTRU?’

There has been previous analysis of the Quantum Resistance of NTRU, such as by Wang, Ma and Ma(Wang 2013), however those works studied previously defined parameter sets. This work is focusing on the parameter sets distributed with the current NTRU library.

NTRU Basics

NTRU works in the ring of polynomials \(Z[x]/x^N-1\), where \(N\) is a prime. Computations in this ring are actually done modulo a prime power; NTRUEncrypt actually evaluates additions and multiplications modulo a prime power (\(q\)) and a small polynomial (\(p\)) during the course of its operation. However, all the operations that we’ll examine are done modulo \(q\) (where \(q=2048\) is a typically choice), hence for the purposes of this paper, we can consider the ring to be \(Z[x]/(x^N-1,q)\). In addition to the base NTRU operation, NTRUEncrypt uses a padding mechanism called NAEP(Nick Howgrave-Graham 2003) to protect the underlying NTRU primitive from the attacker being able to deduce information from decryption failures.

There are a number of parameter sets defined for NTRU; each parameter set includes the value of \(N\) that are used during the NTRU operations, the values of \(p\) and \(q\), as well as the expected security level for this parameter set (that is, the value \(k\) for which we expect any attack against this parameter set to take at least \(O(2^k)\) operations.

NTRUEncrypt is available as a free-for-noncommercial use library from Security Innovation; we will be analyzing the parameter sets and the key generation and padding methods as implemented by that library.

When we select a private key for NTRUEncrypt, we select two polynomials \(F\) and \(G\) with specific sets of coefficients; we also need to make sure that \(F\) is invertible. Once we have that, we can compute the public polynomial \(H = F^{-1}G\). The public key decryption process uses the secret polynomial \(F\) to decrypt.

When we encrypt a message \(m\) with an NTRUEncrypt public key, the library performs the following steps:

  • It first examines the public key to get the security level \(k\) of the parameter set that the public key belongs to. Currently defined parameter sets have \(k \in \{ 112, 128, 192, 256 \}\)

  • It then selects a random \(k\)-bit value \(b\)

  • It encodes the value \(b\), the message \(m\) and a portion of the public key into a string, and hash that string to form a value \(\rho\). It uses SHA-1 as the hash function if \(k \le 160\) and SHA-256 if \(k > 160\)

  • It uses \(\rho\) to seed a random number generator, and uses the output of that random number generator to select a polynomial R

  • It encodes the message \(m\) and the random value \(b\) as a polynomial \(M\) which consists solely of coefficients in the set \(\{0, 1, -1\}\); we run a check on the value M to make sure that it has sufficient coefficient diversity (that is, this check makes sure that each of the possible values occurs sufficiently many times); if not, we go back and select a different value for \(b\).

  • It extracts the polynomial \(H\) from the public key, and generate the ciphertext \(HR + M\) (where the computation is done in the ring, calculating everything modulo \(q\)).

All but the last step is actually the NAEP padding procedure, used for generate the polynomials \(R\) and \(M\) for the actual NTRU operation.

During decryption, the decryptor recovers the values \(m\) and \(b\); it then uses the above logic to recompute \(R\) (and checks to make sure that was the \(R\) used to generate the ciphertext; this prevents invalidly generated ciphertexts from becoming an issue). What this means is that the encryptor must use this formula to generate \(R\) from \(b\), \(m\) and the public key.

Key Recovery Attack 1

The NTRU public key \(H\) is the polynomial \(F^{-1}G\) (computed over \(\mod q\)), where \(F\) and \(G\) are sparse polynomials; the polynomial \(F\) is the private key. One way to try to recover the private key is to search for an \(F\) such the product polynomial \(FH\) is sparse (which, in this case, means consists of \(dG+1\) coefficients of the value \(p\), \(dG\) coefficients of the value \(-p\), and the rest 0, where \(dG\) is a constant from the parameter set).

Now, the defined NTRU parameter sets work in one of two ways; in the straight-forward method, the key generation process selects a random polynomial whose coefficients consists of \(dF\) 1’s, \(dF\) -1’s, and the rest 0 (where \(dF\) is a parameter from the parameter set). The other method, known as the product form, has the key generation process select three polynomials \(F_1, F_2, F_3\), and effectively sets \(F = F_1F_2 + F_3\). Each of these polynomials \(F_1, F_2, F_3\) is sparser than the target \(F\) polynomial; and computing \(F_1(F_2H) + F_3H\) is faster than computing \(FH\) directly.

To use Grover’s algorithm, we could search for the polynomial \(F\) for which \(FH\) is sparse. However, doing this in this straight-forward manner doesn’t work (as for all defined parameter sets, there are more than \(2^{2k}\) possible values of \(F\)).

If we are working with a parameter set that uses the product form, one way to rewrite the equation \(FH = G\) is in the form \(F_1F_2H = G - F_3H\), where we know that each coefficient of \(G\) is either \(0, p\) or \(-p\).

The next obvious improvement is to check for this equality \(\bmod p\); as all coefficients of \(G\) are \(0 \bmod p\), this simplifies the equation to \(F_1F_2 \equiv -F_3H \pmod{p}\).

Now, there is an obvious objection to this; both \(F_1F_2\) and \(F_3H\) are computed modulo \(q\), which is relatively prime to \(p\); what happens if an addition within \(G - F_3H\) which “wraps”; that is, \(-F_3H\) has one sign, and \(G - F_3H\) has the other? Well, the obvious answer is “the search for the public key fails in that case”. It is worth noting that the probability of such a wrap happening is reasonable; the parameter sets in question have \(p=3\), \(q=2048\) and \(G\) having between 267 and 495 nonzero entries; assuming that the coefficents of \(F_3H\) are random, this gives us a success probability between \(0.67\) and \(0.48\). So, the obvious way to address this failure mode is, if the initial search fails, we add a random constant to both sides of the equation, and rerun the search; this has the effect of doubling the expected search time.

So, the obvious search algorithm is to store the coefficients of \(- F_3H \pmod p\) (for all possible \(F_3\) values), and then perform the Quantum Computer search over all possible \(F_1, F_2\) values for where the coefficients of \(F_1F_2H \pmod 3\) is a match for one of the precomputed values. With reasonable probability the correct private key will be the only one that gives a plausible setting; in fact, we don’t need to search over all the coordinates, instead it is sufficient to search over enough to make any false hit unlikely. If we find a match, this will allow us to rederive \(F\) in (strictly speaking) fewer than \(2^k\) operations.

In addition, we can reduce this work effort by taking advantage of the rotational symmetry of the multiply operation within \(F[x]/x^N-1\); if we consider the product \(AB\), and then consider the product \(A'B\) (where \(A'\) has the same coefficients as \(A\), only rotated by \(m\) positions, then the product \(A'B\) will have the same coefficients as \(AB\), only rotated by \(m\) positions. This can easily be seen as the operation of rotating by \(m\) positions is the operation of multiplying by the polynomial \(x^m\), and \((x^mA)B = x^m(AB)\). This allows us to reduce the number of \(F_3\) polynomials we consider by a factor of N (because if a specific value of \(F_3\) gives a solution with small coefficients, so will any rotation of \(F_3\) and the corresponding \(F_1F_2\).

Ttere is also a second symmetry that we can take advantage of; if we rotate the elements of \(F_1\) left by \(m\) positions, and the elements of \(F_2\) right by \(m\) positions, the resulting product \(F'_1 F'_2\) will be unchanged. That is, \((x^m F_1)(x^{-m}) F_2 = F_1 F_2\). This is a second symmetry that reduces the number of the products \(F_1 F_2\) we need to consider by a factor of \(N\).

The result of these two improvements reduce the number of \(- F_3H \bmod p\) values we need to precompute by a factor of \(N\), and the number of \(F_1 F_2 \bmod p\) polynomials that we need the Quantum Computer to search over by a factor of N.

When we consider the parameter set EES593EP1 (which has a design strength of 192), we find it has \(N = 593\), and \(dF_1 = 10\), \(dF_2 = 10\) and \(dF_3 = 8\). This implies that the total number of \(F_3\) polynomials is \(\binom{593}{16}\binom{16}{8}\) (because each \(F_3\) polynomial coefficients consists of 8 \(p\)s, 8 \(-p\)’s, and 577 \(0\)s), and the number of \(F_1F_2\) polynomials as \(\binom{593}{20}\binom{20}{10}\binom{593}{20}\binom{20}{10}\). When we take into account the factor of \(N\) decrease (because of the rotational symmetry) , this gives us \(|F_3|/N \approx 2^{107.285}\). When we consider the number of \(F_1 F_2\) polynomials, we take account of the factor \(N\) decrease (because of the second rotational symmetric), this gives us \(|F_1||F_2|/N \approx 2^{271.165}\). A Quantum Computer is able to search over a set of this size in approximately \(2^{136}\) time, and this second step would dominate. When we account for the failure probability (and the possibility we’re need to rerun this procedure), this gives us an overall time of \(O(2^{137})\), which is considerably smaller than the original design goal of 192 bits.

When we consider all four product form parameter sets, we find that the 112 bit product form set (EES401EP2) can be attacked with an expected \(O(2^{104})\) work, the 128 bit set (EES439EP1) can be attacked with an expected \(O(2^{112})\) work, and the 256 bit set (EES743EP1) can be attacked with an expected \(O(2^{197})\) work. In this last case, it’s actually the derivation of the possible values of \(-F_3H\) which is the dominating factor (because \(dF_3=15\)