Fingerprinting codes and the price of approximate differential privacy

DOI10.1137/15M1033587MaRDI QIDQ4554072zbMATH OpenOpenAlexFDO

Authors Mark Bun, Jonathan Ullman, Salil Vadhan

Publication date 7 November 2018

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

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

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)

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.

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

Cites work

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

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

Describes a project that uses

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)