Local Differential Privacy Location Protection for Mobile Terminals Based on Huffman Coding

doi:10.3778/j.issn.1673-9418.2405025

Abstract

Abstract: The location information of mobile terminals is closely linked to personal privacy, which may threaten users’ life and property safety if leaked. Local differential privacy model provides strict privacy protection effect, allows users to handle and protect sensitive information according to their personal needs, and avoids the dependence on third-party servers. In view of the poor flexibility on the user side and severe loss of perturbation location quality in current local differential privacy location protection methods, a local differential privacy location protection method for mobile terminals based on Huffman encoding is proposed. The mobile user submits the location privacy protection range according to personalized privacy needs, and the server side performs location encoding on demand and returns it to the user. Subsequently, the user selects the Huffman encoding of his region and performs local differential privacy perturbation on it to achieve the privacy protection of the original location. The server side determines where the user is located by decoding the received perturbed location encoding, and provides location-based services accordingly. Experiments on real location datasets demonstrate that the proposed method can provide better location availability and operational efficiency while achieving local differential privacy protection of users’ location.

Key words: location privacy protection, local differential privacy, Huffman coding, random response

摘要： 移动终端的位置信息与个人隐私紧密相连，一旦泄露可能威胁用户的生命和财产安全。本地化差分隐私模型提供了严格的隐私保护效果，允许用户根据个人需求处理和保护敏感信息，避免了对第三方服务器的依赖。针对现有本地化差分隐私位置保护方法用户端灵活性差、扰动位置质量损失严重等问题，提出了一种基于Huffman编码的移动终端本地差分隐私位置保护方法。移动用户根据个性化隐私需求提交位置隐私保护范围，服务器端按需进行位置编码并返回给用户。用户端选择所在区域的Huffman编码，并对其进行本地化差分隐私扰动以实现对原始位置的隐私保护。服务器端通过对接收的扰动位置进行解码来判断用户所处的区域，并据此提供基于位置的服务（location-based services，LBS）。在实际位置数据集合上的实验证明，所提方法能够在实现用户位置本地化差分隐私保护的基础上，提供更好的位置数据可用性和运行效率。

关键词: 位置隐私保护, 本地化差分隐私, Huffman编码, 随机响应

