Answering $n^2+o(1)$ Counting Queries with Differential Privacy is Hard

DOI10.1137/130928121zbMath1339.68069arXiv1207.6945OpenAlexW2344443389MaRDI QIDQ2805511

Jonathan R. Ullman

Publication date: 12 May 2016

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

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

zbMATH Keywords

cryptographytraitor tracingdifferential privacy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Authentication, digital signatures and secret sharing (94A62)

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Faster Algorithms for Privately Releasing Marginals
• Privately Releasing Conjunctions and the Statistical Query Barrier
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• PCPs and the Hardness of Generating Private Synthetic Data
• Fully Collusion Resistant Traitor Tracing with Short Ciphertexts and Private Keys
• Collusion-secure fingerprinting for digital data
• On the complexity of differentially private data release
• Fingerprinting codes and the price of approximate differential privacy
• Pseudorandom generators with long stretch and low locality from random local one-way functions
• Theory of Cryptography
• Optimal probabilistic fingerprint codes