Paper 2025/823
Sampling Arbitrary Discrete Distributions for RV Commitment Schemes Using the Trimmed-Tree Knuth-Yao Algorithm
Abstract
Sampling from non-uniform randomness according to an algorithm which keeps the internal randomness used by the sampler hidden is increasingly important for cryptographic applications, such as timing-attack-resistant lattice-based cryptography or certified differential privacy. In this paper we present a provably efficient sampler that maintains random sample privacy, or random sample hiding, and is applicable to arbitrary discrete random variables. Namely, we present a constant-time version of the classic Knuth-Yao algorithm that we name "trimmed-tree" Knuth-Yao. We establish distribution-tailored Boolean circuit complexity bounds for this algorithm, in contrast to the previous naive distribution-agnostic bounds. For a
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Discrete SamplersVerifiable ComputationDifferential Privacy
- Contact author(s)
-
zbell @ berkeley edu
anvith thudi @ mail utoronto ca - History
- 2025-05-09: approved
- 2025-05-08: received
- See all versions
- Short URL
- https://ia.cr/2025/823
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/823, author = {Zoë Ruha Bell and Anvith Thudi}, title = {Sampling Arbitrary Discrete Distributions for {RV} Commitment Schemes Using the Trimmed-Tree Knuth-Yao Algorithm}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/823}, year = {2025}, url = {https://eprint.iacr.org/2025/823} }