On sampling, anonymization, and differential privacy or, k-anonymization meets differential privacy

By Ninghui Li, Wahbeh H. Qardaji, Dong Su. 2011

306 citations recorded by the source corpus.

This paper aims at answering the following two questions in privacy-preserving data analysis and publishing. The first is: What formal privacy guarantee (if any) does k-anonymization methods provide? k-Anonymization methods have been studied extensively in the database community, but have been known to lack strong privacy guarantees. The second question is: How can we benefit from the adversary's uncertainty about the data? More specifically, can we come up a meaningful relaxation of differential privacy [2, 3] by exploiting the adversary's uncertainty about the dataset? We now discuss these two motivations in more detail.

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 "Draw and Discard" Machine Learning (2018, background): “…of [19]; for the second – from the similarities between DDML and the shufﬂing strategy of [6] and privacy ampliﬁcation by sampling exploited by [32], [47], [1]; for the third – from recent work in differentially private machine learning [1], [20], [37], [50] that beneﬁts from analyses using…”
Prochlo: Strong Privacy for Analytics in the Crowd (2017, background): “, a crowd), for reports to blend into [10, 33, 45].”
Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences (2018, background): “It is also interesting to note that the non-linear relation ε (cid:48) = log(1 + η ( e ε − 1)) already appears in some existing privacy ampliﬁcation results (e.g. Li et al. [2012]).”
Differentially Private Model Publishing for Deep Learning (2019, background): “It has been shown in [27] that running an ( , δ) differentially private mechanism over a set of examples each of which is independently sampled with probability q (0 < q < 1) achieves (log(1+ q(e − 1)), qδ)-DP.”
$\textsf{LoPub}$ : High-Dimensional Crowdsourced Data Publication With Local Differential Privacy (2016, methodology): “Figures 22, 23, and 24 show the average accurate SVM classiﬁcation rate on three datasets Retail , Adult and TPC-E .”
On the Theory and Practice of Privacy-Preserving Bayesian Data Analysis (2016, background): “Alternatively, a random scan Gibbs sampler, which updates a random Q out of N θ l ’s, is 4 (cid:52) log Pr ( θ, X ) -differentially private from the privacy ampliﬁcation beneﬁt of subsampling data (Li et al., 2012).”
Structural Data De-anonymization: Quantification, Practice, and Implications (2014, methodology): “, k-anonymity and its variants [6][7][8], were designed(1).”
Poission Subsampled Rényi Differential Privacy (2019, methodology): “The privacy amplification lemma was derived in (Kasiviswanathan et al., 2011; Beimel et al., 2013; Li et al., 2012), where all three authors adopted what Balle et al. (2018) calls Poisson subsampling: Definition 3 (PoissonSample).”
Towards Measuring Membership Privacy (2017, background): “Follow-up works on DP try to relax the background knowledge by building more realistic background knowledge models [6, 21, 23, 27, 41].”
Deep Learning with Gaussian Differential Privacy (2019, unknown): “In the case where the original algorithm M is ( ε, δ )-DP, this privacy bound strictly improves on the subsampling theorem for ( ε, δ )-DP [36].”
Privacy at Scale: Local Differential Privacy in Practice (2018, background): “The advantage comes from several key observations including privacy amplification under sampling, which is known to hold in the centralized DP setting [16].”
Locally Differentially Private Frequent Itemset Mining (2018, methodology): “This effect has been observed and studied in the standard DP setting [25]: If one applies an algorithm to a dataset randomly sampled from the input with a sampling rate of β < 1, to satisfy -DP, the algorithm can use a privacy budget of ′ such that e ′ −1 e −1 = 1 β .”
PROCHLO: Strong Privacy for Analytics in the Crowd (2017, background): “, a crowd), for reports to blend into [10, 33, 45].”
Technical Privacy Metrics (2015, methodology): “To increase the size of equivalence classes to a minimum of k rows, several algorithms exist to transform a given database to make it k-anonymous, for example, using suppression or generalization [107] or random sampling [81] (the latter is interesting because it also satisfies approximate different”