Fingerprinting codes and the price of approximate differential privacy

DOI10.1137/15M1033587zbMATH Open1402.68071arXiv1311.3158OpenAlexW2898996243MaRDI QIDQ4554072FDOQ4554072

Authors: Mark Bun, Jonathan Ullman, Salil Vadhan 

Publication date: 7 November 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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 $Din({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 $mathcalQ$ of $ggnd$ counting queries on $D$ to within error $pmalpha$ it is necessary that ${\displaystyle }$ n geq ilde{Omega}Bigg(frac{sqrt{d} log |mathcal{Q}|}{alpha^2 varepsilon} Bigg). ${\displaystyle }$ 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|mathcalQ|/alph{a}^2)$. In addition, we show that our lower bound holds for the specific case of $k$-way marginal queries (where $$) 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.

Full work available at URL: https://arxiv.org/abs/1311.3158

Recommendations

• Fingerprinting codes and the price of approximate differential privacy
• Lower bounds in differential privacy
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Faster private release of marginals on small databases
• Answering \(n^2+o(1)\) counting queries with differential privacy is hard

zbMATH Keywords

differential privacyfingerprinting codesprivacy attacks

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15) Authentication, digital signatures and secret sharing (94A62)

Cites Work

• Theory of Cryptography
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower bounds in differential privacy
• Iterative Constructions and Private Data Release
• Differential privacy and the fat-shattering dimension of linear queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release, efficient algorithms and hardness results
• Title not available (Why is that?)
• Collusion-secure fingerprinting for digital data
• Neural Network Learning
• Advances in Cryptology – CRYPTO 2004
• Title not available (Why is that?)
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• What can we learn privately?
• Title not available (Why is that?)
• Preserving statistical validity in adaptive data analysis (extended abstract)
• Algorithmic stability for adaptive data analysis
• Bounds on the sample complexity for private learning and private data release
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Optimal probabilistic fingerprint codes
• Row products of random matrices
• Characterizing the sample complexity of private learners
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Analyze Gauss: optimal bounds for privacy-preserving principal component analysis
• Efficient algorithms for privately releasing marginals via convex relaxations
• Pcps and the hardness of generating private synthetic data
• The complexity of computing the optimal composition of differential privacy

Cited In (6)

• Structure and sensitivity in differential privacy: comparing \(K\)-norm mechanisms
• Fingerprinting codes and the price of approximate differential privacy
• An improved private mechanism for small databases
• Differentially private range query on shortest paths
• Lower bounds in differential privacy
• Stability is stable: connections between replicability, privacy, and adaptive generalization

Uses Software

• SuLQ

This page was built for publication: Fingerprinting codes and the price of approximate differential privacy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554072)