Concurrent Composition for Interactive Differential Privacy with Adaptive Privacy-Loss Parameters
Authors: 
Samuel Haney, Michael Shoemate, Grace Tian, Salil Vadhan, Andrew Vyrros, Vicki Xu, Wanrong ZhangAuthors Info & Claims
Pages 1949 - 1963
Abstract
In this paper, we study the concurrent composition of interactive mechanisms with adaptively chosen privacy-loss parameters. In this setting, the adversary can interleave queries to existing interactive mechanisms, as well as create new ones. We prove that every valid privacy filter and odometer for noninteractive mechanisms extends to the concurrent composition of interactive mechanisms if privacy loss is measured using (ε, δ)-DP, ƒ-DP, or Rényi DP of fixed order. Our results offer strong theoretical foundations for enabling full adaptivity in composing differentially private interactive mechanisms, showing that concurrency does not affect the privacy guarantees. We also provide an implementation for users to deploy in practice.
References
[1]
Skye Berghel, Philip Bohannon, Damien Desfontaines, Charles Estes, Sam Haney, Luke Hartman, Michael Hay, Ashwin Machanavajjhala, Tom Magerlein, Gerome Miklau, Amritha Pai, William Sexton, and Ruchit Shrestha. 2022. Tumult Analytics : a robust, easy-to-use, scalable, and expressive framework for differential privacy. arXiv preprint arXiv:2212.04133 (Dec. 2022).
[2]
Mark Bun and Thomas Steinke. 2016. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference. Springer, 635--658.
[3]
Jinshuo Dong, Aaron Roth, and Weijie J Su. 2019. Gaussian differential privacy. arXiv preprint arXiv:1905.02383 (2019).
[4]
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006. Our data, ourselves: Privacy via distributed noise generation. In Annual international conference on the theory and applications of cryptographic techniques. Springer, 486--503.
[5]
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. 2010a. Differential privacy under continual observation. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC '10). 715--724.
[6]
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan. 2009. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the 41st ACM Symposium on Theory of Computing (STOC '09). 381--390.
[7]
Cynthia Dwork and Aaron Roth. 2014. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, Vol. 9, 3--4 (2014), 211--407.
[8]
Cynthia Dwork and Guy N Rothblum. 2016. Concentrated differential privacy. arXiv preprint arXiv:1603.01887 (2016).
[9]
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. 2010b. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. IEEE, 51--60.
[10]
Vitaly Feldman and Tijana Zrnic. 2022. Individual Privacy Accounting via a Renyi Filter. arXiv preprint arXiv:2008.11193 (2022).
[11]
Marco Gaboardi, Michael Hay, and Salil Vadhan. 2020. A programming framework for opendp. Manuscript (2020).
[12]
Moritz Hardt and Guy N Rothblum. 2010. A multiplicative weights mechanism for privacy-preserving data analysis. In 2010 IEEE 51st annual symposium on foundations of computer science. IEEE, 61--70.
[13]
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2015. The composition theorem for differential privacy. In International conference on machine learning. PMLR, 1376--1385.
[14]
Tumult Labs. 2022. Tumult Analytics. https://tmlt.dev
[15]
Xin Lyu. 2022. Composition Theorems for Interactive Differential Privacy. In Thirty-sixth Conference on Neural Information Processing Systems.
[16]
Mathias Lécuyer. 2021. Practical Privacy Filters and Odometers with Rényi Differential Privacy and Applications to Differentially Private Deep Learning. arxiv: 2103.01379 [stat.ML]
[17]
Ilya Mironov. 2017. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF). IEEE, 263--275.
[18]
Jack Murtagh and Salil Vadhan. 2016. The complexity of computing the optimal composition of differential privacy. In Theory of Cryptography Conference. Springer, 157--175.
[19]
Alfréd Rényi. 1961. On measures of entropy and information. In Proceedings of the fourth Berkeley symposium on mathematical statistics and probability, Vol. 1. Berkeley, California, USA.
[20]
Ryan Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. 2021. Privacy Odometers and Filters: Pay-as-you-Go Composition. arxiv: 1605.08294 [cs.CR]
[21]
Salil Vadhan and Tianhao Wang. 2021. Concurrent Composition of Differential Privacy. In Theory of Cryptography Conference. Springer, 582--604.
[22]
Salil Vadhan and Wanrong Zhang. 2023. Concurrent Composition Theorems for Differential Privacy. In 55th Annual ACM Symposium on Theory of Computing.
[23]
Tim Van Erven and Peter Harremos. 2014. Rényi divergence and Kullback-Leibler divergence. IEEE Transactions on Information Theory, Vol. 60, 7 (2014), 3797--3820.
[24]
Justin Whitehouse, Aaditya Ramdas, Ryan Rogers, and Zhiwei Steven Wu. 2023. Fully Adaptive Composition in Differential Privacy. arxiv: 2203.05481 [cs.LG]
Index Terms
- Concurrent Composition for Interactive Differential Privacy with Adaptive Privacy-Loss Parameters
Recommendations
Concurrent Composition Theorems for Differential Privacy
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of ComputingWe study the concurrent composition properties of interactive differentially private mechanisms, whereby an adversary can arbitrarily interleave its queries to the different mechanisms. We prove that all composition theorems for non-interactive ...
Concurrent Composition of Differential Privacy
Theory of CryptographyAbstractWe initiate a study of the composition properties of interactive differentially private mechanisms. An interactive differentially private mechanism is an algorithm that allows an analyst to adaptively ask queries about a sensitive dataset, with ...
An Emerging Strategy for Privacy Preserving Databases: Differential Privacy
HCI for Cybersecurity, Privacy and TrustAbstractData De-identification and Differential Privacy are two possible approaches for providing data security and user privacy. Data de-identification is the process where the personal identifiable information of individuals is extracted to create ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2023
3722 pages
ISBN:9798400700507
DOI:10.1145/3576915
- General Chairs:
- Weizhi Meng,
- Christian D. Jensen,
- Program Chairs:
- Cas Cremers,
- Engin Kirda
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 November 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Science Foundation
- Simons Foundation
- Alfred P. Sloan Foundation
- Apple
- U.S. Census Bureau
- Computing Research Association
Conference
CCS '23
Sponsor:
CCS '23: ACM SIGSAC Conference on Computer and Communications Security
November 26 - 30, 2023
Copenhagen, Denmark
Acceptance Rates
Overall Acceptance Rate 1,261 of 6,999 submissions, 18%
Upcoming Conference
CCS '24
- Sponsor:
- sigsac
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 251Total Downloads
- Downloads (Last 12 months)251
- Downloads (Last 6 weeks)19
Reflects downloads up to 02 Oct 2024
Other Metrics
Citations
Cited By
View allView Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in