International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Junji Shikata

Publications

Year
Venue
Title
2018
CRYPTO
Lower Bounds on Lattice Enumeration with Extreme Pruning 📺
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.
2016
PKC
2005
ASIACRYPT
2004
PKC
2003
PKC
2002
ASIACRYPT
2002
EUROCRYPT
2002
PKC
2000
ASIACRYPT
1999
ASIACRYPT
1999
EUROCRYPT

Program Committees

Asiacrypt 2019
PKC 2002