Public-key cryptosystem with worst-case/average-case equivalence

Abstract

We present a probabilistic public key cryptosystem which is secure unless the worst case of the following lattice problem can be solved in polynomial time: `Find the shortest nonzero vector in an n dimensional lattice L where the shortest vector υ is unique in the sense that any other vector whose length is at most nc∥υ∥ is parallel to υ.'