Differential Privacy for the Analyst via Private Equilibrium Computation

Justin Hsu, Aaron Roth, Jonathan Ullman

We show how to answer 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. 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 may share information or register multiple accounts. In some settings, we are able to achieve nearly optimal error rates (even as compared to mechanisms which need not offer analyst privacy), and we are able to extend our techniques to give mechanisms which answer even non-linear queries. Our analysis is based on viewing and solving the private query-release problem as a two-player zero sum game, which may be of independent interest.