A core technical component of our constructions is an efficient algorithm that, given a basis of an arbitrary lattice, samples lattice points from a \emph{discrete Gaussian} probability distribution whose standard deviation is essentially the length of the longest Gram-Schmidt vector of the basis. A crucial security property is that the output distribution of the algorithm is oblivious to the particular geometry of the given basis.
Category / Keywords: public-key cryptography / Lattice-based cryptography, trapdoor functions, signatures, identity-based encryption Publication Info: STOC 2008 Date: received 19 Nov 2007, last revised 16 Jun 2010 Contact author: cpeikert at alum mit edu Available format(s): PDF | BibTeX Citation Version: 20100617:023101 (All versions of this report) Short URL: ia.cr/2007/432