眾包環(huán)境下的隱私保護(hù)研究

劉 歡，吳桂興

(中國(guó)科學(xué)技術(shù)大學(xué) 軟件學(xué)院，江蘇 蘇州 215123)

0 引 言

在經(jīng)濟(jì)全球化的發(fā)展進(jìn)程中，企業(yè)將會(huì)面臨越來(lái)越大的競(jìng)爭(zhēng)壓力。對(duì)于那些企業(yè)難以單獨(dú)完成的任務(wù)，眾包可以聚集海量的互聯(lián)網(wǎng)用戶(hù)，使它們通過(guò)合作或者獨(dú)立的方式來(lái)完成，同時(shí)給予完成者一定的報(bào)酬獎(jiǎng)勵(lì)。然而在眾包平臺(tái)的運(yùn)行中，平臺(tái)、任務(wù)請(qǐng)求者和參與者之間常常需要進(jìn)行信息交換，如果處理不當(dāng)，可能會(huì)引起用戶(hù)敏感信息的泄露，從而給用戶(hù)的信息安全造成意想不到的傷害。

為了解決這一問(wèn)題，人們相繼提出了多種隱私保護(hù)模型，如k-anonymity[1]、(a,k)-anonymity[2]和l-diversity[3]等。但是這些模型在面對(duì)一些新型的、有針對(duì)性的攻擊手段時(shí)還需要對(duì)自身進(jìn)行不斷改進(jìn)，才能繼續(xù)提供安全保障。而且，這些模型也沒(méi)有對(duì)其處理結(jié)果的隱私保護(hù)水平進(jìn)行定量分析，即當(dāng)模型的參數(shù)發(fā)生變化時(shí)，無(wú)從得知其隱私保護(hù)水平的變化情況。差分隱私(differential privacy，DP)的出現(xiàn)則完美解決了上述擔(dān)憂(yōu)。所以差分隱私一經(jīng)推出便訊速得到了學(xué)術(shù)界的認(rèn)可，并被廣泛應(yīng)用到了其他領(lǐng)域，產(chǎn)生了一系列新成果。

一方面，對(duì)眾包的定義、工作流程以及差分隱私的數(shù)學(xué)定義和保護(hù)水平評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行了介紹；另一方面，還對(duì)不同眾包應(yīng)用場(chǎng)景下，如何使用差分隱私保護(hù)參與者個(gè)人數(shù)據(jù)的安全，以及該技術(shù)路線(xiàn)如何實(shí)現(xiàn)等進(jìn)行了闡述。接著在這兩方面的基礎(chǔ)上，對(duì)不同眾包場(chǎng)景下差分隱私的應(yīng)用情況進(jìn)行了總結(jié)，尋找改進(jìn)空間，并指出了未來(lái)的研究方向。

1 眾包的基本定義和工作流程

1.1 基本定義

2006年6月，美國(guó)雜志《連線(xiàn)》的記者Jeff Howe提出了眾包的概念[4]。

定義1(眾包)：眾包是一種公開(kāi)面向互聯(lián)網(wǎng)大眾的分布式的問(wèn)題解決機(jī)制，它通過(guò)整合計(jì)算機(jī)和互聯(lián)網(wǎng)上未知的大眾來(lái)完成計(jì)算機(jī)難以單獨(dú)完成的任務(wù)[5]。

1.2 工作流程

一般來(lái)說(shuō)，在眾包應(yīng)用中通常存在兩種角色：任務(wù)請(qǐng)求人(requester)和工人(worker)。

當(dāng)任務(wù)請(qǐng)求人需要通過(guò)眾包來(lái)完成自己的任務(wù)時(shí)，他可以執(zhí)行以下操作：設(shè)計(jì)任務(wù)；將任務(wù)發(fā)布到眾包平臺(tái)上；接收/拒絕工人的答案；整合工人們提交的答案，獲得最終的結(jié)果。而工人則需要執(zhí)行以下步驟：選擇自己感興趣的任務(wù)；接受任務(wù)；執(zhí)行任務(wù)；提交答案。根據(jù)每個(gè)步驟執(zhí)行時(shí)間的先后順序，可以將眾包的工作流程大致分成為三個(gè)階段：任務(wù)準(zhǔn)備、任務(wù)執(zhí)行以及整合答案。

2 差分隱私

