基于局部差分隱私的表情包收集機制

陳航 張帥奇 曾慶馗

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

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

中圖分類號：TP311? ? ? 文獻(xiàn)標(biāo)識碼：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ù)分析公司進(jìn)行數(shù)據(jù)分析，然而在收集用戶信息以改善用戶體驗的過程中也產(chǎn)生了隱私泄漏的問題。包括在數(shù)據(jù)的本地存儲，數(shù)據(jù)的傳輸和數(shù)據(jù)的云端存儲各個環(huán)節(jié)中都有類似的安全事件不斷爆出。例如華住酒店的大量酒店數(shù)據(jù)泄露并在暗網(wǎng)上銷售[1]， Facebook泄露用戶隱私并進(jìn)行違法濫用[2]。

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

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

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

2 基本概念

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

即攻擊者憑借已有的背景知識，即使知道了算法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進(jìn)行Hadamard基變換得到向量w，然后隨機選取向量w中的某一位以概率（ee+1）-1進(jìn)行隨機翻轉(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的阿達(dá)馬矩陣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）

為了進(jìn)一步的解釋此算法，假設(shè)用戶訪問網(wǎng)絡(luò)域名www.example.com。客戶端算法從一組候選散列函數(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ā)送一個隨機坐標(biāo)，然而，這會顯著增加結(jié)果直方圖中的誤差（方差）。為了減少方差，在v中使用Hadamard基變換矩陣H，以獲得V′=Hv=（+1，?1，…，+1）。例如，有一個從V′中采樣獲得的隨機坐標(biāo)，相應(yīng)的比特以概率（ee+1）-1進(jìn)行翻轉(zhuǎn)，從而確保滿足e-差分隱私。發(fā)送到服務(wù)器的報告s包括所選的哈希函數(shù)的索引、采樣的坐標(biāo)索引和隱私化比特。

服務(wù)器端算法使用的是數(shù)據(jù)結(jié)構(gòu)Sketch矩陣M，將從客戶端那里收集到的隱私向量進(jìn)行聚合。M矩陣的行向量為哈希函數(shù)的索引，列向量是由樣本的隨機坐標(biāo)的索引。矩陣的第（j， l）元素聚合了設(shè)備所提交的隱私化向量，即從向量中選擇第j個哈希函數(shù)hj，并采樣第l個坐標(biāo)。繼而進(jìn)一步對私有化向量進(jìn)行適當(dāng)?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（平均絕對值百分比誤差）作為實驗衡量標(biāo)準(zhǔn)，為減小分布偶然性波動對實驗的準(zhǔn)確率影響，每個實驗運行10次，以驗證概算的可靠性。

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

5 結(jié)論

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

參考文獻(xiàn)：

[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ìn)，肖亞飛.局部差分隱私約束的鏈接攻擊保護(hù)[J].計算機科學(xué)與探索，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)編輯：梁書】