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. Howgrave-Graham combined both techniques in 2007 and pointed out that the largest obstacle to attacks is the memory capacity that is required for the meet-in-the-middle phase. In the present 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 w by a factor 1 < c < root w increases the running time by a factor root c. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1112/S1461157016000206 | LMS JOURNAL OF COMPUTATION AND MATHEMATICS |
DocType | Volume | ISSN |
Journal | 19 | 1461-1570 |
Citations | PageRank | References |
4 | 0.79 | 14 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Christine van Vredendaal | 1 | 47 | 7.27 |