A Graph Information Collection Method Based on Local Differential Privacy in Big Data Environment

doi:10.3969/j.issn.1671-1122.2020.06.006

Abstract

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

CLC Number:

TP309

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.

Figures/Tables 9

References 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.