The Composition Theorem for Differential Privacy

By Peter Kairouz, Sewoong Oh, Pramod Viswanath. 2013

825 citations recorded by the source corpus.

Sequential querying of differentially private mechanisms degrades the overall privacy level. In this paper, we answer the fundamental question of characterizing the level of overall privacy degradation as a function of the number of queries and the privacy levels maintained by each privatization mechanism. Our solution is complete: we prove an upper bound on the overall privacy level and construct a sequence of privatization mechanisms that achieves this bound. The key innovation is the introduction of an operational interpretation of differential privacy (involving hypothesis testing) and the use of a data processing inequality along with its converse. Our result improves over the state of the art, and has immediate connections to several problems studied in the literature.

Subfields: Artificial Intelligence, Statistics and Probability, Privacy & Security, Information Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Peter Kairouz
  2. Abhradeep Thakurta
  3. Florian Tramèr
  4. Percy Liang
  5. H. Brendan McMahan
  6. Nicholas Carlini
  7. Dawn Song
  8. Qiang Yang

In Statistics and Probability

  1. Yu-Xiang Wang
  2. Jonathan Ullman
  3. Abhradeep Thakurta
  4. Jayadev Acharya
  5. Peter Kairouz
  6. Ziteng Sun
  7. Borja Balle
  8. Salil P. Vadhan

In Privacy & Security

  1. Peter Kairouz
  2. Abhradeep Thakurta
  3. Borja Balle
  4. Jonathan Ullman
  5. Thomas Steinke
  6. Yu-Xiang Wang
  7. Kunal Talwar
  8. H. Brendan McMahan

In Information Theory

  1. Yu-Xiang Wang
  2. Borja Balle
  3. Ziteng Sun
  4. Albert Cheu
  5. Jonathan Ullman
  6. Ilya Mironov
  7. Peter Kairouz
  8. Adam D. Smith

Citations in the corpus