Loading...
Please wait, while we are loading the content...
Similar Documents
A hybrid lattice-reduction and meet-in-the-middle attack against ntru (2007).
| Content Provider | CiteSeerX |
|---|---|
| Author | Howgrave-Graham, Nick |
| Abstract | 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. |
| File Format | |
| Publisher Date | 2007-01-01 |
| Access Restriction | Open |
| Subject Keyword | Ntruencrypt Private Key Initial Lattice Basis Reduction Hybrid Lattice-reduction Meet-in-the-middle Strategy Conservative Extrapolation Lattice Reduction Scheme One Choice Efficient Attack Certain Space Time Tradeoff Security Parameter Lattice Reduction Ntruencrypt Security Parameter Private Key Meet-in-the-middle Attack Ntruencrypt Parameter |
| Content Type | Text |
