Differential Privacy

I’m low-key. I like my privacy—Kemba Walker.

Avrim Blum, Irit Dinur, Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith, received the ACM 2021 Paris Kanellakis Theory and Practice Award. They worked on and studied the notion of differential privacy.

Privacy

One of the key advances of modern cryptography is its ability to define new types of security. One can be pretty naive in defining simple notions of security. For example, it is not too hard to get correct the notion: Given the encrypted message one cannot easily determine without knowing the key . However, things are much more complex when we wish to define more complex notions.

This happens with notions of privacy. Differential privacy is a framework for reasoning about statistical databases. Imagine you have two otherwise identical databases, one with your personal information in it, and one without it. Differential Privacy ensures that the probability that a statistical query will produce a given result is (nearly) the same whether it’s conducted on the first or second database.

Perhaps a concrete question will help: How can we use data to learn about a population, without learning about specific individuals within the population? Consider these two questions:

1. “How many people live in Vermont?”
2. “How many people named Joe Smith live in Vermont?”

The first reveals a property of the whole population, while the second reveals information about one person. We need to be able to learn about trends in the population while preventing the ability to learn anything new about a particular individual. This is the goal of many statistical analyses of data, such as the statistics published by the U.S. Census Bureau. This is what differential privacy is all about.

The Award

From the award citation:

Differential privacy is a definition and framework for reasoning about privacy in statistical databases. While the privacy of individuals contributing to a dataset has been a long-standing concern, prior to the Kanellakis recipients’ work, computer scientists only knew how to mitigate several specific privacy attacks via a disparate set of techniques. The foundation for differential privacy emerged in the early 2000’s from several key papers. At the ACM Symposium on the Principles of Database Systems (PODS 2003) Dinur and Nissim presented a paper which showed that any technique that allows reasonably accurate answers to a large number of queries is inherently non-private.

Later, a sequence of papers by Dwork and Nissim at the International Conference on Cryptology (Crypto 2004); as well as Blum, Dwork, McSherry, and Nissim at the ACM Symposium on the Principles of Database Systems (PODS 2005); and Dwork, McSherry, Nissim, and Smith at the Theory of Cryptology Conference (TCC 2006) further defined and studied the notion of differential privacy.

Look at the article for more discussion of what it is all about.

Open Problems

We wish Avrim, Irit, Cynthia, Frank, Kobbi, and Adam congrats on their well deserved award.