大数据环境下差分隐私保护技术及应用

doi:10.11959/j.issn.1000-436x.2019209

摘要/Abstract

摘要：

大数据中的隐私保护问题是当前网络空间安全领域的一个研究热点，差分隐私保护作为严格且可证明的隐私保护定义，研究其在大数据环境下的应用现状能够为其后续的系统性应用等提供参考与指导。在系统分析差分隐私保护的相关概念与技术特性的基础上，通过对差分隐私保护技术在数据发布与分析、云计算与大数据计算、位置与轨迹服务及社交网络中的应用等进行综述，阐述了当前具有代表性的研究成果并分析了其存在的问题。研究表明，现有成果从差分隐私保护机理、噪声添加机制与位置、数据处理方式等方面对差分隐私保护应用进行了卓有成效的创新与探究，且相关成果在不同场景下实现了交叉应用。最后提出了差分隐私保护在大数据环境下进一步系统性应用还需要注意的四大问题。

关键词: 差分隐私, 隐私保护, 大数据, 数据发布, 云计算, 位置服务, 社交网络

Abstract:

The privacy protection in big data is a research hotspot in the field of cyberspace security.As a strict and provable definition of privacy protection,studying application status of differential privacy protection in big data environment can provide reference and guidance for its subsequent system applications.Based on the analysis of the related concepts and technical characteristics of differential privacy protection,the application of differential privacy protection technology was reviewed in data distribution and analysis,cloud computing and big data computing,location and trajectory services and social networks,which expounded the current representative research results and analyzed its existing problems.The research shows that the existing results have made effective innovation and exploration of differential privacy protection applications from the aspects of differential privacy protection mechanism,noise addition mechanism and location,and data processing methods,and the related results have been cross-applied in different scenarios.Finally,four major problems that need to be studied in the further systematic application of differential privacy protection in the big data environment are proposed.

Key words: differential privacy, privacy protection, big data, data publishing, cloud computing, location service, social network

中图分类号:

TP393

付钰, 俞艺涵, 吴晓平. 大数据环境下差分隐私保护技术及应用[J]. 通信学报, 2019, 40(10): 157-168.

Yu FU, Yihan YU, Xiaoping WU. Differential privacy protection technology and its application in big data environment[J]. Journal on Communications, 2019, 40(10): 157-168.

图/表 1

参考文献 72

[1]	BERTINO E , FERRARI E . Big data security and privacy[M]// A Comprehensive Guide Through the Italian Database Research Over the Last 25 Years. Springer International Publishing, 2018: 757-761.
[2]	YANG Z , ZHANG Y , JIA H . Influencing factors of online P2P lending success rate in China[J]. Annals of Data Science, 2017,4(2): 1-17.
[3]	HUANG , HUI R . Online P2P lending and regulatory responses in China:opportunities and challenges[J]. European Business Organization Law Review, 2018,19(1): 63-92.
[4]	SREEVANI P , NIRANJAN D P , SHIREESHA P . A novel data anonymization technique for privacy preservation of data publishing[J]. International Journal of Engineering Sciences ＆ Research Technology, 2014,3(11): 201-205.
[5]	ZENG L , POLYTECHNIC L . Research on new data encryption algorithm in big data environment[J]. Bulletin of Science ＆ Technology, 2017,33(6): 205-208.
[6]	李凤华, 李晖, 贾焰 ,等. 隐私计算研究范畴及发展趋势[J]. 通信学报, 2016,37(4): 1-11.
	LI F H , LI H , JIA Y ,et al. Privacy computing:concept,connotation and its research trend[J]. Journal on Communications, 2016,37(4): 1-11.
[7]	彭长根, 丁红发, 朱义杰 ,等. 隐私保护的信息熵模型及其度量方法[J]. 软件学报, 2016,27(8): 1891-1903.
	PENG C G , DING H F , ZHU Y J ,et al. Information entropy models and privacy metrics methods for privacy protection[J]. Journal of Software, 2016,27(8): 1891-1903.
[8]	熊金波, 王敏燊, 田有亮 ,等. 面向云数据的隐私度量研究进展[J]. 软件学报, 2018,29(7): 1963-1980.
	XIONG J B , WANG M S , TIAN Y L ,et al. Research progress on privacy measurement for cloud data[J]. Journal of Software, 2018,29(7): 1963-1980.
