Improved Bernoulli Sampling for Discrete Gaussian Distributions over the Integers

Shaohao Xie, Shaohua Zhuang and Yusong Du
Additional contact information
Shaohao Xie: School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China
Shaohua Zhuang: School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China
Yusong Du: School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China

Mathematics, 2021, vol. 9, issue 4, 1-13

Abstract: Discrete Gaussian sampling is one of the fundamental mathematical tools for lattice-based cryptography. In this paper, we revisit the Bernoulli(-type) sampling for centered discrete Gaussian distributions over the integers, which was proposed by Ducas et al. in 2013. Combining the idea of Karney’s algorithm for sampling from the Bernoulli distribution B e ? 1 / 2 , we present an improved Bernoulli sampling algorithm. It does not require the use of floating-point arithmetic to generate a precomputed table, as the original Bernoulli sampling algorithm did. It only needs a fixed look-up table of very small size (e.g., 128 bits) that stores the binary expansion of ln 2 . We also propose a noncentered version of Bernoulli sampling algorithm for discrete Gaussian distributions with varying centers over the integers. It requires no floating-point arithmetic and can support centers of precision up to 52 bits. The experimental results show that our proposed algorithms have a significant improvement in the sampling efficiency as compared to other rejection algorithms.

Keywords: discrete Gaussian sampling; discrete Gaussian distribution; exponential distribution (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/4/378/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/4/378/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:4:p:378-:d:499059

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().