Make Up Your Mind: The Price of Online Queries in Differential Privacy

DOI10.1137/1.9781611974782.85zbMATH Open1410.68111arXiv1604.04618OpenAlexW2340730520MaRDI QIDQ4575828FDOQ4575828

Authors: Mark Bun, Thomas Steinke, Jonathan Ullman 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We consider the problem of answering queries about a sensitive dataset subject to differential privacy. The queries may be chosen adversarially from a larger set Q of allowable queries in one of three ways, which we list in order from easiest to hardest to answer: Offline: The queries are chosen all at once and the differentially private mechanism answers the queries in a single batch. Online: The queries are chosen all at once, but the mechanism only receives the queries in a streaming fashion and must answer each query before seeing the next query. Adaptive: The queries are chosen one at a time and the mechanism must answer each query before the next query is chosen. In particular, each query may depend on the answers given to previous queries. Many differentially private mechanisms are just as efficient in the adaptive model as they are in the offline model. Meanwhile, most lower bounds for differential privacy hold in the offline setting. This suggests that the three models may be equivalent. We prove that these models are all, in fact, distinct. Specifically, we show that there is a family of statistical queries such that exponentially more queries from this family can be answered in the offline model than in the online model. We also exhibit a family of search queries such that exponentially more queries from this family can be answered in the online model than in the adaptive model. We also investigate whether such separations might hold for simple queries like threshold queries over the real line.

Full work available at URL: https://arxiv.org/abs/1604.04618

Recommendations

• The optimal upper bound of the number of queries for Laplace mechanism under differential privacy
• Near-optimal differentially private mechanism for linear queries
• Differential privacy and the fat-shattering dimension of linear queries
• Approximately optimal mechanism design via differential privacy
• Differential Privacy: A Survey of Results
• Unconditional differentially private mechanisms for linear queries
• Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy
• The Differential Privacy Frontier (Extended Abstract)

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Data encryption (aspects in computer science) (68P25)

Cited In (2)

• On differential privacy and adaptive data analysis with bounded space
• Stability is stable: connections between replicability, privacy, and adaptive generalization

This page was built for publication: Make Up Your Mind: The Price of Online Queries in Differential Privacy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575828)