YAN Yan, LYU Yaqin, LI Feifei. Local Differential Privacy Location Protection for Mobile Terminals Based on Huffman Coding[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(3): 802-817.

晏燕, 吕雅琴, 李飞飞. 基于Huffman编码的移动终端本地差分隐私位置保护[J]. 计算机科学与探索, 2025, 19(3): 802-817.

References

[1] JIANG H B, LI J, ZHAO P, et al. Location privacy-preserving mechanisms in location-based services: a comprehensive survey[J]. ACM Computing Surveys, 2021, 54(1): 1-36.
[2] ZHANG P J, LEI D Z, LIU S, et al. Recursive logit-based meta-inverse reinforcement learning for driver-preferred route planning[J]. Transportation Research Part E: Logistics and Transportation Review, 2024, 185: 103485.
[3] CEPEDA-PACHECO J C, DOMINGO M C. Deep learning and Internet of things for tourist attraction recommendations in smart cities[J]. Neural Computing and Applications, 2022, 34(10): 7691-7709.
[4] 王娟. 基于位置服务的020精准营销实现途径[J]. 全国流通经济, 2024(2): 32-35.
WANG J. Approaches towards realization of 020 precision marketing based on location service[J]. China Circulation Economy, 2024(2): 32-35.
[5] 何林, 张雅斌, 任杰, 等. 任意位置天气实况服务设计与应用[J]. 科学技术与工程, 2023, 23(33): 14088-14094.
HE L, ZHANG Y B, REN J, et al. Design and application of the weather-LBS live service[J]. Science Technology and Engineering, 2023, 23(33): 14088-14094.
[6] WEI X M, LIU Y Z, SUN J S, et al. Dual subgraph-based graph neural network for friendship prediction in location-based social networks[J]. ACM Transactions on Knowledge Discovery from Data, 2023, 17(3): 1-28.
[7] 徐花, 田有亮. 差分隐私下的权重社交网络隐私保护[J]. 西安电子科技大学学报, 2022, 49(1): 17-25.
XU H, TIAN Y L. Protection of privacy of the weighted social network under differential privacy[J]. Journal of Xidian University, 2022, 49(1): 17-25.
[8] CHANG V, MOU Y Q, XU Q A. The ethical issues of location-based services on big data and IoT[C]//Proceedings of the IIoTBDSC 2020: Modern Industrial IoT, Big Data and Supply Chain. Singapore: Springer, 2021: 195-205.
[9] FENG J, YANG L T, REN B C, et al. Tensor recurrent neural network with differential privacy[J]. IEEE Transactions on Computers, 2024, 73(3): 683-693.
[10] 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.
[11] DUCHI J C, JORDAN M I, WAINWRIGHT M J. Local privacy and statistical minimax rates[C]//Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. Piscataway: IEEE, 2013: 429-438.
[12] GRUTESER M, GRUNWALD D, GRUTESER M, et al. 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.
[13] YANG M X, YE B P, CHEN Y L, et al. A trusted de-swinging k-anonymity scheme for location privacy protection[J]. Journal of Cloud Computing, 2022, 11(1): 2.
[14] 殷凤梅, 陈鸿. Geohash编码的k匿名位置隐私保护方案[J]. 武汉大学学报(理学版), 2022, 68(1): 73-82.
YIN F M, CHEN H. K anonymous location privacy preservation scheme based on geohash coding[J]. Journal of Wuhan University (Natural Science Edition), 2022, 68(1): 73-82.
[15] LIU J H, WANG S X. All-dummy k-anonymous privacy protection algorithm based on location offset[J]. Computing, 2022, 104(8): 1739-1751.
[16] LIU H Y, ZHANG S W, LI M L, et al. An effective location privacy-preserving K-anonymity scheme in location based services[C]//Proceedings of the 2021 IEEE International Conference on Electronic Technology, Communication and Information. Piscataway: IEEE, 2021: 24-29.
[17] 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.
[18] FAROUK F, ALKADY Y, RIZK R. Privacy preserving location based services query scheme based on fully homomorphic encryption[J]. Journal of Theoretical and Applied Information Technology, 2021, 99(16): 4098-4121.
[19] 高胜, 陈秀华, 朱建明, 等. 基于区块链的群智感知中任务预算约束的位置隐私保护参与者选择方法[J]. 计算机学报, 2022, 45(5): 1052-1067.
GAO S, CHEN X H, ZHU J M, et al. A location privacy-preserving worker selection scheme under limited budget for blockchain-based crowdsensing[J]. Chinese Journal of Computers, 2022, 45(5): 1052-1067.
[20] LI Z T, WANG T H, LOPUHAÄ-ZWAKENBERG M, et al. Estimating numerical distributions under local differential privacy[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2020: 621-635.
[21] DU R, YE Q Q, FU Y, et al. Collecting high-dimensional and correlation-constrained data with local differential privacy[C]//Proceedings of the 2021 18th Annual IEEE International Conference on Sensing, Communication, and Networking. Piscataway: IEEE, 2021: 1-9.
[22] ZHANG P F, CHENG X, SU S, et al. Effective truth discovery under local differential privacy by leveraging noise-aware probabilistic estimation and fusion[J]. Knowledge-Based Systems, 2023, 261: 110213.
[23] SUN L, PING G L, YE X J. PrivBV: distance-aware encoding for distributed data with local differential privacy[J]. Tsinghua Science and Technology, 2022, 27(2): 412-421.
[24] HONG D, JUNG W, SHIM K. Collecting geospatial data with local differential privacy for personalized services[C]//Proceedings of the 2021 IEEE 37th International Conference on Data Engineering. Piscataway: IEEE, 2021: 2237-2242.
[25] 张啸剑, 付楠, 孟小峰. 基于本地差分隐私的空间范围查询方法[J]. 计算机研究与发展, 2020, 57(4): 847-858.
ZHANG X J, FU N, MENG X F. Towards spatial range queries under local differential privacy[J]. Journal of Computer Research and Development, 2020, 57(4): 847-858.
[26] NAVIDAN H, MOGHTADAIEE V, NAZARAN N, et al. Hide me behind the noise: local differential privacy for indoor location privacy[C]//Proceedings of the 2022 IEEE European Symposium on Security and Privacy Workshops. Piscataway: IEEE, 2022: 514-523.
[27] WANG J, WANG F, LI H T. Differential privacy location protection scheme based on Hilbert curve[J]. Security and Communication Networks, 2021, 2021(1): 5574415.
[28] 晏燕, 董卓越, 徐飞, 等. 一种Hilbert编码的本地化位置隐私保护方法[J]. 西安电子科技大学学报, 2023, 50(2): 147-160.
YAN Y, DONG Z Y, XU F, et al. Localized location privacy protection method using the Hilbert encoding[J]. Journal of Xidian University, 2023, 50(2): 147-160.
[29] YAN Y, CHEN J Z, MAHMOOD A, et al. LDPORR: a localized location privacy protection method based on optimized random response[J]. Journal of King Saud University-Computer and Information Sciences, 2023, 35(8): 101713.
[30] STEPHANIE V, CHAMIKARA M A P, KHALIL I, et al. Privacy-preserving location data stream clustering on mobile edge computing and cloud[J]. Information Systems, 2022, 107: 101728.
[31] WANG H, HONG H B, XIONG L, et al. L-SRR[C]//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2022: 2809-2823.
[32] FU N, NI W W, HU H B, et al. Multidimensional grid-based clustering with local differential privacy[J]. Information Sciences, 2023, 623: 402-420.
[33] ZHANG P F, CHENG X, SU S, et al. Task allocation under geo-indistinguishability via group-based noise addition[J]. IEEE Transactions on Big Data, 2023, 9(3): 860-877.
[34] WARNER S L. Randomized response: a survey technique for eliminating evasive answer bias[J]. Journal of the American Statistical Association, 1965, 60(309): 63-66.