Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR98-010 | 24th June 1999 00:00

A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implic ations Revision of: TR98-010

RSS-Feed

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.


Paper:

TR98-010 | 22nd January 1998 00:00

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


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.



ISSN 1433-8092 | Imprint