疏令

摘要：用戶數(shù)據(jù)的隱私保護已經成了研究熱點，其中局部差分隱私是目前最為完善的隱私保護模型之一，在此基礎上PCMS算法被提出，并應用到實際當中。文中使用采用Adult數(shù)據(jù)集作為原始數(shù)據(jù)，卡方距離作為用戶的原始數(shù)據(jù)與擾動后的數(shù)據(jù)的度量方法。實驗表明PCMS算法具有良好的可用性。

關鍵詞：局部差分隱私;PCMS算法;卡方距離

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

文章編號：1009-3044（2019）22-0059-02

開放科學（資源服務）標識碼（OSID）：

Implementation of PCMS Algorithm Based on Local Differential Privacy

SHU Ling

（ School of Computer Science and Engineering， Anhui University of Science and Technology， Huainan 232001， China）

Abstract： The privacy protection of user data has become a research hotspot. Local differential privacy is one of the most complete privacy protection models. Based on this， the PCMS algorithm is proposed and applied to the actual. In this paper， the Adult data set is used as the original data， and the chi-square distance is used as the measurement method of the user's original data and the disturbed data. Experiments show that the PCMS algorithm has good usability.

Key words： Local differential privacy; PCMS algorithm; Chi-square distance

1 引言

隨著科學技術的飛速發(fā)展，全球計算機與智能手機的用戶已經多到數(shù)以億計。許多部門與企業(yè)在收集用戶的數(shù)據(jù)，于是對于用戶數(shù)據(jù)的隱私保護就成了眾多科研人員與學者的研究對象。在早期的隱私保護模型的研究[1]中，k-anonymity模型、l-diversity模型和t-closeness模型等都被應用于對數(shù)據(jù)隱私的保護，然而這些隱私保護模型都需要一定的背景條件。2006年中心化差分隱私[2]被提出，即使攻擊者掌握了所有背景知識對用戶數(shù)據(jù)隱私也造不成任何威脅。為了在用戶端就對數(shù)據(jù)進行隱私保護，局部差分隱私[3]應運而生。在實際應用中，基于局部差分隱私的PCMS（Private Count Mean Sketch）算法很好地對用戶數(shù)據(jù)進行了隱私保護[4]。

2 基本概念

局部差分隱私：給定有n個數(shù)據(jù)記錄，給定一個隨機化算法M及其定義域Dom（M）和值域Rom（M），如果算法M在任意一對數(shù)據(jù)記錄t和t'（t，t'?Dom（M））上得到的一樣的輸出O（O?Rom（M））滿足下列不等式，則A滿足e-局部差分隱私。

卡方距離[5]可以有效地顯示原始數(shù)據(jù)和隱私保護后的數(shù)據(jù)的偏離程度?？ǚ街档拇笮≌f明了原始數(shù)據(jù)分布與擾動后的差異。卡方值越小，原始數(shù)據(jù)分布就與擾動數(shù)據(jù)分布越相似。若給定兩個數(shù)據(jù)集分布P=（p1，p2，×××，pm），Q=（q1，q2，×××，qm），則卡方距離公式如下：

3 PCMS算法

PCMS算法分為兩個部分，一部分在用戶端，一部分在服務端。設用戶數(shù)據(jù)總體為D，每個數(shù)據(jù)記錄d?D;向量v?{-1，1}m，其中向量長度為m;向量b?{-1，1}m， 其中向量長度為m;哈希函數(shù)集為H，總數(shù)為k，其中hj?H;e為隱私保護預算。

在用戶端算法步驟如下：

Step1.隨機生成j（j?k），得到哈希函數(shù)hj。

Step2.初始化向量v，向量全部由-1組成，個數(shù)為m。

Step3.對數(shù)據(jù)記錄d進行哈希函數(shù)hj映射，并將v向量中對應的比特位由-1改成1。

Step4.給定向量b?{-1，1}m，其中每個比特位以

Step5.將向量v與向量b相乘（v1b1，…，vmbm），得到。

Step6.將向量與索引j發(fā)送給服務端。

在服務端算法步驟如下：

Step1.設定概率。

Step2.將向量。

Step3.初始化矩陣M?{0}k?m，其中行數(shù)為k，列數(shù)為m。

Step4.將向量的哈希函數(shù)索引為j，就加入到對應的矩陣j行中。

Step5.對矩陣M進行以下計算，得到每個用戶數(shù)據(jù)記錄的頻數(shù)。

4 實驗

為了實驗的通用性與可靠性，采用了美國UCI數(shù)據(jù)中人口普查的Adult數(shù)據(jù)集。實驗中的隱私保護預算e分別為2.197、0.762、0.405。為了驗證數(shù)據(jù)的可用性，用卡方距離來度量用戶的原始數(shù)據(jù)集與擾動后的數(shù)據(jù)集的距離，其中數(shù)據(jù)集劃分為2000、4000、8000、16000、32000，并分別進行PCMS算法實驗。其實驗結果如下圖所示：

可以清晰地看出，隱私保護預算e越小，卡方距離越小，數(shù)據(jù)可用性越高。當數(shù)據(jù)集分別取不同數(shù)量時，卡方距離波動較小，數(shù)據(jù)集的大小對數(shù)據(jù)可用性影響較小。在數(shù)據(jù)集的不同屬性下，卡方距離相近，數(shù)據(jù)不同屬性對數(shù)據(jù)可用性影響不大。在總體來看，卡方距離都較小，說明在PCMS算法下，數(shù)據(jù)具有可用性。

5 結束語

實驗結果表明基于局部差分隱私的PCMS算法在保護用戶數(shù)據(jù)隱私的前提下能夠對數(shù)據(jù)記錄進行頻數(shù)統(tǒng)計，數(shù)據(jù)的可用性較好。然而PCMS算法仍有可以改進的地方，用戶數(shù)據(jù)在傳遞時的通信代價較大，算法的計算開銷較大，可以利用相關定理繼續(xù)完善算法。

參考文獻：

[1] 熊平， 朱天清， 王曉峰. 差分隱私保護及其應用[J].計算機學報， 2014，37（1）：101-122.

[2] Dwork C. Differential Privacy： A Survey of Results[C]// International Conference on Theory & Applications of Models of Computation. 2008.

[3]Akter M， Hashem T. Computing Aggregates Over Numeric Data with Personalized Local Differential Privacy[J]. 2017.

[4] Li Y， Dai W， Zhong M， et al. Privacy Protection for Preventing Data Over-Collection in Smart City[J]. IEEE Transactions on Computers， 2016， 65（5）：1339-1350.

[5] Vidal L， Tárrega A， Antúnez L， et al. Comparison of Correspondence Analysis based on Hellinger and chi-square distances to obtain sensory spaces from check-all-that-apply （CATA） questions[J]. Food Quality & Preference， 2015， 43：106-112.

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