Synthesizing coupling proofs of differential privacy

By Aws Albarghouthi, Justin Hsu. 2017

79 citations recorded by the source corpus.

Differential privacy has emerged as a promising probabilistic formulation of privacy, generating intense interest within academia and industry. We present a push-button, automated technique for verifying ε-differential privacy of sophisticated randomized algorithms. We make several conceptual, algorithmic, and practical contributions: (i) Inspired by the recent advances on approximate couplings and randomness alignment, we present a new proof technique called coupling strategies, which casts differential privacy proofs as a winning strategy in a game where we have finite privacy resources to expend. (ii) To discover a winning strategy, we present a constraint-based formulation of the problem as a set of Horn modulo couplings (HMC) constraints, a novel combination of first-order Horn clauses and probabilistic constraints. (iii) We present a technique for solving HMC constraints by transforming probabilistic constraints into logical constraints with uninterpreted functions. (iv) Finally, we implement our technique in the FairSquare verifier and provide the first automated privacy proofs for a number of challenging algorithms from the differential privacy literature, including Report Noisy Max, the Exponential Mechanism, and the Sparse Vector Mechanism.

Subfields: Artificial Intelligence, Sociology and Political Science

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

Citations in the corpus

Detecting Violations of Differential Privacy (2018, methodology): “The “One Above” and “One Below” categories are suitable for algorithms whose input is a histogram (i.e. in adjacent databases, at most one query can change, and it will change by at most 1).”
Proving differential privacy with shadow execution (2019, background): “Recall that α (1) 0 ,α (1) 1 ,α (1) 2 are the noise added toD1, now let α (2) 0 ,α (2) 1 ,α (2) 2 be the noise added to the queries q[0],q[1],q[2] in D2, respectively.”
Relational Symbolic Execution (2017, background): “Close to our work is also Albarghouthi and Hsu (2018) where a proof technique, casting differential privacy proofs as a”
EKTELO: A Framework for Defining Differentially-Private Computations (2018, background): “Additionally, there is a growing literature on formal verification tools that prove that an algorithm satisfies di↵erential privacy [4,6, 13,38].”