Using Lattice Problem in Cryptography

Oded Goldreich, Shafi Goldwasser and Shai Halevi

[Three papers dated 1996-97]

A major project of Complexity Theory is to find concrete hard problems which can be used for ``doing Cryptography'' (e.g., constructing encryption schemes, message-authentication codes and digital signatures). As current state of the art in Complexity Theory does not allow to prove that such (cryptographically-useful) problems are hard, one has to rely on unproven and yet plausible assumptions. It is thus important to have as many alternative/unrelated assumption as possible, so that Cryptography can be based on any one of them. So far there are very few alternatives; and so Ajtai's work, which suggests a new domain out of which adequately-hard problems can be found, marks an important day for Cryptography.

In particular, Ajtai constructed a one-way function based on the assumption that Lattice Reduction is hard in the worst-case. Following his lead, Ajtai and Dwork have recently introduced a public-key encryption scheme which is secure, provided that it is infeasible on worst-case to find a shortest vector in a lattice having a ``unique shortest vector'' (see Ajtai-Dwork encryption).

Our own contributions include

Back to homepages of authors: Oded Goldreich, Shafi Goldwasser, Shai Halevi.