Welcome to the resource topic for 2019/823
Title:
Securely Sampling Biased Coins with Applications to Differential Privacy
Authors: Jeffrey Champion, abhi shelat, 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 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.
ePrint: https://eprint.iacr.org/2019/823
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .