Advanced Probabilistic Couplings for Differential Privacy

By Gilles Barthe, Marco Gaboardi, Benjamin Gr'egoire, Justin Hsu, Pierre-Yves Strub. 2016

68 citations recorded by the source corpus.

Differential privacy is a promising formal approach to data privacy, which provides a quantitative bound on the privacy cost of an algorithm that operates on sensitive information. Several tools have been developed for the formal verification of differentially private algorithms, including program logics and type systems. However, these tools do not capture fundamental techniques that have emerged in recent years, and cannot be used for reasoning about cutting-edge differentially private algorithms. Existing techniques fail to handle three broad classes of algorithms: 1) algorithms where privacy depends on accuracy guarantees, 2) algorithms that are analyzed with the advanced composition theorem, which shows slower growth in the privacy cost, 3) algorithms that interactively accept adaptive inputs. We address these limitations with a new formalism extending apRHL, a relational program logic that has been used for proving differential privacy of non-interactive algorithms, and incorporating aHL, a (non-relational) program logic for accuracy properties. We illustrate our approach through a single running example, which exemplifies the three classes of algorithms and explores new variants of the Sparse Vector technique, a well-studied algorithm from the privacy literature. We implement our logic in EasyCrypt, and formally verify privacy. We also introduce a novel coupling technique called optimal subset coupling that may be of independent interest.

Subfields: Artificial Intelligence, Privacy & Security

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 Privacy & Security

Citations in the corpus

Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning (2017, background): “Several works have adopted DP as an efficient defense mechanism such as [5, 7, 11, 12, 18, 23, 24, 37, 53, 60, 65, 72, 86].”
Detecting Violations of Differential Privacy (2018, background): “Verification techniques, on the other hand, allow programmers to implement a wider variety of algorithms and verify proofs of correctness (written by the developers) [2–7] or synthesize most (or all) of the proofs [1, 24, 35, 41].”
Synthesizing coupling proofs of differential privacy (2017, background): “Researchers have explored a broad array of techniques for static verification of differential privacy, including linear and dependent type systems [6, 19, 24, 39, 45], relational program logics [4, 7, 10], partial evaluation [44], and more.”
Proving differential privacy with shadow execution (2019, background): “Also, instead of building the system on customized relational logics to verify differential privacy [3, 5, 8–10], ShadowDP bases itself on standard program logics, which makes the transformed program re-usable by other program analyses.”
AutoPriv: Automating Differential Privacy Proofs (2016, methodology): “With the exception of (Barthe et al. 2016), most existing formal methods rely on the composition theorem (McSherry 2009), which (in the case ofǫ-differential privacy) essentially treats a program as a series of modules, each with a privacy costǫi and a total privacy cost bounded by ∑ i ǫi.”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, background): “[9, 8] characterize differential privacy through a coupling argument.”
LightDP: towards automating differential privacy proofs (2016, methodology): “The second strategy is the development of languages and formal verification tools for differential privacy (Reed and Pierce 2010; Gaboardi et al. 2013; Barthe et al. 2012, 2014, 2016c,b).”