一种基于时空相关性的差分隐私轨迹保护机制  

Differentially Private Trajectory Protection Based on Spatial and Temporal Correlation

作　　者：吴云乘 陈红[1,2] 赵素云[1,2] 梁文娟 吴垚 李翠平[1,2] 张晓莹[1,2] 

机构地区：[1]中国人民大学数据工程与知识工程教育部重点实验室,北京100872 [2]中国人民大学信息学院,北京100872

出　　处：《计算机学报》2018年第2期309-322,共14页Chinese Journal of Computers

基　　金：国家自然科学基金(61532021;61702522;61772537;61772536);国家"八六三"高技术研究发展计划项目(2014AA015204)资助~~

摘　　要：近年来,基于位置的服务(LBS)越来越成为人们生活中一种重要的查询方式,具有广阔的应用前景和价值.然而,在连续地使用LBS时会暴露用户的位置甚至轨迹,用户对这种位置或轨迹隐私泄露的顾虑一方面阻碍了LBS的应用,另一方面降低了用户得到的服务质量.目前,轨迹隐私保护技术已成为研究热点,但是现有的技术极少考虑到地理空间的限制以及时间序列上位置的相关性,使得攻击者仍有较大可能推断出用户的真实敏感位置和轨迹.该文针对轨迹隐私保护问题,首先根据地理空间的拓扑关系,提出了CPL算法计算地图上各区域的隐私级别,并定义了一种结合隐私级别与差分隐私预算的隐私模型.然后,该文基于马尔可夫概率转移矩阵,分析了发布位置对当前真实位置和之前真实位置的影响,提出了一种差分隐私位置发布机制DPLRM,以保护用户的位置和轨迹隐私.最后,在真实数据集上的实验验证了该文提出的隐私模型和差分隐私位置发布机制的准确性和有效性.In recent years,location based services(LBS)is becoming one of the most important ways for information retrieval in our daily life,and it has broad application prospects and great value.However,people's locations or trajectory may be disclosed when they continuously use LBS to retrieve point of interests.This privacy disclosure problem not only restricts the development of LBS,but also reduces the quality of service the users obtained.Recently,trajectory privacy protection has attracted more and more attention,such as cloaking based technique,perturbation based technique,and so on.However,existing techniques seldom consider the geo-spatial and temporal correlation of the locations between several timestamps,which might degrade the location privacy of users.In this paper,aiming at dealing with the trajectory privacy problem,we explore a popular paradigm for providing privacy with strong theoretical guarantees,differential privacy,which has recently gained significant attention for its robustness to known attacks,anddefine a new privacy model based on differential privacy for trajectory protection.Specifically,we firstly propose an algorithm(CPL)to calculate the privacy level of each location on the map according to geo-spatial correlation.This algorithm transforms the topology of map into an undirected weighted graph.Based on the initial sensitive locations and the corresponding pre-defined privacy levels that provided by users,CPL algorithm iteratively allocates the privacy level of a location to its adjacent locations by the edge weights,and computes the aggregated privacy levels for all other locations that are not in the set of initial sensitive locations.Secondly,we present a privacy model,calledγ-trajectory privacy,that combines the privacy level and differential privacy budget.Fundamentally,for any location in a trajectory,this privacy model requires that the multiplication of privacy level that computed from CPL algorithm and differential privacy budget of this location should equal toγ.In other words,th

关 键 词：轨迹隐私 差分隐私 时空相关性 位置隐私 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]