Improved Bernoulli Sampling for Discrete Gaussian Distributions over the Integers
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 a...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-02-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/4/378 |
| _version_ | 1797396627098435584 |
|---|---|
| author | Shaohao Xie Shaohua Zhuang Yusong Du |
| author_facet | Shaohao Xie Shaohua Zhuang Yusong Du |
| author_sort | Shaohao Xie |
| collection | DOAJ |
| description | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi mathvariant="script">B</mi><msup><mi>e</mi><mrow><mo>−</mo><mn>1</mn><mo>/</mo><mn>2</mn></mrow></msup></msub></semantics></math></inline-formula>, 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>ln</mi><mn>2</mn></mrow></semantics></math></inline-formula>. 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. |
| first_indexed | 2024-03-09T00:54:07Z |
| format | Article |
| id | doaj.art-fd45bb7998744b28b35c50996b300e3f |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T00:54:07Z |
| publishDate | 2021-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-fd45bb7998744b28b35c50996b300e3f2023-12-11T17:01:03ZengMDPI AGMathematics2227-73902021-02-019437810.3390/math9040378Improved Bernoulli Sampling for Discrete Gaussian Distributions over the IntegersShaohao Xie0Shaohua Zhuang1Yusong Du2School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, ChinaSchool of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, ChinaSchool of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, ChinaDiscrete 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi mathvariant="script">B</mi><msup><mi>e</mi><mrow><mo>−</mo><mn>1</mn><mo>/</mo><mn>2</mn></mrow></msup></msub></semantics></math></inline-formula>, 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>ln</mi><mn>2</mn></mrow></semantics></math></inline-formula>. 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.https://www.mdpi.com/2227-7390/9/4/378discrete Gaussian samplingdiscrete Gaussian distributionexponential distribution |
| spellingShingle | Shaohao Xie Shaohua Zhuang Yusong Du Improved Bernoulli Sampling for Discrete Gaussian Distributions over the Integers Mathematics discrete Gaussian sampling discrete Gaussian distribution exponential distribution |
| title | Improved Bernoulli Sampling for Discrete Gaussian Distributions over the Integers |
| title_full | Improved Bernoulli Sampling for Discrete Gaussian Distributions over the Integers |
| title_fullStr | Improved Bernoulli Sampling for Discrete Gaussian Distributions over the Integers |
| title_full_unstemmed | Improved Bernoulli Sampling for Discrete Gaussian Distributions over the Integers |
| title_short | Improved Bernoulli Sampling for Discrete Gaussian Distributions over the Integers |
| title_sort | improved bernoulli sampling for discrete gaussian distributions over the integers |
| topic | discrete Gaussian sampling discrete Gaussian distribution exponential distribution |
| url | https://www.mdpi.com/2227-7390/9/4/378 |
| work_keys_str_mv | AT shaohaoxie improvedbernoullisamplingfordiscretegaussiandistributionsovertheintegers AT shaohuazhuang improvedbernoullisamplingfordiscretegaussiandistributionsovertheintegers AT yusongdu improvedbernoullisamplingfordiscretegaussiandistributionsovertheintegers |