A Pubic Key Cryptosystem with Worst-Case/Average-Case

Cynthia Dwork, IBM Almaden Research Center
Tuesday 10 Dec 1996, 4:15pm, Gates 104


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.