Dynamic local differential privacy location protection method based on critical path

YAN Yan; LIU Kun; ZHANG Yanli; FENG Tao

doi:10.11959/j.issn.2096-109x.2025061

您当前的位置：

首页 >

文章列表页 >

Dynamic local differential privacy location protection method based on critical path

更新时间：2025-11-08

- Dynamic local differential privacy location protection method based on critical path
- Chinese Journal of Network and Information Security Vol. 11, Issue 5, Pages: 68-87(2025)
- 作者机构：
  
  兰州理工大学计算机与人工智能学院，甘肃兰州 730050
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(62361036)
- DOI：10.11959/j.issn.2096-109x.2025061
  CLC： TP309
- Received：22 May 2025，
  
  Revised：2025-07-18，
  
  Published：25 October 2025
- 稿件说明：
移动端阅览
晏燕, 刘坤, 张艳莉, 等. 基于关键路径的动态本地化差分隐私位置保护方法[J]. 网络与信息安全学报, 2025, 11(5): 68-87.

YAN Y, LIU K, ZHANG Y L, et al. Dynamic local differential privacy location protection method based on critical path[J]. Chinese Journal of Network and Information Security, 2025, 11(5): 68-87.
晏燕, 刘坤, 张艳莉, 等. 基于关键路径的动态本地化差分隐私位置保护方法[J]. 网络与信息安全学报, 2025, 11(5): 68-87. DOI： 10.11959/j.issn.2096-109x.2025061.

YAN Y, LIU K, ZHANG Y L, et al. Dynamic local differential privacy location protection method based on critical path[J]. Chinese Journal of Network and Information Security, 2025, 11(5): 68-87. DOI： 10.11959/j.issn.2096-109x.2025061.

摘要

位置信息作为数字时代重要的个人数据资产，在提供便利服务的同时面临着严重的隐私泄露风险。本地化差分隐私模型无须依赖可信的第三方，近年来受到广泛关注。然而，现有本地化差分隐私位置保护方法普遍面临两大挑战：一是空间分割结构难以适应位置分布的复杂特性；二是用户与服务器端的通信与计算开销制约了系统效率。针对上述挑战，提出一种基于关键路径的动态本地化差分隐私位置保护方法。该方法首先通过非均匀四叉树空间分割与Hilbert曲线遍历，构建适配于用户分布密度的空间索引，有效提升了数据可用性。继而由服务器运行提出的关键路径编码机制，将复杂的分割结构压缩为简洁的路径信息，减少了下发参数时的通信开销。用户端根据本地化差分隐私模型对自身所处区域的Hilbert索引编码进行随机响应扰动，实现原始位置的隐私保护。服务器端则根据收集到的用户扰动位置编码进行聚合分析，并依据位置分布的时空连续性执行所提出的空间分割结构动态调整策略，以极低的计算成本高效适应用户分布的动态变化。在实际位置数据集上的实验证明，所提方法能够在实现用户位置本地化差分隐私保护的基础上，提高数据可用性和算法运行效率。

Abstract

Location information was recognized as a critical personal data asset in the digital age

offering convenient services while simultaneously posing significant risks of privacy breaches. Local differential privacy models

which do not rely on trusted third parties

had garnered widespread attention. However

significant challenges were identified in existing location protection methods

including the difficulty of adapting spatial partitioning to complex location distributions

along with high communication and computational overhead that limited system efficiency. To address these challenges

a dynamic local differential privacy location protection method based on a critical path was proposed. A spatial index adapted to user distribution density was constructed through non-uniform quadtree spatial partitioning and Hilbert curve traversal

which effectively improved data usability. Subsequently

the proposed critical path encoding mechanism was executed on the server side to compress the complex partition structure into concise path information

thereby reducing communication overhead during parameter transmission. On the user side

the Hilbert index encoding of the user’s region was perturbed using a randomized response mechanism under the local differential privacy model to protect the privacy of the original location. On the server side

the collected perturbed location encodings from users were aggregated and analyzed. Based on the spatiotemporal continuity of location distribution

