A learning theory approach to non-interactive database privacy
A learning theory approach to non-interactive database privacy
复制标题
DOI：
10.1145/1374376.1374464
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
Avrim Blum;Katrina Ligett;Aaron Roth
中科院分区：
文献类型：
--
作者：
Avrim Blum;Katrina Ligett;Aaron Roth
我们证明，忽略计算约束，它是可以释放的隐私保护数据库，是有用的所有查询在一个离散域从任何给定的概念类多项式VC维。我们展示了一个新的下限释放数据库，是有用的半空间查询一个连续的域。尽管如此，我们给出了一个隐私保护的多项式时间算法，释放有用的信息，所有半空间查询，稍微放松的有用性的定义。受学习理论的启发，我们引入了一个新的数据隐私概念，我们称之为分布式隐私，并表明它严格强于流行的隐私概念，差分隐私。
We demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class with polynomial VC-dimension. We show a new lower bound for releasing databases that are useful for halfspace queries over a continuous domain. Despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, for a slightly relaxed definition of usefulness. Inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy.