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 an computation per coin to achieve sampling error $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 sampling error $2^{-\lambda}$. We present a variant of our work that also concretely beats the folklore method for $\lambda \leq 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.

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

Date: received 15 Jul 2019

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

Available format(s): PDF | BibTeX Citation

Version: 20190716:135154 (All versions of this report)

Short URL: ia.cr/2019/823


[ Cryptology ePrint archive ]