Simple Lattice Trapdoor Sampling from a Broad Class of DistributionsReport as inadecuate

Simple Lattice Trapdoor Sampling from a Broad Class of Distributions - Download this document for free, or read online. Document in PDF available to download.

* Corresponding author 1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities DI-ENS - Département d-informatique de l-École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548 2 LIENS - Laboratoire d-informatique de l-école normale supérieure 3 College of Computer and Information Science Boston

Abstract : At the center of many lattice-based constructions is an algorithm that samples a short vector s, satisfying A|AR − HGs = t mod q where A, AR, H, G are public matrices and R is a trapdoor. Although the algorithm crucially relies on the knowledge of the trapdoor R to perform this sampling efficiently, the distribution it outputs should be independent of R given the public values. We present a new, simple algorithm for performing this task. The main novelty of our sampler is that the distribution of s does not need to be Gaussian, whereas all previous works crucially used the properties of the Gaussian distribution to produce such an s. The advantage of using a non-Gaussian distribution is that we are able to avoid the high-precision arithmetic that is inherent in Gaussian sampling over arbitrary lattices. So while the norm of our output vector s is on the order of √ n to n-times larger the representation length, though, is only a constant factor larger than in the samplers of Gentry, Peikert, Vaikuntanathan STOC 2008 and Micciancio, Peikert EUROCRYPT 2012, the sampling itself can be done very efficiently. This provides a useful time-output trade-off for devices with constrained computing power. In addition, we believe that the conceptual simplicity and generality of our algorithm may lead to it finding other applications.

Author: Vadim Lyubashevsky - Daniel Wichs -



Related documents