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 major flaw in the design of the scheme which has two implications: any ciphertext leaks information on 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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Ajtai. Generating hard instances of lattice problems. In Proc. 28th ACM STOC, pages 99–108, 1996. Available at [10] as TR 96-007.
M. Ajtai. The shortest vector problem in L2 is NP-hard for randomized reductions. In Proc. 30th ACM STOC, 1998. Available at [10] as TR 97-047.
M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In Proc. 29th ACM STOC, pages 284–293, 1997. Available at [10] as TR 96-065.
L. Babai. On Lovász lattice reduction and the nearest lattice point problem. Combinatorica, 6:1–13, 1986.
M. Bellare and D. Micciancio. A new paradigm for collision-free hashing: Incrementality at reduced cost. In Proc. of Eurocrypt’ 97, volume 1233 of LNCS. Springer-Verlag, 1997.
J. Blomer and J.-P. Seifert. On the complexity of computing short linearly independent vectors and short bases in a lattice. In Proc. 31th ACM STOC, 1999. To appear.
J.-Y. Cai and A. P. Nerurkar. An improved worst-case to average-case connection for lattice problems. In Proc. 38th IEEE FOCS, pages 468–477, 1997.
H. Cohen. A course in computational algebraic number theory. Springer, 1995. 2nd Edition.
I. Dinur, G. Kindler, and S. Safra. Approximating-CVP to within almostpolynomial factors is NP-hard. In Proc. 39th IEEE FOCS, pages 99–109, 1998. Available at [10] as TR 98-048.
ECCC. http://www.eccc.uni-trier.de/eccc/. The Electronic Colloquium on Computational Complexity.
P. van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical report, Mathematische Instituut, University of Amsterdam, 1981. Report 81-04.
O. Goldreich. Private communication, Jan. 99.
O. Goldreich and S. Goldwasser. On the limits of non-approximability of lattice problems. In Proc. 30th ACM STOC, 1998. Available at [10] as TR97-031.
O. Goldreich, S. Goldwasser, and S. Halevi. Challenges for the GGH-Cryptosystem. Available at http://theory.lcs.mit.edu/~shaih/challenge.html.
O. Goldreich, S. Goldwasser, and S. Halevi. Collision-free hashing from lattice problems. Available at [10] as TR 96-056., 1996.
O. Goldreich, S. Goldwasser, and S. Halevi. Public-key cryptosystems from lattice reduction problems. In Proc. of Crypto’97, volume 1294 of LNCS, pages 112–131. Springer-Verlag, 1997. Available at [10] as TR96-056.
O. Goldreich, D. Micciancio, S. Safra, and J.-P. Seifert. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Available at [10] as TR 99-002.
The LIDIA Group. LiDIA-a library for computational number theory. Can be obtained at http://www-jb.cs.uni-sb.de/LiDIA/linkhtml/lidia/lidia.html.
R. Impagliazzo and M. Naor. Efficient cryptographic schemes provably as secure as subset sum. Journal of Cryptology, 9(4):199–216, 1996.
A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261:515–534, 1982.
R.J. McEliece. A public-key cryptosystem based on algebraic number theory. Technical report, Jet Propulsion Laboratory, 1978. DSN Progress Report 42-44.
D. Micciancio. The shortest vector problem is NP-hard to approximate within some constant. In Proc. 39th IEEE FOCS, 1998. Available at [10] as TR98-016.
P. Nguyen and J. Stern. Cryptanalysis of the Ajtai-Dwork Cryptosystem. In Proc. of Crypto’ 98, volume 1462 of LNCS, pages 223–242. Springer-Verlag, 1998.
A. M. Odlyzko. The rise and fall of knapsack cryptosystems. In Cryptology and Computational Number Theory, volume 42 of Proceedings of Symposia in Applied Mathematics, pages 75–88. A.M.S., 1990.
C.-P. Schnorr. A hierarchy of polynomial lattice basis reduction algorithms. Theoretical Computer Science, 53:201–224, 1987.
C-P. Schnorr, M. Fischlin, H. Koy, and A. May. Lattice attacks on GGHCryptosystem. Rump session of Crypto’ 97.
C.P. Schnorr and H.H. Horner. Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In Proc. of Eurocrypt’95, volume 921 of LNCS, pages 1–12. Springer-Verlag, 1995.
V. Shoup. Number Theory C++ Library (NTL) version 3.6. Can be obtained at http://www.shoup.net/ntl/.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nguyen, P. (1999). Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97. In: Wiener, M. (eds) Advances in Cryptology — CRYPTO’ 99. CRYPTO 1999. Lecture Notes in Computer Science, vol 1666. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48405-1_18
Download citation
DOI: https://doi.org/10.1007/3-540-48405-1_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66347-8
Online ISBN: 978-3-540-48405-9
eBook Packages: Springer Book Archive