Welcome to the resource topic for
**2014/1027**

**Title:**

Simple Lattice Trapdoor Sampling from a Broad Class of Distributions

**Authors:**
Vadim Lyubashevsky, 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.

**ePrint:**
https://eprint.iacr.org/2014/1027

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .