分布式差分隱私算法

土俊雅

摘要

數據挖掘中的隱私保護問題成為信息安全領域研究的一大熱點。一些惡意算法通過反向推導，觀察輸出或中間參數來推斷輸入數據，使用戶隱私有暴露的危險，為了防止這種“偷竊”行為，我們使用分布式差分隱私保護算法中可能暴露的每個參數。

【關鍵詞】差分隱私 分布式 數據挖掘

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.