Understanding the Sparse Vector Technique for Differential Privacy

By Min Lyu, Dong Su, Ninghui Li. 2016

193 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Science Applications, Sociology and Political Science, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

In Sociology and Political Science

In Privacy & Security

Citations in the corpus

Detecting Violations of Differential Privacy (2018, methodology): “: queries to the database, ϵ0: privacy budget T : threshold, N : bound of outputting True’s ∆: sensitivity 1 function iSVT4(Q , T , ϵ0, ∆, N): 2 out ← [ ] 3 η1 ← Lap(2 ∗ ∆/ϵ0) 4 T̃ ← T + η1 5 count ← 0 6 foreach q in Q do 7 η2 ← Lap(2 ∗ N ∗ ∆/ϵ0) 8 if q + η2 ≥ T̃ then 9 // output numerical value ins”
Advanced Probabilistic Couplings for Differential Privacy (2016, critical): “In particular, the privacy proof of Above Threshold is non-compositional and notoriously tricky, and several variants 1 of the algorithm were supposedly proved to be private but were later shown to be non-private (Lyu et al. [34] provide a comprehensive survey).”
Proving Differential Privacy via Probabilistic Couplings (2016, neutral): “Lyu et al. (2016) provide further discussion of this, and other, incorrect implementations of the Sparse Vector technique.”
Proving differential privacy with shadow execution (2019, methodology): “Verifying Sparse Vector Technique with ShadowDP (slightly simplified for readability).”
Synthesizing coupling proofs of differential privacy (2017, methodology): “NumericSparseN Return the indices and answers of the first N queries above threshold [23, 34].”
Shifting machine learning for healthcare from development to deployment and from models to data (2022, background): “Selective parameter sharing 87 and the sparse vector technique 88 are two strategies for achieving greater privacy, but at the expense of model performance (this is consistent with differential-privacy findings in domains outside of medicine and healthcare 80,89 ).”
Automatic Discovery of Privacy–Utility Pareto Fronts (2019, unknown): “The algorithm has found applications in a number of problems, and several variants of it have been proposed [36].”
Cryptϵ: Crypto-Assisted Differential Privacy on Untrusted Servers (2019, background): “Last, the security (privacy) proofs for just stand-alone cryptographic and DP mechanisms can be notoriously tricky [19, 75].”
Privacy-preserving Federated Brain Tumour Segmentation (2019, methodology): “This procedure satisfies (ε1 + ε2 + ε3)-differential privacy [5].”
Stochastic Adaptive Line Search for Differentially Private Optimization (2020, methodology): “Although [12] shows that many extensions of SVT are not private, it also demonstrates the correctness of the original version (used in our approach), which is further confirmed in [18].”
Differentially Private Chi-squared Test by Unit Circle Mechanism (2017, methodology): “The SVT based procedure works in the interactive setting (Lyu et al., 2017), in which the hypothesis to be considered at each round can be interactively chosen after observing the result of the tests in the previous rounds (Webb & Petitjean, 2016).”
AutoPriv: Automating Differential Privacy Proofs (2016, methodology): “hat it satisﬁes (ǫ,0)-differential privacy. Informal proof and sample runthrough Proofsof correctness (of this and other variants) can be found in (Dwork and Roth 2014; Chen and Machanavajjhala 2015; Lyu et al. 2016). Here we provide an informal proof by example to illustrate the subtleties involved”
Unlocking High-Accuracy Differentially Private Image Classification through Scale (2022, background): “While diﬀerentially private algorithms provide strong formal privacy certiﬁcates, such guarantees are only realized if the algorithm is correctly implemented, which can be prone to human errors arising from minor variations in the algorithm (Lyu et al., 2017; Tramer et al., 2022).”
Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising (2018, background): “Analysing the privacy of such complex mechanisms turns out to be a delicate and error-prone task (Lyu et al., 2017).”