Securely Sampling Biased Coins with Applications to Differential Privacy
Securely Sampling Biased Coins with Applications to Differential Privacy
复制标题
DOI：
10.1145/3319535.3354256
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
J. Champion;Abhi Shelat;Jonathan Ullman
中科院分区：
文献类型：
--
作者：
J. Champion;Abhi Shelat;Jonathan Ullman
我们设计了一种有效的方法，用于对具有给定偏差p ∈ [0，1]的大量d个独立硬币进行采样。为此，民间传说的安全计算方法需要每个硬币O（lambda + log d）通信和计算，以实现总统计差异2-lambda。我们提出了一个指数级的改进民俗方法，使用每枚硬币的O（log（lambda+log d））门时，采样d个硬币的总统计差异2-lambda。我们提出了一个变体，我们的工作，也具体击败了民间传说的方法，λ ≥ 60，这是经常在实践中使用的参数。我们的新技术依赖于使用专门设计的不经意数据结构来实现有偏见的硬币样本，这些样本需要预期的2个随机位来采样。使用我们的新的采样技术，我们提出了一个实现的差分私人报告噪声最大的机制（一个更实际的实现著名的指数机制）作为一个安全的多方计算。我们的基准测试表明，可以在6秒内在大小为d=212的域上运行此机制，并在14分钟内达到d=219。据我们所知，这是第一个完整的分布式实现这些机制。
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.