2.1 基本定義

2006年，為了解決統(tǒng)計(jì)數(shù)據(jù)庫(kù)領(lǐng)域內(nèi)的隱私泄露問(wèn)題，Dwork提出了一種全新的隱私定義[6]。

定義2(差分隱私)：設(shè)有一隨機(jī)算法M,M所有可能產(chǎn)生的結(jié)果組成的集合為PM，SM則是PM的子集，D和D'是兩個(gè)鄰近數(shù)據(jù)集。那么對(duì)于任意的D、D'和SM，如果有Pr[M(D)∈SM]≤exp(ε)×Pr[M(D')∈SM]，則稱(chēng)算法M提供ε-差分隱私保護(hù)，其中參數(shù)ε被稱(chēng)為隱私保護(hù)預(yù)算。一般來(lái)說(shuō)，ε越小，意味著隱私保護(hù)水平越高。

在文獻(xiàn)[7]中，通過(guò)對(duì)輸出結(jié)果進(jìn)行隨機(jī)化處理，算法M對(duì)隱私提供了保護(hù)。與此同時(shí)，參數(shù)ε保證了當(dāng)數(shù)據(jù)集中某一個(gè)記錄發(fā)生變化時(shí)，算法輸出相同結(jié)果的概率差被控制在一個(gè)極小的范圍內(nèi)，而這個(gè)范圍是可以被數(shù)據(jù)所有者接受的。

2.2 實(shí)現(xiàn)機(jī)制

差分隱私的實(shí)現(xiàn)機(jī)制主要有Laplace機(jī)制(Laplace mechanism)[8]和指數(shù)機(jī)制(exponential mechanism)[9]。其中，Laplace機(jī)制是對(duì)數(shù)值型結(jié)果進(jìn)行保護(hù)，而指數(shù)機(jī)制則是對(duì)非數(shù)值型結(jié)果提供保護(hù)。

2.2.1 Laplace機(jī)制

定義3(Laplace機(jī)制)：對(duì)于給定的數(shù)據(jù)集D，假設(shè)有函數(shù)f:D→Rd，它的敏感度為Δf，則隨機(jī)算法M(D)=f(D)+Y提供ε水平的差分隱私保護(hù)。其中，Y～Lap(Δf/ε)是隨機(jī)噪聲，并且服從尺度參數(shù)為Δf/ε的Laplace分布。其中ε越小，說(shuō)明引入的噪聲越大。

2.2.2 指數(shù)機(jī)制

在很多應(yīng)用情況下，查詢(xún)結(jié)果并不僅僅只是數(shù)值型的，也可能會(huì)是實(shí)體對(duì)象型的(比如一種方案或選擇)，所以，McSherry等提出了指數(shù)機(jī)制。

設(shè)Range是查詢(xún)函數(shù)的輸出域，對(duì)于任意r∈Range，均為實(shí)體對(duì)象。在指數(shù)機(jī)制中，輸出值r的可用性函數(shù)可表示為q(D,r)→R，可以用來(lái)對(duì)r的優(yōu)劣程度進(jìn)行評(píng)估。

定義4(指數(shù)機(jī)制)：記數(shù)據(jù)集D為隨機(jī)算法M的輸入，實(shí)體對(duì)象r∈Range為其輸出，q(D,r)為可用性函數(shù)，Δq作為函數(shù)q(D,r)的敏感度。如果算法M以正比于exp(εq(D,r)/(2Δq))的概率從Range中選擇并輸出r，那么稱(chēng)算法M提供ε水平的差分隱私保護(hù)。

3 差分隱私在保護(hù)用戶(hù)提供的數(shù)據(jù)中的應(yīng)用

文獻(xiàn)[10]提出了一個(gè)和以前的研究不同的模式，即假設(shè)數(shù)據(jù)收集者是不可信任的。這樣一來(lái)，目標(biāo)群體就可以完全掌控自己的數(shù)據(jù)隱私，只提交一個(gè)經(jīng)過(guò)隱私處理的版本給數(shù)據(jù)收集者即可。同時(shí)，數(shù)據(jù)收集者也不再負(fù)有保護(hù)這些隱私數(shù)據(jù)的責(zé)任，消除了隱私泄露帶來(lái)的風(fēng)險(xiǎn)。

3.1 基本設(shè)定

如圖1所示，假設(shè)數(shù)據(jù)收集者最后想了解的信息是一個(gè)二進(jìn)制隨機(jī)變量W的狀態(tài)，同時(shí)每個(gè)個(gè)體都對(duì)W有一個(gè)信號(hào)Si，即隱私數(shù)據(jù)。由于知識(shí)水平的限制，每個(gè)個(gè)體的隱私數(shù)據(jù)Si和W的真實(shí)數(shù)據(jù)之間相等的概率為θ，θ的范圍一般為0.5≤θ≤1。為了保護(hù)隱私，每個(gè)個(gè)體只向數(shù)據(jù)收集者報(bào)告一個(gè)經(jīng)過(guò)隱私處理的版本Xi。當(dāng)使用差分隱私方法生成Si時(shí)，產(chǎn)生的隱私損失是ε，個(gè)體的隱私損失成本是ε的函數(shù)，而ε水平隱私數(shù)據(jù)的價(jià)值則被記作V(ε)。

圖1 模型的信息結(jié)構(gòu)

文獻(xiàn)針對(duì)V(ε)提出并證明了其下界和上界，還闡明了這些界限在報(bào)酬準(zhǔn)確性問(wèn)題里的應(yīng)用，即數(shù)據(jù)收集者在保證W的準(zhǔn)確性目標(biāo)的情況下，如何最小化總報(bào)酬。

3.2 V(ε)的下界

首先，定義了V(ε)的一個(gè)下界：

(1)

其中，g'是個(gè)體隱私花費(fèi)函數(shù)的一個(gè)變形。

經(jīng)過(guò)證明，對(duì)任意ε>0，都有ε水平的隱私價(jià)值V(ε)≥VLB(ε)。

3.3 V(ε)的上界

為了方便，定義了：

(2)

其中，對(duì)任意ε>0，都有d>0。

接著，給出了V(ε)的上界：V(ε)≤VLB(ε)+O(e-Nd)，其中N→∞。同樣，文獻(xiàn)給出了證明。

3.4 報(bào)酬-準(zhǔn)確性問(wèn)題

在得到上面關(guān)于隱私價(jià)值函數(shù)V(ε)的上下界之后，還可以將其應(yīng)用到報(bào)酬-準(zhǔn)確性問(wèn)題中去。

在給出準(zhǔn)確性目標(biāo)τ之后，可以用F(τ)來(lái)表示為了實(shí)現(xiàn)τ而要付出的最小總報(bào)酬。因?yàn)橐呀?jīng)有了隱私價(jià)值函數(shù)V(ε)的上下界，所以也能輕易得出F(τ)的上下界。

