2016

Understanding the Sparse Vector Technique for Differential Privacy

Lyu, Min, Su, Dong, Li, Ninghui

Understand

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.

Built on

Revealing information while preserving privacy
I. Dinur and K. Nissim · 2003
Earlier work this paper cites.
Differential privacy
C. Dwork · 2006
Earlier work this paper cites.
Calibrating noise to sensitivity in private data analysis
C. Dwork, F. McSherry, K. Nissim, and A. Smith · 2006
Earlier work this paper cites.
The price of privacy and the limits of LP decoding
C. Dwork, F. McSherry, and K. Talwar · 2007
Earlier work this paper cites.
Mechanism design via differential privacy
F. McSherry and K. Talwar · 2007
Earlier work this paper cites.
New efficient attacks on statistical disclosure control mechanisms
C. Dwork and S. Yekhanin · 2008
Earlier work this paper cites.
On the complexity of differentially private data release: efficient algorithms and hardness results
C. Dwork, M. Naor, O. Reingold, G. Rothblum, and S. Vadhan · 2009
Earlier work this paper cites.

Similar

Boosting and differential privacy
C. Dwork, G. N. Rothblum, and S. Vadhan · 2010
Cited alongside, same era.
A multiplicative weights mechanism for privacy-preserving data analysis
M. Hardt and G. N. Rothblum · 2010
Cited alongside, same era.
Interactive privacy via the median mechanism
A. Roth and T. Roughgarden · 2010
Cited alongside, same era.
The sparse vector technique, 2011
A. Roth · 2011
Cited alongside, same era.
Iterative constructions and private data release
A. Gupta, A. Roth, and J. Ullman · 2012
Cited alongside, same era.
The algorithmic foundations of differential privacy
C. Dwork and A. Roth · 2013
Cited alongside, same era.
Top-k frequent itemsets via differentially private fp-trees
J. Lee and C. W. Clifton · 2014
Cited alongside, same era.

Then

Differentially private algorithms for empirical machine learning
Original
B. Stoddard, Y. Chen, and A. Machanavajjhala · 2014
Later among the works it cites.
Privbayes: Private data release via bayesian networks
J. Zhang, G. Cormode, C. M. Procopiuc, D. Srivastava, and X. Xiao · 2014
Later among the works it cites.
Differentially private high-dimensional data publication via sampling-based inference
R. Chen, Q. Xiao, Y. Zhang, and J. Xu · 2015
Later among the works it cites.
On the privacy properties of variants on the sparse vector technique
Original
Y. Chen and A. Machanavajjhala · 2015
Later among the works it cites.
Privacy-preserving deep learning
R. Shokri and V. Shmatikov · 2015
Later among the works it cites.
Privtree: A differentially private algorithm for hierarchical decompositions
J. Zhang, X. Xiao, and X. Xie · 2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…