Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU
verfasst von : Nick Howgrave-Graham
Erschienen in: Advances in Cryptology - CRYPTO 2007
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
To date the NTRUEncrypt security parameters have been based on the existence of two types of attack: a meet-in-the-middle attack due to Odlyzko, and a conservative extrapolation of the running times of the best (known) lattice reduction schemes to recover the private key. We show that there is in fact a continuum of more efficient attacks between these two attacks. We show that by combining lattice reduction and a meet-in-the-middle strategy one can reduce the number of loops in attacking the NTRUEncrypt private key from 2
84.2
to 2
60.3
, for the
k
= 80 parameter set. In practice the attack is still expensive (dependent on ones choice of cost-metric), although there are certain space/time tradeoffs that can be applied. Asymptotically our attack remains exponential in the security parameter
k
, but it dictates that NTRUEncrypt parameters must be chosen so that the meet-in-the-middle attack has complexity 2
k
even after an initial lattice basis reduction of complexity 2
k
.