High-precision histogram publishing method based on differential privacy

doi:10.11772/j.issn.1001-9081.2020030379

Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (11): 3242-3248.DOI: 10.11772/j.issn.1001-9081.2020030379

• Cyber security • Previous Articles Next Articles

High-precision histogram publishing method based on differential privacy

LI Kunming¹, WANG Chaoqian², NI Weiwei², BAO Xiaohan²

1. Smart Grid Service Center, Jiangsu Frontier Electric Technology Company Limited, Nanjing Jiangsu 210000, China;
2. College of Computer Science and Engineering, Southeast University, Nanjing Jiangsu 211189, China

Received:2020-03-30 Revised:2020-05-29 Online:2020-11-10 Published:2020-06-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61772131).

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

李昆明¹, 王超迁², 倪巍伟², 鲍晓涵²

1. 江苏方天电力技术有限公司智能电网服务中心, 南京 210000;
2. 东南大学计算机科学与工程学院, 南京 211189

通讯作者: 倪巍伟(1979-),男,江苏淮安人,教授,博士生导师,博士,CCF会员,主要研究方向:数据隐私保护、数据挖掘、复杂数据管理;wni@seu.edu.cn
作者简介:李昆明(1984-),男,黑龙江安达人,工程师,主要研究方向:大数据、数据隐私保护;王超迁(1997-),男,河北邢台人,硕士研究生,主要研究方向:数据隐私保护;鲍晓涵(1996-),女,安徽宣城人,硕士研究生,主要研究方向:数据隐私保护
基金资助:
国家自然科学基金资助项目（61772131）。

Abstract

Abstract: 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.

Key words: histogram, Differential Privacy (DP), constraint inference, global grouping, dynamic programming

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

关键词: 直方图, 差分隐私, 约束推断, 全局分组, 动态规划

CLC Number:

TP311

LI Kunming, WANG Chaoqian, NI Weiwei, BAO Xiaohan. High-precision histogram publishing method based on differential privacy[J]. Journal of Computer Applications, 2020, 40(11): 3242-3248.

李昆明, 王超迁, 倪巍伟, 鲍晓涵. 基于差分隐私的高精度直方图发布方法[J]. 计算机应用, 2020, 40(11): 3242-3248.

References

[1] DWORK C. Differential privacy[C]//Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming,LNCS 4052. Berlin:Springer,2006:1-12.
[2] HAY M,RASTOGI V,MIKLAU G,et al. Boosting the accuracy of differentially private histograms through consistency[J]. Proceedings of the VLDB Endowment,2010,3(1/2):1021-1032.
[3] XIAO X,WANG G,GEHRKE J. Differential privacy via wavelet transforms[J]. IEEE Transactions on Knowledge and Data Engineering,2011,23(8):1200-1214.
[4] CORMODE G, PROCOPIUC C, SRIVASTAVA D, et al. Differentially private spatial decompositions[C]//Proceedings of the IEEE 28th International Conference on Data Engineering. Piscataway:IEEE,2012:20-31.
[5] ACS G, CASTELLUCCIA C, CHEN R. Differentially private histogram publishing through lossycompression[C]//Proceedings of the IEEE 12th International Conference on Data Mining. Piscataway:IEEE,2012:1-10.
[6] XU J,ZHANG Z,XIAO X,et al. Differentially private histogram publication[J]. VLDB Journal,2013,22(6):797-822.
[7] KELLARIS G,PAPADOPOULOS S. Practical differential privacy via grouping and smoothing[J]. Proceedings of the VLDB Endowment,2013,6(5):301-312.
[8] 张啸剑, 邵超, 孟小峰. 差分隐私下一种精确直方图发布方法[J]. 计算机研究与发展,2016,53(5):1106-1117.(ZHANG X J, SHAO C, MENG X F. Accurate histogram release under differential privacy[J]. Journal of Computer Research and Development,2016,53(5):1106-1117.)
[9] ZHANG X,CHEN R,XU J,et al. Towards accurate histogram publication under differential privacy[C]//Proceedings of the 2014 SIAM International Conference on Data Mining. Philadelphia,PA:SIAM,2014:587-595.
[10] QARDAJI W, YANG W, LI N. Understanding hierarchical methods for differentially private histograms[J]. Proceedings of the VLDB Endowment,2013,6(14):1954-1965.
[11] HAN Q,SHAO B,LI L,et al. Publishing histograms with outliers under data differential privacy[J]. Security and Communication Networks,2016,9(14):2313-2322.
[12] LI H,XIONG L,JIANG X. Differentially private histogram and synthetic data publication[M]//GKOULALAS-DIVANIS A, LOUKIDES G. Medical Data Privacy Handbook. Cham:Springer,2015:35-58.
[13] LI C,HAY M,RASTOGI V,et al. Optimizing linear counting queries under differential privacy[C]//Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York:ACM,2010:123-134.
[14] DOUDALIS S, MEHROTRA S. SORTaki:a framework to integrate sorting with differential private histogramming algorithms[C]//Proceedings of the 15th Annual Conference on Privacy, Security and Trust. Piscataway:IEEE,2017:9500-9509.
[15] 杨旭东, 高岭, 王海, 等. 一种面向直方图发布的均衡差分隐私保护方法[J]. 计算机学报,2020,43(8):1414-1432.(YANG X D,GAO L,WANG H,et al. Balanced correlation differential privacy protection method for histogram publishing[J]. Chinese Journal of Computers,2020,43(8):1414-1432.)
[16] LI H,CUI J,MENG X,et al. IHP:improving the utility in differential private histogram publication[J]. Distributed and Parallel Databases,2019,37(4):721-750.
[17] 张啸剑, 王淼, 孟小峰. 差分隐私保护下一种精确挖掘top-k频繁模式方法[J]. 计算机研究与发展,2014,51(1):104-114. (ZHANG X J,WANG M,MENG X F. An accurate method for mining top-k frequent pattern under differential privacy[J]. Journal of Computer Research and Development,2014,51(1):104-114.)

