Kobbi Nissim

ACM Paris Kanellakis Theory and Practice Award

USA - 2021

citation

For the formulation and development of the theory of differential privacy and its application to preserving privacy in statistical databases

The theory of differential privacy gives a conceptually new, simple, and mathematically rigorous definition of privacy that allows for the development of mechanisms which provably protect individual information while at the same time enabling statistical analyses of databases. A sequence of papers by Avrim Blum, Irit Dinur, Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith introduced this theory and showed how it could be extended to a wide range of applications.

Differential privacy has important advantages over previously used methods: it requires no assumptions about the knowledge of the attacker and its computational capabilities; and it allows for formal analysis of privacy under composition. It is relatively easy to explain and use and has broad applicability. Differential privacy has been employed by a number of large companies and start-ups and notably the 2020 US Census, to make available data for analyses, including machine learning, with applications from marketing to social science research.

Press Release

2021 ACM Paris Kanellakis Theory and Practice Award

Avrim Blum, Toyota Technological Institute at Chicago; Irit Dinur, Weizmann Institute; Cynthia Dwork, Harvard University; Frank McSherry, Materialize Inc.; Kobbi Nissim, Georgetown University; and Adam Davison Smith, Boston University, receive the ACM Paris Kanellakis Theory and Practice Award for their fundamental contributions to the development of differential privacy.

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.

These separate but related papers formed a definition of differential privacy which captures the kind of privacy needed in statistical settings, where individual information must be protected while still allowing for discovery of common trends. These fundamental works created a vibrant and multidisciplinary area of research, leading to practical deployments of Differential Privacy in industry and by the U.S. Census Bureau, among other applications.

The authors also showed that their definition includes post-processing and composition properties that facilitate design, analysis, and applications of differentially private algorithms. The Laplace and the Gaussian noise mechanisms, which show differentially private analogs of statistical query learning algorithms, also grew out of the Kanellakis recipients’ work on differential privacy.