Cryptology ePrint Archive: Report 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}$.

Category / Keywords: public-key cryptography / cryptanalysis, NTRU, meet-in-the-middle attack, collision search

Date: received 21 Feb 2016

Contact author: c v vredendaal at tue nl

Available format(s): PDF | BibTeX Citation

Version: 20160222:213646 (All versions of this report)

Short URL: ia.cr/2016/177

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]