On the rejection rate of exact sampling algorithm for discrete Gaussian distributions over the integers. (English) Zbl 1504.65008
Summary: A discrete Gaussian distribution over the integers is a Gaussian distribution restricted so that its support is the set of all the integers. This paper studies the problem of sampling exactly from discrete Gaussian distributions over the integers. It is required to generate integers according to a given discrete Gaussian distribution without any statistical discrepancy. C. F. F. Karney [ACM Trans. Math. Softw. 42, No. 1, Article No. 3, 14 p. (2016; Zbl 1357.65008)] proposed an exact sampling algorithm for discrete Gaussian distributions whose parameters are rational numbers. This algorithm uses rejection sampling, and it is a discretization of his algorithm for sampling exactly from the standard normal distribution. In this paper, we give a rigorous and complete analysis of the rejection rate of this algorithm, which was not given by Karney, and show that it cannot generate integers efficiently in the case where the standard deviation of the distribution is very small (e.g. much smaller than 1/2). Then, we present an alternative algorithm for this special case, which can sample exactly and efficiently from discrete Gaussian distributions with very small standard deviations.
MSC:
| 65C10 | Random number generation in numerical analysis |
| 62D05 | Sampling theory, sample surveys |
| 94A20 | Sampling theory in information and communication theory |
Keywords:
random number generation; rejection sampling; exact sampling; discrete Gaussian distributionCitations:
Zbl 1357.65008References:
| [1] | Andrysco, M, Kohlbrenner, D, Mowery, K, Jhala, R, Lerner, S, Shacham, H: On subnormal floating point and abnormal timing. In: 2015 IEEE symposium on security and privacy, SP 2015, San Jose, CA, USA, May 17-21, 2015, pp 623-639. IEEE Computer Society (2015) |
| [2] | Bai, S.; Lepoint, T.; Roux-Langlois, A.; Sakzad, A.; Stehlé, D.; Steinfeld, R., Improved security proofs in lattice-based cryptography: Using the Rényi divergence rather than the statistical distance, J. Cryptol., 31, 2, 610-640 (2018) · Zbl 1444.94043 · doi:10.1007/s00145-017-9265-9 |
| [3] | Barthe, G, Belaïd, S, Espitau, T, Fouque, P.-A., Rossi, M., Tibouchi, M: GALACTICS: gaussian sampling for lattice-based constant-time implementation of cryptographic signatures, revisited. In: Cavallaro, L., Kinder, J., Wang, X.F., Katz, J. (eds.) Proceedings of the 2019 ACM SIGSAC CCS 2019, London, UK, November 11-15, 2019, pp 2147-2164. ACM (2019) |
| [4] | Bruinderink, L.G., Hülsing, A., Lange, T., Yarom, Y.: Flush, gauss, and reload—a cache attack on the BLISS lattice-based signature scheme. In: Gierlichs, B., Poschmann, A.Y. (eds.) CHES 2016, Santa Barbara, CA, USA, August 17-19, 2016, Proceedings, Volume 9813 of LNCS, pp 323-345. Springer (2016) · Zbl 1411.94065 |
| [5] | Ducas, L, Durmus, A, Lepoint, T, Lyubashevsky, V: Lattice signatures and bimodal gaussians. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, Volume 8042 of LNCS, pp 40-56. Springer (2013) · Zbl 1310.94141 |
| [6] | Dwarakanath, NC; Galbraith, SD, Sampling from discrete gaussians for lattice-based cryptography on a constrained device, Appl. Algebra Eng. Commun. Comput., 25, 3, 159 (2014) · Zbl 1372.94425 · doi:10.1007/s00200-014-0218-3 |
| [7] | Espitau, T., Fouque, P.-A., Gérard, B., Tibouchi, M.: Side-channel attacks on bliss lattice-based signatures: Exploiting branch tracing against strongswan and electromagnetic emanations in microcontrollers. In: Proceedings of the 2017 ACM SIGSAC CCS, pp 1857-1874. ACM (2017) |
| [8] | Gentry, C, Peikert, C, Vaikuntanathan, V: Trapdoors for hard lattices and new cryptographic constructions. In: Dwork, C. (ed.) STOC 2008, Victoria, British Columbia, Canada, May 17-20, 2008, pp 197-206. ACM (2008) · Zbl 1231.68124 |
| [9] | Howe, J.; Khalid, A.; Rafferty, C.; Regazzoni, F.; O’Neill, M., On practical discrete gaussian samplers for lattice-based cryptography, IEEE Trans. Comput., 67, 3, 322-334 (2018) · Zbl 1390.94843 · doi:10.1109/TC.2016.2642962 |
| [10] | Karney, C, F.: Sampling exactly from the normal distribution. ACM Trans. Math. Softw. 42(1), 3:1-3:14 (2016) · Zbl 1357.65008 |
| [11] | Lyubashevsky, V.; Peikert, C.; Regev, O., On ideal lattices and learning with errors over rings, J. ACM, 60, 6, 43:1-43:35 (2013) · Zbl 1281.68140 · doi:10.1145/2535925 |
| [12] | Micciancio, D.; Regev, O., Worst-case to average-case reductions based on gaussian measures, SIAM J. Comput., 37, 1, 267-302 (2007) · Zbl 1142.68037 · doi:10.1137/S0097539705447360 |
| [13] | Micciancio, D, Walter, M: Gaussian sampling over the integers: Efficient, generic, constant-time. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part II, Volume 10402 of LNCS, pp 455-485. Springer (2017) · Zbl 1410.94098 |
| [14] | Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem: Extended abstract. In: Mitzenmacher, M. (ed.) STOC 2009, Bethesda, MD, USA, May 31-June 2, 2009, pp 333-342. ACM (2009) · Zbl 1304.94079 |
| [15] | Peikert, C.: An efficient and parallel gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, Volume 6223 of LNCS, pp 80-97. Springer (2010) · Zbl 1280.94091 |
| [16] | Prest, T.: Sharper bounds in lattice-based cryptography using the Rényi divergence. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Hong Kong, China, December 3-7, 2017, Proceedings, Part I, Volume 10624 of LNCS, pp 347-374. Springer (2017) · Zbl 1420.94092 |
| [17] | Regev, O., On lattices, learning with errors, random linear codes, and cryptography, J. ACM, 56, 6, 34:1-34:40 (2009) · Zbl 1325.68101 · doi:10.1145/1568318.1568324 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
