__
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

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

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