Differentially Private SQL with Bounded User Contribution

By Royce J. Wilson, Ce Zhang, William K. C. Lam, Damien Desfontaines, Daniel Simmons-Marengo, Bryant Gipson. 2019

173 citations recorded by the source corpus.

Abstract Differential privacy (DP) provides formal guarantees that the output of a database query does not reveal too much information about any individual present in the database. While many differentially private algorithms have been proposed in the scientific literature, there are only a few end-to-end implementations of differentially private query engines. Crucially, existing systems assume that each individual is associated with at most one database record, which is unrealistic in practice. We propose a generic and scalable method to perform differentially private aggregations on databases, even when individuals can each be associated with arbitrarily many rows. We express this method as an operator in relational algebra, and implement it in an SQL engine. To validate this system, we test the utility of typical queries on industry benchmarks, and verify its correctness with a stochastic test framework we developed. We highlight the promises and pitfalls learned when deploying such a system in practice, and we publish its core components as open-source software.

Subfields: Artificial Intelligence, Sociology and Political Science

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

Citations in the corpus

Differentially Private Set Union (2020, methodology): “Additional applications of this problem include the release of search queries and keys in SQL queries Korolova et al. [2009], Wilson et al. [2020].”
Google COVID-19 Community Mobility Reports: Anonymization Process Description (version 1.0) (2020, methodology): “We also bound the contribution of each LH user to 4 <category,location> pairs per day and per geographic level, using a process similar to the one described in this paper [6]: if an LH user contributes to more than 4 pairs in a given day and given geographic level, we randomly select 4 of them, and ”
Google COVID-19 Community Mobility Reports: Anonymization Process Description (version 1.1) (2020, methodology): “We also bound the contribution of each LH user to 4 〈category,location〉 pairs per day and per geographic level, using a process similar to the one described in this paper [6]: if an LH user contributes to more than 4 pairs in a given day and given geographic level, we randomly select 4 of them, and ”
LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale (2020, background): “In this less restrictive privacy setting, the main industrial differential privacy systems include Microsoft’s PINQ [6], Uber’s FLEX for its internal analytics [7], LinkedIn’s PriPeARL for its ad analytics [8], Google’s recent differential privacy open source project [9, 10], and the 2020 U.”
Efficient Differentially Private F0 Linear Sketching (2020, background): “It is known that differential privacy comes with pitfalls [28], but work in the database community has led to privacy-preserving database systems supporting (limited) SQL, see e.g. [32, 46] and their references.”