大数据环境下的本地差分隐私图信息收集方法

doi:10.3969/j.issn.1671-1122.2020.06.006

摘要/Abstract

摘要：

大数据为各种网络服务的用户带来了诸多便利,但也导致了严重的隐私泄露风险。随着5G时代的到来,数据传输更加便捷,隐私保护问题将会面临更为严峻的挑战。目前,中心化差分隐私和以RAPPOR为代表的本地差分隐私技术,可以为隐私信息的查询与收集过程提供一定保护。然而,针对社交网络、商业网络、金融网络这类复杂的图数据,尚缺乏有效的方法,使得在充分保护节点隐私的情况下,收集相关信息,构建可用性高的图结构。在实际应用中,节点之间的关联性以及信息富集等问题造成了在收集与还原图数据方面的困难。针对上述问题,文章提出了一种利用RAPPOR技术收集节点的边信息的方法,在不泄露节点度信息的同时,实现对节点边信息真正意义上的本地差分隐私保护,并高精度地还原出真实的图结构。此外,该方法充分考虑了数据收集全周期的隐私保护问题,不仅在数据收集过程中保护节点的隐私信息,同时,构建出的图只具有真实数据的结构信息,相关节点则得到了假名化的保护。

关键词: 本地差分隐私, 图信息收集, 隐私保护, RAPPOR, 大数据

Abstract:

Big data brings many conveniences to users of various network services, but it also leads to a serious risk of privacy leakage. In the era of 5G, data transmission is more convenient, and privacy protection will face more severe challenges.At present, centralized differential privacy and local differential privacy technology represented by RAPPOR can provide some protection for the query and collection of private information.However, for complex graph data such as social networks, business networks, and financial networks, there is still no effective method to collect relevant information and build a highly usable graph structure while fully protecting node privacy. In practical applications, problems such as the correlation between nodes and information enrichment have caused difficulties in collecting and restoring graph data. Regarding the problem sabove, in this paper, we propose a new method that applies RAPPOR technology to collect the edge information of the node, while not leaking the degree information. Our new method achieves local differential privacy protection fortheedge information and restores the real graph structure with high accuracy. In addition, our method fully considers the privacy protection of the entire cycle of data collection. Not only the privacy information of the nodesis protected during the data collection process, but the constructed graph has only the structural information of real data. The nodesin the constructed graph get pseudonymized protection.

Key words: local differential privacy, graph information collection, privacy preserving, RAPPOR, big data

中图分类号:

TP309

张佳程, 彭佳, 王雷. 大数据环境下的本地差分隐私图信息收集方法[J]. 信息网络安全, 2020, 20(6): 44-56.

ZHANG Jiacheng, PENG Jia, WANG Lei. A Graph Information Collection Method Based on Local Differential Privacy in Big Data Environment[J]. Netinfo Security, 2020, 20(6): 44-56.

图/表 9

图1

图2

图3

图4

图5

图6

图7

图8

图9

参考文献 33