the proposed spatial partition structure dynamic adjustment strategy was then implemented to efficiently adapt to dynamic changes in user distribution at an extremely low computational cost. Experiments conducted on real-world location datasets demonstrate that the proposed method provides improved location data availability and algorithm runtime efficiency while achieving local differential privacy protection for user locations.

关键词

Keywords

references

XIAO Z R , LI P S , LIU C , et al . MACNS: a generic graph neural network integrated deep reinforcement learning based multi-agent collaborative navigation system for dynamic trajectory planning [J ] . Information Fusion , 2024 , 105 : 102250 .

ZHOU W , FU C , SANG C Y , et al . Next PoI recommendation based on graph convolutional networks and multiple context-awareness [J ] . IEEE Transactions on Services Computing , 2025 , 18 ( 1 ): 302 - 313 .

VAGHEFI M S , NAZARETH D L , NERUR S P , et al . Self-disclosure in online social networks: an empirical study of location-based check-ins and impression management [J ] . Information & Management , 2024 , 61 ( 7 ): 104017 .

QIU G Y , TANG G M , LI C D , et al . Differentiated location privacy protection in mobile communication services: a survey from the semantic perception perspective [J ] . ACM Computing Surveys , 2024 , 56 ( 3 ): 1 - 36 .

ZHOU X K , YANG Q Y , LIU Q , et al . Spatial-temporal federated transfer learning with multi-sensor data fusion for cooperative positioning [J ] . Information Fusion , 2024 , 105 : 102182 .

TANG L L , HE M X , XIONG L , et al . An efficient and privacy-preserving query scheme in intelligent transportation systems [J ] . Information Sciences , 2023 , 647 : 119448 .

LI Z J , MA J F , MIAO Y B , et al . Enabling efficient privacy-preserving spatiotemporal location-based services for smart cities [J ] . IEEE Internet of Things Journal , 2024 , 11 ( 3 ): 5288 - 5300 .

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 .

DUCHI J C , JORDAN M I , WAINWRIGHT M J . Local privacy and statistical minimax rates [C ] // Proceedings of the 2013 51st Annual Allerton Conference on Communication, Control and Computing (Allerton) . Piscataway : IEEE Press , 2013 .

