大数据统计划分发布的等比差分隐私预算分配方法

doi:10.3969/j.issn.1671-1122.2022.11.004

摘要/Abstract

摘要：

针对现有的差分隐私大数据统计划分发布方法关于隐私预算分配的问题，文章提出一种等比差分隐私预算分配方法，通过分析大数据统计划分结构和发布误差，推导出等比差分隐私预算分配方法。将文章所提方法与现有其他隐私预算分配方法进行比较，从理论上证明了该方法在各层隐私预算分配和总体误差方面的优势。实验结果表明，文章所提等比差分隐私预算分配方法在范围计数查询精度方面优于其他隐私预算分配方法，有助于提升大数据统计划分发布结果的可用性。

关键词: 数据发布隐私保护, 隐私空间分解, 差分隐私, 隐私预算分配

Abstract:

In view of the problem of privacy budget allocation method for the existing big data differential privacy statistical partition and publishing, this paper proposed a proportional differential privacy budget allocation method. The hierarchical allocation formula of the proportional privacy budget allocation method was derived through the analysis of the statistical partitioning structure and publishing error of big data. The proposed method was compared with other existing privacy budget allocation methods to prove its advantages theoretically in terms of privacy budget allocation results for each partition layer and the overall publishing error. The experimental results show that the proposed proportional differential privacy budget allocation method has better range counting query accuracy than other existing privacy budget allocation methods, which is helpful to improve the availability of big data statistical partitioning and publishing results.

Key words: privacy preserving data publishing, privacy spatial decomposition, differential privacy, privacy budget allocation

中图分类号:

TP309

晏燕, 张雄, 冯涛. 大数据统计划分发布的等比差分隐私预算分配方法[J]. 信息网络安全, 2022, 22(11): 24-35.

YAN Yan, ZHANG Xiong, FENG Tao. Proportional Differential Privacy Budget Allocation Method for Partition and Publishing of Statistical Big Data[J]. Netinfo Security, 2022, 22(11): 24-35.

图/表 11

图1

图2

图3

图4

表1

图5

图6

图7

图8

图9

图10

参考文献 34

[1]	MUELLER J, SANTOS L, ALEXIS R. The 2020 US Census Differential Privacy Method Introduces Disproportionate Discrepancies for Rural and Non-White Populations[J]. Population Research and Policy Review, 2022(41): 1-14.
[2]	BHAGYA N S, MURAD K, JUNG C S, et al. Urban Planning and Smart City Decision Management Empowered by Real-Time Data Processing Using Big Data Analytics[J]. Sensors, 2018, 18(9): 2994-3008. doi: 10.3390/s18092994 URL
[3]	ZHU Li, YU F R, WANG Yige, et al. Big Data Analytics in Intelligent Transportation Systems: A Survey[J]. IEEE Transactions on Intelligent Transportation Systems, 2019, 20(1): 383-398. doi: 10.1109/TITS.2018.2815678 URL
[4]	HAUER M E, SANTOS-LOZADA A R. Differential Privacy in the 2020 Census Will Distort COVID-19 Rates[EB/OL]. (2021-02-10)[2022-03-21]. .
[5]	CHEN Xi, SIMCHILEVI D, WANG Yining. Privacy-Preserving Dynamic Personalized Pricing with Demand Learning[EB/OL]. (2021-10-11)[2022-03-02]. https://pubsonline.informs.org/doi/10.1287/mnsc.2021.4129.
[6]	ZHANG Shun, LIU Laixiang, CHEN Zhili, et al. Probabilistic Matrix Factorization with Personalized Differential Privacy[EB/OL]. (2018-10-22)[2022-02-11].
[7]	RANDA A, TIAN Yuan, MZNAH A R, et al. Anomaly Detection over Differential Preserved Privacy in Online Social Networks[EB/OL]. (2019-04-25)[2022-02-01]. .
[8]	ZHANG Xiaojian, MENG Xiaofeng. Differential Privacy in Data Publication and Analysis[J]. Chinese Journal of Computers, 2014, 37(4): 927-949.
	张啸剑, 孟小峰. 面向数据发布和分析的差分隐私保护[J]. 计算机学报, 2014, 37(4): 927-949.
[9]	OHKI M, INUIGUCHI M. A K-Anonymous Rule Clustering Approach for Data Publishing[J]. Journal of Advanced Computational Intelligence and Intelligent Informatics, 2017, 21(6): 980-988. doi: 10.20965/jaciii.2017.p0980 URL
[10]	HE Yun, ZHANG Min, YANG Xiaolong, et al. A Survey of Privacy Protection and Network Security in User on-Demand Anonymous Communication[J]. IEEE Access, 2020(8): 54856-54871.
[11]	LI Fengyin, LIU Zhongxing, WANG Yilei, et al. Aitac: An Identity-Based Traceable Anonymous Communication Model[J]. Journal of Ambient Intelligence and Humanized Computing, 2020, 13(3): 1-10.
[12]	DEB N, ELASHIRI M A, VEERAMAKALI T, et al. A Metaheuristic Approach for Encrypting Blockchain Data Attributes Using Ciphertext Policy Technique[EB/OL]. (2022-01-21)[2022-03-05]. .
[13]	FANG Haokun, QIAN Quan. Privacy Preserving Machine Learning with Homomorphic Encryption and Federated Learning[J]. Future Internet, 2021, 13(4): 94-113. doi: 10.3390/fi13040094 URL
[14]	NAKAMURA Y, NISHI H. Digital Watermarking for Anonymized Data with Low Information Loss[J]. IEEE ACCESS, 2021(9): 130570-130585.
[15]	WANG Leye, YANG Dingqi, HAN Xiao, et al. Mobile Crowdsourcing Task Allocation with Differential-and-Distortion Geo-Obfuscation[J]. IEEE Transactions on Dependable and Secure Computing, 2019, 18(2): 967-981. doi: 10.1109/TDSC.2019.2912886 URL
[16]	HO S, QU Youyang, GU B, et al. DP-GAN: Differentially Private Consecutive Data Publishing Using Generative Adversarial Nets[EB/OL]. (2021-07-01)[2022-03-05]. .
[17]	SHEN Yuncheng, GUO Bing, SHEN Yan, et al. Personal Big Data Pricing Method Based on Differential Privacy[J]. (2022-02-06)[2022-03-05]. https://dlnext.acm.org/doi/10.1016/j.cose.2021.102529.
[18]	NAZANIN B. Budget Allocation on Difffferentially Private Decision Trees and Random Forests[D]. Sydney: University of Technology Sydney, 2018.
[19]	SHANG Tao, ZHAO Zheng, SHU Wangwei, et al. Big Data Decision Tree Algorithm Based on Equal-Arrival Privacy Budget Allocation[J]. Advanced Engineering Sciences, 2019, 51(2): 130-136.
	尚涛, 赵铮, 舒王伟, 等. 基于等差隐私预算分配的大数据决策树算法[J]. 工程科学与技术, 2019, 51(2): 130-136.
