#

### 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)*
##### 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)