一种Hilbert编码的本地化位置隐私保护方法

doi:10.19665/j.issn1001-2400.2023.02.015

摘要/Abstract

摘要：

基于位置的各种大数据服务在为用户提供便利的同时,也导致了各种隐私泄露的风险。本地化差分隐私模型避免了对可信第三方数据收集平台的依赖,使得用户能够依据个人需求处理和保护敏感信息,因此更适用于位置隐私保护的场景。针对现有本地化差分隐私位置保护方法编码机制复杂、位置数据可用性低等问题,提出一种基于希尔伯特编码的本地化差分隐私位置保护方法。用户端根据本地化差分隐私模型对自身所处网格的希尔伯特编码进行随机响应扰动处理,实现原始位置的隐私保护;服务器端收集大量用户的扰动位置编码并进行希尔伯特解码,进而判断用户所处的网格位置,实现对用户数量和分布密度的统计分析。通过实际位置数据集合上的实验证明,所提方法能够在实现用户位置本地化差分隐私保护的基础上提供更好的位置数据可用性和运行效率。

关键词: 位置服务, 位置隐私, 本地化差分隐私, 希尔伯特编码, 随机响应

Abstract:

Various location-based big data services not only provide users with convenience but also lead to privacy leakage risks.The local differential privacy model avoids the dependence on trusted third-party data collection platforms and enables users to process and protect sensitive information according to their personal needs.Therefore,it is more suitable for location privacy protection scenarios.In view of the complex encoding mechanism and low availability of the current local differential privacy location protection methods,a local differential privacy location protection method based on the Hilbert encoding is proposed.The user side performs random response perturbation on the Hilbert code of the grid where he is located according to the local differential privacy model,so as to realize the privacy protection of his original location.The server side collects a large number of users’ disturbed location codes and performs the Hilbert decoding,in order to determine the grid location of users and realize the statistical analysis of distribution density of users.Experiments on actual location datasets prove that the proposed method can provide a better location data availability and operational efficiency on the basis of realizing local differential privacy protection of users’ location.

Key words: location-based service, location privacy, local differential privacy, Hilbert encoding, random response

中图分类号:

TP309.2

晏燕,董卓越,徐飞,冯涛. 一种Hilbert编码的本地化位置隐私保护方法[J]. 西安电子科技大学学报, 2023, 50(2): 147-160.

YAN Yan,DONG Zhuoyue,XU Fei,FENG Tao. Localized location privacy protection method using the Hilbert encoding[J]. Journal of Xidian University, 2023, 50(2): 147-160.

图/表 14

图1

图2

图3

图4

表1

图5

图6

图7

图8

图9

图10

图11

图12

表2

参考文献 32

[1]	LIU Z, QIAN J, DU Y, et al. Multi-Level Spatial Distribution Estimation Model of the Inter-Regional Migrant Population Using Multi-Source Spatio-temporal Big Data:A Case Study of Migrants from Wuhan during the Spread of COVID-19[J]. Journal of Geo-Information Science, 2020, 22(2):147-160.
[2]	宋轩, 高云君, 李勇, 等. 空间数据智能:概念、技术与挑战[J]. 计算机研究与发展, 2022, 59(2):255-263.
	SONG Xuan, GAO Yunjun, LI Yong, et al. Spatial Data Intelligence:Concept,Technology and Challenges[J]. Journal of Computer Research and Development, 2022, 59(2):255-263.
[3]	邵明莉, 曹鹗, 胡铭, 等. 面向优先车辆感知的交通灯优化控制方法[J]. 软件学报, 2021, 32(8):2425-2438.
	SHAO Mingli, CAO E, HU Ming, et al. Traffic Light Optimization Control Method for Priority Vehicle Awareness[J]. Journal of Software, 2021, 32(8):2425-2438.
