SCIENCE CHINA Information Sciences, Volume 62 , Issue 3 : 039103(2019) https://doi.org/10.1007/s11432-017-9409-7

A rejection sampling algorithm for off-centered discrete Gaussian distributions over the integers

More info
  • ReceivedOct 22, 2017
  • AcceptedFeb 28, 2018
  • PublishedSep 11, 2018


There is no abstract available for this article.


This work was supported by National Key Research and Development Program of China (Grant No. 2017YFB0802500), Science and Technology Planning Project of Guangdong Province (Grant No. 2014A010103017), Natural Science Foundation of Guangdong Province (Grant No. 2016A030313298), Fundamental Research Funds for the Central Universities (Grant No. 17lgjc45) and Opening Fund of Qiongqing Key Lab of Computer Network and Communication Technology (Grant No. CY-CNCL-2017-04).


Appendixes A–C.


[1] Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the 40 Annual ACM Symposium on Theory of Computing, Victoria, 2008. 197--206. Google Scholar

[2] Micciancio D, Walter M. Gaussian sampling over the integers: efficient, generic, constant-time. In: Proceedings of Annual International Cryptology Conference, Santa Barbara, 2017. 10402: 455--485. Google Scholar

[3] Ducas L, Durmus A, Lepoint T, et al. Lattice signatures and bimodal Gaussians. In: Proceedings of Annual Cryptology Conference, Santa Barbara, 2013. 8042: 40--56. Google Scholar

[4] Saarinen M J O. Arithmetic coding and blinding countermeasures for lattice signatures. J Cryptogr Eng, 2018, 8: 71-84 CrossRef Google Scholar

[5] Karney C. Sampling exactly from the normal distribution. ACM Trans Math Softw, 2016, 42: 1--14. Google Scholar

[6] Prest T. Sharper bounds in lattice-based cryptography using the Rényi divergence. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, 2017. 10624: 347--374. Google Scholar

[7] Ducas L, Nguyen P Q. Faster Gaussian lattice sampling using lazy floating-point arithmetic. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Beijing, 2012. 7658: 415--432. Google Scholar

[8] Aguilar-Melchor C, Albrecht M R, Ricosset T. Sampling from arbitrary centered discrete Gaussians for lattice-based cryptography. In: Proceedings of International Conference on Applied Cryptography and Network Security, Kanazawa, 2017. 10355: 3--19. Google Scholar

[9] Bruinderink L G, Hülsing A, Lange T, et al. Flush, Gauss, and reload - a cache attack on the BLISS lattice-based signature scheme. In: Proceedings of International Conference on Cryptographic Hardware and Embedded Systems, Santa Barbara, 2016. 9813: 323--345. Google Scholar


    Algorithm 1 Off-centered Gaussian sampler over the integers

    Sampling from $D_{\mathbb{Z},\sigma,~c}$ with $\sigma>\sigma_2=\sqrt{1/(2\cdot\ln{2})}$, and $c\in(0,1/2]$

    Require:Double-precision numbers $\sigma$ and $c$

    Output:An integer $z$ according to $D_{\mathbb{Z},\sigma,~c}$

    Set $q\leftarrow~\sigma/\sigma_2$ with $\sigma_2=\sqrt{1/(2\cdot\ln{2})}$;

    Sample $x\in\mathbb{Z}$ according to $D_{\mathbb{Z}^+,\sigma_{2}}$ and $y\in\mathbb{Z}$ uniformly in $\{0,1,2,\ldots,\lceil~q\rceil-1\}$;

    Set $s\leftarrow~\pm1$ with equal probabilities;

    Set $\delta\leftarrow\!\lceil~xq+sc~\rceil\!-\!xq\!-\!sc$ and goto Step 2 if $y+\delta\geq~q$;

    Set $z\leftarrow~\lceil~xq+sc~\rceil~+~y$ and accept it with probability $\exp(-\frac{2xq(y+\delta)+(y+\delta)^2}{2q^2\sigma_2^2})$, otherwise goto Step 2;

    return $s\cdot~z$