CryptoDB

Phong Q. Nguyen

Publications

Year
Venue
Title
2020
CRYPTO
We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP) to allow for arbitrary block sizes, rather than just block sizes that divide the rank n of the lattice. This leads to significantly better running times for most approximation factors. We accomplish this by combining slide reduction with the DBKZ algorithm of Micciancio and Walter [Eurocrypt '16]. We also show a different algorithm that works when the block size is quite large---at least half the total rank. This yields the first non-trivial algorithm for sublinear approximation factors. Together with some additional optimizations, these results yield significantly faster provably correct algorithms for \delta-approximate SVP for all approximation factors n^{1/2+\eps} \leq \delta \leq n^{O(1)}, which is the regime most relevant for cryptography. For the specific values of \delta = n^{1-\eps} and \delta = n^{2-\eps}, we improve the exponent in the running time by a factor of 2 and a factor of 1.5 respectively.
2018
CRYPTO
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.
2018
ASIACRYPT
Enumeration is a fundamental lattice algorithm. We show how to speed up enumeration on a quantum computer, which affects the security estimates of several lattice-based submissions to NIST: if T is the number of operations of enumeration, our quantum enumeration runs in roughly $\sqrt{T}$ operations. This applies to the two most efficient forms of enumeration known in the extreme pruning setting: cylinder pruning but also discrete pruning introduced at Eurocrypt ’17. Our results are based on recent quantum tree algorithms by Montanaro and Ambainis-Kokainis. The discrete pruning case requires a crucial tweak: we modify the preprocessing so that the running time can be rigorously proved to be essentially optimal, which was the main open problem in discrete pruning. We also introduce another tweak to solve the more general problem of finding close lattice vectors.
2017
EUROCRYPT
2016
EUROCRYPT
2015
PKC
2014
PKC
2012
EUROCRYPT
2012
ASIACRYPT
2012
ASIACRYPT
2011
EUROCRYPT
2011
CHES
2011
ASIACRYPT
2010
EUROCRYPT
2009
ASIACRYPT
2009
JOFC
2009
CRYPTO
2008
EUROCRYPT
2007
CRYPTO
2007
PKC
2006
CRYPTO
2006
EUROCRYPT
2006
EUROCRYPT
2005
ASIACRYPT
2005
EUROCRYPT
2005
FSE
2005
PKC
2004
EUROCRYPT
2003
CRYPTO
2002
ASIACRYPT
2002
CRYPTO
2002
JOFC
2001
ASIACRYPT
2000
ASIACRYPT
2000
ASIACRYPT
2000
EUROCRYPT
1999
CRYPTO
1999
CRYPTO
1999
PKC
1998
ASIACRYPT
1998
CRYPTO
1997
CRYPTO

Program Committees

PKC 2016
Crypto 2016
Eurocrypt 2014 (Program chair)
Asiacrypt 2013
Eurocrypt 2013 (Program chair)
Asiacrypt 2012
Asiacrypt 2011
Crypto 2011
Asiacrypt 2010
PKC 2010 (Program chair)
TCC 2010
Crypto 2009
Asiacrypt 2009
Eurocrypt 2008
Eurocrypt 2007
Crypto 2006
Asiacrypt 2005
Eurocrypt 2005
PKC 2004
Asiacrypt 2003
Asiacrypt 2002
Eurocrypt 2002