眾包環境下的隱私保護研究

劉 歡，吳桂興

(中國科學技術大學 軟件學院，江蘇 蘇州 215123)

0 引 言

在經濟全球化的發展進程中，企業將會面臨越來越大的競爭壓力。對于那些企業難以單獨完成的任務，眾包可以聚集海量的互聯網用戶，使它們通過合作或者獨立的方式來完成，同時給予完成者一定的報酬獎勵。然而在眾包平臺的運行中，平臺、任務請求者和參與者之間常常需要進行信息交換，如果處理不當，可能會引起用戶敏感信息的泄露，從而給用戶的信息安全造成意想不到的傷害。

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

一方面，對眾包的定義、工作流程以及差分隱私的數學定義和保護水平評價標準進行了介紹；另一方面，還對不同眾包應用場景下，如何使用差分隱私保護參與者個人數據的安全，以及該技術路線如何實現等進行了闡述。接著在這兩方面的基礎上，對不同眾包場景下差分隱私的應用情況進行了總結，尋找改進空間，并指出了未來的研究方向。

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

1.1 基本定義

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

定義1(眾包)：眾包是一種公開面向互聯網大眾的分布式的問題解決機制，它通過整合計算機和互聯網上未知的大眾來完成計算機難以單獨完成的任務[5]。

1.2 工作流程

一般來說，在眾包應用中通常存在兩種角色：任務請求人(requester)和工人(worker)。

當任務請求人需要通過眾包來完成自己的任務時，他可以執行以下操作：設計任務；將任務發布到眾包平臺上；接收/拒絕工人的答案；整合工人們提交的答案，獲得最終的結果。而工人則需要執行以下步驟：選擇自己感興趣的任務；接受任務；執行任務；提交答案。根據每個步驟執行時間的先后順序，可以將眾包的工作流程大致分成為三個階段：任務準備、任務執行以及整合答案。

2 差分隱私

2.1 基本定義

2006年，為了解決統計數據庫領域內的隱私泄露問題，Dwork提出了一種全新的隱私定義[6]。

