## CryptoDB

### Phong Q. Nguyen

#### Publications

**Year**

**Venue**

**Title**

2020

CRYPTO

Slide Reduction, Revisited—Filling the Gaps in SVP Approximation
📺
Abstract

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

Lower Bounds on Lattice Enumeration with Extreme Pruning
📺
Abstract

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

Quantum Lattice Enumeration and Tweaking Discrete Pruning
Abstract

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.

2016

EUROCRYPT

2012

EUROCRYPT

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

#### Coauthors

- Divesh Aggarwal (1)
- Yoshinori Aono (3)
- Jingguo Bi (1)
- Eli Biham (1)
- Daniel Bleichenbacher (1)
- Dan Boneh (1)
- Eric Brier (1)
- Guilhem Castagnos (1)
- Dario Catalano (1)
- Yuanmi Chen (2)
- Jean-Sébastien Coron (1)
- Christophe Coupé (1)
- Léo Ducas (2)
- Glenn Durfee (1)
- Jean-Charles Faugère (1)
- Pierre-Alain Fouque (1)
- Nicolas Gama (6)
- Louis Granboulan (1)
- Nick Howgrave-Graham (3)
- Malika Izabachène (1)
- Antoine Joux (2)
- Henrik Koy (1)
- Fabien Laguillaumie (1)
- Gaëtan Leurent (2)
- Jianwei Li (1)
- David Naccache (2)
- David Pointcheval (2)
- John Proos (1)
- Oded Regev (3)
- Guénaël Renault (1)
- Takenobu Seito (1)
- Yixin Shen (1)
- Junji Shikata (1)
- Igor E. Shparlinski (2)
- Joseph H. Silverman (1)
- Ari Singer (1)
- Damien Stehlé (1)
- Noah Stephens-Davidowitz (1)
- Jacques Stern (7)
- Mehdi Tibouchi (1)
- Michael Tunstall (1)
- Claire Whelan (1)
- William Whyte (1)
- Xiang Xie (1)
- Rina Zeitoun (1)
- Jiang Zhang (1)
- Zhenfeng Zhang (1)