本地化差分隱私在數據眾包中的應用*

方俊斌，蔣千越，李愛平

(中國人民解放軍國防科技大學 計算機學院，湖南 長沙 410073)

0 引言

近年來，眾包技術得到了工業界和學術界的廣泛關注。美國《連線》雜志的記者杰夫·豪(Jeff Howe)2006年6月提出：眾包是一個公司或機構把過去由員工執行的工作任務，以自由自愿的形式外包給非特定的大眾網絡的做法[1]。傳統的外包是指以合同的形式把任務委派給指定的人或者機構完成，但是很多任務并不能通過簡單的指定的人或機構通過某些具體算法來實現，這類問題可以借助于眾包模式，直接將任務發布到互聯網，通過開放式集合互聯網上未知的大眾來解決傳統工作方式難以單獨處理的問題[2]，例如Wikipedia、reCAPTCHA、標記圖像、語言翻譯[3]等。因為現實生活中存在著大量類似的問題，因此眾包有著廣大的應用前景和市場。

盡管眾包技術充分利用了群體智慧并帶來極大的效益，但眾包過程中涉及許多數據安全和隱私保護問題尚未得到很好的解決，例如眾包平臺中任務完成者(工人)自身隱私泄露問題、工人產生的數據內容的安全問題、眾包過程中手機、傳感器等軟硬件設施的數據安全問題等。上述隱私泄露的風險，極大限制了眾包技術的應用和推廣。

