基于混洗差分隐私的直方图发布方法

摘要

基于中心化/本地化差分隐私的直方图发布已得到了研究者的广泛关注.用户的隐私需求与收集者的分析精度之间的矛盾直接制约着直方图发布的可用性.针对现有直方图发布方法难以有效同时兼顾用户隐私与收集者分析精度的不足,提出了一种基于混洗差分隐私的直方图发布算法HP-SDP(histogram publication with shuffled differential privacy).该算法结合本地哈希编码技术所设计的混洗应答机制SRR (shuffled randomized response),能够以线性分解的方式扰动用户数据以及摆脱数据值域大小的影响.结合SRR机制产生的用户消息,设计了一种基于堆排列技术的用户消息均匀随机排列算法MRS (message random shuffling),混洗方利用MRS对所有用户的消息进行随机排列.由于经过MRS混洗后的消息满足中心化差分隐私,使得恶意收集者无法通过消息与用户之间的链接对目标用户进行身份甄别.此外,HP-SDP利用基于二次规划技术的后置处理算法POP(post-processing)对混洗后的直方图进行求精处理. HP-SDP算法与现有的7种直方图发布算法在4种数据集上所做实验结果表明,其发布精度优于同类算法.