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

- Collision-Free Hashing from Lattice Problems, July 1996. This work extends Ajtai's result as well as provides an exposition of his proof.
- Public-Key Cryptosystems from Lattice Reduction Problems, May 1997. This work was done independently of the work of Ajtai and Dwork. It provides a different construction and relies (but is not reducible) to a random version of the closest vector problem. A list of challenges for this system, in dimensions 200--400, can be obtained from our Challenge Page.
- Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem, May 1997. Here we modify the encryption scheme of Ajtai and Dwork.

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