1. Securely Sampling Biased Coins with Applications to Differential Privacy 2019 CCS DifferentialPrivacy
    Jeffrey Champion, abhi shelat and Jonathan Ullman
    [View PDF on eprint.iacr.org]
    [Show BibTex Citation]

    author = {Champion, Jeffrey and shelat, abhi and Ullman, Jonathan},
    title = {Securely Sampling Biased Coins with Applications to Differential Privacy},
    booktitle = {Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security},
    series = {CCS '19},
    year = {2019},
    isbn = {978-1-4503-6747-9},
    location = {London, United Kingdom},
    pages = {603--614},
    numpages = {12},
    url = {http://doi.acm.org/10.1145/3319535.3354256},
    doi = {10.1145/3319535.3354256},
    acmid = {3354256},
    publisher = {ACM},
    address = {New York, NY, USA},
    keywords = {differential privacy, multi-party computation},

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(λ+logd) communication and computation per coin to achieve total statistical difference 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 statistical difference 2−λ. We present a variant of our work that also concretely beats the folklore method for λ≥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.