陳航 張帥奇 曾慶馗

摘要：數(shù)據(jù)分析公司通過收集用戶的信息來了解某一群體的統(tǒng)計數(shù)據(jù)，例如通過收集用戶聊天時發(fā)送的最頻繁的表情包來獲取人群的情感分析。然而這一過程中卻可能存在著隱私泄露的問題，針對這一特殊情景，本文基于局部差分隱私算法，將其應(yīng)用在表情包頻數(shù)收集的環(huán)境當中，通過模擬數(shù)據(jù)的多輪測試和實驗，得到了該算法的可用性分析，實驗結(jié)果表明本文所采用的方法可以很好地解決表情包收集的隱私保護問題。

關(guān)鍵詞：局部差分隱私;表情包收集;隱私保護

中圖分類號：TP311? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）19-0208-03

1介紹

伴隨網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，互聯(lián)網(wǎng)企業(yè)數(shù)量暴增，互聯(lián)網(wǎng)企業(yè)需要對獲得用戶的統(tǒng)計信息以更好地提供服務(wù)。通常這些公司會將數(shù)據(jù)送往第三方數(shù)據(jù)分析公司進行數(shù)據(jù)分析，然而在收集用戶信息以改善用戶體驗的過程中也產(chǎn)生了隱私泄漏的問題。包括在數(shù)據(jù)的本地存儲，數(shù)據(jù)的傳輸和數(shù)據(jù)的云端存儲各個環(huán)節(jié)中都有類似的安全事件不斷爆出。例如華住酒店的大量酒店數(shù)據(jù)泄露并在暗網(wǎng)上銷售[1]， Facebook泄露用戶隱私并進行違法濫用[2]。

面對隱私保護日益嚴峻的形勢，如何保障用戶的隱私并解決隱私泄露問題已成為當下熱門的討論話題。k-anonymity[3]、l-diversity[4]、t-closeness[5]等方法相繼被提出用于隱私數(shù)據(jù)的保護，這些方法提供了一些隱私保護思路，但是這類隱私保護方法會通過不同的攻擊方法而泄露敏感信息例如鏈接攻擊[6]。差分隱私[7]作為目前最為流行的隱私保護方法，解決了以上方法存在的問題并定義了隱私保護程度。

傳統(tǒng)的差分隱私模型以中心為基礎(chǔ)，用戶收據(jù)收集到服務(wù)商進行聚合，對數(shù)據(jù)庫進行添加噪聲從而發(fā)布帶有噪聲的中間件以提供查詢服務(wù)。然而，這個過程中存在不可信服務(wù)商的問題，第三方服務(wù)者存在將隱私泄露的風險，例如內(nèi)部員工泄露和遭受惡意攻擊。局部差分隱私[8]針對不可信第三方服務(wù)者，提出了更加合理的隱私保護方法，通過對用戶端發(fā)送的數(shù)據(jù)進行擾動，在服務(wù)器端聚合擾動數(shù)據(jù)的方式來提供差分隱私保障。

在不可信第三方數(shù)據(jù)分析平臺分析數(shù)據(jù)時，存在的隱私泄露風險可以通過局部差分隱私模型消除。本文以不可信第三方數(shù)據(jù)收集者收集用戶表情包為例，實現(xiàn)基于局部差分隱私的表情包收集機制，在提供隱私保障的同時保持較高的數(shù)據(jù)可用性，通過實際環(huán)境部署進行試驗測試。

2 基本概念

定義 局部差分隱私：給定n條用戶的隱私記錄，對于數(shù)據(jù)集中的任意兩條記錄d和d′，若算法A作用于兩條記錄的結(jié)果是相同的，且都為[d*]，即滿足如下的關(guān)系式，則稱A算法滿足[?]-局部差分隱私，其中e稱為隱私保護預(yù)算，其值越大，數(shù)據(jù)可用性越高，越小，對用戶隱私保護的效果越好。

