Sampling From Arbitrary Centered Discrete Gaussians For Lattice-Based Cryptography. / Aguilar-Melchor, Carlos; Albrecht, Martin; Ricosset, Thomas.

Applied Cryptography and Network Security: ACNS 2017. Vol. 10355 Springer, 2017. p. 3-19 (Lecture Notes in Computer Science; Vol. 10355).

Research output: Chapter in Book/Report/Conference proceedingConference contribution




Non-Centered Discrete Gaussian sampling is a fundamental building block in many lattice-based constructions in cryptography, such as signature and identity-based encryption schemes. On the one hand, the center-dependent approaches, e.g. cumulative distribution tables (CDT), Knuth-Yao, the alias method, discrete Zigurat and their variants, are the fastest known algorithms to sample from a discrete Gaussian distribution. However, they use a relatively large precomputed table for each possible real center in [0,1)[0,1) making them impracticable for non-centered discrete Gaussian sampling. On the other hand, rejection sampling allows to sample from a discrete Gaussian distribution for all real centers without prohibitive precomputation cost but needs costly floating-point arithmetic and several trials per sample. In this work, we study how to reduce the number of centers for which we have to precompute tables and propose a non-centered CDT algorithm with practicable size of precomputed tables as fast as its centered variant. Finally, we provide some experimental results for our open-source C++ implementation indicating that our sampler increases the rate of Peikert’s algorithm for sampling from arbitrary lattices (and cosets) by a factor 3 with precomputation storage up to 6.2 MB.
Original languageEnglish
Title of host publicationApplied Cryptography and Network Security
Subtitle of host publicationACNS 2017
Number of pages17
ISBN (Electronic)978-3-319-61204-1
ISBN (Print)978-3-319-61203-4
Publication statusPublished - 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Cham
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 28018616