A learning theory approach to non-interactive database privacy

By Avrim Blum, Katrina Ligett, Aaron Roth. 2008

559 citations recorded by the source corpus.

We demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class with polynomial VC-dimension. We show a new lower bound for releasing databases that are useful for halfspace queries over a continuous domain. Despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, for a slightly relaxed definition of usefulness. Inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical Learning Theory, Privacy & Security

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 Computational Theory and Mathematics

In Statistical Learning Theory

In Privacy & Security

Citations in the corpus

Pure Differentially Private Summation from Anonymous Messages (2020, background): “Private summation is also closely related to functions in the widely studied class of counting queries (e.g., [Vad17, BLR08, HT10, HR10, NTZ13]).”
Differential Privacy for Growing Databases (2018, methodology): “If the queries are known in advance, however, [BLR08] showed how to answer exponentially many queries relative to the database size for ﬁxed ǫ and α .”
Boosting and Differential Privacy (2010, background): “(Previously, Roth and Roughgarden [22] gave such an interactive mechanism that achieved similar accuracy and efficiency to [3].”
Privacy Aware Learning (2012, background): “[5] also give lower bounds on the closeness of certain statistical quantities computed from the dataset, though their upper and lower bounds do not match.”
On the Difficulties of Disclosure Prevention in Statistical Databases or The Case for Differential Privacy (2010, background): “See also [30, 28, 5, 4, 30, 3, 27] for other works dealing with the notion.”
Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning (2009, background): “In this paper we consider e cient mechanisms for private SVM learning, whose range spaces parametrize real-valued functions (whose sign form trained classi ers).”
Distributed Private Data Analysis: On Simultaneously Solving How and What (2008, background): “It has been demonstrated that differentially private analyses exist for a variety of tasks including the approximation of numerical functions (by adding carefully chosen random noise that conceals any single individual’s contribution) [11, 2, 22, 17], non-numerical analyses [20], datamining [2, 22],”
On the geometry of differential privacy (2009, background): “Blum, Ligett and Roth [BLR08] show that it is possible to release approximate counts for all concepts in a concept class C on { 0 , 1 } m with error O (( N 2 m VCDim( C ) /ε ) 13 ), where VCDim( C ) is the VC dimension of the concept class.”
Minimax Optimal Procedures for Locally Private Estimation (2016, background): “…requires a formal definition of privacy, and differential privacy has been put forth as one such candidate (see, e.g., the articles Dwork et al. 2006; Blum, Ligett, and Roth 2008; Dwork, Rothblum, and Vadhan 2010; Hardt and Rothblum 2010; Hardt and Talwar 2010, and references therein).”
Universally utility-maximizing privacy mechanisms (2008, background): “The diﬀerential privacy literature [10, 8, 16, 18, 5, 7, 12, 4] has proposed a rigorous and quantiﬁable deﬁnition of privacy, as well as provably privacy-preserving mechanisms for diverse applications including statistical queries, machine learning, and pricing.”
Composition attacks and auxiliary information in data privacy (2008, background): “Recent work has greatly expanded the applicability of differential privacy and its relaxations, both in the theoretical [16, 6, 15, 4, 30, 7] and applied [18, 3, 27] literature.”
Fingerprinting codes and the price of approximate differential privacy (2013, background): “ve an algorithm|the so-called Laplace mechanism|whose sample complexity is O~(jQj1=2), and thus incurs a large price of dierential privacy. Fortunately, a remarkable result of Blum, Ligett, and Roth [BLR08] showed that the dependence on jQjcan be improved exponentially to O(dlogjQj) where dis the di”
Interactive privacy via the median mechanism (2009, methodology): “In particular, our dependence on the number of queries k nearly matches the optimal dependence of log k achieved in the offline setting by [BLR08].”