即攻擊者憑借已有的背景知識，即使知道了算法A的輸出也不能輕易推斷出輸入到底是對應(yīng)哪一條記錄，提供了不可確定性。

其中本文應(yīng)用的HCMS（Hadamard Count Mean Sketch）[9]算法引入的隨機噪音，在原始的輸入上添加噪音，是滿足差分隱私定義的，首先客戶端算法是A，對于兩個數(shù)據(jù)條目d和d′，得到相同的輸出[d*]的概率是相近的。

3 算法

假設(shè)一個用戶a給用戶b發(fā)送了一個表情emo1，客戶端算法首先根據(jù)哈希函數(shù)的范圍初始化一個獨熱向量v，然后在k個哈希函數(shù)中隨機選取一個哈希函數(shù)hj，然后通過選取的哈希函數(shù)hj將表情emo1編碼成一個索引，然后把v的第hj（emo1）位比特置為1，然后對向量v進行Hadamard基變換得到向量w，然后隨機選取向量w中的某一位以概率（ee+1）-1進行隨機翻轉(zhuǎn)，最后向服務(wù)器端發(fā)送噪聲報告s。

算法1：HCMS（Hadamard Count Mean Sketch）客戶端算法

輸入：用戶的某個屬性值d∈D，隱私預(yù)算[?]，哈希散列函數(shù)列表

輸出：擾動位w，哈希函數(shù)索引j，擾動位索引

1） 首先從k個哈希函數(shù)中隨機選取一個，記下其索引j

2） 初始化一個m位的向量v，初始值為0

3） 把v的第[hj（d）]位設(shè)為1

4） 構(gòu)建一個大小為m的阿達馬矩陣Hm，使w=Hmv

5） 在v中隨機抽取一個位，記下其索引l

6） 按概率（ee+1）-1隨機翻轉(zhuǎn)[wl]比特位，翻轉(zhuǎn)后的向量記為[w]

7） 返回報告s{[w]，索引j和索引l）

算法2：HCMS（Hadamard Count Mean Sketch）服務(wù)端算法

輸入：n條用戶記錄{（[w（1），j（1），l（1）]），…， （[w（n），j（n），l（n）]）}，隱私預(yù)算[?]，哈希函數(shù)個數(shù)k和向量長度m

1） 使[c?=e?+1e?-1]

2） 初始化長度為n的x二維數(shù)組

3） 對于每一個i∈[n]，使[x（i）=k·c?·w（i）]

4） 初始化一個{0}k*m維度的Mh矩陣

5） 通過Mh=MhHmT將矩陣的行轉(zhuǎn)換回來

6） 計算屬性值d的頻數(shù)[f（d）=（mm-1）（1kl=1kMl，hl（d）-nm）]

7） 返回每個屬性值的頻數(shù)f（d）

為了進一步的解釋此算法，假設(shè)用戶訪問網(wǎng)絡(luò)域名www.example.com?？蛻舳怂惴◤囊唤M候選散列函數(shù){h1，h2，h3，...，hk}中選擇一個隨機哈希函數(shù)，并使用選擇的哈希函數(shù)h1將web域編碼到一個小空間中，我們令h1（www.example.com）=33。這個編碼被寫成一個獨熱向量v=（0， 0， ...， 0， 1， 0， ...， 0， 0），其中，第33位置的值為1。想要傳輸一個比特，一個簡單的方法就是從向量v中采樣并發(fā)送一個隨機坐標，然而，這會顯著增加結(jié)果直方圖中的誤差（方差）。為了減少方差，在v中使用Hadamard基變換矩陣H，以獲得V′=Hv=（+1，?1，…，+1）。例如，有一個從V′中采樣獲得的隨機坐標，相應(yīng)的比特以概率（ee+1）-1進行翻轉(zhuǎn)，從而確保滿足e-差分隱私。發(fā)送到服務(wù)器的報告s包括所選的哈希函數(shù)的索引、采樣的坐標索引和隱私化比特。

服務(wù)器端算法使用的是數(shù)據(jù)結(jié)構(gòu)Sketch矩陣M，將從客戶端那里收集到的隱私向量進行聚合。M矩陣的行向量為哈希函數(shù)的索引，列向量是由樣本的隨機坐標的索引。矩陣的第（j， l）元素聚合了設(shè)備所提交的隱私化向量，即從向量中選擇第j個哈希函數(shù)hj，并采樣第l個坐標。繼而進一步對私有化向量進行適當?shù)臄U展，使用可逆Hadamard矩陣將M轉(zhuǎn)換回原來的基底中。在這個階段，矩陣的每一行都有助于為元素的頻率提供一個無偏差估計量。要計算一個web域www.example.com的頻率，這個算法首先通過讀取j行的M[j，hj （www.example.com）]以獲得M中每一行的無偏差估計，最后計算出這些k估計的平均值以減少方差。

