TY - JOUR

T1 - Deciding accuracy of differential privacy schemes

AU - Barthe, Gilles

AU - Chadha, Rohit

AU - Krogmeier, Paul

AU - Sistla, A. Prasad

AU - Viswanathan, Mahesh

N1 - Funding Information:
The authors would like to thank anonymous reviewers for their interesting and useful comments. This work was partially supported by National Science Foundation grants NSF CNS 1553548, NSF CCF 1900924, NSF CCF 1901069 and NSF CCF 2007428.
Publisher Copyright:
© 2021 Owner/Author.

PY - 2021/1

Y1 - 2021/1

N2 - 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.

AB - 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.

KW - accuracy

KW - decidability

KW - differential privacy

UR - http://www.scopus.com/inward/record.url?scp=85099030458&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85099030458&partnerID=8YFLogxK

U2 - 10.1145/3434289

DO - 10.1145/3434289

M3 - Article

AN - SCOPUS:85099030458

SN - 2475-1421

VL - 5

JO - Proceedings of the ACM on Programming Languages

JF - Proceedings of the ACM on Programming Languages

IS - POPL

M1 - 8

ER -