提供差分隐私保护的线性查询新方法.pdf

《提供差分隐私保护的线性查询新方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、万方数据摘要差分隐私是一种处理敏感数据分析任务时的隐私保护原理，在许多的场合下都得到了成功的应用。差分隐私与许多更早的隐私保护原理不同，它定义了十分严谨的隐私担保形式，并要求其数据分析技术都能够从数学上严格证明满足所定义的隐私担保。简单来说，差分隐私在数据发布过程中对任何个人敏感数据参与发布过程所招致的风险进行了定量的控制，从而使任何攻击者都无法从发布结果推断出任何单个参与者的敏感信息。目前，研究者们已经对差分隐私进行了大量的研究工作，并提出了许多有效的敏感数据分析方法。然而，差分隐私作为一个新的研究领域，仍然有许多

2、新的问题有待解决。在这篇论文中，我们提出了三种在差分隐私下进行数据查询的新方法，显著提高了敏感数据查询的效率与有效性。实现差分隐私的一个最简单有效的方法是Laplace机制，它通过往查询结果中引入独立同分布的Laplace噪声来隐藏个人信息。虽然这个方法十分简单且被』。泛应用，但它却要求查询结果对个体参与者的全局敏感度必须是有限而且较小的。对于许多复杂查询，例女NSQL查询结果上的聚合以及子图计数，查询结果却很可能有着过大甚至无限的全局敏感度。现有的差分隐私机制并不能够处理如此复杂的查询。我们首先提出了一个基二=F经

3、验敏感度的查询机制，它可以处理跟个体参与者之间有着复杂关系的查询，并且允许查询有无限大的全局敏感度。除此之外，我们的机制还能用于处理任意的子图计数查询并实现节点差分隐私，而这在过去是无法做到的。对于许多线性查询，Laplace机制所引入的独立噪声并不是最优的。为了优化查询精度，一些机制往查询结果引入相关的噪声来减小所需噪声的大小。然而，当查询序列是用户任意给定时，这些机制为了找到最优的噪声分布需要的计算开销非常大，随数据维度增加呈指数增长。因此，这些机制在实践中无法用于高维数据集。我们提出了一个基于子敏感度概念的改进

4、机制，它不但可以通过往查询结果引入相关的噪声来优化查询精度，且其计算开销随数据维度增加仅呈多项式增长。冈此，它在实践巾的效率和可用性跟以往的方法相比有着显著的提高。最后，我们提出了一种用于整合所有已知查询结果的后处理技术，以利用查询中隐藏的冗余性和相关性来提高查询的精度。我们的方法还可以在隐私预算完全耗尽的场合下根据已知的信息给新查询返回有意义的估计结果。这个方法的一个重要优点是，它避免了在整个数据域上显式地构造柱状图，对于许多重要的查询类型它的计算开销随数据维度增加仅呈多项式增长，因此可适用于高维数据集。关键字：隐

5、私保护，差分隐私，Laplace机制，全局敏感度，局部敏感度，递归机制，平滑敏感度，经验敏感度，子敏感度机制，K—norm机制，主成分分析，最大熵。万方数据AbstractDifferentialprivacyisarobustprincipleforprivacypreservingdataanalysistasks，andhasbeensuccessfullyappliedtoavarietyofapplications．Differingfrommanyearlierprivacypreservingprinc

6、iple，differentialprivacydefinesaformalprivacyguaranteeinaveryrigorousInanner．Alldifferentiallyprivatedataanalysistechniquesshouldbeabletobeprovedtosatisfydifferentialprivacybymathematics．Roughlyspeaking，theriskforanindividualincurredbyparticipatinginaprivatedat

7、apublishingisquantitativelycontrolledbydifferentialprivacy,hencenoadversarycaninfersensitiveinformationforanyparticipantfrompublisheddata．Todate，differentialprivacyhasbeenstudiedbyavastofresearchers，andmanyeffectivetechniquesforprivatedataanalysistaskshavebeenp

8、roposed．Asanewresearchdomain，however，manynewproblemsarestillleftopen．Inthispaper，weproposethreenewqueryprocessingmethodsunderdifferentialprivacy,whichsignificantlyimprovethe