當前，針對眾包的隱私保護模型主要有基于加密技術的隱私保護模型、基于K-匿名等匿名技術的保護模型和基于差分隱私技術的保護模型等?；诩用艿碾[私保護方法具有較高的隱私保護水平，但其運行開銷巨大，且需要構建專門的數據庫?；谀涿椒ǖ碾[私保護技術具有較好的數據安全性和可用性，目前已經得到較為廣泛的應用，但該方法大都對攻擊者的背景知識做出了前提假設，面對層出不窮、角度多樣的攻擊方式(如組合攻擊、背景知識攻擊、關聯攻擊等)時的抵御能力較弱，存在安全隱患?；诓罘蛛[私的保護模型，不對攻擊者的背景知識做出限定，即使攻擊者已經掌握除某一條記錄之外的所有其他信息，仍能夠對攻擊者未掌握的記錄進行有效保護，具有很強的安全性。對比上述幾種模型，由于差分隱私保護模型較強的隱私保護能力，同時兼顧適當的運行開銷和較好的數據可用性，隨著研究的深入將具有更廣闊的應用前景。

1 眾包技術與隱私問題

1.1 眾包技術

眾包技術是一種分布式的問題解決機制，采用的主要方式是公開召集互聯網大眾參與。眾包任務通常是難以獨自完成的、需要大量參與者共同解決的問題，大眾通過相互協作或獨立的方式完成分發的任務。根據參與眾包的不同形式，眾包被分為協作式眾包和競賽式眾包。協作式眾包的任務是需要大眾協作來完成的，競賽式眾包的任務通常是由個人獨立完成。

協作式眾包中典型的案例有維基百科Wikipedia和reCAPTCHA等。維基百科是開放的、自由的、免費的百科全書編輯平臺，任何大眾都可以進行編輯和修改。reCAPTCHA項目則通過在驗證碼中嵌入書籍的掃描信息，來完成紙質書籍的電子化[4]。

競賽式眾包中典型的例子是Amazon Mechanical Turk(Mturk)。Mturk為任務請求者和工人構建了一個在線平臺，為雙方提供數據收集、分類工作等任務的發布與接受服務。

1.2 眾包模型中的隱私問題

以典型的競爭式眾包為例，假設一個空間眾包平臺，為任務請求者和工人建立基于位置信息等空間任務的合作關系，并負責任務請求者和工人提交的空間任務、個人位置等信息的綜合處理。

圖1展示了空間眾包的基本工作流程。

圖1 空間眾包的工作流程

空間眾包平臺收集任務請求者提交的任務以及工人的位置等信息，并由數據處理模塊預處理后提交至任務分配模塊，由任務分配模塊完成任務的分配，最后在工人完成任務后提交至質量控制模塊，綜合分析并反饋給任務請求者。

在這個場景中，空間眾包平臺在數據處理的各個環節都可能存在用戶、工人、服務內容等方面的隱私泄露問題，例如任務請求者發布任務的內容可能泄露其自身信息、工人的位置數據等包含個人住址、健康狀況、生活習慣等許多隱私。這種隱私泄露的風險，極大打擊用戶使用眾包技術的信心。

2 眾包隱私保護模型及應用

2.1 本地化差分隱私保護模型

DWORK C[5]等人提出了差分隱私，這是一種有數學理論支撐并且對隱私泄露風險給出定量表示的方法。差分隱私在原始數據上添加隨機噪聲，使得對任意與-1條信息查詢返回的結果幾乎一致，即無法通過差分攻擊從數據集中識別出個體信息，同時還能保持數據的統計特性，便于執行良性的聚合分析，實現較高的數據可用性。將差分隱私技術運用到眾包中，能夠有效防止基于背景知識的惡意攻擊[6]。

目前，差分隱私技術的研究主要分兩種[7]。一是中心化差分隱私保護技術。其要求可信的第三方數據收集者對原始數據進行隱私化處理。二是本地化差分隱私技術(Local Differential Privacy,LDP)。LDP中，用戶在上傳數據前先對個體數據進行隱私化處理，第三方收集的用戶數據只涉及加噪后的泛化信息，原始數據被保護在本地設備，降低了非可信第三方隱私泄露的風險。LDP的形式化定義如下[8]:

定義：給定n個用戶，每個用戶對應一條記錄，給定一個隱私算法M及其定義域Dom(M)和值域Ran(M)，若算法M在任意兩條記錄t和t′(t,t′∈Dom(M))上得到相同輸出結果t*(t*∈Ran(M))滿足下列不等式，則M滿足ε-本地化差分隱私。

Pr[M(t)=t*]≤eεPr[M(t′)=t*]

即LDP通過控制任意兩條記錄輸出結果的相似性，確保算法M滿足ε-本地化差分隱私。根據隱私算法M的某個輸出結果，幾乎無法推理出其輸入數據為哪一條記錄。

LDP數據處理框架如圖2所示。

圖2 本地化差分隱私處理框架

在常規的中心化差分隱私保護技術中，為保證算法滿足ε-差分隱私，需要噪聲機制的介入，常用的噪聲機制包括拉普拉斯機制[9]和指數機制[10]。其中，拉普拉斯機制面向連續型數據的查詢，而指數機制面向離散型數據的查詢。上述兩種噪聲機制均與查詢函數的全局敏感性密切相關，而全局敏感性定義在至多相差一條記錄的近鄰數據集之上，使得攻擊者無法根據統計結果推測個體記錄。在LDP中，用戶上傳至第三方的數據已經過隱私化處理，用戶無法獲知其他用戶的數據，即LDP中不存在全局敏感性的概念，因此拉普拉斯機制和指數機制并不適用。目前，LDP主要采用隨機響應技術、Bloom Filter[11]等技術來確保隱私算法滿足ε-本地化差分隱私。LDP下，離散型數據的隨機響應方法包括 RAPPOR[12]、S-Hist[13]、k-RR[14]和O-RR[15]等，連續型數據的隨機響應方法有MeanEst[16]和 Harmony-mean[17]等。

LDP相比中心化差分隱私具有更廣泛的應用場景，十分適用于當前的眾包模型。在上述的空間眾包模型中引入LDP技術，每個用戶(包括任務發布者和工人)先在各自本地對數據進行隱私化處理，再將隱私化后的數據發送給眾包平臺，眾包平臺對采集到的隱私化數據進行集合、統計特征分析、綜合應用與反饋等處理。在此過程中，敏感的原始數據都保留在用戶本地，眾包平臺僅對隱私化的數據進行操作，有效保證個體的隱私信息不被泄露。

另外，由于差分隱私保護模型本質上是通過添加噪聲實現對數據的擾動，使算法滿足ε-差分隱私。噪聲越大，對數據的保護程度越高，數據可用性就會降低。反之，噪聲越低，隱私保護程度越低，數據可用性越大。因此，如何針對不同的眾包應用場景，界定隱私與數據可用性，在其之間進行有效的權衡，并設計適當的隱私算法，確保模型同時具有高隱私性和高可用性，是當前LDP模型的研究重點。

2.2 研究與應用

當前，本地化差分隱私技術在數據眾包中的研究持續深入研究與發展，并在許多場景中得到應用。

2.2.1主要研究方向

(1) 針對高維數據的研究。隨著各種傳感器和人群感知系統的發展，眾包數據信息不斷向高維發展，數據之間的關聯性日益加強，眾包參與者的隱私更容易被推斷或者識別。針對這個特點，Ren Xuebin等[18]提出一個基于本地化差分隱私技術的高維眾包數據發布算法LoPub。LoPub基于EM和Lasso回歸，可以從分布式用戶收集和構建高維數據，并通過將數據集分割成許多緊湊的聚類來降低原始數據集中的維數和稀疏度。在對聚類的分布進行分析之后，從中繪制一個新的數據集，從而實現對整個原始人群數據的近似處理，同時保證個人隱私。文獻[17]研究了智能手機端收集用戶的多種數值和類別數據中本地化差分隱私機制Harmony，既可以處理數值型數據，又可以處理類別型數據；在ε-差分隱私下，文獻[17]研究了線性回歸、邏輯回歸和SVM分類器在訓練參數過程中使用SGD方法避免受到噪聲干擾的mini-batch數。

2.2.2當前主要應用

(1) Google的RAPPOR技術。Google在Chrome瀏覽器中采用RAPPOR[12]技術，利用隨機應答策略和Bloom Filter實現了針對客戶端群體的類別、頻率、直方圖和字符串類型統計數據的隱私保護分析，為提供差分隱私保護。在RAPPOR中，采用永久和即時的隨機響應，可以單獨調節隱私保護水平，而且Bloom Filter可以增加額外的不確定性，不僅壓縮報文大小，更增加攻擊者的攻擊難度。在解碼過程中結合成熟的假設檢驗、最小二乘求解和LASSO回歸實現了針對字符串抽樣群體頻率的高可用解碼框架。此外，RAPPOR的改進模型實現了數據字典未知情況下的本地學習多變量聯合概率分布估計。

(2) Apple的本地化差分隱私部署應用。Apple在2016年6月的WWDC上正式宣布，在iOS 10及以后的產品中使用本地差分隱私技術。利用本地差分隱私技術，服務器以眾包的方式學習由用戶客戶端設備生成的信息，同時保持客戶端設備的本地隱私[22]。系統為本地數據添加隨機信息，使得Apple無法將數據與每個用戶設備關聯，又能通過大量加噪數據分析出用戶群體的使用模式。其應用主要涉及局部抽樣、散列加密、噪聲擾動等手段。

3 結束語

差分隱私作為一種隱私保護模型，最強大的地方在于只要算法每一個步驟都滿足差分隱私的要求，那么它可以保證這個算法的最終輸出結果滿足差分隱私，即攻擊者具有足夠多的背景知識，也無法在最終的輸出中找出單個人的某項屬性。作為數據眾包中的一種隱私保護手段，本地化差分隱私表現出了足夠的防護能力和應用潛力。但在技術飛速發展、數據眾包技術也不斷演變的今天，對于本地化差分隱私保護技術，還存在理論和應用上的一些難題和新的研究方向，有待進一步深入探索。總的來說，本地化差分隱私在眾包等領域中已經取得了一些研究成果，但作為一個新的保護手段，仍然需要不斷深入研究，以取得更大的理論和應用成果。

[1] 馮劍紅, 李國良, 馮建華. 眾包技術研究綜述[J]. 計算機學報, 2015, 38(9): 1713-1726.

[2] HOWE J. Crowdsourcing: why the power of the crowd is driving the future of business[M]. 2008.

[3] IPEIROTIS P G. Analyzing the amazon mechanical turk marketplace[J]. Social Science Electronic Publishing, 2010, 17(2):16-21.

[4] VON AHN L, MAURER B, MCMILLEN C, et al. Recaptcha: human-based character recognition via web security measures[J]. Science, 2008, 321(5895): 1465-1468.

[5] DWORK C. Differential privacy: a survey of results[C]. International Conference on Theory and Applications of Models of Computation. Springer, Berlin, Heidelberg, 2008: 1-19.

[6] 張琳, 劉彥, 王汝傳. 位置大數據服務中基于差分隱私的數據發布技術[J]. 通信學報, 2016, 37(9): 46-54.

[7] 高志強, 王宇濤. 差分隱私技術研究進展[J]. 通信學報, 2017, 38(S1): 151-155.

[8] 葉青青, 孟小峰, 朱敏杰, 等. 本地化差分隱私研究綜述[J/OL]. 軟件學報, 2018, 29(7). http://www.jos.org.cn/1000-9825/5364.ht

[9] DWORK C, MCSHERRY F, NISSIM K. Calibrating Noise to Sensitivity in Private Data Analysis[M].Theory of Cryptography. Springer Berlin Heidelberg, 2006:637-648.

[10] MCSHERRY F, TALWAR K. Mechanism design via differential privacy[C]// IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 2007:94-103.

[11] BLOOM B H. Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM, 1970, 13(7): 422-426.

[13] BASSILY R, SMITH A. Local, private, efficient protocols for succinct histograms[C]//Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing. ACM, 2015: 127-135.

[14] KAIROUZ P, OH S, VISWANATH P. Extremal mechanisms for local differential privacy[C]//Advances in Neural Information Processing Systems, 2014: 2879-2887.

[15] KAIROUZ P, BONAWITZ K, RAMAGE D. Discrete distribution estimation under local privacy[J]. arXiv preprint arXiv:1602.07387, 2016.

[16] DUCHI J C, JORDAN M I, WAINWRIGHT M J. Local privacy, data processing inequalities, and statistical minimax rates[J]. arXiv preprint arXiv:1302.3203, 2013.

[17] NGUYêN T T, XIAO X, YANG Y, et al. Collecting and analyzing data from smart device users with local differential privacy[J]. arXiv preprint arXiv:1606.05053, 2016.

[18] REN X, YU C M, YU W, et al. LoPub: high-dimensional crowdsourced data publication with local differential privacy[J]. IEEE Transactions on Information Forensics and Security, 2018, 13(9): 2151.

[19] BASSILY R, STEMMER U, THAKURTA A G. Practical locally private heavy hitters[C]//Advances in Neural Information Processing Systems, 2017: 2285-2293.

[20] QIN Z, YANG Y, YU T, et al. Heavy hitter estimation over set-valued data with local differential privacy[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2016: 192-203.

[21] BUN M, NELSON J, STEMMER U. Heavy hitters and the structure of local privacy[C]//Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. ACM, 2018: 435-447.

[22] THAKURTA A G, VYRROS A H, VAISHAMPAYAN U S, et al. Learning new words[P].US: US15477921, 2018-02-08.