@inproceedings{csw18,
 title = {Securely Sampling Biased Coins with Applications to Differential Privacy},
 author = {Jeffrey Champion and abhi shelat and Jonathan Ullman},
 howpublished = {CCS'2019 and eprint 2019/823},
 year = {2019},
}

eprint

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(λ+logd) communication an computation per coin to achieve sampling error 2−λ. We present an exponential improvement over the folklore method that uses just O(log(λ+logd)) gates per coin when sampling d coins with total sampling error 2−λ. We present a variant of our work that also concretely beats the folklore method for λ≤2−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 take an 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.