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.
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.
Note:
This article deals with the GGH encryption scheme.
The GGH signature scheme was later
broken here.