High-precision histogram publishing method based on differential privacy

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	JIANG Kun, LIU Zheng, ZHU Lei, LI Xiaoxing. Fixed word-aligned partition compression algorithm of inverted list based on directed acyclic graph [J]. Journal of Computer Applications, 2021, 41(3): 727-732.
[2]	ZENG Zhiyang, CHEN Yan, WANG Ke. Design and implementation of parallel genetic algorithm for cutting stock of circular parts [J]. Journal of Computer Applications, 2020, 40(2): 392-397.
[3]	CHEN Lichao, ZHANG Lei, CAO Jianfang, ZHANG Rui. Vehicle classification based on HOG-C CapsNet in traffic surveillance scenarios [J]. Journal of Computer Applications, 2020, 40(10): 2881-2889.
[4]	SHI Wenxu, YANG Yang, BAO Shengli. Greedy core acceleration dynamic programming algorithm for solving discounted {0-1} knapsack problem [J]. Journal of Computer Applications, 2019, 39(7): 1912-1917.
[5]	LOU Mengying, YUAN Lisha, LIU Yaqin, WAN Xuemei, YANG Feng. Palm vein enhancement method based on adaptive fusion [J]. Journal of Computer Applications, 2019, 39(4): 1176-1182.
[6]	WAN Yuan, ZHANG Jinghui, CHEN Zhiping, MENG Xiaojing. Non-negative local sparse coding algorithm based on elastic net and histogram intersection [J]. Journal of Computer Applications, 2019, 39(3): 706-711.
[7]	NIU Ke, ZHANG Shuo, YANG Xiaoyuan. Reversible data hiding scheme in encrypted videos based on vector histogram shifting [J]. Journal of Computer Applications, 2019, 39(3): 756-762.
[8]	YANG Shiqiang, LUO Xiaoyu, QIAO Dan, LIU Peilei, LI Dexin. Continuous action segmentation and recognition based on sliding window and dynamic programming [J]. Journal of Computer Applications, 2019, 39(2): 348-353.
[9]	LI Qi, YAN Bin, CHEN Na, YANG Hongmei. 3D medical image reversible watermarking algorithm based on unidirectional prediction error expansion [J]. Journal of Computer Applications, 2019, 39(2): 483-487.
[10]	ZHOU Chong, LIU Huan, ZHAO Ailing, ZHANG Pengcheng, LIU Yi, GUI Zhiguo. Industrial X-ray image enhancement algorithm based on gradient field [J]. Journal of Computer Applications, 2019, 39(10): 3088-3092.
[11]	ZHENG Hongchang, WANG Chuntao, WANG Junxiang. LASSO based image reversible watermarking [J]. Journal of Computer Applications, 2018, 38(8): 2287-2292.
[12]	LI Tianxue, ZHANG Minqing, WANG Jianping, MA Shuangpeng. Reversible data hiding algorithm based on pixel value order [J]. Journal of Computer Applications, 2018, 38(8): 2311-2315.
[13]	FAN Jiaqing, SONG Huihui, ZHANG Kaihua. Real-time visual tracking algorithm via channel stability weighted complementary learning [J]. Journal of Computer Applications, 2018, 38(6): 1751-1754.
[14]	LIU Yuanyuan, WANG Hui, GUO Gongde, JIANG Nanfeng. Multi-perspective multi-region feature fusion for apple classification [J]. Journal of Computer Applications, 2018, 38(5): 1309-1314.
[15]	LIU Li, ZHAN Enqi, ZHENG Jianbin, WANG Yang. Online signature verification based on curve segment similarity matching [J]. Journal of Computer Applications, 2018, 38(4): 1046-1050.