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.

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.