基于差分隐私的高精度直方图发布方法

作者：李昆明; 王超迁; 倪巍伟^*; 鲍晓涵

来源：计算机应用, 2020, 40(11): 3242-3248.

• 直方图
• 差分隐私
• 约束推断
• 全局分组
• 动态规划

针对已有基于分组平抑差分噪声误差的隐私保护直方图发布方法无法有效均衡分组近似误差与差分隐私(DP)拉普拉斯误差,从而造成直方图可用性缺失的问题,提出基于差分隐私的高精度直方图发布方法(HPHP)。首先,采用约束推断方法,在满足DP约束的前提下实现直方图排序;然后,基于有序直方图,采用动态规划分组方法在添加噪声的直方图上生成具有最小总误差的分组;最后,在各组均值上添加拉普拉斯噪声。方便对比分析起见,提出具有理论最小误差的隐私保护直方图发布方法(Optimal)。将HPHP与直接添加噪声的DP方法、AHP方法以及Optimal进行实验分析,实验结果表明:相较于AHP方法,HPHP所发布直方图的Kullback-Leibler散度(KLD)能够降低90%,接近Optimal的效果。因此,在相同的预置条件下,HPHP可以在保证满足DP的前提下发布更高精度的直方图。

• 单位
  江苏方天电力技术有限公司; 东南大学