Scott Fluhrer edited section_Abstract_This_paper_explores__.tex  almost 9 years ago

Commit id: 55f1d6d3b5dcdcaae050945c4c24c26c1b5c029f

deletions | additions      

       

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; we cannot modify how we generate $R$ without modifying how the decryptor works.  \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. 

\section{Conclusions}  We have presented an attack two attacks  where an adversary with a Quantum Computer is able to recover a low entropy plainttext; this attack might be plausible in some not-too-unreasonable circumstances. plainttexts.  We have also presented an attack that uses fewer operations than expected to recover the private key (assuming one of two parameter sets), and which is thoroughly impractical.