Understanding the sparse vector technique for differential privacy
- 1 February 2017
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 10 (6), 637-648
- https://doi.org/10.14778/3055330.3055331
Abstract
The Sparse Vector Technique (SVT) is a fundamental technique for satisfying differential privacy and has the unique quality that one can output some query answers without apparently paying any privacy cost. SVT has been used in both the interactive setting, where one tries to answer a sequence of queries that are not known ahead of the time, and in the non-interactive setting, where all queries are known. Because of the potential savings on privacy budget, many variants for SVT have been proposed and employed in privacy-preserving data mining and publishing. However, most variants of SVT are actually not private. In this paper, we analyze these errors and identify the misunderstandings that likely contribute to them. We also propose a new version of SVT that provides better utility, and introduce an effective technique to improve the performance of SVT. These enhancements can be applied to improve utility in the interactive setting. Through both analytical and experimental comparisons, we show that, in the non-interactive setting (but not the interactive setting), the SVT technique is unnecessary, as it can be replaced by the Exponential Mechanism (EM) with better accuracy.Keywords
Other Versions
This publication has 18 references indexed in Scilit:
- Privacy-Preserving Deep LearningPublished by Association for Computing Machinery (ACM) ,2015
- Differentially Private High-Dimensional Data Publication via Sampling-Based InferencePublished by Association for Computing Machinery (ACM) ,2015
- PrivBayesPublished by Association for Computing Machinery (ACM) ,2014
- Iterative Constructions and Private Data ReleaseLecture Notes in Computer Science, 2012
- New Efficient Attacks on Statistical Disclosure Control MechanismsLecture Notes in Computer Science, 2008
- The price of privacy and the limits of LP decodingPublished by Association for Computing Machinery (ACM) ,2007
- Differential PrivacyLecture Notes in Computer Science, 2006
- Calibrating Noise to Sensitivity in Private Data AnalysisLecture Notes in Computer Science, 2006
- Revealing information while preserving privacyPublished by Association for Computing Machinery (ACM) ,2003
- Cumulated gain-based evaluation of IR techniquesACM Transactions on Information Systems, 2002