Representing hard lattices with O(n log n) bits

Abstract

We present a variant of the Ajtai-Dwork public-key cryptosystem where the size of the public-key is only O(n log n) bits and the encrypted text/clear text ratio is also O(n log n). This is true with the assumption that all of the participants in the cryptosystem share O(n 2 log n) random bits which has to be picked only once and the users of the cryptosystem get them e.g. together with the software implementing the protocol. The public key is a random lattice with an n c-unique nonzero shortest vector, where the constant c > 1/2 can be picked arbitrarily close to 5, and we pick the lattice according to a distribution described in the paper. We do not prove a worst-case average-case equivalence but the security of the system follows from the hardness of a randomized diophantine approximation problem related to a well-known theorem of Dirichlet. Copyright 2005 ACM.