deletions | additions       diff --git a/section_Abstract_This_paper_explores__.tex b/section_Abstract_This_paper_explores__.tex  index 52cc2a3..08886df 100644  --- a/section_Abstract_This_paper_explores__.tex  +++ b/section_Abstract_This_paper_explores__.tex 
...
\section{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. library from Security Innovation.  We show two ways where the attacker is able to recover 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, in at least 2 of the parameter sets defined for NTRUEncrypt. \section{Introduction}  NTRUEncrypt\cite{Whyte_2005} 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. 
...
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.  NTRUEncrypt is available as a free-for-noncommercial use library from Security Innovations; \href{http://www.securityinnovation.com}{Security Innovation};  we will be analyzing the parameter sets 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. 
...
\begin{itemize}  \item 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 \}$  \item It then selects a random $k$-bit value $b$  \item It encodes the value $b$, the message $m$ and a portion of the public key into a string, and hash that string. We use string to form a value $\rho$. It uses  SHA-1 as the hash function  if $k \le 160$ and SHA-256 if $k > 160$ \item It uses that hash $\rho$  to seed a random number generator, and use uses  the output of that random number generator to select a polynomial R \item 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$.  \item It extracts the polynomial $H$ from the public key, and generate the ciphertext $HR + M$  \end{itemize}  
...
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$.  \section{Plaintext Recovery Attack 1}  If someone has a Quantum Computer, one way they may try to recover the plaintext given a ciphertext $C$ and a public key $H$ is to run Grover's algorithm, with the guess being $\rho$  the output of the hashed string. That is, they would take the guessed hash, $\rho$,  run it through the random number generator to generate a guess of $R$, and check if the polynomial $C-HR$ consists solely of the coefficients $\{0, 1, -1\}$; the correct guess of the hash will do that (as $C-HR$ is the encoded message $M$, which is a polynomial with those coefficients); an incorrect guess is quite unlikely to have coefficients limited to that range. For security levels 112, 128, we use a 160 bit hash, hence this approach will take an expected $O(2^{80})$ operations. For security levels 192, 256, we use a 256 bit hash, hence this approach will take an expected $O(2^{128})$ operations; in both cases, the work required is significantly smaller than the target security levels.  Note that, in the current NTRU library, there is a similar issue with generating the private key (as they use the same logic to generate $F$ and $G$ as they do to generate $R$). However, that is less of an issue, as we could modify the routines to generate $F$ and $G$ in a stronger manner; manner without affected interoperability;  we cannot modify how we generate $R$ without modifying how the decryptor works. decryption is done.  \section{Plaintext Recovery Attack 2}  Another way an attacker can attempt to recover the plaintext, if the plaintext is low entropy, is to noticy that the ciphertext is a determanistic function of the plaintext, the public key, and the $k$-bit random value $b$. If the entropy of the plaintext is low (had only $2^n$ possible values, for $n \lll k$), then 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 is, $m$ and $b$) that generates the known ciphertext in $O(2^{(n+k)/2})$ time, which is less than the security level $2^k$ (and if $n$ is sufficiently small, this value may be even smaller than the previous attack.