基于直方图的隐私键-值数据收集算法

张啸剑 徐雅鑫 付 楠 孟小峰

1(河南财经政法大学计算机与信息工程学院 郑州 450002) 2(中国人民大学信息学院 北京 100872)

(xjzhang82@ruc.edu.cn)

移动互联网环境下的新兴技术快速发展与应用，使得键-值(key-value)数据的获取与收集变得尤为容易，例如网购、健康医疗、金融等数据的收集与分析.键-值数据收集与分析能够提升产品服务与设备服务的质量，以及向用户提供个性化的体验.然而，键-值数据通常蕴含着丰富的个人敏感信息，在提供给收集者或者第三方应用的同时，个人的敏感信息有可能被泄露.表1为某不可信购物网站收集用户购买与评分的记录.通过表1中键的频率以及键所对应值的均值分析，可以学习出用户的购物行为模式与偏好.例如，商品k2的频率为2，k2所对应值的均值为0.61.不可信收集者分析出k2的频率之后，即可对表1中的用户进行统计攻击.因此，在此情景下，用户无法控制自己的隐私数据.本地差分隐私保护技术的出现有效地解决了此类矛盾.该技术允许每个用户扰动自身数据之后再响应收集者的需求.

目前基于本地差分隐私的键-值收集算法包括PrivKV[1],KVUE[2],KVOH[2],PCKV-GRR[3],LDPKV[4].PrivKV,KVUE,KVOH,LDPKV算法基于键的整个值域进行编码，利用简单随机抽样技术减少收集者与用户之间的通信代价.然而，这4种算法均没有考虑到键的值域稀疏性与偏斜性问题.例如，假设表1中商品的值域为7.以u3为例，对其键编码之后可以获得长度为7的向量(〈1,0.6〉,〈0,0〉,〈0,0〉,〈0,0〉,〈0,0〉,〈0,0〉,〈0,0〉).基于该向量进行随机抽样时，〈0,0〉以67的概率被抽取到，而〈0,0〉对最终统……