%0 Journal Article %1 bun2013fingerprinting %A Bun, Mark %A Ullman, Jonathan %A Vadhan, Salil %D 2013 %K differential-privacy %T Fingerprinting Codes and the Price of Approximate Differential Privacy %U http://arxiv.org/abs/1311.3158 %X We show new lower bounds on the sample complexity of $(\varepsilon, \delta)$-differentially private algorithms that accurately answer large sets of counting queries. A counting query on a database $D (\0,1\^d)^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 $nd$ counting queries on $D$ to within error $\alpha$ it is necessary that $$ n Ømega\Bigg(\sqrtd łog |Q|\alpha^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, \delta)$-differential privacy is asymptotically larger than what is required merely for accuracy, which is $O(|Q| / \alpha^2)$. In addition, we show that our lower bound holds for the specific case of $k$-way marginal queries (where $|Q| = 2^k dk$) when $\alpha$ is not too small compared to $d$ (e.g. when $\alpha$ 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.

@article{bun2013fingerprinting, abstract = {We show new lower bounds on the sample complexity of $(\varepsilon, \delta)$-differentially private algorithms that accurately answer large sets of counting queries. A counting query on a database $D \in (\{0,1\}^d)^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 $\mathcal{Q}$ of $\gg nd$ counting queries on $D$ to within error $\pm \alpha$ it is necessary that $$ n \geq \tilde{\Omega}\Bigg(\frac{\sqrt{d} \log |\mathcal{Q}|}{\alpha^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, \delta)$-differential privacy is asymptotically larger than what is required merely for accuracy, which is $O(\log |\mathcal{Q}| / \alpha^2)$. In addition, we show that our lower bound holds for the specific case of $k$-way marginal queries (where $|\mathcal{Q}| = 2^k \binom{d}{k}$) when $\alpha$ is not too small compared to $d$ (e.g. when $\alpha$ is any fixed constant). Our results rely on the existence of short \emph{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.}, added-at = {2019-06-04T13:54:46.000+0200}, author = {Bun, Mark and Ullman, Jonathan and Vadhan, Salil}, biburl = {https://www.bibsonomy.org/bibtex/24b73e0a741587b5fdf456d4dd9497b06/kirk86}, description = {[1311.3158] Fingerprinting Codes and the Price of Approximate Differential Privacy}, interhash = {2f15a66fb223c7f950734edf6af6452b}, intrahash = {4b73e0a741587b5fdf456d4dd9497b06}, keywords = {differential-privacy}, note = {cite arxiv:1311.3158Comment: Full version of our STOC 2014 paper. To appear in SIAM Journal on Computing}, timestamp = {2019-06-04T13:54:46.000+0200}, title = {Fingerprinting Codes and the Price of Approximate Differential Privacy}, url = {http://arxiv.org/abs/1311.3158}, year = 2013 }