Title: Definitions Matter: Reconciling Differential and Adversarial Privacy
Abstract: Several well documented attacks in recent years have highlighted the dangers of publishing poorly anonymized data. Today, we have a wealth of anonymization techniques, but the question remains: when do we know that the data is truly anonymous and can be published? There have been two approaches to define a yardstick for anonymized data: in "adversarial privacy" one assumes an adversary and compares its prior and a posteriori probability distribution (requiring that they differ only slightly); in "differential privacy" one measures the difference in the output of an algorithm when one data item is inserted or removed from the database (also requiring that they differ only slightly). In this talk I will discuss the advantages and disadvantages of these two definitions, and will present a recent theoretical result that characterizes their relationship. As an application, I will describe an anonymization technique for privacy-preserving queries over social networks. Such queries require joins over the data, and the standard differentially private algorithm leads to very low utility; but by assuming a more realistic adversary, we can design a query perturbation technique that ensures quite practical utility for a class of conjunctive queries, and yet protects privacy against all but the most powerful adversaries. This work was done jointly with Vibhor Rastogi.
Bio: Dan Suciu is a Professor in Computer Science at the University of Washington. He received his Ph.D. from the University of Pennsylvania in 1995, then was a principal member of the technical staff at AT&T Labs until he joined the University of Washington in 2000. Suciu is conducting research in data management, with an emphasis on topics that arise from sharing data on the Internet, such as management of semistructured and heterogeneous data, data security, and managing data with uncertainties. He is a co-author of the book Data on the Web: from Relations to Semistructured Data and XML, holds twelve US patents, received the 2000 ACM SIGMOD Best Paper Award, is a recipient of the NSF Career Award and of an Alfred P. Sloan Fellowship.