定義2(差分隱私)：設有一隨機算法M,M所有可能產生的結果組成的集合為PM，SM則是PM的子集，D和D'是兩個鄰近數據集。那么對于任意的D、D'和SM，如果有Pr[M(D)∈SM]≤exp(ε)×Pr[M(D')∈SM]，則稱算法M提供ε-差分隱私保護，其中參數ε被稱為隱私保護預算。一般來說，ε越小，意味著隱私保護水平越高。

在文獻[7]中，通過對輸出結果進行隨機化處理，算法M對隱私提供了保護。與此同時，參數ε保證了當數據集中某一個記錄發生變化時，算法輸出相同結果的概率差被控制在一個極小的范圍內，而這個范圍是可以被數據所有者接受的。

2.2 實現機制

差分隱私的實現機制主要有Laplace機制(Laplace mechanism)[8]和指數機制(exponential mechanism)[9]。其中，Laplace機制是對數值型結果進行保護，而指數機制則是對非數值型結果提供保護。

2.2.1 Laplace機制

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

2.2.2 指數機制

在很多應用情況下，查詢結果并不僅僅只是數值型的，也可能會是實體對象型的(比如一種方案或選擇)，所以，McSherry等提出了指數機制。

設Range是查詢函數的輸出域，對于任意r∈Range，均為實體對象。在指數機制中，輸出值r的可用性函數可表示為q(D,r)→R，可以用來對r的優劣程度進行評估。

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

3 差分隱私在保護用戶提供的數據中的應用

文獻[10]提出了一個和以前的研究不同的模式，即假設數據收集者是不可信任的。這樣一來，目標群體就可以完全掌控自己的數據隱私，只提交一個經過隱私處理的版本給數據收集者即可。同時，數據收集者也不再負有保護這些隱私數據的責任，消除了隱私泄露帶來的風險。

3.1 基本設定

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

圖1 模型的信息結構

文獻針對V(ε)提出并證明了其下界和上界，還闡明了這些界限在報酬準確性問題里的應用，即數據收集者在保證W的準確性目標的情況下，如何最小化總報酬。

3.2 V(ε)的下界

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

(1)

其中，g'是個體隱私花費函數的一個變形。

經過證明，對任意ε>0，都有ε水平的隱私價值V(ε)≥VLB(ε)。

3.3 V(ε)的上界

為了方便，定義了：

(2)

其中，對任意ε>0，都有d>0。

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

3.4 報酬-準確性問題

在得到上面關于隱私價值函數V(ε)的上下界之后，還可以將其應用到報酬-準確性問題中去。

在給出準確性目標τ之后，可以用F(τ)來表示為了實現τ而要付出的最小總報酬。因為已經有了隱私價值函數V(ε)的上下界，所以也能輕易得出F(τ)的上下界。

4 差分隱私在保護用戶位置中的應用

在傳統的移動群智應用中，有些任務是需要工人到達指定地點才能完成的，因此，為了實現最優的任務分配，比如使工人的移動距離最小化，平臺往往需要事先知曉工人們的準確位置。但是位置信息是工人們的個人隱私，暴露給平臺會引起人們的安全擔憂，同時，并不是每個工人最終都會被分配任務，這樣他們的位置隱私也就白白泄露了。如何在任務分配的過程中既注意保護工人們的位置隱私，又能使目標函數實現最優化就成為一個需要解決的難題。

文獻[11]針對這個問題提出了一個解決框架，在此框架下，允許工人們將自己的位置信息模糊化之后再提供給眾包平臺。這樣一來不僅滿足了差分隱私，而且不用牽涉到任何第三方。接下來，將依次介紹該框架的工作流程、差分隱私保護、目標函數以及實驗結果。

4.1 工作流程

該平臺運行過程包含三個步驟：平臺端生成地理位置模糊函數；用戶端對位置信息進行模糊化；平臺端分析模糊結果，并進行任務分配。

4.2 差分隱私保護

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

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

4.3 目標函數

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

4.3.1 位置模糊函數

簡單來說，在生成位置模糊函數P時，需要考慮的問題是：(1)使被選工人的移動距離最小化；(2)P同時滿足差分隱私。

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

(3)

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

(4)

4.3.2 任務分配

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

(5)

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

接下來則可以使用Benders分解[13]和遺傳算法(genetic algorithm，GA)[14]對問題進行求解。

4.4 實驗結果

文獻[11]既在模擬數據集上，又在真實數據集D4D上進行了實驗。從實驗結果可以看出，在各種參數設定下，該文獻算法的效果都要優于對比算法。

5 差分隱私在保護用戶出價中的應用

文獻[15]提出了一種差分隱私化的激勵機制，以保護工人們的出價隱私。接下來，將詳細介紹該機制的實現過程。

5.1 工作流程

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

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

(3)根據工人們的出價信息，眾包平臺最終決定任務的分配，以及最終給工人們的報酬pi；

(4)當被分配到任務的工人執行完以后，需要將結果反饋給平臺，平臺對所有的結果進行處理整合，得到最終的任務結果，并付給工人報酬。

5.2 hSRC Auction

5.3 差分隱私保護

文獻將提出的hSRC拍賣機制看作將出價信息b映射到報酬P的函數M(·),當且僅當M滿足如下條件時，稱M是符合ε-差分隱私的：

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

其中，A是報酬集合；b和b'是只相差一個出價的出價集合；ε稱為隱私預算，其值越小，表示隱私保護水平越高。

這樣一來，當某個工人的出價集合b發生變化時，其最后對應的報酬集合并不會發生明顯的變化，從而確保了某些好奇的工人無法從報酬集合上推斷出該工人的出價信息，就實現了保護工人出價隱私的目標。

5.4 機制設計

在付給工人酬勞時，將使平臺要支付的總酬勞最小化稱為TPM(total payment minimization)問題。同時，文獻證明了TPM是NP難問題。所以，無法在多項式時間內計算出使總酬勞最小的那個任務分配集。針對這種情況，文獻設計了一種機制DP-hSRC，能在多項式時間內得到一定比率的近似最優總酬勞，而且還考慮了保護工人出價隱私的目標。而且證明，該機制滿足ε-差分隱私保護、近似真實性和個體合理性等性質，時間復雜度被控制在了O(N2*K)。

5.5 實驗結果

5.5.1 對比算法

Optimal：最優總報酬。

Baseline Auction：實現方法略有不同的對比算法。

5.5.2 實驗參數設定

實驗設置了四種不同的參數設定，正如表1所示[15]。

5.5.3 實驗結果

最終的實驗結果表明，提出的機制DP-hSRC在總酬勞上已經很接近最優算法，同時效果也比Baseline Auction好很多。

表1 仿真參數設定

6 結束語

由于眾包的工作流程牽涉到任務準備、任務執行和答案整合等一系列步驟，期間眾包平臺和參與者之間也需要進行多次的信息交換，所以有很多方面需要對參與者的隱私數據進行保護，也就是在應用場景方面還有很大的拓展空間。另一方面，在保護參與者隱私數據的同時，如何使系統的總體收益更加優化，也是一個可以開展的方向，比如在保護用戶位置隱私的場景下，系統的總體目標函數還可以是傳感數據質量最大化，也可以是總花費最小，也可以是工人的總體移動距離最小。

經過數年的發展，眾包機制已經有了長足的進步，對參與者的隱私數據也有了相當的保護，但是仍然沒有到達成熟的地步，所以未來還有大量的實際應用開發和優化工作有待完成。