Chicago Journal of Theoretical Computer Science

Volume 2008

Article 2

Published by Dept. CS U. Chicago. Copyright 2008 CJTCS and the author.

Representing Hard Lattices with O(nlogn) Bits

Miklos Ajtai, IBM Almaden Research Center
May 12, 2008
(Submitted July 27, 2007)

We present a variant of the Ajtai-Dwork public-key cryptosystem where the size of the public-key is only O(nlog n) bits and the encrypted text/clear text ratio is also O(nlogn). This is true with the assumption that all of the participants in the cryptosystem share O(n*n*log n) random bits which have 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 1/2, 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 an average-case diophantine approximation problem related to a well-known theorem of Dirichlet.

DOI: 10.4086/cjtcs.2008.002
[] Volume 2008, Article 1
[back] Volume 2008 [back] Published articles
[CJCTS home]