2016

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

Bun, Mark, Steinke, Thomas, Ullman, Jonathan

Understand

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.

Randomized response: A survey technique for eliminating evasive answer bias
Stanley L. Warner · 1965
Earlier work this paper cites.
Collusion-secure fingerprinting for digital data
Dan Boneh and James Shaw · 1998
Earlier work this paper cites.
Revealing information while preserving privacy
Irit Dinur and Kobbi Nissim · 2003
Earlier work this paper cites.
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith · 2006
Earlier work this paper cites.
New efficient attacks on statistical disclosure control mechanisms
Cynthia Dwork and Sergey Yekhanin · 2008
Earlier work this paper cites.
Optimal probabilistic fingerprint codes
Gábor Tardos · 2008
Earlier work this paper cites.
Differential privacy and robust statistics
Cynthia Dwork and Jing Lei · 2009
Earlier work this paper cites.
On the complexity of differentially private data release: efficient algorithms and hardness results
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan · 2009
Earlier work this paper cites.
Differential privacy under continual observation
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum · 2010
Earlier work this paper cites.

Boosting and differential privacy
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan · 2010
Cited alongside, same era.
A multiplicative weights mechanism for privacy-preserving data analysis
Moritz Hardt and Guy N. Rothblum · 2010
Cited alongside, same era.
On the geometry of differential privacy
Moritz Hardt and Kunal Talwar · 2010
Cited alongside, same era.
Interactive privacy via the median mechanism
Aaron Roth and Tim Roughgarden · 2010
Cited alongside, same era.
Private and continual release of statistics
T.-H. Hubert Chan, Elaine Shi, and Dawn Song · 2011
Cited alongside, same era.
A learning theory approach to noninteractive database privacy
Avrim Blum, Katrina Ligett, and Aaron Roth · 2013
Cited alongside, same era.
Private learning and sanitization: Pure vs. approximate differential privacy
Amos Beimel, Kobbi Nissim, and Uri Stemmer · 2013
Cited alongside, same era.
Answering n 2 + o ⁡ ( 1 ) n^{2+o(1)} counting queries with differential privacy is hard
Jonathan Ullman · 2013
Cited alongside, same era.
Fingerprinting codes and the price of approximate differential privacy
Mark Bun, Jonathan Ullman, and Salil P. Vadhan · 2014
Cited alongside, same era.

The algorithmic foundations of differential privacy
Cynthia Dwork and Aaron Roth · 2014
Later among the works it cites.
Preventing false discovery in interactive data analysis is hard
Moritz Hardt and Jonathan Ullman · 2014
Later among the works it cites.
Differentially private release and learning of threshold functions
Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan · 2015
Later among the works it cites.
Preserving statistical validity in adaptive data analysis
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth · 2015
Later among the works it cites.
Pure differential privacy for rectangle queries via private partitions
Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N. Rothblum · 2015
Later among the works it cites.
Robust traceability from trace amounts
Cynthia Dwork, Adam D. Smith, Thomas Steinke, Jonathan Ullman, and Salil P. Vadhan · 2015
Later among the works it cites.
Between pure and approximate differential privacy
Original
Thomas Steinke and Jonathan Ullman · 2015
Later among the works it cites.
Interactive fingerprinting codes and the hardness of preventing false discovery
Thomas Steinke and Jonathan Ullman · 2015
Later among the works it cites.
Algorithmic stability for adaptive data analysis
Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman · 2016
Closest in time.

alphaXiv searches the wider corpus for related work and actual follow-ups.

alphaXiv is searching for related work…

Reading the bibliography…