Identifying hard computational problems which are amenable for cryptographic use is a very important task. Although hard computational problems seem to be all around us, only very few of those problems were found to be useful for cryptography. In fact, after two decades of research in cryptography, the vast majority of the public-key cryptosystems still depend on either the hardness of integer factorization or the hardness of extracting discrete logarithms. Moreover, often it has been the case that algorithmic advance in one of these problems was then applied to the other one as well.

To avoid "putting all the cryptographic eggs in one basket", it is important to find ways to use other hard computational problems in cryptographic schemes. A current research direction of ours is centered around the design of cryptosystems which are based on geometric problems (in particular, problems in the Geometry of Numbers). Along this line, we have the following results:

• O. Goldreich, S. Goldwasser and S. Halevi observed that a newly discovered construction by M. Ajtai from IBM can be used to obtain collision-intractable hashing scheme. This work is described in Record 96-09 of the Theory of Cryptography On-Line Library.
• In a recent work, O. Goldreich, S. Goldwasser and S. Halevi described constructions of public-key cryptosystems whose security is also based on the hardness of certain lattice-reduction problems.
• A preliminary report on this work is available as Record 96-06 of the Theory of Cryptography On-Line Library.
• The slides of a talk which describes this construction are available in either postscript format (204 Kbyte), or in pdf format (102 Kbyte).
• A list of challenges for this system, in dimensions 200-400, can be obtained from our Challenge Page.
• S. Tzvetkov has implemented this cryptosystem, and the code is available here.
• 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). Their encryption scheme has a small decryption error, which has been eliminated in a modified scheme proposed by O. Goldreich, S. Goldwasser and S. Halevi. The modified encryption scheme, maintains the security features of the original one.
• On the Limits of Non-Approximability of Lattice Problems (download Postscript) by Oded Goldreich and Shafi Goldwasser, presents simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of sqrt(n), of optimization problems in integer lattices; specifically, the closest vector problem (CVP), and the shortest vector problem (SVP). These interactive proofs are for the ``coNP direction''; that is, we give an interactive protocol showing that a vector is ``far'' from the lattice (for CVP), and an interactive protocol showing that the shortest-lattice-vector is ``long'' (for SVP). Furthermore, these interactive proof systems are Honest-Verifier Perfect Zero-Knowledge. We conclude that approximating CVP (resp., SVP) within a factor of sqrt(n) is in both NP and coAM. Thus, it seems unlikely that approximating these problems to within a sqrt(n) factor is NP-hard. We comment that the Ajtai one-way function and the Ajtai-Dwork encryption are based on the conjecture that lattice problems as such are hard to approximate upto much larger factors.
• The security of lattice-based cryptosystems relies on the hardness of finding approximate solutions to lattice problems. In The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant (download Postscript), Daniele Micciancio proves that the Shortest Vector Problem is NP-hard to approximate to within any constant less than square root of 2. This means that unless P=NP, it is not feasible to find approximate solutions to that problem. We remark that there is still a big gap between the factors for which we can prove the NP-hardness of lattice problems and those required by current lattice-based cryptosystems. Bridging this gap is certainly an extremely challanging but attractive goal, as it would result in a cryptosystem based on the P different from NP assumption (for a discussion about basing cryptography on the P vs. NP question see On the possibility of basing Cryptography on the assumption that P differs from NP (download Postscript) , by O.Goldreich and S.Goldwasser). We are currently working to improve the inapproximability result for SVP to larger approximation factors.