基于局部差分隐私的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.

【通聯编辑：梁书】