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.