[4]	ZHOU C, SU F, PEI T, et al. COVID-19:Challenges to GIS with Big Data[J]. Geography and Sustainability, 2020, 1(1):77-87. doi: 10.1016/j.geosus.2020.03.005
[5]	SCHMIDTKE H R. Location-Aware Systems or Location-Based Services:A Survey with Applications to CoViD-19 Contact Tracking[J]. Journal of Reliable Intelligent Environments, 2020, 6(4):191-214. doi: 10.1007/s40860-020-00111-4
[6]	孙国道, 杨雨璠, 潘翔, 等. 流行病数据可视分析综述[J]. 计算机学报, 2022,(3):601-623.
	SUN Guodao, YANG Yupan, PAN Xiang, et al. A Survey on Visual Analysis of Epidemic Data[J]. Chinese Journal of Computers, 2022,(3):601-623.
[7]	徐花, 田有亮. 差分隐私下的权重社交网络隐私保护[J]. 西安电子科技大学学报, 2022, 49(1):17-25.
	XU Hua, TIAN Youliang. Protection of Privacy of the Weighted Social Network Under Differential Privacy[J]. Journal of Xidian University. 2022, 49(1):17-25.
[8]	AGARWAL R, HUSSAIN M. Generic Framework for Privacy Preservation in Cyber-Physical Systems[M]. Heidelberg:Springer, 2021:257-266.
[9]	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
[10]	DUCHI J C, JORDAN M I, WAINWRIGHT M J, et al. Local Privacy and Statistical Minimax Rates[C]//51st IEEE Annual Allerton Conference on Communication,Control,and Computing. Piscataway:IEEE, 2013:1592-1597.
[11]	GRUTESER M, GRUNWALD D. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking[C]// Proceedings of the 1st International Conference on Mobile Systems,Applications and Services. New York: ACM, 2003:31-42.
[12]	GEDIK B, LIU L. Protecting Location Privacy with Personalized K-Anonymity:Architecture and Algorithms[J]. IEEE Transactions on Mobile Computing, 2008, 7(1):1-18. doi: 10.1109/TMC.2007.1062
[13]	GEDIK B, LIU L. A Customizable K-Anonymity Model for Protecting Location Privacy[C]//Proc.IEEE ICDCS. Piscataway:IEEE, 2005:620-629.
[14]	NI L N, TIAN F L, NI Q H, et al. An Anonymous Entropy-Based Location Privacy Protection Scheme in Mobile Social Networks[J]. Eurasip Journal on Wireless Communications and Networking, 2019,(1):93-96.
[15]	SHEN X Y, WANG L C, PEI Q Q, et al. Location Privacy-Preserving in Online Taxi-Hailing Services[J]. Peer-To-Peer Networking and Applications, 2021, 14(1):69-81. doi: 10.1007/s12083-020-00982-7
[16]	宋成, 金彤, 倪水平, 等. 一种面向移动终端的K匿名位置隐私保护方案[J]. 西安电子科技大学学报, 2021, 48(3):138-145.
	SONG Cheng, JIN Tong, NI Shuiping, et al. K-Anonymous Location Privacy Protection Scheme for the Mobile Terminal.Journal of Xidian University[J]. 2021, 48(3):138-145.
[17]	ZHANG Y B, ZHANG Q Y,YAN,Y, et al. A K-Anonymous Location Privacy Protection Method of Polygon Based on Density Distribution[J]. International Journal of Network Security, 2021, 23(1):57-66.
[18]	LIU H, ZHANG S, LI M, et al. An Effective Location Privacy-Preserving K-Anonymity Scheme in Location Based Services[C]//2021 IEEE International Conference on Electronic Technology,Communication and Information. Piscataway:IEEE, 2021,24-29.
[19]	WANG Y, ZUO K, LIU R, et al. Dynamic Pseudonym Semantic-Location Privacy Protection Based on Continuous Query for Road Network[J]. International Journal of Network Security, 2021, 23(4):642-649.
[20]	HAYASHIDA S, AMAGATA D, HARA T, et al. Dummy Generation Based on User-Movement Estimation for Location Privacy Protection[J]. IEEE Access, 2018, 6:22958-22969. doi: 10.1109/ACCESS.2018.2829898
[21]	CHEN R, LI H, QIN A K, et al. Private Spatial Data Aggregation in the Local Setting[C]//32nd IEEE International Conference on Data Engineering. Piscataway:IEEE, 2016:289-300.
[22]	高志强, 崔翛龙, 杜波, 等. 满足本地差分隐私的位置数据采集方案[J]. 清华大学学报:自然科学版, 2019, 59(1):23-27.
	GAO Zhiqiang, CUI Xiaolong, DU Bo, et al. Collection Scheme of Location Data Based on Local Differential Privacy[J]. Journal of Tsinghua University(Science and Technology), 2019, 59(1):23-27.
