International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Phong Q. Nguyen

Publications

Year
Venue
Title
2020
CRYPTO
Slide Reduction, Revisited—Filling the Gaps in SVP Approximation 📺
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 📺
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
Yoshinori Aono Phong Q. Nguyen Yixin Shen
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
EPRINT
2015
PKC
2014
PKC
2014
EPRINT
2014
EPRINT
2012
EUROCRYPT
2012
ASIACRYPT
2012
ASIACRYPT
2011
EUROCRYPT
2011
CHES
2011
ASIACRYPT
2010
EUROCRYPT
2009
ASIACRYPT
2009
JOFC
2009
CRYPTO
2008
EUROCRYPT
2008
EPRINT
How Risky is the Random-Oracle Model?
Gaëtan Leurent Phong Q. Nguyen
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
CRYPTO
2007
PKC
2007
EPRINT
Automatic Search of Differential Path in MD4
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
CRYPTO
2006
EUROCRYPT
2006
EUROCRYPT
2006
EPRINT
A Note on the Security of NTRUSign
Phong Q. Nguyen
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.
2005
ASIACRYPT
2005
EUROCRYPT
2005
FSE
2005
PKC
2004
EUROCRYPT
2004
EPRINT
Experimenting with Faults, Lattices and the DSA
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.
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
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