Understanding the Sparse Vector Technique for Differential Privacy
Understanding the Sparse Vector Technique for Differential Privacy
复制标题
DOI：
10.14778/3055330.3055331
复制
发表时间：
2017-02-01
影响因子：
2.5
通讯作者：
Li, Ninghui
中科院分区：
文献类型：
--
作者：
Lyu, Min;Su, Dong;Li, Ninghui
稀疏矢量技术（SVT）是满足差异隐私的基本技术，并且具有独特的质量，可以在不支付任何隐私成本的情况下输出一些查询答案。 SVT已在两种交互式设置中都使用，在该设置中，人们试图回答一系列不知道的查询序列，而在非相互作用的环境中，所有查询都是已知的。由于隐私预算的潜在节省，因此已经提出了许多用于保存数据挖掘和发布的SVT的变体。但是，大多数SVT的变体实际上不是私有的。在本文中，我们分析了这些错误，并确定了可能造成这些错误的误解。我们还提出了一种新版本的SVT，可提供更好的实用性，并引入有效的技术来提高SVT的性能。这些增强功能可以应用于在交互式环境中提高效用。通过分析和实验比较，我们表明，在非相互作用的设置（但不是交互式设置）中，SVT技术是不必要的，因为它可以以更好的精度代替指数机制（EM）。
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.