Synthesizing Coupling Proofs of Differential Privacy

Abstract

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 $\epsilon$-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.

References in corpus (7)

• Proving Differential Privacy via Probabilistic Couplings
• Proving differential privacy in Hoare logic
• Higher-Order Approximate Relational Refinement Types for Mechanism Design and Differential Privacy
• Advanced Probabilistic Couplings for Differential Privacy
• A Semantic Account of Metric Preservation
• Coupling proofs are probabilistic product programs
• Really Natural Linear Indexed Type Checking

Cited by in corpus (10)

• Detecting Violations of Differential Privacy
• Proving Differential Privacy with Shadow Execution
• Chorus: a Programming Framework for Building Scalable Differential Privacy Mechanisms
• Approximate Span Liftings
• Symbolic Execution for Randomized Programs
• Deciding Accuracy of Differential Privacy Schemes
• Bisimilarity Distances for Approximate Differential Privacy
• The Complexity of Verifying Boolean Programs as Differentially Private
• Data-Driven Invariant Learning for Probabilistic Programs
• Approximate Algorithms for Verifying Differential Privacy with Gaussian Distributions