deletions | additions       diff --git a/section_Abstract_This_paper_explores__.tex b/section_Abstract_This_paper_explores__.tex  index d103eb7..20bfd0e 100644  --- a/section_Abstract_This_paper_explores__.tex  +++ b/section_Abstract_This_paper_explores__.tex 
...
\section{Abstract}  This paper explores some attacks that may be possible against NTRUEncrypt if the attacker has a Quantum Computer; we show one way where the attacker may be able to recover a low entropy plaintext from the ciphertext and public key with less than expected effort. We also show an academic attack that can recover the private key from the public key with fewer operations than expected. expected, in at least 2 of the parameter sets defined for NTRUEncrypt.  \section{Introduction}  NTRUEncrypt is a public key encryption system designed by [Look up who/when]. 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 discete log hard problem). Hence, it looks to be a logical component as a part of a Quantum-Resistant cryptosystem. 
...
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$.  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|$ denotes the size of the set of possible values for $F_i$). At this setting of $z$, with reasonable probability the correct private key will be the only one that gives a plausible setting for the first $z$ coefficients of $G$.  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) 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 $G - F_3H$ values we need to precompute by a factor of $N$, and the number of $F_1 F_2$ polynomials that we need the Quantum Computer to search over by a factor of N. We can also reduce $z$ somewhat (because we are checking fewer combinations).  When we consider the parameter set EES593EP1, 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}$. This gives us $z = 40$, 41$,  and so (when we take into account the factor of $N$ decrease (because of the rotational symmetry) and the factor of $3^{40}$ $3^{41}$  increase (because of the values of $G$ we need to consider), this gives us $3^{40}/N|F_3| \approx 2^{170.68}$. 2^{172.269}$.  When we consider the number of $F_1 F_2$ polynomials, we get ; when we take account of the factor $N$ decrease (because of the second rotational symmetric), this gives us $1/N|F_1||F_2| \approx 2^{271.165}$. A Quantum Computer is able to search over a set of this size in approximately $2^{136}$ time, andfor  the first step would dominate. This search The  time to enumerate the possibilities for $G - F_3H$ is approximately $2^{172)$, which  is strictly smaller than the $2^{192}$ time that is the design strength of this parameter set. ... This approach also has some advantage for the EES430EP1 parameter set (which has a design strength of 128); it has $N= 439$, $dF_1 = 9$, $dF_2 = 8$, and $dF_3 = 5$. This gives us a $z = 31$, and so scanning for the possible values of $G - F_3H$ takes $2^{114.173)$ time, and searching through the possible $F_1F_2$ combinations would take $2^{110.616}$ time on a Quantum Computer, giving us a total time of about $2^{115}$, which is smaller than the $2^{128}$ design strength.  So, Now, this approach has managed to recover  the attack consists of having private key using fewer NTRU multiplications than expected. On  the Quantum Computer search through other hand, this approach is quite impractical (even beyond  the possible values number  of $F_1, F_2, F_3$ (reduced by the known symmetries), giving operations involved);  it a function that evaluates the polynomial $(F_1F_2 + F_3)H \bmod 2$, and returning 1 of assumes  thatpolynomial has weight $2G_r$; if there are $2^x$ such possible triples, then  we can find such a triple in $2^{x/2}$ time.  [TODO: CHECK TO MAKE SURE THAT SUCH A LOW WEIGHT POLYNOMIAL IS SUFFICIENTLY IMPROBABLE THAT WE HAVE A GOOD CHANCE THAT ONLY THE CORRECT KEY WILL DO SO]  There are two parameter sets practically check  forwhich this search time is less than  the designed security level existance  of the parameter set.  The first such parameter set is EES593EP1; this has $N=593$, $DF_1 = 10$, $DF_2 = 10$, and $DF_3 = 8$. an entry in a table with more than $2^{100}$ entries in constant time.