Formalizing Privacy-Utility trade-offs

Mukund Sundararajan




Wednesday, Jan 13, 2010
4:30 - 5:30 PM
Terman Engineering Center, Room 453


Abstract:


Abstract: A mechanism for releasing statistical information about sensitive data must resolve a trade-off between utility to the information consumer and the privacy to the database participants. (Think of a situation where Stanford releases the average salary of its employees.) We formalize privacy as 'differential privacy', a well-studied, cryptographic definition of privacy (see for instance, Dwork[08]) . Typically, mechanisms will satisfy this definition of privacy by adding noise to the query result, thereby introducing inaccuracies. We propose a decision-theoretic definition of utility by modeling the information consumer as a rational agent with side-information about the query result and a loss-function that models its tolerance to inaccuracies. Our model encompasses both Bayesian and Minimax models.
Our main result is that for each fixed counting query and differential privacy level, there is a single mechanism that is \emph{simultaneously} utility-maximizing for every possible information consumer.
We discuss why is such simultanesous optimality possible.
Joint work with Arpita Ghosh and Tim Roughgarden.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html