## 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

2014

EPRINT

2012

EUROCRYPT

2008

EPRINT

How Risky is the Random-Oracle Model?
Abstract

RSA-FDH and many other schemes provably secure in the Random-Oracle Model (ROM) require
a cryptographic hash function whose output size does not match any of the standard hash functions.
We show that the random-oracle instantiations proposed in the literature for such general cases are insecure,
including the two historical instantiations proposed by Bellare and Rogaway themselves in their seminal papers
from ACM~CCS~'93 and EUROCRYPT~'96:
for instance, for 1024-bit digests, we present a $2^{68}$ preimage attack on BR93 and a $2^{106}$ collision attack on BR96.
This leads us to study the potential security impact of such defects.
While one might think that a hash collision may at worst
give rise to an existential forgery on a signature scheme,
we show that for several (real-world) schemes secure in the ROM,
collisions or slight hash function defects can have much more dramatic consequences,
namely key-recovery attacks.
For instance, we point out that a hash collision discloses the master key
in the Boneh-Gentry-Hamburg identity-based cryptosystem from FOCS~'07,
and the secret key in the Rabin-Williams signature scheme
for which Bernstein proved tight security at EUROCRYPT~'08.
This problem can be fixed, but still, such schemes, as well as the Rabin-Williams variant implemented
in the IEEE P1363 standard, strongly require that the hash function
is immune to malleability variants of collision attacks, which does not hold for
the BR93 instantiation.
Our results suggest an additional criterion to compare schemes secure in the ROM:
assessing the risks by carefully studying the impact of potential flaws in the random-oracle instantiation.
In this light, RSA-PSS seems more robust than other RSA signatures secure in the ROM.

2007

EPRINT

Automatic Search of Differential Path in MD4
Abstract

In 2004, Wang et al. obtained breakthrough collision attacks on the main
hash functions from the MD4 family. The attacks are differential
attacks in which one closely follows the inner steps of the underlying
compression function, based on a so-called differential path. It is
generally assumed that such differential paths were found ``by hand''.
In this paper, we present an algorithm which automatically finds
suitable differential paths, in the case of MD4. As a first
application, we obtain new differential paths for MD4, which improve
upon previously known MD4 differential paths. This algorithm could be
used to find new differential paths, and to build new attacks against
MD4.

2006

EPRINT

A Note on the Security of NTRUSign
Abstract

At Eurocrypt '06, Nguyen and Regev presented a new key-recovery attack on the
Goldreich-Goldwasser-Halevi (GGH) lattice-based signature scheme:
when applied to NTRUSign-251 without perturbation, the attack recovers the secret key
given only 90,000 signatures. At the rump session, Whyte speculated whether the number
of required signatures might be significantly decreased to say 1,000, due to the special
properties of NTRU lattices. This short note shows that this is indeed the case: it turns out that as few as 400 NTRUSign-251 signatures are sufficient in practice to recover the
secret key. Hence, NTRUSign without perturbation should be considered totally insecure.

2004

EPRINT

Experimenting with Faults, Lattices and the DSA
Abstract

We present an attack on DSA smart-cards which combines physical fault injection and lattice reduction techniques. This seems to be
the first (publicly reported) physical experiment allowing to concretely pull-out DSA keys out of smart-cards. We employ a particular type of fault attack known as a glitch attack, which will be used to actively modify the DSA nonce k used for generating the signature: k will be tampered with so that a number of its least significant bytes will flip to zero. Then we apply well-known lattice attacks on El Gamal-type signatures which can recover the private key, given sufficiently many signatures such that a few bits of each corresponding k are known. In practice, when one byte of each k is zeroed, 27 signatures are sufficient to disclose the private key. The more bytes of k we can reset, the fewer signatures will be required. This paper presents the theory, methodology and results of the attack as well as possible countermeasures.

1997

CRYPTO

#### Program Committees

- PKC 2016
- Crypto 2016
- Eurocrypt 2014
- Asiacrypt 2013
- Eurocrypt 2013
- Asiacrypt 2012
- Asiacrypt 2011
- Crypto 2011
- Asiacrypt 2010
- PKC 2010
- 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 (2)
- 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 (2)
- Christophe Coupé (1)
- Léo Ducas (2)
- Glenn Durfee (1)
- Jean-Charles Faugère (2)
- Pierre-Alain Fouque (2)
- Nicolas Gama (7)
- Louis Granboulan (1)
- Nick Howgrave-Graham (3)
- Malika Izabachène (2)
- Antoine Joux (2)
- Henrik Koy (1)
- Fabien Laguillaumie (1)
- Gaëtan Leurent (4)
- Jianwei Li (1)
- David Naccache (3)
- David Pointcheval (2)
- John Proos (1)
- Oded Regev (3)
- Guénaël Renault (2)
- 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 (2)
- Claire Whelan (2)
- William Whyte (1)
- Xiang Xie (2)
- Rina Zeitoun (2)
- Jiang Zhang (2)
- Zhenfeng Zhang (2)