FINGERPRINTING CODES AND THE PRICE OF APPROXIMATE DIFFERENTIAL PRIVACY∗

By Mark Bun. 2018

How researchers see this paper

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

Citations in the corpus

Tight Lower Bounds for Differentially Private Selection (2017, methodology): “Our argument is closely related to the work on tracing attacks [HSR + 08, SOJH09, BUV14, SU17, DSS + 15, BSU17, DSSU17].”
Between Pure and Approximate Differential Privacy (2015, methodology): “In particular, Bun et al. [BUV14] showed that ﬁngerprinting codes can be used to construct an attack demonstrating that any mechanism that accurately answers one-way marginals is not di ﬀ eren-tially private.”
Make Up Your Mind: The Price of Online Queries in Differential Privacy (2016, background): “To prove the online lower bound, we build on a lower bound for marginal queries [BUV14], which is based on the existence of short secure ﬁngerprinting codes [BS98, Tar08].”
Generalized Gaussian Mechanism for Differential Privacy (2016, background): “…complexity – the required sample size n to reach a certain level of accuracy α and privacy guarantee ( (cid:15), δ ) for count queries [18, 23, 24]. α often refers to the accuracy of perturbed results in the DP literature, such as the worst case accuracy L ∞ or average accuracy L 1 , and…”
When is memorization of irrelevant training data necessary for high-accuracy learning? (2020, background): “In itself, that is nothing new: there is a long line of work on diﬀerentially private learning (e.g., [8, 25]), including a number of striking separations from nonprivate algorithms [11, 5, 2].”
Differentially Private Fine-tuning of Language Models (2021, background): “A randomized algorithm A is ( ε , δ )-differentially private if for any two neighboring datasets D and D (cid:48) , which differ in exactly the data pertaining to a single user, and for all sets S of possible outputs: We review prior techniques for private ﬁne-tuning.”
Privately Learning High-Dimensional Distributions (2018, methodology): “To privately estimate the mean of this distribution up to ± α per coordinate, it is necessary [BUV14, SU17a] and suﬃcient [BDMN05, DMNS06] to have n = Θ( 1 α 2 + √ ) samples from the distribution, whereas Θ( 1 α 2 ) samples are necessary and suﬃcient without privacy.”
Differentially Private Assouad, Fano, and Le Cam (2020, methodology): “These include packing argument [HT10, Vad17, Val12, BKN10], ﬁngerprinting [BNSV15, SU17, SU15, BSU17, BUV18, KLSU19] and coupling based arguments [ASZ18, KV18].”