A Pubic Key Cryptosystem with Worst-Case/Average-Case
Cynthia Dwork, IBM Almaden Research Center
Tuesday 10 Dec 1996, 4:15pm, Gates 104
Abstract
This talk describes a public key cryptosystem whose security is based
on the computational infeasibility of solving the worst-case instance
of the famous "unique shortest vector problem" involving lattices:
"Find the shortest nonzero vector in an n-dimensional lattice L where
the shortest vector v is unique in the sense that any other vector
whose length is at most n^c times the length of v is parallel to v."
Specifically, if a random instance of the cryptosystem can be broken,
then the worst-case unique shortest vector problem has a probabilistic
polynomial time solution.
To our knowledge this is the first public key cryptosystem with the
property that to break a random instance is as hard as to solve the
worst-case instance of the problem on which the system is based.
This is joint work with Miki Ajtai.