Cryptology ePrint Archive: Report 2019/823

Securely Sampling Biased Coins with Applications to Differential Privacy

Jeffrey Champion and abhi shelat and Jonathan Ullman

Abstract: 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 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.

Category / Keywords: applications / distributed differential privacy, secure computation

Date: received 15 Jul 2019, last revised 6 Jan 2020

Contact author: champion j at husky neu edu, a shelat at northeastern edu, jullman at ccs neu edu

Available format(s): PDF | BibTeX Citation

Version: 20200107:053710 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]