Individual Sensitivity Preprocessing for Data Privacy
Individual Sensitivity Preprocessing for Data Privacy
复制标题
数据隐私的个人敏感性预处理
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
D. Durfee
中科院分区：
文献类型：
--
作者：
Rachel Cummings;D. Durfee
差异隐私中的敏感性度量被非正式地定义为相邻数据库之间输出的最大边际变化，对于确定隐私数据分析的准确性具有重要意义。在差异隐私文献中已经开发了在平均灵敏度远小于最坏情况灵敏度时提高准确性的技术，包括平滑灵敏度、样本和聚合、提议-测试-发布和Lipschitz扩展等工具。
在这项工作中，我们为这个问题提供了一个新的敏感度-预处理框架，它克服了以前技术的一些限制，并在高度通用的环境下工作。与Lipschitz扩展类似，我们的框架也用另一个敏感度较小的函数逼近数据库上的函数。然而，与通常无法计算的Lipschitz扩展相比，我们利用相邻数据库的特定度量空间结构来给出更局部化的指数时间一般结构。在我们的框架中，我们建设性地定义了一个敏感度-预处理函数，对于它，我们给出了近似最优性和NP-难结果，并进一步补充如下：
(1)对于重要的统计指标，如均值、$\α$-剪裁均值、中位数、最大值、最小值和方差，我们证明了我们的灵敏度-预处理函数可以在$O(n^2)$时间内实现。
(2)引入了个体敏感度的新概念，并证明了它是个性化差异隐私定义的一个重要度量。我们表明，我们的算法可以扩展到这一背景下，并为这种变体定义及其在隐私市场中的应用提供了一个有用的工具。
(3)我们考虑将我们的框架扩展到映射到更高维度的函数，并给出了正反两方面的结果。
The sensitivity metric in differential privacy, which is informally defined as the largest marginal change in output between neighboring databases, is of substantial significance in determining the accuracy of private data analyses. Techniques for improving accuracy when the average sensitivity is much smaller than the worst-case sensitivity have been developed within the differential privacy literature, including tools such as smooth sensitivity, Sample-and-Aggregate, Propose-Test-Release, and Lipschitz extensions.
In this work, we provide a new Sensitivity-Preprocessing framework for this problem that overcomes some of the limitations of the previous techniques and works in a highly generalized setting. Similar to Lipschitz extensions, our framework also approximates a function over databases with another function of smaller sensitivity. However, we exploit the specific metric space structure of neighboring databases to give a more localized exponential-time general construction, compared to Lipschitz extensions which can often be uncomputable. We constructively define a Sensitivity-Preprocessing Function in our framework for which we give approximate optimality and NP-hardness results, and further complement it with the following:
(1) For important statistical metrics such as mean, $\alpha$-trimmed mean, median, maximum, minimum, and variance, we show that our Sensitivity-Preprocessing Function can be implemented in $O(n^2)$ time.
(2) We introduce a new notion of individual sensitivity and show that it is an important metric in the variant definition of personalized differential privacy. We show that our algorithm can extend to this context and serve as a useful tool for this variant definition and its applications in markets for privacy.
(3) We consider extending our framework to functions mapping to higher dimensions and give both positive and negative results.
DOI：
--
发表时间：
2018-05
期刊：
--
影响因子：
--
作者：
Gautam Kamath;Jerry Li;Vikrant Singhal;Jonathan Ullman
通讯作者：
Gautam Kamath;Jerry Li;Vikrant Singhal;Jonathan Ullman
影响因子：
1.2
作者：
Cummings, Rachel;Pennock, David M.;Vaughan, Jennifer Wortman
通讯作者：
Vaughan, Jennifer Wortman