Paper 2022/1227
How to Sample a Discrete Gaussian (and more) from a Random Oracle
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 $\mathcal{D}$, even though most heuristic implementations such as SHA3 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 $\mathsf{Sample}$ for a distribution is explainable if there exists an algorithm $\mathsf{Explain}$ where, for a $x$ in the domain, we have that $\mathsf{Explain}(x) \rightarrow r \in \{0,1\}^n$ such that $\mathsf{Sample}(r)=x$. Moreover, if $x$ is sampled from $\mathcal{D}$ 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 $\mathsf{Explain}$ 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 \emph{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 $\mathsf{Sample}$ for a distribution into a new $\mathsf{Sample}'$ 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 MiccancioWalter discrete Gaussian sampler is explainable as is. This suggests that other discrete Gaussian samplers in a similar vein might also be explainable as is.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 Random Oracle Lattice Discrete Gaussian
 Contact author(s)

gclu @ cs utexas edu
bwaters @ cs utexas edu  History
 20220916: approved
 20220916: received
 See all versions
 Short URL
 https://ia.cr/2022/1227
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1227, author = {George Lu and Brent Waters}, title = {How to Sample a Discrete Gaussian (and more) from a Random Oracle}, howpublished = {Cryptology ePrint Archive, Paper 2022/1227}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1227}}, url = {https://eprint.iacr.org/2022/1227} }