基于混洗差分隐私的直方图发布方法
作者:
作者单位:

作者简介:

通讯作者:

基金项目:

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


Histogram Publication under Shuffled Differential Privacy
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
    摘要:

    基于中心化/本地化差分隐私的直方图发布已得到了研究者的广泛关注.用户的隐私需求与收集者的分析精度之间的矛盾直接制约着直方图发布的可用性.针对现有直方图发布方法难以有效同时兼顾用户隐私与收集者分析精度的不足,提出了一种基于混洗差分隐私的直方图发布算法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算法与现有七种直方图发布算法在四种数据集上实验结果表明,其发布精度优于同类算法.

    Abstract:

    Given a distributed set D of categorical data defined on a domain D, we study 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 paper 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 our methods can effectively improve the utility of the histogram, and outperform the existing solutions.

    参考文献
    相似文献
    引证文献
引用本文

张啸剑,徐雅鑫,夏庆荣.基于混洗差分隐私的直方图发布方法.软件学报,,():0

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
历史
  • 收稿日期:2020-11-10
  • 最后修改日期:2021-01-28
  • 录用日期:
  • 在线发布日期: 2021-11-24
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号