Paper 2014/1027

Simple Lattice Trapdoor Sampling from a Broad Class of Distributions

Vadim Lyubashevsky and Daniel Wichs

Abstract

At the center of many lattice-based constructions is an algorithm that samples a short vector $s$, satisfying $[A|AR-HG]s=t\bmod 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 $\sqrt{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.

Note: Fixed some typos.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in PKC 2015
Keywords
lattice cryptographypre-image sampling
Contact author(s)
lyubash @ di ens fr
History
2015-01-04: last of 2 revisions
2015-01-02: received
See all versions
Short URL
https://ia.cr/2014/1027
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/1027,
      author = {Vadim Lyubashevsky and Daniel Wichs},
      title = {Simple Lattice Trapdoor Sampling from a Broad Class of Distributions},
      howpublished = {Cryptology ePrint Archive, Paper 2014/1027},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/1027}},
      url = {https://eprint.iacr.org/2014/1027}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.