Paper 2016/177

Reduced Memory Meet-in-the-Middle Attack against the NTRU Private Key

Christine van Vredendaal

Abstract

NTRU is a public-key cryptosystem introduced at ANTS-III. The two most used techniques in attacking the NTRU private key are meet-in-the-middle attacks and lattice-basis reduction attacks. In the 2007 CRYPTO paper ``A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU'' both techniques are combined and it is pointed out that the largest obstacle to attacks is the memory capacity that is required for the meet-in-the-middle phase. In this paper an algorithm is presented that applies low-memory techniques to find `golden' collisions to Odlyzko's meet-in-the-middle attack against the NTRU private key. Several aspects of NTRU secret keys and the algorithm are analysed. The running time of the algorithm with a maximum storage capacity of $w$ is estimated and experimentally verified. Experiments indicate that decreasing the storage capacity by a factor $c$ increases the running time by a factor $\sqrt{c}$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
cryptanalysisNTRUmeet-in-the-middle attackcollision search
Contact author(s)
c v vredendaal @ tue nl
History
2016-02-22: received
Short URL
https://ia.cr/2016/177
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/177,
      author = {Christine van Vredendaal},
      title = {Reduced Memory Meet-in-the-Middle Attack against the NTRU Private Key},
      howpublished = {Cryptology ePrint Archive, Paper 2016/177},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/177}},
      url = {https://eprint.iacr.org/2016/177}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.