Cryptography and Information Security Group Research
Project: LatticeBased Cryptography 
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 publickey 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 collisionintractable
hashing scheme. This work is described in Record
9609 of the Theory of Cryptography OnLine Library.

In a recent work, O. Goldreich, S. Goldwasser and S. Halevi described constructions
of publickey cryptosystems whose security is also based on the hardness
of certain latticereduction problems.

A preliminary report on this work is available as Record
9606 of the Theory of Cryptography OnLine 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 200400, 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 publickey encryption scheme
which is secure, provided that it is infeasible on worstcase to
find a shortest vector in a lattice having a ``unique shortest vector''
(see AjtaiDwork
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 NonApproximability of Lattice Problems (download Postscript) by
Oded Goldreich and Shafi Goldwasser, presents simple constantround 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 shortestlatticevector
is ``long'' (for SVP). Furthermore, these interactive proof systems are
HonestVerifier Perfect ZeroKnowledge. 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 NPhard. We comment that the Ajtai oneway function and the AjtaiDwork
encryption are based on the conjecture that lattice problems as such are
hard to approximate upto much larger factors.

The security of latticebased 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 NPhard 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 NPhardness of lattice
problems and those required by current latticebased 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.
Back to CIS Home Page