Detecting violations of differential privacy

Zeyu Ding, Yuxin Wang, Guanhong Wang, Danfeng Zhang, Daniel Kifer

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

96 Scopus citations

Abstract

The widespread acceptance of differential privacy has led to the publication of many sophisticated algorithms for protecting privacy. However, due to the subtle nature of this privacy definition, many such algorithms have bugs that make them violate their claimed privacy. In this paper, we consider the problem of producing counterexamples for such incorrect algorithms. The counterexamples are designed to be short and human-understandable so that the counterexample generator can be used in the development process - a developer could quickly explore variations of an algorithm and investigate where they break down. Our approach is statistical in nature. It runs a candidate algorithm many times and uses statistical tests to try to detect violations of differential privacy. An evaluation on a variety of incorrect published algorithms validates the usefulness of our approach: it correctly rejects incorrect algorithms and provides counterexamples for them within a few seconds.

Original languageEnglish (US)
Title of host publicationCCS 2018 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Pages475-489
Number of pages15
ISBN (Electronic)9781450356930
DOIs
StatePublished - Oct 15 2018
Event25th ACM Conference on Computer and Communications Security, CCS 2018 - Toronto, Canada
Duration: Oct 15 2018 → …

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Other

Other25th ACM Conference on Computer and Communications Security, CCS 2018
Country/TerritoryCanada
CityToronto
Period10/15/18 → …

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Detecting violations of differential privacy'. Together they form a unique fingerprint.

Cite this