[20]	FAN Zexuan, XU Xiaolong. APDPk-Means: A New Differential Privacy Clustering Algorithm Based on Arithmetic Progression Privacy Budget Allocation[C]// IEEE. 2019 IEEE 21st International Conference on High Performance Computing and Communications. New York: IEEE, 2019: 1737-1742.
[21]	XIAO Biao, YAN Hongqiang, LUO Haining, et al. Research on Improvement of Bayesian Network Privacy Protection Algorithm Based on Differential Privacy[J]. Netinfo Security, 2020, 20(11): 75-86.
	肖彪, 闫宏强, 罗海宁, 等. 基于差分隐私的贝叶斯网络隐私保护算法的改进研究[J]. 信息网络安全, 2020, 20(11): 75-86.
[22]	LEE J, KIFER D. Concentrated Differentially Private Gradient Descent with Adaptive Per-Iteration Privacy Budget[C]// ACM. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2018: 1656-1665.
[23]	BKAKRIA A, TASIDOU A, CUPPENS B N, et al. Optimal Distribution of Privacy Budget in Differential Privacy[C]// Springer. International Conference on Risks and Security of Internet and Systems. Heidelberg: Springer, 2018: 222-236.
[24]	TANG Haixia, YANG Geng, BAI Yunlu. Histogram Publishing Algorithm Based on Adaptive Privacy Budget Allocation Strategy under Differential Privacy[J]. Application Research of Computers, 2020, 37(7): 1952-1957, 1963.
	唐海霞, 杨庚, 白云璐. 自适应差分隐私预算分配策略的直方图发布算法[J]. 计算机应用研究, 2020, 37(7): 1952-1957, 1963.
[25]	CHEN Rui, FUNG B C M, DESAI B C, et al. Differentially Private Transit Data Publication: A Case Study on the Montreal Transportation System[C]// ACM. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012: 213-221.
[26]	CORMODE G, PROCOPIUC C, SRIVASTAVA D, et al. Differentially Private Spatial Decompositions[C]// IEEE. 2012 IEEE 28th International Conference on Data Engineering. New York: IEEE, 2012: 20-31.
[27]	WANG Jun, LIU Shubo, LI Yongkai, et al. Differentially Private Spatial Decompositions for Geospatial Point Data[J]. China Communications, 2016, 13(4): 97-107.
[28]	WANG Xiaohan, HAN Huihui, ZHANG Zepei, et al. Differential Privacy Budget Allocation Method for Data of Tree Index[J]. Journal of Computer Applications, 2018, 38(7): 1960-1966. doi: 10.11772/j.issn.1001-9081.2018010014
	汪小寒, 韩慧慧, 张泽培, 等. 树索引数据差分隐私预算分配方法[J]. 计算机应用, 2018, 38(7): 1960-1966. doi: 10.11772/j.issn.1001-9081.2018010014
[29]	WANG Xuan. Optimization and Application of Privacy Budget in Differential Privacy Protection[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2019.
	王璇. 差分隐私保护中隐私预算的优化与应用[D]. 南京: 南京邮电大学, 2019.
[30]	YAN Yan, GAO Xin, MAHMOOD A, et al. An Arithmetic Differential Privacy Budget Allocation Method for the Partitioning and Publishing of Location Information[C]// IEEE. 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom). New York:IEEE, 2021: 1395-1401.
[31]	DWORK C,LEI Jing. Differential Privacy and Robust Statistics[C]// ACM. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. New York: ACM, 2009: 371-380.
[32]	DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating Noise to Sensitivity in Private Data Analysis[C]// Springer. Proceedings of the Third Conference on Theory of Cryptography. Heidelberg: Springer, 2006: 108-121.
[33]	DWORK C. Calibrating Noise to Sensitivity in Private Data Analysis[J]. Lecture Notes in Computer Science, 2012, 3876(8): 265-284.
[34]	MCSHERRY F. Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis[J]. Communications of the ACM, 2010, 53(9): 89-97.

参数	数据集
参数	Landmark	Checkin	Yellow_tripdata
数据总量	870052	1000000	12504938
覆盖范围/km²	6634×4423	39806×16586	110×110
最小查询范围/km²	1×1	10×10	0.5×0.5
中等查询范围/km²	10×10	100×100	5×5
最大查询范围/km²	100×100	1000×1000	50×50