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 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 $\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 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.

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
2022-09-16: approved
See all versions
Short URL
https://ia.cr/2022/1227

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}
}
`
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.