分布式差分隱私算法

土俊雅

摘要

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

【關(guān)鍵詞】差分隱私 分布式 數(shù)據(jù)挖掘

1 引言

近年來，網(wǎng)絡(luò)和大型計算機(jī)的應(yīng)用發(fā)展，使分布式網(wǎng)絡(luò)受到極大關(guān)注并被廣泛研究。分布式網(wǎng)絡(luò)由多個節(jié)點(diǎn)信息交互耦合而成，每個節(jié)點(diǎn)僅與周圍鄰居個體進(jìn)行信息交流，不需要網(wǎng)絡(luò)全局信息，因此分布式網(wǎng)絡(luò)具有極強(qiáng)的魯棒性和適應(yīng)性。

隨著互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，用戶之間數(shù)據(jù)共享變得越來越便捷，引發(fā)了人們對隱私泄露的擔(dān)憂。同時，數(shù)據(jù)挖掘技術(shù)的高速發(fā)展，也為隱私信息保護(hù)帶來了新的挑戰(zhàn)。差分隱私保護(hù)通過添加噪聲使數(shù)據(jù)失真，從而達(dá)到隱私保護(hù)的目的。而且，差分隱私具有添加噪聲少，泄露隱私風(fēng)險低的優(yōu)點(diǎn)，是目前國際上唯一公認(rèn)的隱私保護(hù)算法，并被谷歌、蘋果等大型網(wǎng)絡(luò)公司所采用。本文介紹了差分隱私和分布式網(wǎng)絡(luò)的結(jié)合，即分布式差分隱私算法，不僅具有極強(qiáng)的魯棒性，使網(wǎng)絡(luò)保持穩(wěn)定，不易癱瘓，而且極大地保護(hù)了用戶的隱私。

2 分布式模型

本文考慮如下分布式凸優(yōu)化問題：

其中f_t，i（x_i）：R^d→R是僅為節(jié)點(diǎn)i∈V所知道的局部凸損失函數(shù)，x=（x₁，…，x_n）∈x表示所有節(jié)點(diǎn)本地估計的集合，x是一個凸緊集。

3 差分隱私模型

差分隱私：Dwork在文獻(xiàn)[4]中首次提出差分隱私的定義。差分隱私使得數(shù)據(jù)挖掘者能夠發(fā)布其數(shù)據(jù)庫的某些統(tǒng)計信息，而不會泄露有關(guān)特殊值本身的敏感信息。在本文中，我們使用差分隱私保護(hù)節(jié)點(diǎn)的隱私性并給出以下定義：

定義1讓K表示差分隱私。令x=1ⁱ，x₂ⁱ，…，x_Tⁱ>;是從任意節(jié)點(diǎn)的本地數(shù)據(jù)源中抽取的一系列問題，令w=1ⁱ，w₂ⁱ，…，w_Tⁱ>是節(jié)點(diǎn)的T輸出序列，且W=K（x）。如果給定任何兩個相鄰的問題序列x和x'在一個問題條目中不同，那么我們的算法K是差分隱私的，下面是：

這種不平等保證了個體是否參與數(shù)據(jù)庫，它不會對我們算法的輸出產(chǎn)生任何重大差異，因此對手無法獲得關(guān)于個體的有用信息。此外，如果滿足

則K提供了（ε，δ）-差分隱私，通過隱私算法輸出增加隨機(jī)噪聲來弱化K（x）和K（x'）之間的顯著差異。

定義2對于K的敏感度定義為：

其中‖K（χ）-K（χ'）‖₁是K（x）和K（x'）之間的1-階范數(shù)距離。

4 分布式差分隱私算法

輸入：

初始值：x_t，i∈R^d

5 結(jié)論

差分隱私通過添加噪聲使數(shù)據(jù)失真，從而達(dá)到保護(hù)隱私的目的。本文將差分隱私和分布式網(wǎng)絡(luò)的結(jié)合，提出分布式差分隱私算法，不僅使網(wǎng)絡(luò)有極強(qiáng)的魯棒性，且極大地保護(hù)了用戶的隱私。未來將差分隱私算法拓展到非線性和交互式查詢

參考文獻(xiàn)

[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]熊平，朱天清，王曉峰.差分隱私保護(hù)及其應(yīng)用[J].計算機(jī)學(xué)報，2014，37（01）：101-122.

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