张啸剑 , 付楠 , 孟小峰 . 基于本地差分隐私的空间范围查询方法 [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 .

晏燕 , 董卓越 , 徐飞 , 等 . 一种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 .

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 .

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

YAN Y , LYU Y Q , LI F F . 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 .

晏燕 , 丛一鸣 , MAHMOOD A , 等 . 基于深度学习的位置大数据统计发布与隐私保护方法 [J ] . 通信学报 , 2022 , 43 ( 1 ): 203 - 216 .

YAN Y , CONG Y M , MAHMOOD A , et al . Statistics release and privacy protection method of location big data based on deep learning [J ] . Journal on Communications , 2022 , 43 ( 1 ): 203 - 216 .

霍峥 , 张坤 , 贺萍 , 等 . 满足本地化差分隐私的众包位置数据采集 [J ] . 计算机应用 , 2019 , 39 ( 3 ): 763 - 768 .

HUO Z , ZHANG K , HE P , et al . Crowdsourcing location data collection for local differential privacy [J ] . Journal of Computer Applications , 2019 , 39 ( 3 ): 763 - 768 .

ZHANG E Z , GUAN Y G , LU R X , et al . An efficient heap tree-based range query scheme under local differential privacy [J ] . IEEE Internet of Things Journal , 2024 , 11 ( 11 ): 20648 - 20659 .

JU Z C , LI Y C . Local differential privacy-based privacy-preserving data range query scheme for electric vehicle charging [J ] . IEEE Transactions on Network Science and Engineering , 2024 , 11 ( 1 ): 673 - 684 .

WANG L X , YE Q Q , HU H B , et al . PriPL-tree: accurate range query for arbitrary distribution under local differential privacy [J ] . Proceedings of the VLDB Endowment , 2024 , 17 ( 11 ): 3031 - 3044 .

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 .

KAIROUZ P , BONAWITZ K A , RAMAGE D . Discrete distribution estimation under local privacy [C ] // Proceedings of the 33nd International Conference on Machine Learning . 2016 : 2436 - 2444 .

WANG T H , BLOCKI J , LI N H , et al . Locally differentially private protocols for frequency estimation [C ] // Proceedings of the USENIX Security Symposium . Berkeley : USENIX Association , 2017 : 729 - 745 .

ERLINGSSON Ú , PIHUR V , KOROLOVA A . RAPPOR: randomized aggregatable privacy-preserving ordinal response [C ] // Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM , 2014 : 1054 - 1067 .

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 .

YAN Y , YAN P B , MAHMOOD A , et al . Achieving local differential location privacy protection in 3D space via Hilbert encoding and optimized random response [J ] . Journal of King Saud University - Computer and Information Sciences , 2024 , 36 ( 6 ): 102085 .

杨宏宇 , 张恒鸣 , 朱友文 , 等 . 面向LBS的ADS-B报文定位数据本地化差分隐私保护方法 [J ] . 网络与信息安全学报 , 2025 , 11 ( 4 ): 32 - 49 .

YANG H Y , ZHANG H M , ZHU Y W , et al . Differential privacy protection method for localization of ADS-B message positioning data oriented to LBS [J ] . Chinese Journal of Network and Information Security , 2025 , 11 ( 4 ): 32 - 49 .

ACHARYA J , SUN Z T , ZHANG H Y . Hadamard response: estimating distributions privately, efficiently, and with little communication [C ] // Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics . New York : PMLR , 2018 : 1120 - 1129 .

ZHAO D , CHEN H , ZHAO S Y , et al . FLDP: flexible strategy for local differential privacy [C ] // Proceedings of the 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) . Piscataway : IEEE Press , 2022 : 2974 - 2978 .

VARMA G , CHAUHAN R , SINGH D . Sarve: synthetic data and local differential privacy for private frequency estimation [J ] . Cybersecurity , 2022 , 5 ( 1 ): 26 .

HONG D , JUNG W , SHIM K . Collecting geospatial data under local differential privacy with improving frequency estimation [J ] . IEEE Transactions on Knowledge and Data Engineering , 2023 , 35 ( 7 ): 6739 - 6751 .

FENG G H , WANG G J , PENG T . Toward answering federated spatial range queries under local differential privacy [J ] . International Journal of Intelligent Systems , 2024 , 2024 ( 1 ): 2408270 .

LI Z T , ZENG X Y , XIAO Y , et al . Pattern-sensitive local differential privacy for finite-range time-series data in mobile crowdsensing [J ] . IEEE Transactions on Mobile Computing , 2025 , 24 ( 1 ): 1 - 14 .

SUN X Y , YE Q Q , HU H B , et al . Generating location traces with semantic- constrained local differential privacy [J ] . IEEE Transactions on Information Forensics and Security , 2024 , 19 : 9850 - 9865 .

叶青青 , 孟小峰 , 朱敏杰 , 等 . 本地化差分隐私研究综述 [J ] . 软件学报 , 2018 , 29 ( 7 ): 1981 - 2005 .

YE Q Q , MENG X F , ZHU M J , et al . Survey on local differential privacy [J ] . Journal of Software , 2018 , 29 ( 7 ): 1981 - 2005 .

YAN Y , GAO X , MAHMOOD A , et al . Differential private spatial decomposition and location publishing based on unbalanced quadtree partition algorithm [J ] . IEEE Access , 2020 , 8 : 104775 - 104787 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Differential privacy protection method for localization of ADS-B message positioning data oriented to LBS

Survey of differentially private methods for trajectory data

Social network user geolocating method based on weighted least squares

Location privacy protection for mobile social network

Related Author

YANG Hongyu

ZHANG Hengming

ZHU Youwen

HU Huiling

HU Juncheng

SUN Xinyue

ZHANG Weizhe

HE Hui

Related Institution

School of Safety Science and Engineering, Civil Aviation University of China

School of Computer Science and Technology, Civil Aviation University of China

College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics

Air Traffic Management Department, Central and Southern Regional Air Traffic Management Bureau of CAAC

School of Computer Science and Technology, Jilin University

⁰