Answering n^2+o(1) counting queries with differential privacy is hard

DOI10.1137/130928121zbMATH Open1339.68069arXiv1207.6945OpenAlexW2344443389MaRDI QIDQ2805511FDOQ2805511

Authors: Jonathan Ullman 

Publication date: 12 May 2016

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

Abstract: A central problem in differentially private data analysis is how to design efficient algorithms capable of answering large numbers of counting queries on a sensitive database. Counting queries of the form "What fraction of individual records in the database satisfy the property q?" We prove that if one-way functions exist, then there is no algorithm that takes as input a database D in ({0,1}^d)^n, and k = n^{2+o(1)} arbitrary efficiently computable counting queries, runs in time poly(d, n), and returns an approximate answer to each query, while satisfying differential privacy. We also consider the complexity of answering "simple" counting queries, and make some progress in this direction by showing that the above result holds even when we require that the queries are computable by constant depth (AC-0) circuits. Our result is almost tight in the sense that nearly n^2 counting queries can be answered efficiently while satisfying differential privacy. Moreover, super-polynomially many queries can be answered in exponential time. We prove our results by extending the connection between differentially private counting query release and cryptographic traitor-tracing schemes to the setting where the queries are given to the sanitizer as input, and by constructing a traitor-tracing scheme that is secure in this setting.

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

Recommendations

• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Differential privacy and the fat-shattering dimension of linear queries
• Optimal private halfspace counting via discrepancy
• The optimal upper bound of the number of queries for Laplace mechanism under differential privacy
• On the complexity of differentially private data release, efficient algorithms and hardness results
• Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy
• The complexity of differential privacy
• On the complexity of two-party differential privacy
• Near-optimal differentially private mechanism for linear queries

zbMATH Keywords

cryptographydifferential privacytraitor tracing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• 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
• Title not available (Why is that?)
• Fully Collusion Resistant Traitor Tracing with Short Ciphertexts and Private Keys
• Pseudorandom generators with long stretch and low locality from random local one-way functions
• Title not available (Why is that?)
• Optimal probabilistic fingerprint codes
• Faster algorithms for privately releasing marginals
• Fingerprinting codes and the price of approximate differential privacy
• Private data release via learning thresholds
• Pcps and the hardness of generating private synthetic data

Cited In (8)

• The complexity of computing the optimal composition of differential privacy
• Fingerprinting codes and the price of approximate differential privacy
• Strong hardness of privacy from weak traitor tracing
• Fingerprinting codes and the price of approximate differential privacy
• On the complexity of differentially private data release, efficient algorithms and hardness results
• Hardness of non-interactive differential privacy from one-way functions
• The complexity of computing the optimal composition of differential privacy
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard

Uses Software

• SuLQ

This page was built for publication: Answering \(n^2+o(1)\) counting queries with differential privacy is hard

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