Paper 2019/823

Securely Sampling Biased Coins with Applications to Differential Privacy

Jeffrey Champion, abhi shelat, and Jonathan Ullman


We design an efficient method for sampling a large batch of $d$ independent coins with a given bias $p \in [0,1]$. The folklore secure computation method for doing so requires $O(\lambda + \log d)$ communication and computation per coin to achieve total statistical difference $2^{-\lambda}$. We present an exponential improvement over the folklore method that uses just $O(\log(\lambda+\log d))$ gates per coin when sampling $d$ coins with total statistical difference $2^{-\lambda}$. We present a variant of our work that also concretely beats the folklore method for $\lambda \geq 60$ which are parameters that are often used in practice. Our new technique relies on using specially designed oblivious data structures to achieve biased coin samples that takean expected $2$ random bits to sample. Using our new sampling technique, we present an implementation of the differentially private report-noisy-max mechanism (a more practical implementation of the celebrated exponential mechanism) as a secure multi-party computation. Our benchmarks show that one can run this mechanism on a domain of size $d=2^{12}$ in 6 seconds and up to $d=2^{19}$ in 14 minutes. As far as we know, this is the first complete distributed implementation of either of these mechanisms.

Available format(s)
Publication info
Preprint. MINOR revision.
distributed differential privacysecure computation
Contact author(s)
champion j @ husky neu edu
a shelat @ northeastern edu
jullman @ ccs neu edu
2020-01-07: last of 2 revisions
2019-07-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jeffrey Champion and abhi shelat and Jonathan Ullman},
      title = {Securely Sampling Biased Coins with Applications to Differential Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2019/823},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.