Differential privacy for the analyst via private equilibrium computation

DOI10.1145/2488608.2488651zbMATH Open1293.68099arXiv1211.0877OpenAlexW2127208184MaRDI QIDQ5495804FDOQ5495804

Authors: Justin Hsu, Aaron Roth, Jonathan Ullman 

Publication date: 7 August 2014

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Abstract: We give new mechanisms for answering exponentially many queries from multiple analysts on a private database, while protecting differential privacy both for the individuals in the database and for the analysts. That is, our mechanism's answer to each query is nearly insensitive to changes in the queries asked by other analysts. Our mechanism is the first to offer differential privacy on the joint distribution over analysts' answers, providing privacy for data analysts even if the other data analysts collude or register multiple accounts. In some settings, we are able to achieve nearly optimal error rates (even compared to mechanisms which do not offer analyst privacy), and we are able to extend our techniques to handle non-linear queries. Our analysis is based on a novel view of the private query-release problem as a two-player zero-sum game, which may be of independent interest.

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

Recommendations

• The algorithmic foundations of differential privacy
• Universally utility-maximizing privacy mechanisms
• Universally utility-maximizing privacy mechanisms
• Differential Privacy
• A statistical framework for differential privacy

zbMATH Keywords

Bregman projectiondifferential privacyzero-sum gameno-regret learninganalyst privacy

Mathematics Subject Classification ID

Applications of game theory (91A80) 2-person games (91A05) Database theory (68P15) Authentication, digital signatures and secret sharing (94A62)

Cited In (4)

• Differentially private distributed algorithms for stochastic aggregative games
• Private matchings and allocations
• Computing payoff allocations in the approximate core of linear programming games in a privacy-preserving manner
• Concurrent composition of differential privacy

This page was built for publication: Differential privacy for the analyst via private equilibrium computation

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