Barthe, Gilles and Espitau, Thomas and Hsu, Justin and Sato, Tetsuya and Strub, Pierre-Yves - Relational $\star$-Liftings for Differential Privacy

lmcs:4380 - Logical Methods in Computer Science, December 19, 2019, Volume 15, Issue 4
Relational $\star$-Liftings for Differential Privacy

Authors: Barthe, Gilles and Espitau, Thomas and Hsu, Justin and Sato, Tetsuya and Strub, Pierre-Yves

Recent developments in formal verification have identified approximate liftings (also known as approximate couplings) as a clean, compositional abstraction for proving differential privacy. This construction can be defined in two styles. Earlier definitions require the existence of one or more witness distributions, while a recent definition by Sato uses universal quantification over all sets of samples. These notions have each have their own strengths: the universal version is more general than the existential ones, while existential liftings are known to satisfy more precise composition principles. We propose a novel, existential version of approximate lifting, called $\star$-lifting, and show that it is equivalent to Sato's construction for discrete probability measures. Our work unifies all known notions of approximate lifting, yielding cleaner properties, more general constructions, and more precise composition theorems for both styles of lifting, enabling richer proofs of differential privacy. We also clarify the relation between existing definitions of approximate lifting, and consider more general approximate liftings based on $f$-divergences.


DOI : 10.23638/LMCS-15(4:18)2019
Volume: Volume 15, Issue 4
Published on: December 19, 2019
Submitted on: March 16, 2018
Keywords: Computer Science - Logic in Computer Science,Computer Science - Programming Languages


Share

Consultation statistics

This page has been seen 129 times.
This article's PDF has been downloaded 79 times.