Securely Sampling Biased Coins with Applications to Differential Privacy
Abstrak
We design an efficient method for sampling a large batch of d independent coins with a given bias p ∈ [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 ≥ 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=212 in 6 seconds and up to d=219 in 14 minutes. As far as we know, this is the first complete distributed implementation of either of these mechanisms.
Topik & Kata Kunci
Penulis (3)
J. Champion
Abhi Shelat
Jonathan Ullman
Akses Cepat
- Tahun Terbit
- 2019
- Bahasa
- en
- Total Sitasi
- 34×
- Sumber Database
- Semantic Scholar
- DOI
- 10.1145/3319535.3354256
- Akses
- Open Access ✓