# Fingerprinting Codes and the Price of Approximate Differential Privacy

arXiv: https://arxiv.org/abs/1311.3158 · HTML: https://mlsanity.com/paper/1311.3158/

## Key facts

- Cited by 82 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2013.

## Built on by (most cited first, 30 of 82)

- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Harnessing large-language models to generate private synthetic text](https://mlsanity.com/paper/2306.01684/) (2023)
- [Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods](https://mlsanity.com/paper/2106.07153/) (2021)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [Composition of Differential Privacy & Privacy Amplification by Subsampling](https://mlsanity.com/paper/2210.00597/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021)
- [New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma](https://mlsanity.com/paper/2205.08532/) (2022)
- [On the Impossible Safety of Large AI Models](https://mlsanity.com/paper/2209.15259/) (2022)
- [On the Privacy-Robustness-Utility Trilemma in Distributed Learning](https://mlsanity.com/paper/2302.04787/) (2023)
- [Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning](https://mlsanity.com/paper/2303.07152/) (2023)
- [Unleashing the Power of Randomization in Auditing Differentially Private ML](https://mlsanity.com/paper/2305.18447/) (2023)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [Information Theoretic Lower Bounds for Information Theoretic Upper Bounds](https://mlsanity.com/paper/2302.04925/) (2023)
- [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023)
- [Privately Learning Subspaces](https://mlsanity.com/paper/2106.00001/) (2021)
- [Differential Privacy Over Riemannian Manifolds](https://mlsanity.com/paper/2111.02516/) (2021)
- [Parameters or Privacy: A Provable Tradeoff Between Overparameterization and Membership Inference](https://mlsanity.com/paper/2202.01243/) (2022)
- [Differentially Private Zeroth-Order Methods for Scalable Large Language Model Finetuning](https://mlsanity.com/paper/2402.07818/) (2024)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [Privately Learning Mixtures of Axis-Aligned Gaussians](https://mlsanity.com/paper/2106.02162/) (2021)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023)
- [Private learning implies quantum stability](https://mlsanity.com/paper/2102.07171/) (2021)
- [Differentially Private Coordinate Descent for Composite Empirical Risk Minimization](https://mlsanity.com/paper/2110.11688/) (2021)

## Abstract (arXiv)

We show new lower bounds on the sample complexity of (varepsilon, δ)-differentially private algorithms that accurately answer large sets of counting queries. A counting query on a database D ∈ (0,1d)n has the form "What fraction of the individual records in the database satisfy the property q?" We show that in order to answer an arbitrary set Q of gg nd counting queries on D to within error ± α it is necessary that  n ≥ tildeOmegaBigg(frac√d log |Q|α2 varepsilon Bigg).  This bound is optimal up to poly-logarithmic factors, as demonstrated by the Private Multiplicative Weights algorithm (Hardt and Rothblum, FOCS'10). In particular, our lower bound is the first to show that the sample complexity required for accuracy and (varepsilon, δ)-differential privacy is asymptotically larger than what is required merely for accuracy, which is O(log |Q| / α2). In addition, we show that our lower bound holds for the specific case of k-way marginal queries (where |Q| = 2k binomdk) when α is not too small compared to d (e.g. when α is any fixed constant). Our results rely on the existence of short fingerprinting codes (Boneh and Shaw, CRYPTO'95, Tardos, STOC'03), which we show are closely connected to the sample complexity of differentially private data release. We also give a new method for combining certain types of sample complexity lower bounds into stronger lower bounds.