4 實驗

實驗環(huán)境設(shè)置，CPU：i7-7700hq，內(nèi)存：16G，實驗所用數(shù)據(jù)聚為模擬數(shù)據(jù)集使用均勻分布和拉帕拉斯分布隨機生成的數(shù)據(jù)集。使用MAPE（平均絕對值百分比誤差）作為實驗衡量標準，為減小分布偶然性波動對實驗的準確率影響，每個實驗運行10次，以驗證概算的可靠性。

在實驗設(shè)置中分別控制m和k不變，以驗證e和d的改變對實驗造成的影響，在選定k=8192， m=256， n=100000的條件下生成十組滿足均勻分布的模擬數(shù)據(jù)，通過服務(wù)器端算法進行聚合獲得每個屬性的估計值，如圖1所示。

5 結(jié)論

針對收集表情包頻數(shù)這一具體問題，提出了如何保護用戶隱私的同時高效的收集數(shù)據(jù)，采用了局部差分隱私機制作為收集方法，通過實際瀏覽器插件模擬真實收集場景，并部署服務(wù)器端算法以收集數(shù)據(jù)。最后通過仿真實驗對算法機制進行討論，該機制可以很好地保持原始數(shù)據(jù)分布的特征，在數(shù)據(jù)效用和隱私保障方面有很好的效果。然而還存在一些不足的地方，當數(shù)據(jù)量較小時，數(shù)據(jù)可用性較差，以及參數(shù)的最優(yōu)化選取等問題。之后將對這機制進行改進研究，更高效的收集數(shù)據(jù)信息同時保護用戶的隱私。

參考文獻：

[1] https：//www.sohu.com/a/250601044_100216761

[2] https：//www.sohu.com/a/226062595_460436

[3] L. Sweeney. k-anonymity： A model for protecting privacy. International Journal of Uncertainty[J]. Fuzziness and Knowledge-Based Systems，2002，10（5）： 557～570.

[4] A. Machanavajjhala， D. Kifer， J. Gehrke and et al..l-diversity： Privacy beyond k-anonymity[C]. ACM Transactions on Knowledge Discovery from Data （TKDD） 1， no. 1 （2007）： 3

[5] Li， Ninghui， Tiancheng Li， and Suresh Venkatasubramanian. t-closeness： Privacy beyond k-anonymity and l-diversity[C].2007 IEEE 23rd International Conference on Data Engineering. IEEE， 2007.

[6] 楊高明，方賢進，肖亞飛.局部差分隱私約束的鏈接攻擊保護[J].計算機科學與探索，2019， 13（02）：251-262.

[7] Dwork， Cynthia. Differential privacy[J]. Encyclopedia of Cryptography and Security ，2011： 338-340.

[8] Duchi， John C.， Michael I. Jordan， and Martin J. Wainwright. Local privacy and statistical minimax rates[C].2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE， 2013.

[9] Differential Privacy Team Apple. Learning with privacy at scale. Technical report， Apple， 2017

【通聯(lián)編輯：梁書】