分布式差分隐私算法

土俊雅

摘要

数据挖掘中的隐私保护问题成为信息安全领域研究的一大热点。一些恶意算法通过反向推导，观察输出或中间参数来推断输入数据，使用户隐私有暴露的危险，为了防止这种“偷窃”行为，我们使用分布式差分隐私保护算法中可能暴露的每个参数。

【关键词】差分隐私 分布式 数据挖掘

1 引言

近年来，网络和大型计算机的应用发展，使分布式网络受到极大关注并被广泛研究。分布式网络由多个节点信息交互耦合而成，每个节点仅与周围邻居个体进行信息交流，不需要网络全局信息，因此分布式網络具有极强的鲁棒性和适应性。

随着互联网技术的迅猛发展，用户之间数据共享变得越来越便捷，引发了人们对隐私泄露的担忧。同时，数据挖掘技术的高速发展，也为隐私信息保护带来了新的挑战。差分隐私保护通过添加噪声使数据失真，从而达到隐私保护的目的。而且，差分隐私具有添加噪声少，泄露隐私风险低的优点，是目前国际上唯一公认的隐私保护算法，并被谷歌、苹果等大型网络公司所采用。本文介绍了差分隐私和分布式网络的结合，即分布式差分隐私算法，不仅具有极强的鲁棒性，使网络保持稳定，不易瘫痪，而且极大地保护了用户的隐私。

2 分布式模型

本文考虑如下分布式凸优化问题：

其中f_t，i（x_i）：R^d→R是仅为节点i∈V所知道的局部凸损失函数，x=（x₁，…，x_n）∈x表示所有节点本地估计的集合，x是一个凸紧集。

3 差分隐私模型

差分隐私：Dwork在文献[4]中首次提出差分隐私的定义。差分隐私使得数据挖掘者能够发布其数据库的某些统计信息，而不会泄露有关特殊值本身的敏感信息。在本文中，我们使用差分隐私保护节点的隐私性并给出以下定义：

定义1让K表示差分隐私。令x=1ⁱ，x₂ⁱ，…，x_Tⁱ>;是从任意节点的本地数据源中抽取的一系列问题，令w=1ⁱ，w₂ⁱ，…，w_Tⁱ>是节点的T输出序列，且W=K（x）。如果给定任何两个相邻的问题序列x和x'在一个问题条目中不同，那么我们的算法K是差分隐私的，下面是：

这种不平等保证了个体是否参与数据库，它不会对我们算法的输出产生任何重大差异，因此对手无法获得关于个体的有用信息。此外，如果满足

则K提供了（ε，δ）-差分隐私，通过隐私算法输出增加随机噪声来弱化K（x）和K（x'）之间的显着差异。

定义2对于K的敏感度定义为：

其中‖K（χ）-K（χ'）‖₁是K（x）和K（x'）之间的1-阶范数距离。

4 分布式差分隐私算法

输入：

初始值：x_t，i∈R^d

5 结论

差分隐私通过添加噪声使数据失真，从而达到保护隐私的目的。本文将差分隐私和分布式网络的结合，提出分布式差分隐私算法，不仅使网络有极强的鲁棒性，且极大地保护了用户的隐私。未来将差分隐私算法拓展到非线性和交互式查询

参考文献

[1]Dorfler F，Chertkov M，Bullo F.Synchronization in complex oscillatornetworks and smart grids.[J].Proceedings of the National Academyof Sciences of the United States ofAmerica，2013，110（06）：2005-10.

[2]On M，Du H，Li S.Finite-time formation control ofmultiple nonholonomic mobilerobots[J].InternationalJournal of Robust&NonlinearControl;，2012，24（01）：140-165.

[3]熊平，朱天清，王晓峰.差分隐私保护及其应用[J].计算机学报，2014，37（01）：101-122.

[4]Dwork C.Differential privacy[J].Lecture Notes in ComputerScience，2011，26（02）：1-12.