The Composition Theorem for Differential Privacy

Peter Kairouz, Sewoong Oh, Pramod Viswanath
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1376-1385, 2015.

Abstract

Interactive querying of a database degrades the privacy level. In this paper we answer the fundamental question of characterizing the level of privacy degradation as a function of the number of adaptive interactions and the differential privacy levels maintained by the individual queries. Our solution is complete: the privacy degradation guarantee is true for every privacy mechanism, and further, we demonstrate a sequence of privacy mechanisms that do degrade in the characterized manner. The key innovation is the introduction of an operational interpretation (involving hypothesis testing) to differential privacy and the use of the corresponding data processing inequalities. Our result improves over the state of the art and has immediate applications to several problems studied in the literature.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-kairouz15, title = {The Composition Theorem for Differential Privacy}, author = {Kairouz, Peter and Oh, Sewoong and Viswanath, Pramod}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {1376--1385}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/kairouz15.pdf}, url = {https://proceedings.mlr.press/v37/kairouz15.html}, abstract = {Interactive querying of a database degrades the privacy level. In this paper we answer the fundamental question of characterizing the level of privacy degradation as a function of the number of adaptive interactions and the differential privacy levels maintained by the individual queries. Our solution is complete: the privacy degradation guarantee is true for every privacy mechanism, and further, we demonstrate a sequence of privacy mechanisms that do degrade in the characterized manner. The key innovation is the introduction of an operational interpretation (involving hypothesis testing) to differential privacy and the use of the corresponding data processing inequalities. Our result improves over the state of the art and has immediate applications to several problems studied in the literature.} }
Endnote
%0 Conference Paper %T The Composition Theorem for Differential Privacy %A Peter Kairouz %A Sewoong Oh %A Pramod Viswanath %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-kairouz15 %I PMLR %P 1376--1385 %U https://proceedings.mlr.press/v37/kairouz15.html %V 37 %X Interactive querying of a database degrades the privacy level. In this paper we answer the fundamental question of characterizing the level of privacy degradation as a function of the number of adaptive interactions and the differential privacy levels maintained by the individual queries. Our solution is complete: the privacy degradation guarantee is true for every privacy mechanism, and further, we demonstrate a sequence of privacy mechanisms that do degrade in the characterized manner. The key innovation is the introduction of an operational interpretation (involving hypothesis testing) to differential privacy and the use of the corresponding data processing inequalities. Our result improves over the state of the art and has immediate applications to several problems studied in the literature.
RIS
TY - CPAPER TI - The Composition Theorem for Differential Privacy AU - Peter Kairouz AU - Sewoong Oh AU - Pramod Viswanath BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-kairouz15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 1376 EP - 1385 L1 - http://proceedings.mlr.press/v37/kairouz15.pdf UR - https://proceedings.mlr.press/v37/kairouz15.html AB - Interactive querying of a database degrades the privacy level. In this paper we answer the fundamental question of characterizing the level of privacy degradation as a function of the number of adaptive interactions and the differential privacy levels maintained by the individual queries. Our solution is complete: the privacy degradation guarantee is true for every privacy mechanism, and further, we demonstrate a sequence of privacy mechanisms that do degrade in the characterized manner. The key innovation is the introduction of an operational interpretation (involving hypothesis testing) to differential privacy and the use of the corresponding data processing inequalities. Our result improves over the state of the art and has immediate applications to several problems studied in the literature. ER -
APA
Kairouz, P., Oh, S. & Viswanath, P.. (2015). The Composition Theorem for Differential Privacy. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:1376-1385 Available from https://proceedings.mlr.press/v37/kairouz15.html.

Related Material