文献类型：期刊文献

中文题名：基于混洗差分隐私的直方图发布方法

英文题名：Histogram Publication under Shuffled Differential Privacy

作者：张啸剑[1];徐雅鑫[1];夏庆荣[1]

第一作者：张啸剑

机构：[1]河南财经政法大学计算机与信息工程学院,河南郑州450046

第一机构：河南财经政法大学计算机与信息工程学院

年份：2022

卷号：33

期号：6

起止页码：2348-2363

中文期刊名：软件学报

外文期刊名：Journal of Software

收录：CSTPCD;;EI(收录号：20222412217544);Scopus;北大核心:【北大核心2020】；CSCD:【CSCD2021_2022】；

基金：国家自然科学基金(61502146,91646203,91746115,62072156);河南省自然科学基金(162300410006);河南省科技攻关项目(202102310563);河南财经政法大学青年拔尖人才资助计划。

语种：中文

中文关键词：中心化差分隐私;本地化差分隐私;混洗差分隐私;直方图发布;消息混洗;后置处理

外文关键词：central differential privacy;local differential privacy;shuffled differential privacy;histogram publication;message shuffling;post-processing

摘要：基于中心化/本地化差分隐私的直方图发布已得到了研究者的广泛关注.用户的隐私需求与收集者的分析精度之间的矛盾直接制约着直方图发布的可用性.针对现有直方图发布方法难以有效同时兼顾用户隐私与收集者分析精度的不足,提出了一种基于混洗差分隐私的直方图发布算法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种数据集上所做实验结果表明,其发布精度优于同类算法.
Given a distributed set D of categorical data defined on a domain D, this work studies differentially private algorithms for releasing a histogram to approximate the categorical data distribution in D. Existing solutions for this problem mostly use central/local differential privacy models, which are two extreme assumptions of differential privacy. The two models, however, cannot balance the contradiction between the privacy requirement of users and the analysis accuracy of collectors. To remedy the deficiency caused by the current solutions under central/local differential privacy, this study proposes a differentially private method in a shuffling way, called HP-SDP, to release histogram. HP-SDP firstly employs the local hash technology to design the shuffled randomized response mechanism.Based on this mechanism, each user perturbs her/his data in a linear decomposition way of perturbation function, without worrying about the domain size, and reports the perturbed messages to the shuffler. And then, the shuffler in HP-SDP permutes the reported messages by using a uniformly random permutation method, which makes sure the shuffled messages satisfy central differential privacy, and the collector cannot reidentify a target user. Furthermore, HP-SDP adopts the convex programming technology to boost the accuracy of the released histogram. Theoretical analysis and experimental evaluations show that the proposed methods can effectively improve the utility of the histogram, and outperform the existing solutions.