Abstract: In 1976, Diffie and Hellman introduced the revolutionary concept of public-key cryptography, also known as asymmetric cryptography. Today, asymmetric cryptography is routinely used to secure the Internet. The most famous and most widely used asymmetric cryptosystem is RSA, invented by Rivest, Shamir and Adleman. Surprisingly, there are very few alternatives known, and most of them are also based on number theory. How secure are those asymmetric cryptosystems? Can we attack them in certain settings? Should we implement RSA the way it was originally described thirty years ago? Those are typical questions that cryptanalysts have tried to answer since the appearance of public-key cryptography. In these notes, we present the main techniques and principles used in public-key cryptanalysis, with a special emphasis on attacks based on lattice basis reduction, and more generally, on algorithmic geometry of numbers. To simplify our exposition, we focus on the two most famous asymmetric cryptosystems: RSA and Elgamal. Cryptanalysis has played a crucial role in the way cryptosystems are now implemented, and in the development of modern security notions. Interestingly, it also introduced in cryptology several mathematical objects which have since proved very useful in cryptographic design. This is for instance the case of Euclidean lattices, elliptic curves and pairings.

Bibtex: @inbook{Ng08, author={P. Q. Nguyen}, booktitle={Recent Trends in Cryptography}, title={Public-Key Cryptanalysis}, editor={I. Luengo}, series={Contemporary Mathematics}, publisher={AMS--RSME}, year=2009, volume=477 }

La cryptologie : enjeux et perspectives

Invited survey in French

top of the page

Authors: Phong Q. Nguyen and Jacques Stern

Chapitre 6 du livre Paradigmes et enjeux de l'informatique

sous la direction de N. Bidoit, L; Farinas del Cerro, S. Fdida, B. Vallée
édité par Lavoisier, mars 2005.
Pages 101--120.

Abstract: Dans cet article, nous tenterons de faire un état de l'art de la cryptologie, et d'esquisser les perspectives de la recherche fondamentale. Auparavant, nous rappelerons les fondements de la cryptologie et ses principales fonctionnalités. Pour des raisons d'espace, nous nous limiterons aux aspects théoriques fondamentaux de la cryptologie, laissant de côté les nombreuses applications.

The Two Faces of Lattices in Cryptology

Invited survey ( .gz version)

top of the page

Authors: Phong Q. Nguyen and Jacques Stern

Cryptography and Lattices -- Proceedings of CALC '01
(March 29--30, 2001, Providence, Rhode Island, USA)
J. Silverman (Ed.)
vol. 2146 of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: Lattices are regular arrangements of points in n-dimensional space, whose study appeared in the 19th century in both number theory and crystallography. Since the appearance of the celebrated Lenstra-Lenstra-Lovasz lattice basis reduction algorithm twenty years ago, lattices have had surprising applications in cryptology. Until recently, the applications of lattices to cryptology were only negative, as lattices were used to break various cryptographic schemes. Paradoxically, several positive cryptographic applications of lattices have emerged in the past five years: there now exist public-key cryptosystems based on the hardness of lattice problems, and lattices play a crucial role in a few security proofs. We survey the main examples of the two faces of lattices in cryptology.

Journal Papers

An LLL Algorithm with Quadratic Complexity

Full version in pdf, to appear in SIAM J. of Computing.
This supersedes the former proceedings version, which appeared at EUROCRYPT 2005.	top of the page

Authors: Phong Q. Nguyen and Damien Stehlé

Abstract: The Lenstra--Lenstra--Lov\'asz lattice basis reduction algorithm (called LLL or L^3) is a fundamental tool in computational number theory and theoretical computer science, which can be viewed as an efficient algorithmic version of Hermite's inequality on Hermite's constant. Given an integer d-dimensional lattice basis with vectors of Euclidean norm less than~$B$ in an $n$-dimensional space, the ${\rm L}^3$~algorithm outputs a reduced basis in~$O(d^3n\,{\rm log}\,B\cdot\mathcal{M}(d\,{\rm log}\,B))$ bit operations, where~$\mathcal{M}(k)$ denotes the time required to multiply $k$-bit integers. This worst-case complexity is problematic for applications where $d$ or/and ${\rm log}\,B$ are often large. As a result, the original ${\rm L}^3$~algorithm is almost never used in practice, except in tiny dimension. Instead, one applies floating-point variants where the long-integer arithmetic required by Gram--Schmidt orthogonalization is replaced by floating-point arithmetic. Unfortunately, this is known to be unstable in the worst case: the usual floating-point ${\rm L}^3$~algorithm is not even guaranteed to terminate, and the output basis may not be ${\rm L}^3$-reduced at all. In this article, we introduce the ${\rm L}^2$~algorithm, a new and natural floating-point variant of the ${\rm L}^3$~algorithm which provably outputs ${\rm L}^3$-reduced bases in polynomial time $O(d^2n(d+{\rm log}\,B)\,{\rm log}\,B\cdot\mathcal{M}(d))$. This is the first ${\rm L}^3$~algorithm whose running time (without fast integer arithmetic) provably grows only quadratically with respect to ${\rm log}\,B$, like Euclid's gcd algorithm and Lagrange's two-dimensional algorithm.

