In this paper, we present a push-button, automated technique for verifying $\epsilon$-differential privacy of sophisticated randomized algorithms. We make a range of conceptual, algorithmic,and practical contributions: (1) 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 discovering a strategy in a game where we have finite privacy resources to expend. (2) To discover a winning strategy, we present a constraint-based formulation of the problem as solving a set of Horn modulo couplings (HMC) constraints, a novel kind of constraints combining first-order Horn clauses with probabilistic constraints. (3) We present a technique for solving HMC constraints by transforming probabilistic constraints into logical constraints with uninterpreted functions. (4) Finally, we implement our technique and provide the first automated proofs of a number of algorithms from the differential privacy literature, including Report Noisy Max, the Exponential Mechanism, and the Sparse Vector Mechanism.
Fri 12 JanDisplayed time zone: Tijuana, Baja California change
13:40 - 15:20 | |||
13:40 25mTalk | Proving expected sensitivity of probabilistic programs Research Papers Gilles Barthe IMDEA Software Institute, Thomas Espitau Universite Pierre et Marie Curie, Benjamin Gregoire INRIA, Justin Hsu University College London, Pierre-Yves Strub Ecole Polytechnique | ||
14:05 25mTalk | Synthesizing Coupling Proofs of Differential Privacy Research Papers | ||
14:30 25mTalk | Measurable cones and stable, measurable functions Research Papers Thomas Ehrhard CNRS and University Paris Diderot, Michele Pagani University Paris Diderot, Christine Tasson University Paris Diderot | ||
14:55 25mTalk | Denotational validation of higher-order Bayesian inference Research Papers Adam Ścibior University of Cambridge and MPI Tuebingen, Ohad Kammar University of Oxford, Matthijs Vákár University of Oxford, Sam Staton University of Oxford, Hongseok Yang University of Oxford, Yufei Cai University of Tuebingen, Klaus Ostermann University of Tuebingen, Sean Moss University of Oxford, Chris Heunen University of Edinburgh, Zoubin Ghahramani University of Cambridge |