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

Abstract

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.

• The article: PDF (414,014 bytes)
• Source materials: ZIP (91,759 bytes)
• Original version (pre-July 2011): PDF (737,862 bytes)
• Self citation in BIBTeX (259 bytes)

DOI: 10.4086/cjtcs.2008.002

---

Volume 2008, Article 1
Volume 2008 Published articles


-------------->