deletions | additions       diff --git a/section_Abstract_This_paper_explores__.tex b/section_Abstract_This_paper_explores__.tex  index 6c93394..a7e4c54 100644  --- a/section_Abstract_This_paper_explores__.tex  +++ b/section_Abstract_This_paper_explores__.tex 
...
\section{Plaintext Recovery Attack}  When someone with the NTRUEncrypt public key does an public key encryption, it runs through this process: first, he examines the public key to get its security level $k$ for the parameter set. He then selects a $k$-bit random value $b$, and encodes that value (along with the plaintext $m$ and part of the public key) to form a string; it then uses that string as a seed to a random number generator to select a polynomial $R$; he then encodes the plaintext (and $b$) as a polynomial $M$, extracts the polynomial $H$ from the public key, and outputs the polynomial $HR+M$ as the ciphertext.  Now, it is slightly more complicated than that; the polynomial $R$ $M$  is subject to tests to make sure that it has sufficiently high weight; weight (it consists of coefficients of values $0, 1, -1$, we make sure that enough of each value appear);  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 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$ $M$  during the encryption process, this attack can ignore that. This is because any value of $b$ that gives an unacceptable $R$ $M$  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).