Pierre-Yves Strub (École Polytechnique), Proving Differential Privacy via Probabilistic Couplings


Couplings are a powerful mathematical tool for reasoning about pairs of probabilistic processes. Recent developments in formal verification identify a close connection between couplings and pRHL, a relational program logic motivated by applications to provable security, enabling formal construction of couplings from the probability theory literature. However, existing work using pRHL merely shows existence of a coupling and does not give a way to prove quantitative properties about the coupling, needed to reason about mixing and convergence of probabilistic processes. Furthermore, pRHL is inherently incomplete, and is not able to capture some advanced forms of couplings such as shift couplings.

In this talk, after having introduced pRHL, I will present an extension of pRHL, which explicitly constructs the coupling in a pRHL derivation in the form of a probabilistic product program that simulates two correlated runs of the original program. Existing verification tools for probabilistic programs can then be directly applied to the probabilistic product to prove quantitative properties of the coupling. Moreover, this extension can be equipped with a new rule for while loops, where reasoning can freely mix synchronized and unsynchronized loop iterations, making the logic relatively complete for deterministic programs.

Last, I will show how the notion of couplings can be extended to approximate lifting, a notation this captures a compositional abstraction for proving differential privacy. (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.)