4 差分隱私在保護(hù)用戶(hù)位置中的應(yīng)用

在傳統(tǒng)的移動(dòng)群智應(yīng)用中，有些任務(wù)是需要工人到達(dá)指定地點(diǎn)才能完成的，因此，為了實(shí)現(xiàn)最優(yōu)的任務(wù)分配，比如使工人的移動(dòng)距離最小化，平臺(tái)往往需要事先知曉工人們的準(zhǔn)確位置。但是位置信息是工人們的個(gè)人隱私，暴露給平臺(tái)會(huì)引起人們的安全擔(dān)憂(yōu)，同時(shí)，并不是每個(gè)工人最終都會(huì)被分配任務(wù)，這樣他們的位置隱私也就白白泄露了。如何在任務(wù)分配的過(guò)程中既注意保護(hù)工人們的位置隱私，又能使目標(biāo)函數(shù)實(shí)現(xiàn)最優(yōu)化就成為一個(gè)需要解決的難題。

文獻(xiàn)[11]針對(duì)這個(gè)問(wèn)題提出了一個(gè)解決框架，在此框架下，允許工人們將自己的位置信息模糊化之后再提供給眾包平臺(tái)。這樣一來(lái)不僅滿(mǎn)足了差分隱私，而且不用牽涉到任何第三方。接下來(lái)，將依次介紹該框架的工作流程、差分隱私保護(hù)、目標(biāo)函數(shù)以及實(shí)驗(yàn)結(jié)果。

4.1 工作流程

該平臺(tái)運(yùn)行過(guò)程包含三個(gè)步驟：平臺(tái)端生成地理位置模糊函數(shù)；用戶(hù)端對(duì)位置信息進(jìn)行模糊化；平臺(tái)端分析模糊結(jié)果，并進(jìn)行任務(wù)分配。

