Cited By
View all- Boudgoust KSimkin M(2024)The Power of NAPs:Theory of Cryptography10.1007/978-3-031-78011-0_2(35-66)Online publication date: 2-Dec-2024
How to Sample a Discrete Gaussian (and more) from a Random Oracle
Authors: 
George Lu, 
Brent WatersAuthors Info & Claims
Pages 653 - 682
Abstract
The random oracle methodology is central to the design of many practical cryptosystems. A common challenge faced in several systems is the need to have a random oracle that outputs from a structured distribution , even though most heuristic implementations such as SHA-3 are best suited for outputting bitstrings.
Our work explores the problem of sampling from discrete Gaussian (and related) distributions in a manner that they can be programmed into random oracles. We make the following contributions:
•
We provide a definitional framework for our results. We say that a sampling algorithm for a distribution is explainable if there exists an algorithm which, when given an x in the support of , outputs an such that . Moreover, if x is sampled from the explained distribution is statistically close to choosing r uniformly at random. We consider a variant of this definition that allows the statistical closeness to be a “precision parameter” given to the algorithm. We show that sampling algorithms which satisfy our ‘explainability’ property can be programmed as a random oracle.
•
We provide a simple algorithm for explaining any sampling algorithm that works over distributions with polynomial sized ranges. This includes discrete Gaussians with small standard deviations.
•
We show how to transform a (not necessarily explainable) sampling algorithm for a distribution into a new that is explainable. The requirements for doing this is that (1) the probability density function is efficiently computable (2) it is possible to efficiently uniformly sample from all elements that have a probability density above a given threshold p, showing the equivalence of random oracles to these distributions and random oracles to uniform bitstrings. This includes a large class of distributions, including all discrete Gaussians.
•
A potential drawback of the previous approach is that the transformation requires an additional computation of the density function. We provide a more customized approach that shows the Miccancio-Walter discrete Gaussian sampler is explainable as is. This suggests that other discrete Gaussian samplers in a similar vein might also be explainable as is.
References
[1]
Agrawal S, Wichs D, and Yamada S Pass R and Pietrzak K Optimal broadcast encryption from LWE and pairings in the standard model Theory of Cryptography 2020 Cham Springer 149-178
[2]
Aguilar-Melchor C, Albrecht MR, and Ricosset T Gollmann D, Miyaji A, and Kikuchi H Sampling from arbitrary centered discrete Gaussians for lattice-based cryptography Applied Cryptography and Network Security 2017 Cham Springer 3-19
[3]
Asharov G, Jain A, López-Alt A, Tromer E, Vaikuntanathan V, and Wichs D Pointcheval D and Johansson T Multiparty computation with low communication, computation and interaction via threshold FHE Advances in Cryptology – EUROCRYPT 2012 2012 Heidelberg Springer 483-501
[4]
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, pp. 2147–2164, November 2019
[5]
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Denning, D.E., Pyle, R., Ganesan, R., Sandhu, R.S., Ashby, V. (eds.) CCS 1993: Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, 3–5 November 1993, pp. 62–73. ACM (1993)
[6]
Bellare M and Rogaway P Maurer U The exact security of digital signatures-how to sign with RSA and Rabin Advances in Cryptology — EUROCRYPT ’96 1996 Heidelberg Springer 399-416
[7]
Boneh D and Franklin M Kilian J Identity-based encryption from the Weil pairing Advances in Cryptology — CRYPTO 2001 2001 Heidelberg Springer 213-229
[8]
Boneh D, Lynn B, and Shacham H Boyd C Short signatures from the Weil pairing Advances in Cryptology — ASIACRYPT 2001 2001 Heidelberg Springer 514-532
[9]
Brakerski Z, Cash D, Tsabary R, and Wee H Hirt M and Smith A Targeted homomorphic attribute-based encryption Theory of Cryptography 2016 Heidelberg Springer 330-360
[10]
Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 575–584. Association for Computing Machinery, New York (2013)
[11]
Brier E, Coron J-S, Icart T, Madore D, Randriam H, and Tibouchi M Rabin T Efficient indifferentiable hashing into ordinary elliptic curves Advances in Cryptology – CRYPTO 2010 2010 Heidelberg Springer 237-254
[12]
Buchmann J, Cabarcas D, Göpfert F, Hülsing A, and Weiden P Lange T, Lauter K, and Lisoněk P Discrete Ziggurat: a time-memory trade-off for sampling from a Gaussian distribution over the integers Selected Areas in Cryptography – SAC 2013 2014 Heidelberg Springer 402-417
[13]
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited (preliminary version). In: Vitter, J.S. (ed.) Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, 23–26 May 1998, pp. 209–218. ACM (1998)
[14]
Datta P, Komargodski I, and Waters B Canteaut A and Standaert F-X Decentralized multi-authority ABE for DNFs from LWE Advances in Cryptology – EUROCRYPT 2021 2021 Cham Springer 177-209
[15]
Dwarakanath NC and Galbraith SD Sampling from discrete Gaussians for lattice-based cryptography on a constrained device Appl. Algebra Eng. Commun. Comput. 2014 25 3 159-180
[16]
Fiat A and Shamir A Odlyzko AM How to prove yourself: practical solutions to identification and signature problems Advances in Cryptology — CRYPTO’ 86 1987 Heidelberg Springer 186-194
[17]
Fujisaki E and Okamoto T Wiener M Secure integration of asymmetric and symmetric encryption schemes Advances in Cryptology — CRYPTO’ 99 1999 Heidelberg Springer 537-554
[18]
Genise N and Micciancio D Nielsen JB and Rijmen V Faster Gaussian sampling for trapdoor lattices with arbitrary modulus Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 174-203
[19]
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 197–206 (2008)
[20]
Goh E-J, Jarecki S, Katz J, and Wang N Efficient signature schemes with tight reductions to the Diffie-Hellman problems J. Cryptol. 2007 20 4 493-514
[21]
Hofheinz D, Jager T, Khurana D, Sahai A, Waters B, and Zhandry M Cheon JH and Takagi T How to generate and use universal samplers Advances in Cryptology – ASIACRYPT 2016 2016 Heidelberg Springer 715-744
[22]
Howe J, Prest T, Ricosset T, and Rossi M Ding J and Tillich J-P Isochronous Gaussian sampling: from inception to implementation Post-Quantum Cryptography 2020 Cham Springer 53-71
[23]
Icart T Halevi S How to hash into elliptic curves Advances in Cryptology - CRYPTO 2009 2009 Heidelberg Springer 303-316
[24]
Karmakar A, Roy SS, Reparaz O, Vercauteren F, and Verbauwhede I Constant-time discrete Gaussian sampling IEEE Trans. Comput. 2018 67 11 1561-1571
[25]
Karney CFF Sampling exactly from the normal distribution ACM Trans. Math. Softw. 2016 42 1 1-14
[26]
Lewko A and Waters B Paterson KG Decentralizing attribute-based encryption Advances in Cryptology – EUROCRYPT 2011 2011 Heidelberg Springer 568-588
[27]
Lu, G., Waters, B.: How to sample a discrete Gaussian (and more) from a random oracle. Cryptology ePrint Archive, Paper 2022/1227 (2022). https://eprint.iacr.org/2022/1227
[28]
Lyubashevsky V and Wichs D Katz J Simple lattice trapdoor sampling from a broad class of distributions Public-Key Cryptography – PKC 2015 2015 Heidelberg Springer 716-730
[29]
Maurer U, Renner R, and Holenstein C Naor M Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology Theory of Cryptography 2004 Heidelberg Springer 21-39
[30]
Micciancio D and Walter M Katz J and Shacham H Gaussian sampling over the integers: efficient, generic, constant-time Advances in Cryptology – CRYPTO 2017 2017 Cham Springer 455-485
[31]
Pöppelmann T, Ducas L, and Güneysu T Batina L and Robshaw M Enhanced lattice-based signatures on reconfigurable hardware Cryptographic Hardware and Embedded Systems – CHES 2014 2014 Heidelberg Springer 353-370
[32]
Ristenpart T, Shacham H, and Shrimpton T Paterson KG Careful with composition: limitations of the indifferentiability framework Advances in Cryptology – EUROCRYPT 2011 2011 Heidelberg Springer 487-506
[33]
Zhao RK, Steinfeld R, and Sakzad A Ding J and Tillich J-P COSAC: compact and scalable arbitrary-centered discrete Gaussian sampling over integers Post-Quantum Cryptography 2020 Cham Springer 284-303
[34]
Zhao RK, Steinfeld R, and Sakzad A FACCT: fast, compact, and constant-time discrete Gaussian sampler over integers IEEE Trans. Comput. 2020 69 1 126-137
Index Terms
- How to Sample a Discrete Gaussian (and more) from a Random Oracle
Index terms have been assigned to the content through auto-classification.
Recommendations
Arbitrary-Centered Discrete Gaussian Sampling over the Integers
Information Security and PrivacyAbstractDiscrete Gaussian sampling over the integers, which is to sample from a discrete Gaussian distribution over the integers with parameter and center , is one of fundamental operations in lattice-based cryptography. The sampling algorithm should ...
Algorithm 488: A Gaussian pseudo-random number generator
The algorithm calculates the exact cumulative distribution of the two-sided Kolmogorov-Smirnov statistic for samples with few observations. The general problem for which the formula is needed is to assess the probability that a particular sample comes ...
Constant-Time Discrete Gaussian Sampling
Sampling from a discrete Gaussian distribution is an indispensable part of lattice-based cryptography. Several recent works have shown that the timing leakage from a non-constant-time implementation of the discrete Gaussian sampling algorithm could be ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Nov 2022
812 pages
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 21 December 2022
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025
Other Metrics
Citations
Cited By
View all- Boudgoust KSimkin M(2024)The Power of NAPs:Theory of Cryptography10.1007/978-3-031-78011-0_2(35-66)Online publication date: 2-Dec-2024