Paper 2025/823

Sampling Arbitrary Discrete Distributions for RV Commitment Schemes Using the Trimmed-Tree Knuth-Yao Algorithm

Zoë Ruha Bell, University of California, Berkeley
Anvith Thudi, University of Toronto
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 -sub-Gaussian discrete distribution where is the number of bits for representing the domain, and is the bits for precision of the PDF values, we prove the Boolean circuit complexity of the trimmed-tree Knuth-Yao algorithm has upper bound , an exponential improvement over the naive bounds, and in certain parameter regimes establish the lower bound . Moreover, by proving the subtrees in the trimmed-tree Knuth-Yao circuit are small, we prove it can computed by running circuits of size in parallel and then running sequential operations on the output. We apply these circuits for trimmed-tree Knuth-Yao to constructing random variable commitment schemes for arbitrary discrete distributions, giving exponential improvements in the number of random bits and circuit complexity used for certified differentially private means and counting queries over large datasets and domains.

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