4.2 差分隱私保護(hù)

差分隱私是由Andres等介紹到位置保護(hù)中去的[12]。其中，最為重要的就是模糊位置信息的概率函數(shù)P，它的基本思想是：對(duì)于模糊后的位置l*，將任意兩個(gè)位置l1、l2映射到l*的概率都是相同的。這樣一來(lái)，即使攻擊者知道了模糊函數(shù)P，并且觀察到一個(gè)工人u處于位置l*，也無(wú)法分辨出他的真實(shí)位置到底是l1還是l2，從而實(shí)現(xiàn)了保護(hù)工人位置隱私的目標(biāo)。

定義5(差分隱私):假設(shè)目標(biāo)區(qū)域包含一個(gè)位置集合L，那么當(dāng)且僅當(dāng)對(duì)?l1,l2,l*∈L，都有P(l*|l1)≤eεd(l1,l2)P(l*|l2)成立時(shí)，稱(chēng)概率函數(shù)P滿(mǎn)足差分隱私保護(hù)。其中，P(l*|l)是將l模糊到l*的概率，d(l1,l2)是l1、l2之間的距離，ε是隱私預(yù)算(ε越小，表示隱私保護(hù)水平越高)。

4.3 目標(biāo)函數(shù)

這部分將主要介紹的是位置模糊函數(shù)的求解和任務(wù)分配。

4.3.1 位置模糊函數(shù)

簡(jiǎn)單來(lái)說(shuō)，在生成位置模糊函數(shù)P時(shí)，需要考慮的問(wèn)題是：(1)使被選工人的移動(dòng)距離最小化；(2)P同時(shí)滿(mǎn)足差分隱私。

在把位于lt的一個(gè)任務(wù)分配給位于l*(模糊化后的位置)的工人之后，該工人預(yù)期需要移動(dòng)的距離是：

(3)

假設(shè)x(l*,lt)是把位于lt的任務(wù)分配給位于l*的工人的任務(wù)數(shù)量，那么就可以得出所有被選工人總的移動(dòng)距離：

(4)

4.3.2 任務(wù)分配

在工人們將自己模糊化后的位置信息上傳到平臺(tái)之后，接著就需要進(jìn)行任務(wù)分配了，也就是求出x。

(5)

其中，Nc(l*)是處于位置l*的實(shí)際工人數(shù)量。

接下來(lái)則可以使用Benders分解[13]和遺傳算法(genetic algorithm，GA)[14]對(duì)問(wèn)題進(jìn)行求解。

4.4 實(shí)驗(yàn)結(jié)果

文獻(xiàn)[11]既在模擬數(shù)據(jù)集上，又在真實(shí)數(shù)據(jù)集D4D上進(jìn)行了實(shí)驗(yàn)。從實(shí)驗(yàn)結(jié)果可以看出，在各種參數(shù)設(shè)定下，該文獻(xiàn)算法的效果都要優(yōu)于對(duì)比算法。

5 差分隱私在保護(hù)用戶(hù)出價(jià)中的應(yīng)用

文獻(xiàn)[15]提出了一種差分隱私化的激勵(lì)機(jī)制，以保護(hù)工人們的出價(jià)隱私。接下來(lái)，將詳細(xì)介紹該機(jī)制的實(shí)現(xiàn)過(guò)程。

5.1 工作流程

(1)眾包平臺(tái)首先向工人們公布任務(wù)集合T；

(2)在拍賣(mài)階段，工人需要向平臺(tái)提交他的出價(jià)信息bi=(Γi,ρi)。其中，Γi是工人感興趣的任務(wù)集合，ρi是他執(zhí)行這些任務(wù)的出價(jià)；

(3)根據(jù)工人們的出價(jià)信息，眾包平臺(tái)最終決定任務(wù)的分配，以及最終給工人們的報(bào)酬pi；

(4)當(dāng)被分配到任務(wù)的工人執(zhí)行完以后，需要將結(jié)果反饋給平臺(tái)，平臺(tái)對(duì)所有的結(jié)果進(jìn)行處理整合，得到最終的任務(wù)結(jié)果，并付給工人報(bào)酬。

5.2 hSRC Auction

5.3 差分隱私保護(hù)

