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

High-precision histogram publishing method based on differential privacy

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

Aiming at the problem that the existing privacy protection histogram publishing methods based on grouping to suppress differential noise errors cannot effectively balance the group approximation error and the Differential Privacy(DP)Laplacian error,resulting in the lack of histogram availability,a High-Precision Histogram Publishing method(HPHP)was proposed.First,the constraint inference method was used to achieve the histogram ordering under the premise of satisfying the DP constraints.Then,based on the ordered histogram,the dynamic programming grouping method was used to generate groups with the smallest total error on the noise-added histogram.Finally,the Laplacian noise was added to each group mean.For the convenience of comparative analysis,the privacy protection histogram publishing method with the theoretical minimum error(Optimal)was proposed.Experimental analysis results between HPHP,DP method with noise added directly,AHP(Accurate Histogram Publication)method and Optimal show that the Kullback-Leibler Divergence(KLD)of the histogram published by HPHP is reduced by 90%compared to that of AHP method and is close to the effect of Optimal.In conclusion,under the same pre-conditions,HPHP can publish higher-precision histograms on the premise of ensuring DP.