logo

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

Abstract

There is no abstract available for this article.


Acknowledgment

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


Supplement

Appendixes A–C.


References

[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$

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1