The Composition Theorem for Differential Privacy

Peter Kairouz, Sewoong Oh, Pramod Viswanath

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Article number7883827
Pages (from-to)4037-4049
Number of pages13
JournalIEEE Transactions on Information Theory
Volume63
Issue number6
DOIs
StatePublished - Jun 2017

Fingerprint

Privatization
privacy
Chemical analysis
Innovation
privatization
Degradation
Testing
hypothesis testing
innovation
interpretation

Keywords

  • Differential privacy
  • hypothesis testing

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this

The Composition Theorem for Differential Privacy. / Kairouz, Peter; Oh, Sewoong; Viswanath, Pramod.

In: IEEE Transactions on Information Theory, Vol. 63, No. 6, 7883827, 06.2017, p. 4037-4049.

Research output: Contribution to journalArticle

Kairouz, Peter ; Oh, Sewoong ; Viswanath, Pramod. / The Composition Theorem for Differential Privacy. In: IEEE Transactions on Information Theory. 2017 ; Vol. 63, No. 6. pp. 4037-4049.
@article{920212112e6148c5a64004a1c3ee7462,
title = "The Composition Theorem for Differential Privacy",
abstract = "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.",
keywords = "Differential privacy, hypothesis testing",
author = "Peter Kairouz and Sewoong Oh and Pramod Viswanath",
year = "2017",
month = "6",
doi = "10.1109/TIT.2017.2685505",
language = "English (US)",
volume = "63",
pages = "4037--4049",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "6",

}

TY - JOUR

T1 - The Composition Theorem for Differential Privacy

AU - Kairouz, Peter

AU - Oh, Sewoong

AU - Viswanath, Pramod

PY - 2017/6

Y1 - 2017/6

N2 - 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.

AB - 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.

KW - Differential privacy

KW - hypothesis testing

UR - http://www.scopus.com/inward/record.url?scp=85028081797&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85028081797&partnerID=8YFLogxK

U2 - 10.1109/TIT.2017.2685505

DO - 10.1109/TIT.2017.2685505

M3 - Article

AN - SCOPUS:85028081797

VL - 63

SP - 4037

EP - 4049

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 6

M1 - 7883827

ER -