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.

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.