[9]	DWORK C , . Differential privacy[M]// Automata,Languages and Programming. Springer Berlin Heidelberg, 2006: 1-12.
[10]	SHRIVASTVA K M P , RIZVI M A , SINGH S . Big data privacy based on differential privacy a hope for big data[C]// International Conference on Computational Intelligence and Communication Networks. IEEE, 2015: 776-781.
[11]	HAEBERLEN A , PIERCE B C , NARAYAN A . Differential privacy under fire[C]// Usenix Conference on Security. USENIX Association, 2011:33.
[12]	DWORK C . A firm foundation for private data analysis[J]. Communications of the ACM, 2011,54(1): 86-95.
[13]	DWORK C , MCSHERRY F , NISSIM K . Calibrating noise to sensitivity in private data analysis[J]. Proceedings of the VLDB Endowment, 2006,7(8): 637-648.
[14]	NISSIM K , RASKHODNIKOVA S . Smooth sensitivity and sampling in private data analysis[C]// Thirty-Ninth ACM Symposium on Theory of Computing. ACM, 2007: 75-84.
[15]	DWORK C , ROTH A . The algorithmic foundations of differential privacy[M]. Now Publishers Inc. 2014.
[16]	MCSHERRY F , TALWAR K . Mechanism design via differential privacy[C]// 48th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2007: 94-103.
[17]	CHAUDHURI K , MONTELEONI C , SARWATE A D . Differentially private empirical risk minimization[J]. Journal of Machine Learning Research, 2009,12(2): 1069-1109.
[18]	HAN C , WANG K . Sensitive Disclosures under differential privacy guarantees[C]// IEEE International Congress on Big Data. IEEE Computer Society, 2015: 110-117.
[19]	HAI B , NISSIM K . Impossibility of differentially private universally optimal mechanisms[J]. Foundations of Computer Science Annual Symposium on, 2010,43(5): 71-80.
[20]	GHOSH A , ROUGHGARDEN T , SUNDARARAJAN M . Universally utility-maximizing privacy mechanisms[C]// ACM Symposium on Theory of Computing. ACM, 2009: 351-360.
[21]	GUPTE M , SUNDARARAJAN M . Universally optimal privacy mechanisms for minimax agents[C]// Twenty-Ninth ACM SigmodSigact-Sigart Symposium on Principles of Database Systems. ACM, 2010: 135-146.
[22]	GENG Q , VISWANATH P . The optimal mechanism in differential privacy[C]// IEEE International Symposium on Information Theory. IEEE, 2013: 2371-2375.
[23]	CHEN C L , PAL R , GOLUBCHIK L . Oblivious mechanisms in differential privacy:experiments,conjectures,and open questions[C]// Security and Privacy Workshops. IEEE, 2016: 41-48.
[24]	LIN C , SONG Z , SONG H ,et al. Differential privacy preserving in big data analytics for connected health[J]. Journal of Medical Systems, 2016,40(4): 1-9.
[25]	JI Z , XIN D , YU J ,et al. Differentially private multidimensional data publication[J]. China Communications, 2014,11(s1): 79-85.
[26]	DE A . Lower bounds in differential privacy[J]. Lecture Notes in Computer Science, 2013,7194: 321-338.
[27]	ZHANG X , WU Y , WANG X . Differential privacy data release through adding noise on average value[M]// Network and System Security. Springer Berlin Heidelberg, 2012: 417-429.
[28]	LI C , HAY M , RASTOGI V ,et al. Optimizing linear counting queries under differential privacy[C]// Twenty-Ninth ACM Sigmod-Sigact-Sigart Symposium on Principles of Database Systems. DBLP, 2010: 123-134.
[29]	KOUFOGIANNIS F , HAN S , PAPPAS G J . Gradual release of sensitive data under differential privacy[J]. Journal of Privacy and Confidentiality, 2015(12): 1-25.
[30]	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.
[31]	KELLARIS G , PAPADOPOULOS S , XIAO X ,et al. Differentially private event sequences over infinite streams[J]. Proceedings of the VLDB Endowment, 2014,7(12): 1155-1166.
[32]	FAN L , XIONG L . An adaptive approach to real-time aggregate monitoring with differential privacy[J]. IEEE Transactions on Knowledge＆ Data Engineering, 2014,26(9): 2094-2106.
[33]	CHAN T H H , SHI E , SONG D . Private and continual release of statistics[J]. ACM Transactions on Information ＆ System Security, 2011,14(3): 1-24.
[34]	DWORK C , NAOR M , PITASSI T ,et al. Differential privacy under continual observation[C]// STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing. ACM, 2010: 715-724.
[35]	WANG Q , ZHANG Y , LU X ,et al. RescueDP:real-time spatio-temporal crowd-sourced data publishing with differential privacy[C]// International Conference on Computer Communications. IEEE, 2016: 1-9.
[36]	CHEN R , FUNG B C M , DESAI B C . Differentially private trajectory data publication[J]. arXiv Preprint,arXiv:1112.2020, 2011.
[37]	CHEN R , ACS G , CASTELLUCCIA C . Differentially private sequential data publication via variable-length n-grams[C]// ACM Conference on Computer and Communications Security. ACM, 2012: 638-649.
[38]	KANG H Y , ZHANG S X , JIA Q Q . A method for time-series location data publication based on differential privacy[J]. Wuhan University Journal of Natural Sciences, 2019(2): 107-115.
[39]	ABADI M , GOODFELLOW I . Deep learning with differential privacy[C]// ACM Sigsac Conference on Computer and Communications Security. ACM, 2016: 308-318.
[40]	CAI T T , WANG Y , ZHANG L . The cost of privacy:optimal rates of convergence for parameter estimation with differential privacy[J]. Statistics, 2019.
[41]	MCSHERRY F , MIRONOV I . Differentially private recommender systems:building privacy into the net[M]// Differentially Private Recommender Systems. 2009: 627-636.
[42]	XU C , REN J , ZHANG D ,et al. GANobfuscator:mitigating information leakage under GAN via differential privacy[J]. IEEE Transactions on Information Forensics and Security, 2019,14(9): 2358-2371.
[43]	LI C , ZHOU P , JIANG T . Differential privacy and distributed online learning for wireless big data[C]// International Conference on Wireless Communications ＆ Signal Processing. IEEE, 2015: 1-5.
[44]	BEIMEL A , NISSIM K , STEMMER U.Private learning and sanitization:pure vs . approximate differential privacy[M]// Approximation,Randomization,and Combinatorial Optimization.Algorithms and Techniques. Springer Berlin Heidelberg, 2013: 363-378.
[45]	KASIVISWANATHAN S P , LEE H K , NISSIM K ,et al. What can we learn privately?[J]. Siam Journal on Computing, 2008,40(3): 793-826.
[46]	BEIMEL A , KASIVISWANATHAN S P , NISSIM K . Bounds on the sample complexity for private learning and private data release[C]// International Conference on Theory of Cryptography. Springer-Verlag, 2010: 437-454.
[47]	BEIMEL A , NISSIM K , STEMMER U . Characterizing the sample complexity of private learners[J]. Computer Science, 2014: 97-110.
[48]	TANG J , KOROLOVA A , BAI X ,et al. Privacy loss in Apple’s implementation of differential privacy on MacOS 10.12[J]. arXiv Preprint,arXiv:1709.02753, 2017.
[49]	ROY I , SETTY S T V , KILZER A ,et al. Airavat:security and privacy for MapReduce[C]// Usenix Symposium on Networked Systems Design and Implementation. DBLP, 2010: 297-312.
[50]	MIR D J , ISAACMAN S , CACERES R ,et al. DP-WHERE:differentially private modeling of human mobility[C]// IEEE International Conference on Big Data. IEEE, 2013: 580-588.
[51]	KELLARIS G , PAPADOPOULOS S . Practical differential privacy viagrouping and smoothing[J]. Proceedings of the VLDB Endowment, 2013,6(5): 301-312.
[52]	CORMODE G , PROCOPIUC C , SRIVASTAVA D ,et al. Differentially private spatial decompositions[C]// International Conference on Data Engineering. IEEE, 2012: 20-31.
[53]	WANG J , LIU S , LI Y K ,et al. Differentially private spatial decompositions for geospatial point data[J]. China Communications, 2016,13(4): 97-107.
[54]	LIN C , WANG P , SONG H ,et al. A differential privacy protection scheme for sensitive big data in body sensor networks[J]. Annals of Telecommunications, 2016,71(9-10): 465-475.
[55]	XIONG P , ZHU T , NIU W ,et al. A differentially private algorithm for location data release[J]. Knowledge ＆ Information Systems, 2016,47(3): 647-669.
[56]	HE X , CORMODE G , SRIVASTAVA D ,et al. DPT:differentially private trajectory synthesis using hierarchical reference systems[J]. Proceedings of the VLDB Endowment, 2015,8(11): 1154-1165.
[57]	HUA J , GAO Y , ZHONG S . Differentially private publication of general time-serial trajectory data[C]// Computer Communications. IEEE, 2015: 549-557.
[58]	LI M , ZHU L , ZHANG Z ,et al. Achieving differential privacy of trajectory data publishing in participatory sensing[J]. Information Sciences, 2017,400-401: 1-13.
[59]	CHATZIKOKOLAKIS K , PALAMIDESSI C , STRONATI M . A predictive differentially-private mechanism for mobility traces[J]. Privacy Enhancing Technologies, 2014,8555: 21-41.
[60]	ASADA M , YOSHIKAWA M , CAO Y . When and where do you want to hide? Recommendation of location privacy preferences with local differential privacy[C]// IFIP Annual Conference on Data and Applications Security and Privacy. Springer, 2019: 1-20.
[61]	TASK C , CLIFTON C . A guide to differential privacy theory in social network analysis[C]// International Conference on Advances in Social Networks Analysis and Mining. IEEE Computer Society, 2012: 411-417.
[62]	TASK C , CLIFTON C . What should we protect? defining differential privacy for social network analysis[M]// State of the Art Applications of Social Network Analysis. Springer International Publishing, 2014: 139-161.
[63]	KARWA V , RASKHODNIKOVA S , SMITH A ,et al. Private analysis of graph structure[J]. ACM Transactions on Database Systems, 2011,39(3): 1146-1157.
[64]	DWORK C , MCSHERRY F , NISSIM K . Calibrating noise to sensitivity in private data analysis[C]// Theory of Cryptography Conference. Springer, 2006: 265-284.
[65]	WANG Y , WU X , ZHU J ,et al. On learning cluster coefficient of private networks[C]// International Conference on Advances in Social Networks Analysis and Mining. IEEE Computer Society, 2012: 395-402.
[66]	COSTEA S , BARBU M , RUGHINIS R . Qualitative analysis of differential privacy applied over graph structures[C]// Roedunet International Conference. IEEE, 2013: 1-4.
[67]	HAY M , LI C , MIKLAU G ,et al. Accurate estimation of the degree distribution of private networks[C]// Ninth IEEE International Conference on Data Mining. IEEE Computer Society, 2009: 169-178.
[68]	JAVIDBAKHT O , VENKITASUBRAMANIAM P . Differential privacy in networked data collection[C]// Conference on Information Science and Systems. IEEE, 2016: 117-122.
[69]	LI X Y , YANG J , SUN Z J ,et al. Publishing social graphs with differential privacy guarantees based on wPINQ[J]. Chinese Journal of Electronics, 2019,28(2): 273-279.
[70]	KIFER D , MACHANAVAJJHALA A . No free lunch in data privacy[C]// ACM SIGMOD International Conference on Management of Data. DBLP, 2011: 193-204.
[71]	LI N , QARDAJI W , DONG S . On sampling,anonymization,and differential privacy or,k-anonymization meets differential privacy[C]// ACM Symposium on Information,Computer and Communications Security. ACM, 2012: 32-33.
[72]	GEHRKE J , HAY M , LUI E ,et al. Crowd-blending privacy[C]// Cryptology Conference on Advances in Cryptology. Springer-Verlag, 2012: 479-496.

技术	相关文献	具体方式	主要优点	主要缺点
选择最优噪声机制	19-23]	针对特定数据类型和查询函数选择最优噪声机制	对查询函数为计数函数等情况优化效果明显	普适性差
优化噪声添加策略	14,24-25]	为噪声、敏感度定界	算法计算复杂度降低，可适用于多维数据	数据可用性降低
	26]	采取近似差分隐私策略	数据可用性提升	数据隐私性降低
优化数据发布策略	27-38]	通过各类转换技术、划分技术扩大查询范围和提高查询精度；合理分配隐私预算，提高效用	能够适用于大数据环境下动态数据流中，数据发布准确性高，优化了查询精度与查询范围	存在计算复杂度高、通信开销大的问题，一般只适用于特定的数据类型