Gautam Kamath and colleagues win 2024 Caspar Bowden PET Award

University of Waterloo Professor Gautam Kamath, along with his colleagues Professor Clément Canonne at the University of Sydney and Thomas Steinke, a Research Scientist at Google DeepMind, have been awarded the 2024 Caspar Bowden Award for Outstanding Research in Privacy Enhancing Technologies. The prestigious recognition was given to the team for their paper, “The Discrete Gaussian for Differential Privacy,” research that was presented initially at NeurIPS 2020 and published in the Journal of Privacy and Confidentiality.

The Caspar Bowden Award for Outstanding Research in Privacy Enhancing Technologies, established in 2003, recognizes researchers who have made an outstanding contribution to the theory, design, implementation, or deployment of privacy enhancing technologies. Presented at the Privacy Enhancing Technologies Symposium, the award includes a $3,000 USD cash prize and a monument.

“Congratulations to Gautam and his colleagues Clément and Thomas on their receiving this prestigious PET Award,” said Raouf Boutaba, University Professor and Director of the Cheriton School of Computer Science. “Their groundbreaking work in differential privacy was quickly adopted and has already seen significant real-world impact. It was deployed in the 2020 US Census as the key primitive underlying the Disclosure Avoidance System, the most high-profile deployment of differential privacy to date.”

This research introduced a new mechanism for releasing data subject to differential privacy. The algorithm developed by the research team was deployed in the 2020 US Census, protecting the confidential data of more than 300 million people in the United States. 

“This discrete Gaussian paper is one of the most important papers for differential privacy deployment of all time,” wrote Daniel Kifer, Professor of Computer Science at Pennsylvania State University, in his nomination statement. “It provides exact and provably secure algorithms for sampling from the discrete Laplace and discrete Gaussian distributions. There are very few papers that go from theory to practice, and this one was adopted right away and had immense practical impact.”

Differential privacy provides a rigorous standard ensuring that the output of an algorithm does not reveal private details about the individuals contained in its input data. A standard method to ensure differential privacy involves evaluating a function on the input, then adding a small amount of random noise from a Laplace or a Gaussian distribution to the result before releasing it. This noise is scaled according to the sensitivity of the function — by how much one person’s data can change the function value. 

Laplace and Gaussian distributions, however, are continuous. They are comprised of real numbers. Finite computers cannot exactly represent samples from continuous distributions, let alone produce such a sample. Although this may appear to be of only theoretical interest this is not the case. Computer scientist Ilya Mironov showed that a naive use of finite-precision approximations can cause catastrophic privacy failures. By examining the low-order bits of the noisy output, the noiseless value often can be determined, allowing the entire input dataset to be reconstructed while only a negligible privacy loss is recorded by the system. Despite this flaw, the methods continue to be used in open source implementations of differentially private mechanisms. Safe and practical solutions to deploy differentially private systems in real-world privacy-critical settings is very much needed.

With these shortcomings in mind, the researchers considered how to securely implement these basic differentially private methods on finite computers that cannot faithfully represent real numbers. One solution involves sampling from a discrete distribution that can be sampled on a finite computer. For many natural queries, the output of the function to be computed is naturally discrete — such as simply counting how many records are in a dataset — so accuracy is not lost when adding discrete noise to it. 

The discrete Laplace distribution (also known as the two-sided geometric distribution) is the natural discrete analogue of the continuous Laplace distribution. However, the continuous Gaussian distribution has many advantages over the continuous Laplace distribution, making it better suited for many applications. 

For example, the Gaussian distribution has lighter tails than the Laplace distribution. In settings with a high degree of composition — answering many queries with independent noise rather than a single query — the scale of Gaussian noise is lower than the scale of Laplace noise required for a comparable privacy guarantee. The privacy analysis under composition of Gaussian noise addition is typically simpler and sharper. These privacy guarantees can be expressed cleanly in terms of concentrated differential privacy and related variants of differential privacy. Thus, it is natural to consider whether a discretization of the Gaussian distribution retains the privacy and utility properties of the continuous Gaussian distribution, as is the case for the Laplace distribution. In their paper, the researchers show that this is indeed the case.

The research team’s investigations focused on three aspects of the discrete Gaussian: privacy, utility, and sampling. They demonstrated that the discrete Gaussian provides the same level of privacy and utility as the continuous Gaussian. They also show that it can be efficiently sampled on a finite computer, addressing the shortcomings of continuous distributions. Additionally, they also proved and empirically demonstrated several additional properties of the discrete Gaussian of interest and use to those deploying it to preserve data privacy.

To learn more about the research on which this article is based, please see to Clément L. Canonne, Gautam Kamath, and Thomas Steinke. 2022. The Discrete Gaussian for Differential Privacy. Journal of Privacy and Confidentiality 12 (1). https://doi.org/10.29012/jpc.784.