[1]	PAPADIMITRIOU A, NARAYAN A, HAEBERLEN A. DStress: Efficient Differentially Private Computations on DISTRIBUTED DATA [C]//ACM. EuroSys '17: Proceedings of the Twelfth European Conference on Computer Systems, April 1-3, 2017, Belgrade, Serbia. New York: ACM, 2017: 560-574.
[2]	DWORK C. Differential Privacy[M]. Boston:Springer US, 2011.
[3]	KARWA V, SLAVKOVIĆ A B. Privacy in Statistical Databases[M]. Berlin:Springer, 2012.
[4]	SALA A, ZHAO Xiaohan, WILSON C, et al. [Sharing Graphs Using Differentially Private Graph Models[[C]//ACM. IMC ' 11: Proceedings of the 2011 ACM SIGCOMM Conference on Internet Measurement Conference, November 5-6, 2011, Berlin, Germany. New York: ACM Press, 2011: 81-98.
[5]	JORGENSEN Z, YU Ting, Cormode Graham. [Publishing Attributed Social Graphs with Formal Privacy Guarantees[[C]//ACM. SIGMOD ' 16: Proceedings of the 2016 International Conference on Management of Data, June 11-13, 2016, New York, NY, USA. New York: ACM Press, 2016: 107-122.
[6]	WANG Yue, WU Xintao. Preserving Differential Privacy in Degree-Correlation Based Graph Generation[J]. Transactions on Data Privacy, 2013,6(2):127. URL pmid: 24723987
[7]	ERLINGSSON Ú, PIHUR V, KOROLOVA A. Rappor: Randomized Aggregatable Privacy-Preserving Ordinal Response [C]//ACM. CCS '14: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 10-12, 2014, Scottsdale, Arizona, USA. New York: ACM, 2014: 1054-1067.
[8]	QIN Zhan, YU Ting, YANG Yin, et al. Generating Synthetic Decentralized Social Graphs with Local Differential Privacy [C]//ACM. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, October 30-November 3, 2017, Dallas, TX, USA. New York: ACM, 2017: 425-438.
[9]	YE Qingqing, MENG Xiaofeng, ZHU Minjie, et al. Survey on Local Differential Privacy[J]. Journal of Software, 2018,29(5):1981-2005.
[10]	DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating Noise to Sensitivity in Private Data Analysis [C]//Springer. TCC'06: Proceedings of the Third conference on Theory of Cryptography, March 4-7, 2006, New York, NY, USA. Berlin: Springer, 2006: 265-284.
[11]	YAO A C. Protocols for Secure Computations [C]//ACM. SFCS '82: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, November 3-5, 1982, Chicago, IL, USA. Washington: IEEE Computer Society, 1982: 160-164.
[12]	MICALI S, GOLDREICH O, WIGDERSON A. How to Play any Mental Game [C]//ACM. STOC '87: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, January 1, 1987, New York, NY, USA. New York: ACM, 1987: 218-229.
[13]	BEN O M, GOLDWASSER S, WIGDERSON A. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation [C]//ACM. STOC '88: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, January 6-8, 1988, Chicago, Illinois, USA. New York: ACM, 1988: 1-10.
[14]	KASIVISWANATHAN S P, LEE H K, NISSIM K, et al. What Can We Learn Privately?[J]. SIAM Journal on Computing, 2011,40(3):793-826. doi: 10.1137/090756090 URL
[15]	QIN Zhan, YANG Yin, YU Ting, et al. Heavy Hitter Estimation over Set-Valued Data with local Differential Privacy[C]//ACM. CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, October 9-12, 2016, New York, NY, USA. New York: ACM:192-203.
[16]	KAIROUZ P, BONAWITZ K, RAMAGE D. Discrete Distribution Estimation under Local Privacy[EB/OL]. http://www.researchgate.net/publication/301842950_Discrete_Distribution_Estimation_under_Local_Privacy, 2019-10-15.
[17]	BASSILY R, SMITH A. Local, Private, Efficient Protocols for Succinct Histograms [C]//ACM. STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, June 7-9, 2015, Portland, Oregon, USA. New York: ACM, 2015: 127-135.
[18]	KAIROUZ P, OH S, VISWANATH P. Extremal Mechanisms for Local Differential Privacy[J]. Journal of Machine Learning Research, 2016,17(1):492-542.
[19]	NGUYÊN T T, XIAO Xiaokui, YANG Yin, et al. Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy[EB/OL]. http://www.researchgate.net/publication/304018115_Collecting_and_Analyzing_Data_from_Smart_Device_Users_with_Local_Differential_Privacy, 2019-10-15.
[20]	CHEN Rui, LI Haoran, QIN Akai, et al. Private Spatial Data Aggregation in the Local Setting [C]//IEEE. 2016 IEEE 32nd International Conference on Data Engineering (ICDE), May 16-20, 2016, Helsinki, Finland. New York: IEEE, 2016: 289-300.
[21]	WANG Shaowei, HUANG Liusheng, WANG Pengzhan, et al. Mutual Information Optimally Local Private Discrete Distribution Estimation[EB/OL]. http://www.researchgate.net/publication/305683207_Mutual_Information_Optimally_Local_Private_Discrete_Distribution_Estimation, 2019-10-15.
[22]	FANTI G, PIHUR V, ERLINGSSON Ú. Building A Rappor with The Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries[J]. Proceedings on Privacy Enhancing Technologies, 2016,2016(3):41-61. doi: 10.1515/popets-2016-0015 URL
[23]	DUCHI J C, JORDAN M I, Wainwright Martin J. Local Privacy, Data Processing Inequalities, Statistical Minimax Rates[EB/OL]. https://www.oalib.com/paper/4036423, 2019 -10-15.
[24]	DUCHI J C, JORDAN M I, WAINWRIGHT M J. Privacy Aware Learning[J]. Journal of the ACM, 2014,61(6):1-57.
[25]	WARNER S L. Randomized Response: A survey Technique for Eliminating Evasive Answer Bias[J]. Journal of the American Statistical Association, 1965,60(9):63-69. doi: 10.1080/01621459.1965.10480775 URL
[26]	XIONG Sijie, SARWATE A D, MANDAYAM N B. Randomized Requantization with Local Differential Privacy [C]//IEEE. 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), March 20-25, 2016, Shanghai, China. New York: IEEE, 2016: 2189-2193.
[27]	SARWATE A D, SANKAR L. A Rate-Disortion Perspective on Local Differential Privacy [C]//IEEE. 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), September 30-Octorber 3, 2014, Monticello, IL, USA. New York: IEEE, 2015: 903-908.
[28]	DAY Weiyen, LI Ninghui, LYU Min. Publishing Graph Degree Distribution with Node Differential Privacy[C]//ACM. SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data, June 8-11, 2016, San Francisco, California, USA. New York: ACM, 2016: 123-138.
[29]	LU Wentian, MIKLAU G. Exponential Random Graph Estimation under Differential Privacy [C]//ACM. KDD '14: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 5-7, 2014, New York, NY, USA. New York: ACM, 2014: 921-930.
[30]	MIR D, WRIGHT R N. A Differentially Private Estimator for the Stochastic Kronecker Graph Model [C]//ACM. EDBT-ICDT '12: Proceedings of the 2012 Joint EDBT/ICDT Workshops, March 6-10, 2012, New York, NY, USA. New York: ACM, 2012: 167-176.
[31]	ZHANG J, CORMODE G, PROCOPIUC C M, et al. Private Release of graph Statistics Using Ladder Functions [C]//ACM. SIGMOD '15: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, May 9-10, 2015, Melbourne, Victoria, Australia. New York: ACM, 2015: 731-745.
[32]	WANG Yue, WU Xintao, WU Leting. Advances in Knowledge Discovery and Data Mining[M]. Berlin: Springer, 2013: 329-340.
[33]	DWORK C, LEI Jing. Differential Privacy and Robust Statistics [C]//ACM. STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing, May 8-10, 2009, Bethesda, MD, USA. New York: ACM, 2009: 371-380.