于乃文 杨少杰 陈振国 张光华

摘 要：为了兼顾共享位置数据的可用性和隐私保护需求，针对第三方收集的用户共享位置信息，提出了一种基于差分隐私的LBS用户位置隐私保护方案。首先，对共享位置数据集进行预处理，使用字典查询方式构建位置事务数据库，采用Trie树结构存储位置数据和频率，提高查询效率，减少加噪次数;其次，在Trie树上进行频繁位置选取，并使用差分隐私下的拉普拉斯机制扰动位置频率;最后，基于向上后置处理和一致性约束后置处理2种技术对扰动后的数据进行优化，并通过理论证明所提方案满足ε-差分隐私。结果表明，与已有方法相比，差分隐私保护方案提高了数据处理效率，泛化了敏感位置同时具有较高的精确率和较低的拒真率。所提方案能够有效保护用户的位置隐私，同时在共享位置数据可用性方面具有一定的参考价值。

关键词：数据安全与计算机安全;位置数据;隐私保护;差分隐私;可用性

中图分类号：TP309.2 文献标识码：A

doi：10.7535/hbkd.2021yx03003

Location privacy protection scheme for LBS users based on differential privacy

YU Naiwen1， YANG Shaojie1， CHEN Zhenguo2， ZHANG Guanghua1，3

（1.School of Information Science and Engineering，Hebei University of Science and Technology，Shijiazhuang，Hebei 050018，China;

2.Hebei Engineering Technology Research Center for IoT Data Acquisition & Processing，North China Institute of Science and Technology，Langfang，Hebei 065201，China;

3.State Key Laboratory of Integrated Services Networks，Xidian University，Xi'an，Shaanxi 710071，China）

Abstract：In order to take into account the availability of shared location data and privacy protection requirements，aiming at the shared location information collected by the third party，a location privacy protection scheme of LBS users was proposed based on differential privacy.Firstly，the shared location data set was preprocessed，the dictionary query mode was used to build the location transaction database，and the trie tree structure was adopted to store the location data and frequency，so as to improve the query efficiency and reduce the number of noise.Secondly，frequent location selection was carried out in the Trie tree，and Laplacian mechanism under differential privacy was used to disturb the location frequency.Finally，the perturbed data was optimized based on the two techniques of upward post-processing and consistency constrained post-processing，and theoretically prove that the proposed scheme satisfies ε-differential privacy.The experimental results show that，compared with the existing methods，this scheme improves the efficiency of data processing，generalizes the sensitive locations，and has higher accuracy and lower rejection rate.This scheme has a certain reference value in user location privacy protection and shared location data availability.

Keywords：

data security and computer security;location data;privacy protection;differential privacy;availability

隨着GPS、无线通信等技术的飞速发展，基于位置服务（LBS，location-based service）[1]给人们的生活起居、外出工作和社交活动带来了巨大变化。用户通过智能设备从应用商店可以下载基于位置的应用程序，如百度地图、谷歌地图等，在提交的位置信息和查询内容基础上获取所需的服务数据[2]。功能多样化的LBS应用遍及人们的日常生活，其应用场景主要有导航服务、社交网络服务、兴趣点推荐服务。然而，位置服务给用户带来诸多便利的同时，各种隐私泄露问题也层出不穷[3-4]。……