[23]	ZHAO X G, LI Y H, YUAN Y, et al. LDPart:Effective Location-Record Data Publication via Local Differential Privacy[J]. IEEE Access, 2019, 7:31435-31445. doi: 10.1109/ACCESS.2019.2899099
[24]	HONG D, JUNG W, SHIM K, et al. Collecting Geospatial Data with Local Differential Privacy for Personalized Services[C]//37th IEEE International Conference on Data Engineering. Piscataway:IEEE, 2021:2237-2242.
[25]	WANG J, WANG F, LI H T. Differential Privacy Location Protection Scheme Based on Hilbert Curve[J]. Security and Communication Networks, 2021, 2021:12.
[26]	张啸剑, 付楠, 孟小峰. 基于本地差分隐私的空间范围查询方法[J]. 计算机研究与发展, 2020, 57(4):847-858.
	ZHANG Xiaojian, FU Nan, MENG Xiaofeng, et al. Towards Spatial Range Queries Under Local Differential Privacy[J]. Journal of Computer Research and Development, 2020, 57(4):847-858.
[27]	霍峥, 张坤, 贺萍, 等. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3):763-768. doi: 10.11772/j.issn.1001-9081.2018071541
	HUO Zheng, ZHANG Kun, HE Ping, et al. Crowdsourcing Location Data Collection for Local Differential Privacy[J]. Journal of Computer Applications, 2019, 39(3):763-768. doi: 10.11772/j.issn.1001-9081.2018071541
[28]	DAI J, QIAO K. A Privacy Preserving Framework for Worker’s Location in Spatial Crowdsourcing Based on Local Differential Privacy[J]. Future Internet, 2018, 10(6):53. doi: 10.3390/fi10060053
[29]	LUO X, WANG J, XU J, et al. Research on Data Privacy Protection of Internet of Vehicles Based on Differential Privacy[J]. IOP Conference Series:Earth and Environmental Science, 2020, 428:012007. doi: 10.1088/1755-1315/428/1/012007
[30]	叶青青, 孟小峰, 朱敏杰, 等. 本地化差分隐私研究综述[J]. 软件学报, 2018, 29(7):1981-2005.
	YE Qingqing, MENG Xiaofeng, ZHU Minjie, et al. Survey on Local Differential Privacy[J]. Journal of Software, 2018, 29(7):1981-2005.
[31]	WARNER S L. Randomized Response:A Survey Technique for Eliminating Evasive Answer Bias[J]. Journal of the American Statistical Association, 1965, 60(309):63-69. doi: 10.1080/01621459.1965.10480775
[32]	CHEN N, WANG N, SHI B. A New Algorithm for Encoding and Decoding the Hilbert Order[J]. Software:Practice and Experience, 2007, 37(8):897-908. doi: 10.1002/(ISSN)1097-024X

数据集	位置范围	位置数据量
Yellow_tripdata	[40.54,41.02]×[-74.30,-73.52]	30 000
Tokyo	[35.50,35.87]×[139.47,139.91]	573 703
Landmark	[-124.44,-67.02]×[24.55,49.00]	870 000

算法	数据长度/bit
PSDA	N²
LDPart	N²
GT-R	N²
LDPHE	2$\lceil$lb N$\rceil$