deletions | additions       diff --git a/section_Abstract_This_paper_explores__.tex b/section_Abstract_This_paper_explores__.tex  index 094f2d6..b47e49d 100644  --- a/section_Abstract_This_paper_explores__.tex  +++ b/section_Abstract_This_paper_explores__.tex 
...
While NTRU is immune to Shor's algorithm (which allows the attack to quickly factor numbers and compute discrete logarithms). However, a Quantum Computer also allows an attacker to run Grover's algorithm, 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?'  \section{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 uses evaluates additions and multiplications modulo  two different prime powers ($p$ and $q$) during the course of its operation; operation. However,  all the operations that we'll examine are done modulo $q$ (where $q=2048$ is a typically choice). choice), hence for the purposes of this paper, we can consider the ring to be $Z[x]/(x^N-1,q)$  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$, the density of the internal polynomials $F$, $G$ and $R$ (these densities are known as $dF$ and $dG$), 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. 
...
Now, it is slightly more complicated than that; the polynomial $R$ is subject to tests to make sure that it has sufficiently high weight; if it does not, it is rejected (and a different random value for $b$ is selected). However, it turns out that does not matter for this attack.  The key observation is that the ciphertext is a determanistic deterministic  function of the plaintext, the public key and a $k$-bit random value. If the attacker knows that the message $m$ had low entropy (e.g. there were only $2^n$ possible values for it, for $n \lll k$), what an attacker with a Quantum Computer could do is model the system as one with $2^{n+k}$ inputs (which consists of the $2^n$ possible inputs for the plaintext, paired with the $2^k$ possible values for $b$), and then apply Grover's algorithm to find a solution that generates the known ciphertext in $O(2^{(n+k)/2})$ time, which is less than the security level $2^k$. As for the tests that are done on $R$ during the encryption process, this attack can ignore that. This is because any value of $b$ that gives an unacceptable $R$ will result in a different ciphertext than what we see, hence it will not be selected by Grover's algorithm.  Now, in practice, this attack would not generally appear to be a significant threat; in most cases, NTRUEncrypt will be used to pass symmetric keying data, and symmetric keying data has sufficiently high entropy to make this attack infeasible. However, in those cases where NTRUEncrypt is used to transmit low-entropy plaintexts or if the attacker might have a plausible guess for the plaintext (and it is important to make such verification infeasible, it would be advisable to include some extra random bits in the plaintext (to invalidate this attack).  \section{Key Recovery Attack}  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. sparse (which, in this case, means considers of $dG+1$ coefficients of the value $p$, $dG$ coefficients of the value $-p$, and the rest 0).  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. Now, if we do that in the straight-forward manner, that doesn't work (as for all defined parameter sets, there are more than $2^{2k}$ possible values of $F$); however there are several tricks we can do to reduce the number of $F$s the algorithm needs to consider. $F$).  The first trick is to compute $FH$ modulo 2, rather than modulo $q$ (assuming that $q$ is even, which it is for the If we are working with a  parameter sets in question). What set  that does is effectively reduce uses  the number of $F$s we need to consider; instead of considering all $F$s with $F_r$ 1's and $F_r$ -1's (that is, $\binom{2F_r}{F_r}\binom{N}{2F_r}$ possibilities), we need product form, one way  to consider only those $F$s with $2F_r$ 1's (as $1 \equiv -1 \pmod{2}$); this reduces rewrite  the number of $F$s we need to consider to $\binom{N}{2F_r}$. The resulting $FH$ remains sparse when computed modulo 2, hence that equation $FH = G$  is detected. It does mean that once we have reconstructed $F \bmod 2$, we need then to recover the signs for in  the nonzero coefficients; form $F_1F_2H = G - F_3H$, where we know  that can be done efficiently. each coefficient of $G$ is either $0, p$ or $-p$.  The second trick So, the obvious search algorithm  is to just the first $z$ coefficients (including $\pm p$) of $G - F_3H$ (for all possible $F_3$ values), and then value the Quantum Computer search over all possible $F_1, F_2$ values for which the first $z$ coefficients of $F_1F_2H$ is a match for one of the precomputed values (for $z \approx log_{q/3} | F_1 | |F_2| |F_3|$ (where $|F_i|$ deontes the size of the set of possible values for $F_i$). If we have $2^k > 3^z | F_3 |$ and $2^{2k} > |F_1||F_2|$, this will allow us to rederive $F$ in (strictly speaking) less than $2^k$ operations.  In addition, we can  take 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)$. As we are searching for sparse $FH$ values, rotating the values does not change the sparseness, and hence there are $N$ equivalent values for $F$ (and hence we can reduce the space of $F$s we consider by a factor of $N$). For the product form parameter sets, there is 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 triples $F_1, F_2, F_3$ we need to consider by another factor of $N$, giving us a total of $N^2$ in this case.