文獻(xiàn)將提出的hSRC拍賣(mài)機(jī)制看作將出價(jià)信息b映射到報(bào)酬P(guān)的函數(shù)M(·),當(dāng)且僅當(dāng)M滿(mǎn)足如下條件時(shí)，稱(chēng)M是符合ε-差分隱私的：

Pr[M(b)∈A]≤exp(ε)Pr[M(b')∈A]

其中，A是報(bào)酬集合；b和b'是只相差一個(gè)出價(jià)的出價(jià)集合；ε稱(chēng)為隱私預(yù)算，其值越小，表示隱私保護(hù)水平越高。

這樣一來(lái)，當(dāng)某個(gè)工人的出價(jià)集合b發(fā)生變化時(shí)，其最后對(duì)應(yīng)的報(bào)酬集合并不會(huì)發(fā)生明顯的變化，從而確保了某些好奇的工人無(wú)法從報(bào)酬集合上推斷出該工人的出價(jià)信息，就實(shí)現(xiàn)了保護(hù)工人出價(jià)隱私的目標(biāo)。

5.4 機(jī)制設(shè)計(jì)

在付給工人酬勞時(shí)，將使平臺(tái)要支付的總酬勞最小化稱(chēng)為T(mén)PM(total payment minimization)問(wèn)題。同時(shí)，文獻(xiàn)證明了TPM是NP難問(wèn)題。所以，無(wú)法在多項(xiàng)式時(shí)間內(nèi)計(jì)算出使總酬勞最小的那個(gè)任務(wù)分配集。針對(duì)這種情況，文獻(xiàn)設(shè)計(jì)了一種機(jī)制DP-hSRC，能在多項(xiàng)式時(shí)間內(nèi)得到一定比率的近似最優(yōu)總酬勞，而且還考慮了保護(hù)工人出價(jià)隱私的目標(biāo)。而且證明，該機(jī)制滿(mǎn)足ε-差分隱私保護(hù)、近似真實(shí)性和個(gè)體合理性等性質(zhì)，時(shí)間復(fù)雜度被控制在了O(N2*K)。

5.5 實(shí)驗(yàn)結(jié)果

5.5.1 對(duì)比算法

Optimal：最優(yōu)總報(bào)酬。

Baseline Auction：實(shí)現(xiàn)方法略有不同的對(duì)比算法。

5.5.2 實(shí)驗(yàn)參數(shù)設(shè)定

實(shí)驗(yàn)設(shè)置了四種不同的參數(shù)設(shè)定，正如表1所示[15]。

5.5.3 實(shí)驗(yàn)結(jié)果

最終的實(shí)驗(yàn)結(jié)果表明，提出的機(jī)制DP-hSRC在總酬勞上已經(jīng)很接近最優(yōu)算法，同時(shí)效果也比Baseline Auction好很多。

表1 仿真參數(shù)設(shè)定

6 結(jié)束語(yǔ)

由于眾包的工作流程牽涉到任務(wù)準(zhǔn)備、任務(wù)執(zhí)行和答案整合等一系列步驟，期間眾包平臺(tái)和參與者之間也需要進(jìn)行多次的信息交換，所以有很多方面需要對(duì)參與者的隱私數(shù)據(jù)進(jìn)行保護(hù)，也就是在應(yīng)用場(chǎng)景方面還有很大的拓展空間。另一方面，在保護(hù)參與者隱私數(shù)據(jù)的同時(shí)，如何使系統(tǒng)的總體收益更加優(yōu)化，也是一個(gè)可以開(kāi)展的方向，比如在保護(hù)用戶(hù)位置隱私的場(chǎng)景下，系統(tǒng)的總體目標(biāo)函數(shù)還可以是傳感數(shù)據(jù)質(zhì)量最大化，也可以是總花費(fèi)最小，也可以是工人的總體移動(dòng)距離最小。

經(jīng)過(guò)數(shù)年的發(fā)展，眾包機(jī)制已經(jīng)有了長(zhǎng)足的進(jìn)步，對(duì)參與者的隱私數(shù)據(jù)也有了相當(dāng)?shù)谋Ｗo(hù)，但是仍然沒(méi)有到達(dá)成熟的地步，所以未來(lái)還有大量的實(shí)際應(yīng)用開(kāi)發(fā)和優(yōu)化工作有待完成。