Deciding accuracy of differential privacy schemes
Deciding accuracy of differential privacy schemes
复制标题
DOI：
10.1145/3434289
复制
发表时间：
2020-11
影响因子：
--
通讯作者：
G. Barthe;Rohit Chadha;Paul Krogmeier;A. Sistla;Mahesh Viswanathan
中科院分区：
文献类型：
--
作者：
G. Barthe;Rohit Chadha;Paul Krogmeier;A. Sistla;Mahesh Viswanathan
差异隐私是一个数学框架，可以与差异隐私的隐私组成部分相比，具有可证明的保证和准确性的统计计算。差异隐私算法的准确性主张从算法到算法不等，并且不是一般定义的实例化。输入X W.R.T.确定性计算F和距离D是所有Y上的最小距离D（X，Y），因此F（y）≠f（x）。理论上的计算机科学捕获了差异性隐私算法的准确性。然后，我们定义了确定准确性的非平凡的概率计算（无条件或假设Schanuel的概念）。文学。
Differential privacy is a mathematical framework for developing statistical computations with provable guarantees of privacy and accuracy. In contrast to the privacy component of differential privacy, which has a clear mathematical and intuitive meaning, the accuracy component of differential privacy does not have a generally accepted definition; accuracy claims of differential privacy algorithms vary from algorithm to algorithm and are not instantiations of a general definition. We identify program discontinuity as a common theme in existing ad hoc definitions and introduce an alternative notion of accuracy parametrized by, what we call, — the of an input x w.r.t. a deterministic computation f and a distance d, is the minimal distance d(x,y) over all y such that f(y)≠ f(x). We show that our notion of accuracy subsumes the definition used in theoretical computer science, and captures known accuracy claims for differential privacy algorithms. In fact, our general notion of accuracy helps us prove better claims in some cases. Next, we study the decidability of accuracy. We first show that accuracy is in general undecidable. Then, we define a non-trivial class of probabilistic computations for which accuracy is decidable (unconditionally, or assuming Schanuel’s conjecture). We implement our decision procedure and experimentally evaluate the effectiveness of our approach for generating proofs or counterexamples of accuracy for common algorithms from the literature.