基于局部差分隱私的PCMS算法實現

疏令

摘要：用戶數據的隱私保護已經成了研究熱點，其中局部差分隱私是目前最為完善的隱私保護模型之一，在此基礎上PCMS算法被提出，并應用到實際當中。文中使用采用Adult數據集作為原始數據，卡方距離作為用戶的原始數據與擾動后的數據的度量方法。實驗表明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 引言

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

2 基本概念

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

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

3 PCMS算法

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

在用戶端算法步驟如下：

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

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

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

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

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

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

在服務端算法步驟如下：

Step1.設定概率。

Step2.將向量。

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

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

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

4 實驗

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

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

5 結束語

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

參考文獻：

[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.

【通聯編輯：梁書】