Scott Fluhrer edited section_Abstract_This_paper_explores__.tex  almost 9 years ago

Commit id: 48dbe9b643cf64208f9e817041c0c4700ce3db21

deletions | additions      

       

\section{Abstract} bb\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 from Security Innovation. We show four attacks that an attacker with a Quantum Computer might be able to perform against encryption performed by this library. Two of these attacks recover the private key from the public key with less effort than expected; in one case taking advantage of how the published library is implemented, and the other, an academic attack that works against four of the parameter sets defined for NTRUEncrypt. In addition, we also show two attacks allow that an attacker to be able to recover plaintext from the ciphertext and public key with less than expected effort.  \section{Introduction} 

We have presented four attacks where an adversary with a Quantum Computer is able to attempt against NTRUEncrpyt (as implemented by the current NTRU library). One of the key recovery attacks actually attacks the key generation process that the NTRU library uses; it would be easy to modify the library to foil this approach (for example, both to use stronger hash functions when generating the hashed value $h$, and by extending the additional 64 bits to prevent someone using Grover's algorithm to guess the preimage value). Because of the ease of this modification, and because the modified library would continue to interoperate with existing NTRU implementations, we recommend that such a change be made.  We have also presented another key recover attack that uses fewer operations than expected to recover the private key (assuming one of two the four standardized  parameter sets); however this attack is thoroughly impractical. We don't recommend any change to cover this attack. Neither of the two plaintext recovery attacks we have presented actually attack the NTRU primitive itself; instead, they attack the NAEP padding method, and take advantage of the fact that the internal primitives selected for the parameter sets are scaled to withstand attacks by a classical computer, and are not sufficient if the attacker has a Quantum Computer.