Proving differential privacy in Hoare logic

Gilles Barthe, Marco Gaboardi, Emilio Jesús Gallego Arias, Justin Hsu, César Kunz, Pierre Yves Strub

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Citations (Scopus)

Abstract

Differential privacy is a rigorous, worst-case notion of privacy-preserving computation. Informally, a probabilistic program is differentially private if the participation of a single individual in the input database has a limited effect on the program's distribution on outputs. More technically, differential privacy is a quantitative 2-safety property that bounds the distance between the output distributions of a probabilistic program on adjacent inputs. Like many 2-safety properties, differential privacy lies outside the scope of traditional verification techniques. Existing approaches to enforce privacy are based on intricate, non-conventional type systems, or customized relational logics. These approaches are difficult to implement and often cumbersome to use.

We present an alternative approach that verifies differential privacy by standard, non-relational reasoning on non-probabilistic programs. Our approach transforms a probabilistic program into a non-probabilistic program which simulates two executions of the original program. We prove that if the target program is correct with respect to a Hoare specification, then the original probabilistic program is differentially private. We provide a variety of examples from the differential privacy literature to demonstrate the utility of our approach. Finally, we compare our approach with existing verification techniques for privacy.

Original languageEnglish
Title of host publicationProceedings of the 2014 IEEE 27th Computer Security Foundations Symposium, CSF 2014
PublisherIEEE Computer Society
Pages411-424
Number of pages14
ISBN (Print)9781479942909
DOIs
Publication statusPublished - 2014
Event27th IEEE Computer Security Foundations Symposium - Vienna, Austria
Duration: 19 Jul 201422 Jul 2014
http://csf2014.di.univr.it/

Conference

Conference27th IEEE Computer Security Foundations Symposium
Abbreviated titleCSF 2014
CountryAustria
CityVienna
Period19/07/1422/07/14
Internet address

Keywords

  • Differential privacy
  • Hoare logic
  • Privacy
  • Probabilistic hoare logic
  • Relational hoare logic
  • Verification

Fingerprint Dive into the research topics of 'Proving differential privacy in Hoare logic'. Together they form a unique fingerprint.

Cite this