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