Back to Search Start Over

Liftings for Differential Privacy

Authors :
Barthe, Gilles
Espitau, Thomas
Hsu, Justin
Sato, Tetsuya
Strub, Pierre-Yves
Institute IMDEA Software [Madrid]
ALgorithms for coMmunicAtion SecuriTY (ALMASTY)
Laboratoire d'Informatique de Paris 6 (LIP6)
Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)
University of Pennsylvania
Research Institute for Mathematical Sciences, Kyoto University, Japan
University of Pennsylvania [Philadelphia]
Source :
ICALP 2017, ICALP 2017, Jul 2017, Varsovie, Poland. ⟨10.4230/LIPIcs.ICALP.2017⟩
Publication Year :
2017
Publisher :
HAL CCSD, 2017.

Abstract

International audience; Recent developments in formal verification have identified approximate liftings (also known as approximate couplings) as a clean, compositional abstraction for proving differential privacy. There are two styles of definitions for this construction. 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 different strengths and weaknesses: the universal version is more general than the existential ones, but the existential versions enjoy more precise composition principles. We propose a novel, existential version of approximate lifting, called-lifting, and show that it is equivalent to Sato's construction for discrete probability measures. Our work unifies all known notions of approximate lifting, giving 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 generalize our constructions to approximate liftings based on f-divergences.

Details

Language :
English
Database :
OpenAIRE
Journal :
ICALP 2017, ICALP 2017, Jul 2017, Varsovie, Poland. ⟨10.4230/LIPIcs.ICALP.2017⟩
Accession number :
edsair.dedup.wf.001..f2354dede6c5f63c8b6a7ed29f4d73dc