Bibtex: @article{NgSt09, title={An {LLL} Algorithm with Quadratic Complexity}, author={P. Q. Nguyen and D. Stehl\'e}, journal={SIAM J. of Computing}, volume={ 39}, number= 3, pages = {874–-903}, year=2009 }

Sieve Algorithms for the Shortest Vector Problem Are Practical

In Journal of Mathematical Cryptology. ( .pdf version)

top of the page

Authors: Phong Q. Nguyen and Thomas Vidick

Abstract: The most famous lattice problem is the Shortest Vector Problem (SVP), which has many applications in cryptology. The best approximation algorithms known for SVP in high dimension rely on a subroutine for exact SVP in low dimension. In this paper, we assess the practicality of the best (theoretical) algorithm known for exact SVP in low dimension: the sieve algorithm proposed by Ajtai, Kumar and Sivakumar (AKS) in 2001. AKS is a randomized algorithm of time and space complexity $2^{O(n)}$, which is theoretically much lower than the super-exponential complexity of all alternative SVP algorithms. Surprisingly, no implementation and no practical analysis of AKS has ever been reported. It was in fact widely believed that AKS was impractical: for instance, Schnorr claimed in 2003 that the constant hidden in the $2^{O(n)}$ complexity was at least 30. In this paper, we show that AKS can actually be made practical: we present a heuristic variant of AKS whose running time is $(4/3+ \eps)^{n}$ polynomial-time operations, and whose space requirement is $(4/3+\eps)^{n/2}$ polynomially many bits. Our implementation can experimentally find shortest lattice vectors up to dimension 50, but is slower than classical alternative SVP algorithms in these dimensions.

Bibtex: @article{NgVi08, title={Sieve Algorithms for the Shortest Vector Problem are Practical}, author={P. Q. Nguyen and T. Vidick}, journal={J. of Mathematical Cryptology}, volume=2, number=2, year=2008 }

Testing set proportionality and the Ádám isomorphism of circulant graphs

In Journal of Discrete Algorithms.

top of the page

Authors: Don Coppersmith and Nick Howgrave-Graham and Phong Q. Nguyen and Igor E. Shparlinski

Abstract: Given two k element subsets in Z/nZ, we give a quasi-linear algorithm to either find λ in (Z/nZ)* such that S=λT or prove that no such λ exists. This question is closely related to isomorphism testing of circulant graphs and has recently been studied in the literature. Keywords: Circulant graphs; Graph isomorphism; Ádám conjecture

The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces

In *Design, Codes and Cryptography*, Vol 30, Number 2, Pages 201-217 (2003). ( .gz version)

top of the page

Authors: Phong Q. Nguyen and Igor E. Shparlinski

Abstract: Nguyen and Shparlinski have recently presented a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in \log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. The number of required bits is about \log^{1/2} q, but can be decreased to \log \log q with a running time q^{O(1/\log \log q)} subexponential in \log q, and even further to 2 in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who introduced the topic. Here, we obtain similar results for the elliptic curve variant of DSA (ECDSA).

The Insecurity of the Digital Signature Algorithm with Partially Known Nonces

In *J. of Cryptology*, Vol. 15, Number 3, Pages 151-176, 2002 ( .gz version)

top of the page

Authors: Phong Q. Nguyen and Igor E. Shparlinski

Journal of Cryptology, Volume 15 (2002), pp 151--176.

Abstract: We present a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in \log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. For most significant or least significant bits, the number of required bits is about \log^{1/2} q, but can be decreased to \log \log q with a running time q^{O(1/\log \log q)} subexponential in \log q, and even further to 2 in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. For arbitrary consecutive bits, the attack requires twice as many bits. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who recently introduced that topic. Our attack is based on a connection with the {\em hidden number problem} (HNP) introduced at Crypto~'96 by Boneh and Venkatesan in order to study the bit-security of the Diffie--Hellman key exchange. The HNP consists, given a prime number q, of recovering a number \alpha \in \F_q such that for many known random t \in \F_q a certain approximation of of t \alpha is known. To handle the DSA case, we extend Boneh and Venkatesan's results on the HNP to the case where t has not necessarily perfectly uniform distribution, and establish uniformity statements on the DSA signatures, using exponential sum techniques. The efficiency of our attack has been validated experimentally, and illustrates once again the fact that one should be very cautious with the pseudo-random generation of the nonce within DSA.

International Conference and Workshop Papers

Extended abstract in pdf

top of the page

Authors: Guilhem Castagnos and Antoine Joux and Fabien Laguillaumie and Phong Q. Nguyen

Proceedings of ASIACRYPT '09
M. Matsui (Ed.)
vol. ???? of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: We present a new algorithm based on binary quadratic forms to factor integers of the form $N=pq^2$. Its heuristic running time is exponential in the general case, but becomes polynomial when special (arithmetic) hints are available, which is exactly the case for the so-called NICE family of public-key cryptosystems based on quadratic fields introduced in the late 90s. Such cryptosystems come in two flavours, depending on whether the quadratic field is imaginary or real. Our factoring algorithm yields a general key-recovery polynomial-time attack on NICE, which works for both versions: Castagnos and Laguillaumie recently obtained a total break of imaginary-NICE, but their attack could not apply to real-NICE. Our algorithm is rather different from classical factoring algorithms: it combines Lagrange's reduction of quadratic forms with a provable variant of Coppersmith's lattice-based root finding algorithm for homogeneous polynomials. It is very efficient given either of the following arithmetic hints: the public key of imaginary-NICE, which provides an alternative to the CL attack; or the knowledge that the regulator of the quadratic field $\mathbb{Q}(\sqrt{p})$ is unusually small, just like in real-NICE.

Bibtex: @inproceedings{CJLN09, AUTHOR = {Guilhem Castagnos and Antoine Joux and Fabien Laguillaumie and Phong Q. Nguyen}, TITLE = {Factoring $pq^2$ with Quadratic Forms: Nice Cryptanalyses}, booktitle= {Advances in Cryptology -- Proc. Asiacrypt '09}, publisher= {Springer}, series = {Lecture Notes in Computer Science}, year = 2009 }

Extended abstract in pdf

top of the page

Authors: Nicolas Gama and Phong Q. Nguyen

Proceedings of STOC '08
(May 17 - 20)
C. Dwork (Ed.)
ACM.
Pages ???--???.

Abstract: The celebrated Lenstra-Lenstra-Lovász lattice basis reduction algorithm (LLL) can naturally be viewed as an algorithmic version of Hermite's inequality on Hermite's constant. We present a polynomial-time blockwise reduction algorithm based on duality which can similarly be viewed as an algorithmic version of Mordell's inequality on Hermite's constant. This achieves a better and more natural approximation factor for the shortest vector problem than Schnorr's algorithm and its transference variant by Gama, Howgrave-Graham, Koy and Nguyen. Furthermore, we show that this approximation factor is essentially tight in the worst case.

Bibtex: @inproceedings{GaNg08b, author = {N. Gama and P. Q. Nguyen}, title = {Finding Short Lattice Vectors within {M}ordell's Inequality}, booktitle = {STOC '08 -- Proc. 40th ACM Symposium on the Theory of Computing}, year = {2008}, publisher = {ACM} }

Extended abstract in pdf

top of the page

Authors: Nicolas Gama and Phong Q. Nguyen

Proceedings of EUROCRYPT '08
(Apr 13 - 17)
N. Smart (Ed.)
vol. ???? of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: Despite their popularity, lattice reduction algorithms remain mysterious cryptanalytical tools. Though it has been widely reported that they behave better than their proved worst-case theoretical bounds, no precise assessment has ever been given. Such an assessment would be very helpful to predict the behaviour of lattice-based attacks, as well as to select keysizes for lattice-based cryptosystems. The goal of this paper is to provide such an assessment, based on extensive experiments performed with the NTL library. The experiments suggest several conjectures on the worst case and the actual behaviour of lattice reduction algorithms. We believe the assessment might also help to design new reduction algorithms overcoming the limitations of current algorithms.

Bibtex: @inproceedings{GaNg08, AUTHOR = {Nicolas Gama and Phong Q. Nguyen}, TITLE = {Predicting Lattice Reduction}, booktitle= {Advances in Cryptology -- Proc. Eurocrypt '08}, publisher= {Springer}, series = {Lecture Notes in Computer Science}, year = 2008 }

Extended abstract in pdf

top of the page

Authors: Pierre-Alain Fouque and Gaëtan Leurent and Phong Q. Nguyen

Proceedings of CRYPTO '07
(Aug 19 - 23)
A. Menezes (Ed.)
vol. ???? of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: At Crypto '06, Bellare presented new security proofs for HMAC and NMAC, under the assumption that the underlying compression function is a pseudo-random function family. Conversely, at Asiacrypt '06, Contini and Yin used collision techniques to obtain forgery and partial key-recovery attacks on HMAC and NMAC instantiated with MD4, MD5, SHA0 and reduced SHA1. In this paper, we present the first full key-recovery attacks on NMAC and HMAC instantiated with a real-life hash function, namely MD4. Our main result is an attack on HMAC/NMAC-MD4 which recovers the full MAC secret key after roughly $2^{88}$ MAC queries and $2^{95}$ MD4 computations. We also extend the partial key-recovery Contini-Yin attack on NMAC-MD5 (in the related-key setting) to a full key-recovery attack. The attacks are based on generalizations of collision attacks to recover a secret IV, using new differential paths for MD4.

Bibtex: @inproceedings{FLN07, author = {Pierre-Alain Fouque and Ga{\"e}tan Leurent and Phong Q. Nguyen}, title = {Full Key-Recovery Attacks on {HMAC/NMAC-MD4} and {NMAC-MD5}}, booktitle = {Proc. CRYPTO '07}, year = {2007}, pages = {13-30}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {4622} }

Extended abstract in pdf ( .gz version).

top of the page

Authors: Nicolas Gama and Nick Howgrave-Graham and Henrik Koy and Phong Q. Nguyen

Proceedings of CRYPTO '06
(Aug 20 - 24)
C. Dwork (Ed.)
vol. 4117 of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: Lattice reduction is a hard problem of interest to both public-key cryptography and cryptanalysis. Despite its importance, extremely few algorithms are known. The best algorithm known in high dimension is due to Schnorr, proposed in 1987 as a block generalization of the famous LLL algorithm. This paper deals with Schnorr's algorithm and potential improvements. We prove that Schnorr's algorithm outputs better bases than what was previously known: namely, we decrease all former bounds on Schnorr's approximation factors to their (ln 2)-th power. On the other hand, we also show that the output quality may have intrinsic limitations, even if an improved reduction strategy was used for each block, thereby strengthening recent results by Ajtai. This is done by making a connection between Schnorr's algorithm and a mathematical constant introduced by Rankin more than 50 years ago as a generalization of Hermite's constant. Rankin's constant leads us to introduce the so-called smallest volume problem, a new lattice problem which generalizes the shortest vector problem, and which has applications to blockwise lattice reduction generalizing LLL and Schnorr's algorithm, possibly improving their output quality. Schnorr's algorithm is actually based on an approximation algorithm for the smallest volume problem in low dimension. We obtain a slight improvement over Schnorr's algorithm by presenting a cheaper approximation algorithm for the smallest volume problem, which we call transference reduction.

Bibtex: @inproceedings{GHKN06, author = {Nicolas Gama and Nick Howgrave-Graham and Henrik Koy and Phong Q. Nguyen}, title = {Rankin's Constant and Blockwise Lattice Reduction}, pages = {112-130}, booktitle = "Advances in Cryptology -- Proceedings of CRYPTO '06", publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = "4117", year = 2006 }

Extended abstract in pdf ( .gz version).
Full Version in pdf to appear in the J. Cryptology (2009), which incorporates this.	top of the page

Authors: Phong Q. Nguyen and Oded Regev

Proceedings of EUROCRYPT '06 -- Best Paper Award
(May 28-June 1)
S. Vaudenay (Ed.)
vol. 4004 of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: Lattice-based signature schemes following the Goldreich-Goldwasser-Halevi (GGH) design have the unusual property that each signature leaks information on the signer's secret key, but this does not necessarily imply that such schemes are insecure. At Eurocrypt '03, Szydlo proposed a potential attack by showing that the leakage reduces the key-recovery problem to that of distinguishing integral quadratic forms. He proposed a heuristic method to solve the latter problem, but it was unclear whether his method could attack real-life parameters of GGH and NTRUsign. Here, we propose an alternative method to attack signature schemes a la GGH, by studying the following learning problem: given many random points uniformly distributed over an unknown n-dimensional parallelepiped, recover the parallelepiped or an approximation thereof. We transform this problem into a multivariate optimization problem that can be solved by a gradient descent. Our approach is very effective in practice: we present the first succesful key-recovery experiments on NTRUsign-251 without perturbation, as proposed in half of the parameter choices in NTRU standards under consideration by IEEE P1363.1. Experimentally, 90,000 signatures are sufficient to recover the NTRUsign-251 secret key. We are also able to recover the secret key in the signature analogue of all the GGH encryption challenges, using a number of signatures which is roughly quadratic in the lattice dimension.

Bibtex: @article{NgRe08, title={Learning a Parallelepiped: Cryptanalysis of {GGH} and {NTRU} Signatures}, author={P. Q. Nguyen and O. Regev}, journal={J. of Cryptology}, year=2008, note={To appear} } and @inproceedings{NgRe06, author = {P. Q. Nguyen and O. Regev}, title = "{Learning a Parallelepiped: Cryptanalysis of {GGH} and {NTRU} Signatures}", pages = {215--233}, booktitle= "Advances in Cryptology -- Proceedings of EUROCRYPT '06", publisher= {Springer}, volume = "4004", series = {LNCS}, year = 2006, }

Extended abstract in pdf ( .gz version).

top of the page

Authors: Nicolas Gama and Nick Howgrave-Graham and Phong Q. Nguyen

Proceedings of EUROCRYPT '06
(May 28-June 1)
S. Vaudenay (Ed.)
vol. 4004 of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: NTRU is a very efficient public-key cryptosystem based on polynomial arithmetic. Its security is related to the hardness of lattice problems in a very special class of lattices. This article is motivated by an interesting peculiar property of NTRU lattices. Namely, we show that NTRU lattices are proportional to the so-called symplectic lattices. This suggests to try to adapt the classical reduction theory to symplectic lattices, from both a mathematical and an algorithmic point of view. As a first step, we show that orthogonalization techniques (Cholesky, Gram-Schmidt, QR factorization, etc.) which are at the heart of all reduction algorithms known, are all compatible with symplecticity, and that they can be significantly sped up for symplectic matrices. Surprisingly, by doing so, we also discover a new integer Gram-Schmidt algorithm, which is faster than the usual algorithm for all matrices. Finally, we study symplectic variants of the celebrated LLL reduction algorithm, and obtain interesting speed ups.

Extended abstract in pdf ( .gz version).

top of the page

Authors: Phong Q. Nguyen and Jacques Stern

Proceedings of Asiacrypt '05
(Dec 4-9)
B. Roy (Ed.)
vol. of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: Cryptosystems based on the knapsack problem were among the first public-key systems to be invented. Their high encryption/decryption rate attracted considerable interest until it was noticed that the underlying knapsacks often had a low density, which made them vulnerable to lattice attacks, both in theory and practice. To prevent low-density attacks, several designers found a subtle way to increase the density beyond the critical density by decreasing the weight of the knapsack, and possibly allowing non-binary coefficients. This approach is actually a bit misleading: we show that low-weight knapsacks do not prevent efficient reductions to lattice problems like the shortest vector problem, they even make reductions more likely. To measure the resistance of low-weight knapsacks, we introduce the novel notion of pseudo-density, and we apply the new notion to the Okamoto-Tanaka-Uchiyama (OTU) cryptosystem from Crypto '00. We do not claim to break OTU and we actually believe that this system may be secure with an appropriate choice of the parameters. However, our research indicates that, in its current form, OTU cannot be supported by an argument based on density. Our results also explain why Schnorr and H\"orner were able to solve at Eurocrypt '95 certain high-density knapsacks related to the Chor-Rivest cryptosystem, using lattice reduction.

Impossible Fault Analysis of RC4 and Differential Fault Analysis of RC4

Extended Abstract in postscript ( .gz version and pdf version)

top of the page

Authors: Eli Biham Louis Granboulan and Phong Q. Nguyen

Proceedings of Fast Software Encryption '05
(Feb 21-23, 2005, Paris, France)
H. Handschuh and H. Gilbert (Eds.)
vol. ???? of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: In this paper we introduce the notion of impossible fault analysis, and present an impossible fault analysis of RC4, whose complexity 2^21 is smaller than the previously best known attack of Hoch and Shamir (2^26), along with an even faster fault analysis of RC4, based on different ideas, with complexity smaller than 2^16.

Floating-Point LLL Revisited

Extended Abstract in postscript ( .gz version and pdf version)
Full version in pdf, to appear in SIAM J. of Computing.	top of the page

Authors: Phong Q. Nguyen and Damien Stehlé

Proceedings of Eurocrypt '05
(May 22-26, 2005, Aarhus, Denmark)
R. Cramer (Ed.)
vol. ???? of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: The Lenstra-Lenstra-Lovasz lattice basis reduction algorithm (LLL or L^3) is a very popular tool in public-key cryptanalysis and in many other fields. Given an integer d-dimensional lattice basis with n-dimensional vectors of norm less than B, L^3 outputs a so-called L^3-reduced basis in polynomial time $O(d^5 n \log^3 B)$, using arithmetic operations on integers of bit-length $O(d \log B)$. This worst-case complexity is problematic for lattices arising in cryptanalysis where $d$ or/and $\log B$ are often large. As a result, the original L^3 is almost never used in practice. Instead, one applies floating-point variants of L^3, where the long-integer arithmetic required by Gram-Schmidt orthogonalisation (central in L^3) is replaced by floating-point arithmetic. Unfortunately, this is known to be unstable in the worst-case: the usual floating-point L^3 is not even guaranteed to terminate, and the output basis may not be L^3-reduced at all. In this article, we introduce the L^2 algorithm, a new and natural floating-point variant of L^3 which provably outputs L^3-reduced bases in polynomial time $O(d^4 n (d+\log B) \log B)$. This is the first L^3 algorithm whose running time (without fast integer arithmetic) provably grows only quadratically with respect to $\log B$, like the well-known Euclidean and Gaussian algorithms, which it generalizes.

Low-Dimensional Lattice Basis Reduction Revisited

Extended Abstract published at ANTS ( .gz version)	top of the page
Full Version to appear in ACM Transactions on Algorithms (2009).

Authors: Phong Q. Nguyen and Damien Stehlé

Algorithmic Number Theory -- Proceedings of ANTS-VI
(June 13--18, 2004, Burlington, U.S.A.)
D. Buell (Ed.)
vol. ???? of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: Most of the interesting algorithmic problems in the geometry of numbers are NP-hard as the lattice dimension increases. This article deals with the low-dimensional case. We study a greedy lattice basis reduction algorithm for the Euclidean norm, which is arguably the most natural lattice basis reduction algorithm, because it is a straightforward generalization of the well-known two-dimensional Gaussian algorithm. Our results are two-fold. From a mathematical point of view, we show that up to dimension four, the output of the greedy algorithm is optimal: the output basis reaches all the successive minima of the lattice. However, as soon as the lattice dimension is strictly higher than four, the output basis may not even reach the first minimum. More importantly, from a computational point of view, we show that up to dimension four, the bit-complexity of the greedy algorithm is quadratic without fast integer arithmetic: this allows to compute various lattice problems (e.g. computing a Minkowski-reduced basis and a closest vector) in quadratic time, without fast integer arithmetic, up to dimension four, while all other algorithms known for such problems have a bit-complexity which is at least cubic. This was already proved by Semaev up to dimension three using rather technical means, but it was previously unknown whether or not the algorithm was still polynomial in dimension four. Our analysis, based on geometric properties of low-dimensional lattices and in particular Voronoï cells, arguably simplifies Semaev's analysis in dimensions two and three, unifies the cases of dimensions two, three and four, but breaks down in dimension five.

Bibtex: @article{NgSt09, title={Low-Dimensional Lattice Basis Reduction Revisited}, author={P. Q. Nguyen and D. Stehl\'e}, journal={ACM Transactions on Algorithms}, year=2009, note={To appear} } and @inproceedings{NgSt04, AUTHOR = {Phong Q. Nguyen and Damien Stehl{\'e}}, TITLE = {Low-dimensional lattice basis reduction revisited}, PAGES = {338--357}, booktitle = "Proceedings of the 6th International Algorithmic Number Theory Symposium, (ANTS-VI)", publisher = "Springer", series = "LNCS", volume = {3076}, YEAR = {2004} }

Can We Trust Cryptographic Software? Cryptographic Flaws in GNU Privacy Guard v1.2.3

Extended abstract ( .gz version).

top of the page

Author: Phong Q. Nguyen

Proceedings of Eurocrypt '04
(May 2-6)
C. Cachin (Ed.)
vol. ???? of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: More and more software use cryptography. But how can one know if what is implemented is good cryptography? For proprietary software, one cannot say much unless one proceeds to reverse-engineering, and history tends to show that bad cryptography is much more frequent than good cryptography there. Open source software thus sounds like a good solution, but the fact that a source code can be read does not imply that it is actually read, especially by cryptography experts. In this paper, we illustrate this point by examining the case of a basic Internet application of cryptography: secure email. We analyze parts of the source code of the latest version of GNU Privacy Guard (GnuPG or GPG), a free open source alternative to the famous PGP software, compliant with the OpenPGP standard, and included in most GNU/Linux distributions such as Debian, MandrakeSoft, Red Hat and SuSE. We observe several cryptographic flaws in GPG v1.2.3. The most serious flaw has been present in GPG for almost four years: we show that as soon as one (GPG-generated) ElGamal signature of an arbitrary message is released, one can recover the signer's private key in less than a second on a PC. As a consequence, ElGamal signatures and the so-called ElGamal sign+encrypt keys have recently been removed from GPG. Fortunately, ElGamal was not GPG's default option for signing keys.

The Impact of Decryption Failures on the Security of NTRU Encryption

Extended abstract ( .gz version).

top of the page

Authors: Nick Howgrave-Graham, Phong Q. Nguyen, David Pointcheval, John Proos, Joseph H. Silverman, Ari Singer and William Whyte

Proceedings of Crypto '03
(Aug 17-21)
D. Boneh (Ed.)
vol. 2729 of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: NTRUEncrypt is unusual among public-key cryptosystems in that, with standard parameters, validly generated ciphertexts can fail to decrypt. This affects the provable security properties of a cryptosystem, as it limits the ability to build a simulator in the random oracle model without knowledge of the private key. We demonstrate attacks which use decryption failures to recover the private key. Such attacks work for all standard parameter sets, and one of them applies to any padding. The appropriate countermeasure is to change the parameter sets and possibly the decryption process so that decryption failures are vanishingly unlikely, and to adopt a padding scheme that prevents an attacker from directly controlling any part of the input to the encryption primitive. We outline one such candidate padding scheme.

The Hardness of Hensel Lifting: The Case of RSA and Discrete Logarithm

Extended abstract ( .gz version).

top of the page

Authors: Dario Catalano and Phong Q. Nguyen and Jacques Stern

Proceedings of Asiacrypt '02
(Dec 1-5)
Y. Zheng (Ed.)
vol. of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: At ACM CCS '01, Catalano et al. proposed a mix of the RSA cryptosystem with the Paillier cryptosystem from Eurocrypt '99. The resulting scheme, which we call RSAP, is a probabilistic cryptosystem which is both semantically secure under an appropriate decisional assumption and as efficient as RSA, but without the homomorphic property of the Paillier scheme. Interestingly, Sakurai and Takagi presented at PKC '02 a proof that the one-wayness of RSAP was equivalent to the RSA assumption. However, we notice in this paper that the above proof is not completely correct (it works only in the case when a perfect oracle - i.e. an oracle that always provides correct answers - is given). We fix the proof by presenting a new proof based on low-dimensional lattices. The new proof, inspired by the work of Sakurai and Takagi, is somewhat related to Hensel lifting and the $N$-adic decomposition of integer exponentiation. Roughly speaking, we consider the problem of computing $f(x) \bmod M^\ell$ given $f(x) \bmod M$ and an exponent $\ell>1$. By studying the case $f(x)=x^e$ and $M$ is an RSA-modulus, we deduce that the one-wayness of RSAP is indeed equivalent to the RSA assumption, and we are led to conjecture that the one-wayness of the original Paillier scheme may not be equivalent to the RSA assumption with exponent $N$. By analogy, we also study the discrete logarithm case, namely when $f(x)=g^x$ and $M$ is a prime, and we show that the corresponding problem is curiously equivalent to the discrete logarithm problem in the subgroup spanned by $g$.

Analysis and Improvements of NTRU Encryption Paddings

Extended abstract ( .gz version).

top of the page

Authors: Phong Q. Nguyen and David Pointcheval

Proceedings of Crypto '02
(Aug 18-22)
M. Yung (Ed.)
vol. 2442 of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: NTRU is an efficient patented public-key cryptosystem proposed in 1996 by Hoffstein, Pipher and Silverman. Although no devastating weakness of NTRU has been found, Jaulmes and Joux presented at Crypto '00 a simple chosen-ciphertext attack against NTRU as originally described. This led Hoffstein and Silverman to propose three encryption padding schemes more or less based on previous work by Fujisaki and Okamoto on strengthening encryption schemes. It was claimed that these three padding schemes made NTRU secure against adaptive chosen-ciphertext attacks (IND-CCA) in the random oracle model. In this paper, we analyze and compare the three NTRU schemes obtained. It turns out that the first one is not even semantically secure (IND-CPA). The second and third ones can be proven IND-CCA-secure in the random oracle model, under however rather unusual assumptions. They indeed require a partial-domain one-wayness of the NTRU one-way function which is likely to be a stronger assumption than the one-wayness of the NTRU one-way function. We propose several modifications to achieve IND-CCA-security in the random oracle model under the original NTRU inversion assumption.

On the Insecurity of a Server-Aided RSA Protocol

Extended abstract ( .gz version).

top of the page

Authors: Phong Q. Nguyen and Igor E. Shparlinski

Proceedings of Asiacrypt '01
(Dec 9--13, 2001, Gold Coast, Australia)
C. Boyd (Ed.)
vol. 2248 of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: At Crypto '88, Matsumoto, Kato and Imai proposed a protocol, known as RSA-S1, in which a smart card computes an RSA signature, with the help of an untrusted powerful server. There exist two kinds of attacks against such protocols: passive attacks (where the server does not deviate from the protocol) and active attacks (where the server may return false values). Pfitzmann and Waidner presented at Eurocrypt '92 a passive meet-in-the-middle attack and a few active attacks on RSA-S1. They discussed two simple countermeasures to thwart such attacks: renewing the decomposition of the RSA private exponent, and checking the signature (in which case a small public exponent must be used). We present a new lattice-based provable passive attack on RSA-S1 which recovers the factorization of the RSA modulus when a very small public exponent is used, for many choices of the parameters. The first countermeasure does not prevent this attack because the attack is a one-round attack, that is, only a single execution of the protocol is required. Interestingly, Merkle and Werchner recently provided a security proof of RSA-S1 against one-round passive attacks in some generic model, even for parameters to which our attack provably applies. Thus, our result throws doubt on the real significance of security proofs in the generic model, at least for server-aided RSA protocols. We also present a simple analysis of a multi-round lattice-based passive attack proposed last year by Merkle.

Paillier's Cryptosystem Revisited

Extended abstract ( .gz version).

top of the page

Authors: Dario Catalano and Rosario Gennaro and Nick Howgrave-Graham and Phong Q. Nguyen

Proceedings of the 8th ACM Conference on Computer and Communications Security
(Nov 5-8, 2001, Philadelphia, USA)
Published by the ACM.
Pages ???--???.

Abstract: We re-examine Paillier's cryptosystem, and show that by choosing a particular discrete log base g, and by introducing an alternative decryption procedure, we can extend the scheme to allow an arbitrary exponent e instead of N. The use of low exponents substantially increases the efficiency of the scheme, at the expense of the homomorphic property. The semantic security is now based on a new decisional assumption, namely the hardness of deciding whether an element is a ``small'' e-th residue modulo N^2. We also show how to use Paillier's original cryptosystem to build a trapdoor commitment scheme. This new scheme is information-theoretically private, and computationally binding (this property holds under the assumption that the RSA function with exponent N is hard to invert). A novel property of this new commitment scheme is that most of the work can be done offline before knowing the message one wants to commit to. Once the message is known only two multiplications are required. This is the first trapdoor commitment scheme with this online-offline efficiency property which is also length-preserving.

Cryptanalysis of the RSA Schemes with Short Secret Exponent from Asiacrypt '99

Extended abstract ( .gz version) and Slides ( .gz version).

top of the page

Authors: Glenn Durfee and Phong Q. Nguyen

Proceedings of Asiacrypt '00
(Dec 3--7, 2000, Kyoto, Japan)
T. Okamoto (Ed.)
vol. 1976 of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: At Asiacrypt '99, Sun, Yang and Laih proposed three RSA variants with short secret exponent that resisted all known attacks, including the recent Boneh-Durfee attack from Eurocrypt '99 that improved Wiener's attack on RSA with short secret exponent. The resistance comes from the use of unbalanced primes $p$ and $q$. In this paper, we extend the Boneh-Durfee attack to break two out of the three proposed variants. While the Boneh-Durfee attack was based on Coppersmith's lattice-based technique for finding small roots to bivariate modular polynomial equations, our attack is based on its generalization to trivariate modular polynomial equations. The attack is heuristic but works well in practice, as the Boneh-Durfee attack. In particular, we were able to break in a few minutes the numerical examples proposed by Sun, Yang and Laih. The results illustrate once again the fact that one should be very cautious when using short secret exponent with RSA.

Why Textbook ElGamal and RSA Encryption are Insecure

Extended abstract ( .gz version) and Slides ( .gz version).

top of the page

Authors: Dan Boneh and Antoine Joux and Phong Q. Nguyen

Proceedings of Asiacrypt '00
(Dec 3--7, 2000, Kyoto, Japan)
T. Okamoto (Ed.)
vol. 1976 of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: We present an attack on plain ElGamal and plain RSA encryption. The attack shows that without proper preprocessing of the plaintexts, both ElGamal and RSA encryption are fundamentally insecure. Namely, when one uses these systems to encrypt a (short) secret key of a symmetric cipher it is often possible to recover the secret key from the ciphertext. Our results demonstrate that preprocessing messages prior to encryption is an essential part of both systems.

Lattice Reduction in Cryptology: An Update

Invited survey ( .gz version) and Slides ( .gz version).

top of the page

Authors: Phong Q. Nguyen and Jacques Stern

Algorithmic Number Theory -- Proceedings of ANTS-IV
(July 3--7, 2000, Leiden, Netherlands)
W. Bosma (Ed.)
vol. 1838 of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: Lattices are regular arrangements of points in space, whose study appeared in the 19th century in both number theory and crystallography. The goal of lattice reduction is to find useful representations of lattices. A major breakthrough in that field occurred twenty years ago, with the appearance of Lovasz's reduction algorithm, also known as LLL or L^3. Lattice reduction algorithms have since proved invaluable in many areas of mathematics and computer science, especially in algorithmic number theory and cryptology. In this paper, we survey some applications of lattices to cryptology. We focus on recent developments of lattice reduction both in cryptography and cryptanalysis, which followed seminal works of Ajtai and Coppersmith.

Noisy Polynomial Interpolation and Noisy Chinese Remaindering

Full Version ( .gz version).

top of the page

Authors: Daniel Bleichenbacher and Phong Q. Nguyen

In Advances in Cryptology -- Proceedings of EUROCRYPT '00
(May 14 -- 18, 2000, Bruges, Belgium)
B. Preneel (Ed.)
vol. 1807 of Lecture Notes in Computer Science, Springer-Verlag.
Pages 53--69.

Abstract: The noisy polynomial interpolation problem is a new intractability assumption which was introduced last year in oblivious polynomial evaluation. It also appeared independently in password identification schemes, due to its connection with secret sharing schemes based on Lagrange's polynomial interpolation. This paper presents new algorithms to solve the noisy polynomial interpolation problem. In particular, we prove a reduction from noisy polynomial interpolation to the lattice shortest vector problem, when the parameters satisfy a certain condition that we make explicit. Standard lattice reduction techniques appear to solve most of the practical instances of the problem. It follows that noisy polynomial interpolation is much easier than expected. We therefore suggest simple modifications to several cryptographic schemes recently proposed, in order to change the intractability assumption. We also discuss analogous methods for the related noisy Chinese remaindering problem arising from the well-known duality between polynomials and integers.

Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto '97

Extended Abstract ( .gz version) and Slides ( .gz version).

top of the page

Author: Phong Nguyen

In Advances in Cryptology -- Proceedings of CRYPTO '99
(August 15 -- 19, 1999, Santa Barbara, California)
M. Wiener (Ed.)
vol. 1666 of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: Recent results of Ajtai on the hardness of lattice problems have inspired several cryptographic protocols. At Crypto '97, Goldreich, Goldwasser and Halevi proposed a public-key cryptosystem based on the closest vector problem in a lattice, which is known to be NP-hard. We show that there is a flaw in the design of the scheme which has two implications: the cryptosystem is not semantically secure (each ciphertext leaks a non-negligible fraction of the plaintext), and the problem of decrypting ciphertexts can be reduced to a special closest vector problem which is much easier than the general problem. As an application, we solved four out of the five numerical challenges proposed on the Internet by the authors of the cryptosystem. At least two of those four challenges were conjectured to be intractable. We discuss ways to prevent the flaw, but conclude that, even modified, the scheme cannot provide sufficient security without being impractical.

The Hardness of the Hidden Subset Sum Problem and its Cryptographic Implications

Extended Abstract ( .gz version) and Slides ( .gz version).

top of the page

Authors: Phong Nguyen and Jacques Stern

In Advances in Cryptology -- Proceedings of CRYPTO '99
(August 15 -- 19, 1999, Santa Barbara, California)
M. Wiener (Ed.)
vol. 1666 of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: At Eurocrypt'98, Boyko, Peinado and Venkatesan presented simple and very fast methods for generating randomly distributed pairs of the form $(x,g^x \mod p)$ using precomputation. The security of these methods relied on the potential hardness of a new problem, the so-called hidden subset sum problem. Surprisingly, apart from exhaustive search, no algorithm to solve this problem was known. In this paper, we exhibit a security criterion for the hidden subset sum problem, and discuss its implications on the practicability of the precomputation schemes. Our results are twofold. On the one hand, we present an efficient lattice-based attack which is expected to succeed if and only if the parameters satisfy a particular condition that we make explicit. Experiments have validated the theoretical analysis, and show the limitations of the precomputation methods. For instance, any realistic smart-card implementation of Schnorr's identification scheme using these precomputations methods is either vulnerable to the attack, or less efficient than with traditional precomputation methods. On the other hand, we show that, when another condition is satisfied, the pseudo-random generator based on the hidden subset sum problem is strong in some precise sense which includes attacks {\em via} lattice reduction. Namely, using the discrete Fourier transform, we prove that the distribution of the generator's output is indistinguishable from the uniform distribution. The two conditions complement each other quite well, and therefore form a convincing picture of the security level.

The Effectiveness of Lattice Attacks Against Low-Exponent RSA

Extended abstract: plain ps or gz version .

top of the page

Authors: Christophe Coupé and Phong Nguyen and Jacques Stern

Second International Workshop on Practice and Theory in Public Key Cryptography, PKC'99
(March 1--3, 1999, Kamakura, Kanagawa, Japan)
H. Imai and Y. Zheng (Eds.)
Volume 1560 of Lecture Notes in Computer Science, Springer-Verlag

Abstract:At Eurocrypt '96, Coppersmith presented a novel application of lattice reduction to find small roots of a univariate modular polynomial equation. This led to rigorous polynomial attacks against RSA with low public exponent, in some particular settings such as encryption of stereotyped messages, random padding, or Hastad-like broadcast applications. Theoretically, these are the most powerful known attacks against low-exponent RSA. However, the practical behaviour of Coppersmith's method was unclear. On the one hand, the method requires reductions of high-dimensional lattices with huge entries, which could be out of reach. On the other hand, it is well-known that lattice reduction algorithms output better results than theoretically expected, which might allow better bounds than those given by Coppersmith's theorems. In this paper, we present extensive experiments with Coppersmith's method, and discuss various trade-offs together with practical improvements. Overall, practice meets theory. The warning is clear: one should be very cautious when using the low-exponent RSA encryption scheme, or one should use larger exponents.

Cryptanalysis of a Fast Public Key Cryptosystem Presented at SAC '97

Extended Abstract ( plain postscript or gzipped version ) and Slides

top of the page

Authors: Phong Nguyen and Jacques Stern

Selected Areas in Cryptography '98, 5th Annual International Workshop
(August 17--18, 1998, Kingston, Ontario, Canada)
S. Tavares (Ed.)
Volume 1556 of Lecture Notes in Computer Science, Springer-Verlag

Abstract: At SAC '97, Itoh, Okamoto and Mambo presented a fast public key cryptosystem, and claimed that its security was high, although it had some resemblances with the former knapsack cryptosystems. In this paper, we show how to recover the private key from a fraction of the public key in less than 10 minutes for the suggested choice of parameters.

The Béguin-Quisquater Server-Aided RSA Protocol from Crypto '95 is not Secure

Extended Abstract ( plain postscript or gzipped version) and Slides (plain postscript or gzipped version)

top of the page

Authors: Phong Nguyen and Jacques Stern

Advances in Cryptology -- Proceedings of ASIACRYPT '98
(October 18--22, 1998, Beijing, P.R. China)
K. Ohta and D. Pei (Eds.)
vol. 1514 of Lecture Notes in Computer Science, Springer-Verlag
Pages 372--379.

Abstract: At Crypto '95, Béguin and Quisquater proposed an efficient server-aided RSA protocol which was resistant against all known passive and active attacks. We present a very effective lattice-based passive attack against this protocol. An implementation is able to recover the secret factorization of an RSA-512 or RSA-768 key in less than 5 minutes, once the card has produced about 50 signatures.

Cryptanalysis of the Ajtai-Dwork Cryptosystem

Extended Abstract ( .gz version) and Slides ( .gz version)

top of the page

Authors: Phong Nguyen and Jacques Stern

In Advances in Cryptology -- Proceedings of CRYPTO '98
(August 23 -- 27, 1998, Santa Barbara, California)
H. Krawczyk (Ed.)
vol. 1462 of Lecture Notes in Computer Science, Springer-Verlag.
Pages 223--242.

Abstract: Recently, Ajtai and Dwork proposed a cryptosystem provably secure if a particular lattice problem is difficult in the worst-case. We present a heuristic attack which shows that in order to be secure, implementations of the Ajtai-Dwork cryptosystem would require very large keys. We also show that there is a converse to the Ajtai-Dwork security result, which implies, from a recent result of Goldreich and Goldwasser, that breaking the Ajtai-Dwork cryptosystem is not NP-hard, assuming the polynomial-time hierarchy does not collapse.

A Montgomery-like Square Root for the Number Field Sieve

Extended Abstract ( .gz version) and Slides ( .gz version)

top of the page

Author: Phong Nguyen

Algorithmic Number Theory -- Proceedings of ANTS-III
(June 21 -- 25, 1998, Portland, Oregon, USA)
J. Buhler (Ed.)
vol. 1423 of Lecture Notes in Computer Science, Springer-Verlag.
Pages ???--???.

Abstract: The Number Field Sieve (NFS) is the asymptotically fastest factoring algorithm known. In the last stage of the NFS, one has to compute a square root of a huge algebraic number given as a product of hundreds of thousands of small ones. This problem was not satisfactorily solved until the appearance of an algorithm by Peter Montgomery. We present a variant of the algorithm and discuss its complexity.

Merkle-Hellman Revisited: a Cryptanalysis of the Qu-Vanstone Cryptosystem Based on Group Factorizations

Extended Abstract ( .gz version)

top of the page

Authors: Phong Nguyen and Jacques Stern

In Advances in Cryptology -- Proceedings of CRYPTO '97
(August 17 -- 21, 1998, Santa Barbara, California, USA)
B. Kaliskik (Ed.)
vol. 1294 of Lecture Notes in Computer Science, Springer-Verlag.
Pages 198--212.

Abstract: Cryptosystems based on the knapsack problem were among the first public key systems to be invented and for a while were considered quite promising. Few knapsack-like cryptosystems have withstood cryptanalysis, among which the Chor-Rivest scheme and the Qu-Vanstone scheme. The Qu-Vanstone scheme is a public key scheme based on group factorizations in the additive group of integers modulo n that generalizes Merkle-Hellman cryptosystems. In this paper, we present a novel use of lattice reduction, which is of independent interest, exploiting in a systematic manner the notion of an orthogonal lattice. Using the new technique, we successfully attack the Qu-Vanstone cryptosystem.

Technical Reports

New Trends in Cryptology

.pdf version

top of the page

Editor: Phong Q. Nguyen

Abstract: This is the document identifying the problems faced by cryptographers and users of cryptology, either currently or in the short or medium term future. It was produced by the European project STORK: -- Strategic Roadmap for Crypto -- IST-2002-38273.

A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications

ECCC-TR98-010

top of the page

Authors: Phong Nguyen and Jacques Stern

Abstract: Recently, Ajtai discovered a fascinating connection between the worst-case complexity and the average-case complexity of some well-known lattice problems. Later, Ajtai and Dwork proposed a cryptosystem inspired by Ajtai's work, provably secure if a particular lattice problem is difficult. We show that there is a converse to the Ajtai-Dwork security result, by reducing the question of distinguishing encryptions of one from encryptions of zero to approximating some lattice problems. This is especially interesting in view of a result of Goldreich and Goldwasser, which seems to rule out any form of NP-hardness for such approximation problems.