Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy
Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy
复制标题
通过数据隐私应用来测试产品分布上的 Lipschitz 属性
DOI：
10.1007/978-3-642-36594-2_24
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Abhradeep Thakurta
中科院分区：
文献类型：
--
作者：
Kashyap Dixit;Madhav Jha;Sofya Raskhodnikova;Abhradeep Thakurta
在过去的几年里，统计数据隐私领域的研究重点一直是为满足一些严格的隐私概念的各种问题设计算法。然而，没有太多的努力去设计技术来通过计算验证给定的算法是否满足某些预定义的隐私概念。在这项工作中，我们解决了以下问题：我们是否可以设计算法来测试给定的算法是否满足某些特定的严格隐私概念(例如，差异隐私)？
我们设计算法来测试给定算法$\mathcal{A}$在包含关于个人的潜在敏感信息的数据集x上运行时的隐私保证。更形式化地，我们设计了一个计算效率高的算法${\cal T}_{PRIV}$，该算法验证$\mathcal{A}$是否满足典型数据集上的时间次线性保证(DPTD)。DPTD是由[3]首次提出的类似于广义差异隐私的概念，是对流行的差异隐私概念的分布放宽[14]。
为了设计算法，我们证明了算法的隐私保证测试与相关函数的Lipschitz性质测试之间的形式联系。更具体地说，我们证明了一种有效的Lipschitz性质测试算法可以作为${cal T}_{PRIV}$的子例程来测试算法在典型数据集上是否满足差分隐私。
除了形式化隐私保证测试和Lipschitz属性测试之间的联系外，我们将[21]的工作推广到产品分布下的属性测试的设置。更准确地说，我们设计了一种高效的Lipschitz测试器，用于根据某个固定但未知的乘积分布而不是均匀分布从超立方体中提取域点的情况。
In the past few years, the focus of research in the area of statistical data privacy has been in designing algorithms for various problems which satisfy some rigorous notions of privacy. However, not much effort has gone into designing techniques to computationally verify if a given algorithm satisfies some predefined notion of privacy. In this work, we address the following question: Can we design algorithms which tests if a given algorithm satisfies some specific rigorous notion of privacy (e.g., differential privacy)?
We design algorithms to test privacy guarantees of a given algorithm $\mathcal{A}$ when run on a dataset x containing potentially sensitive information about the individuals. More formally, we design a computationally efficient algorithm ${\cal T}_{priv}$ that verifies whether $\mathcal{A}$ satisfies differential privacy on typical datasets (DPTD) guarantee in time sublinear in the size of the domain of the datasets. DPTD, a similar notion to generalized differential privacy first proposed by [3], is a distributional relaxation of the popular notion of differential privacy [14].
To design algorithm ${\cal T}_{priv}$, we show a formal connection between the testing of privacy guarantee for an algorithm and the testing of the Lipschitz property of a related function. More specifically, we show that an efficient algorithm for testing of Lipschitz property can be used as a subroutine in ${\cal T}_{priv}$ that tests if an algorithm satisfies differential privacy on typical datasets.
Apart from formalizing the connection between the testing of privacy guarantee and testing of the Lipschitz property, we generalize the work of [21] to the setting of property testing under product distribution. More precisely, we design an efficient Lipschitz tester for the case where the domain points are drawn from hypercube according to some fixed but unknown product distribution instead of the uniform distribution.