Lower bounds on the error of query sets under the differentially-private matrix mechanism

DOI10.1007/S00224-015-9610-ZzbMATH Open1352.68083arXiv1202.3399OpenAlexW1990051990MaRDI QIDQ269340FDOQ269340

Authors: Gerome Miklau, Chao Li 

Publication date: 18 April 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: A common goal of privacy research is to release synthetic data that satisfies a formal privacy guarantee and can be used by an analyst in place of the original data. To achieve reasonable accuracy, a synthetic data set must be tuned to support a specified set of queries accurately, sacrificing fidelity for other queries. This work considers methods for producing synthetic data under differential privacy and investigates what makes a set of queries "easy" or "hard" to answer. We consider answering sets of linear counting queries using the matrix mechanism, a recent differentially-private mechanism that can reduce error by adding complex correlated noise adapted to a specified workload. Our main result is a novel lower bound on the minimum total error required to simultaneously release answers to a set of workload queries. The bound reveals that the hardness of a query workload is related to the spectral properties of the workload when it is represented in matrix form. The bound is most informative for $(epsilon,delta)$-differential privacy but also applies to $epsilon$-differential privacy.

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

Recommendations

• The optimal upper bound of the number of queries for Laplace mechanism under differential privacy
• Near-optimal differentially private mechanism for linear queries
• Lower bounds in differential privacy
• Differential privacy and the fat-shattering dimension of linear queries
• Unconditional differentially private mechanisms for linear queries
• On differentially private low rank approximation
• Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy
• Optimal lower bound for differentially private multi-party aggregation
• Lower bounds for differential privacy from Gaussian width

zbMATH Keywords

lower boundspectral decompositiondifferential privacylinear queryminimal error

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25)

Cites Work

• Generalized inverses. Theory and applications.
• Theory of Cryptography
• Nearly optimal private convolution
• 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
• Iterative Constructions and Private Data Release
• Toeplitz and circulant matrices: a review.
• Title not available (Why is that?)
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Eigenvalues, invariant factors, highest weights, and Schubert calculus
• On the complexity of differentially private data release, efficient algorithms and hardness results
• Title not available (Why is that?)
• Unconditional differentially private mechanisms for linear queries

Cited In (2)

• Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness

This page was built for publication: Lower bounds on the error of query sets under the differentially-private matrix mechanism

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