Optimal error of query sets under the differentially-private matrix mechanism

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.
Type de document :
Pré-publication, Document de travail
35 pages; Short version to appear in the 16th International Conference on Database Theory (ICDT),.. 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00878876
Contributeur : Émilien Antoine <>
Soumis le : jeudi 31 octobre 2013 - 10:31:39
Dernière modification le : jeudi 11 janvier 2018 - 06:20:13

Lien texte intégral

Identifiants

  • HAL Id : hal-00878876, version 1
  • ARXIV : 1202.3399

Collections

Citation

Chao Li, Gerome Miklau. Optimal error of query sets under the differentially-private matrix mechanism. 35 pages; Short version to appear in the 16th International Conference on Database Theory (ICDT),.. 2012. 〈hal-00878876〉

Partager

Métriques

Consultations de la notice

110