On the Privacy Properties of Variants on the Sparse Vector Technique

By Yan Chen, Ashwin Machanavajjhala. 2015

35 citations recorded by the source corpus.

The sparse vector technique is a powerful differentially private primitive that allows an analyst to check whether queries in a stream are greater or lesser than a threshold. This technique has a unique property -- the algorithm works by adding noise with a finite variance to the queries and the threshold, and guarantees privacy that only degrades with (a) the maximum sensitivity of any one query in stream, and (b) the number of positive answers output by the algorithm. Recent work has developed variants of this algorithm, which we call {\em generalized private threshold testing}, and are claimed to have privacy guarantees that do not depend on the number of positive or negative answers output by the algorithm. These algorithms result in a significant improvement in utility over the sparse vector technique for a given privacy budget, and have found applications in frequent itemset mining, feature selection in machine learning and generating synthetic data. In this paper we critically analyze the privacy properties of generalized private threshold testing. We show that generalized private threshold testing does not satisfy \epsilon-differential privacy for any finite \epsilon. We identify a subtle error in the privacy analysis of this technique in prior work. Moreover, we show an adversary can use generalized private threshold testing to recover counts from the datasets (especially small counts) exactly with high accuracy, and thus can result in individuals being reidentified. We demonstrate our attacks empirically on real datasets.

Subfields: Artificial Intelligence, Computer Science Applications

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

Citations in the corpus

Detecting Violations of Differential Privacy (2018, background): “A sign of this problem is the existence of papers that are solely designed to point out errors in other papers [12, 28].”
Understanding the Sparse Vector Technique for Differential Privacy (2016, methodology): “The fact that many usages of SVT are not private, even when proofs of their privacy were given, is already known [2, 20]; however, we feel that what led to the erroneous proofs were not cl early explained, and such an explanation can help researchers to a void similar errors in the future.”
PrivBayes: private data release via bayesian networks (2014, methodology): “However, this technique is shown to be flawed [10], as its privacy analysis is erroneous.”
AutoPriv: Automating Differential Privacy Proofs (2016, background): “Proofs of correctness (of this and other variants) can be found in (Dwork and Roth 2014; Chen and Machanavajjhala 2015; Lyu et al. 2016).”
LightDP: towards automating differential privacy proofs (2016, background): “Informal proof and sample runthrough Proofs of correctness (of this and other variants) can be found in (Dwork and Roth 2014; Chen and Machanavajjhala 2015; Lyu et al. 2016).”