OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Sampling from Arbitrary Centered Discrete Gaussians for Lattice-Based Cryptography

Aguilar Melchor, Carlos and Albrecht, Martin R. and Ricosset, Thomas Sampling from Arbitrary Centered Discrete Gaussians for Lattice-Based Cryptography. (2017) In: International Conference on Applied Cryptography and Network Security (ACNS 2017), 10 July 2017 - 12 July 2017 (Kanazawa, Japan).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


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) 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.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Springer editor. This paper appears in volume 10355 of Lecture Notes in Computer Science ISSN : 0302-9743 ISBN 978-3-319-61203-4 The original PDF is available at: https://link.springer.com/chapter/10.1007/978-3-319-61204-1_1
HAL Id:hal-02548105
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Other partners > Thales (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Royal Holloway University of London - RHUL (UNITED KINGDOM)
Laboratory name:
EPSRC : Engineering and Physical Sciences Research Council (UK)
Deposited On:09 Apr 2020 13:18

Repository Staff Only: item control page