Lower Bounds on Lattice Enumeration with Extreme Pruning

Yoshinori Aono (1) , Phong Q. Nguyen (2, 3) , Takenobu Seito (4) , Junji Shikata (5)

1 NICT - National Institute of Information and Communications Technology [Tokyo]
2 Inria de Paris
3 JFLI - Japanese French Laboratory for Informatics
4 Bank of Japan
5 Graduate School of Environment and Information Sciences [Yokohama]

At Eurocrypt '10, Gama, Nguyen and Regev introduced lattice enumeration with extreme pruning: this algorithm is implemented in state-of-the-art lattice reduction software and used in challenge records. They showed that extreme pruning provided an exponential speed-up over full enumeration. However, no limit on its efficiency was known, which was problematic for long-term security estimates of lattice-based cryptosystems. We prove the first lower bounds on lattice enumeration with extreme pruning: if the success probability is lower bounded, we can lower bound the global running time taken by extreme pruning. Our results are based on geometric properties of cylinder intersections and some form of isoperimetry. We discuss their impact on lattice security estimates.

Domaines: Cryptographie et sécurité [cs.CR]; Théorie des nombres [math.NT]

Yoshinori Aono, Phong Q. Nguyen, Takenobu Seito, Junji Shikata. Lower Bounds on Lattice Enumeration with Extreme Pruning. CRYPTO 2018, 38th Annual International Cryptology Conference, IACR, Aug 2018, Santa-Barbara, United States. ⟨10.1007/978-3-319-96881-0_21⟩. ⟨hal-01845023⟩