CryptoDB
How to Sample a Discrete Gaussian (and more) from a Random Oracle
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2022 |
| 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 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 Sample() for a distribution is explainable if there exists an algorithm Explain(), where, for a x in the domain, we have that Explain(x) -> r \in {0,1}^n such that Sample(r)=x. Moreover, if x is sampled from 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 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 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 Sample() for a distribution into a new 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. |
BibTeX
@inproceedings{tcc-2022-32472,
title={How to Sample a Discrete Gaussian (and more) from a Random Oracle},
publisher={Springer-Verlag},
author={George Lu and Brent Waters},
year=2022
}