基于Geohash编码的位置隐私保护算法

针对基于位置服务中用户位置信息易泄露用户个人隐私的问题，利用Geohash编码优化网格化Casper模型，提出了基于Geohash的位置隐私保护算法G-Casper。该算法采用自底向上的机制，对目标位置的Geohash编码进行字符串模糊查询来确定组成匿名区域的[k-1]个近邻，在扩大扫描区域时，对请求用户所在网格以及周边网格跨域扫描，然后再进行层级的递归，同时使用[Lmax]和[Lmin]两个参数来控制匿名区域范围，最终通过剪枝算法删除冗余网格并随机发送一个候选网格区域代替用户原本位置，达到[k]-匿名的效果。实验结果表明，该算法能够更好地提高位置服务的质量和匿名区域的成功率，并且减少了查询时间和所需储存空间。     

P2P模式下基于网格扩增的位置匿名算法

位置k-匿名方法是当前基于位置的服务中隐私保护领域的研究热点。典型的位置匿名算法多采用单一可信的中心匿名服务器对用户位置进行匿名,但中心服务器容易成为性能瓶颈和集中攻击点,而已有P2P模式下的位置匿名算法在安全性上较弱。针对上述问题,提出了一种P2P模式下基于网格扩增的位置匿名算法,其利用网格划分平面,通过不断翻倍扩增网格宽度寻找满足用户隐私需求的匿名区,最终完成对用户位置的匿名。同时算法在运行中能够与邻近节点分享计算所得中间结果,并对其进行缓存。实验表明,与已有算法相比,本算法可显著降低网络带宽的消耗,减少位置匿名耗时,同时能够避免匿名区中心攻击,且抗查询采样攻击的能力得到较大提升。     

基于用户网格和两级缓存的LBS位置隐私保护方案

提出了一种采用用户网格和两级缓存技术相结合的方案,该方法采用基于第三方可信服务器的体系结构,在用户提交服务查询请求时,将用户的真实位置以正方形网格区域代替并发送给匿名服务器;在匿名服务器中,将地理空间以最小匿名区域为大小的固定网格划分以提高缓存利用率,同时使用四叉树存储固定网格区域,加快k-匿名区域的生成速度;在移动终端和第三方可信服务器中同时引入缓存机制,减少用户与第三方可信服务器以及位置服务提供商之间的交互次数,有效提高了查询响应速度与用户隐私保护程度。     

路网环境下敏感位置匿名区域的生成方法

用户的位置信息涉及个人隐私,用户精确的位置信息可能会暴露其爱好、行为等敏感信息,因此,位置信息的匿名显得非常重要。现有的位置隐私保护方法大多是在欧氏空间下基于k-匿名算法生成位置匿名区域。欧氏空间下的k-匿名算法虽然可以在一定程度上解决用户位置信息的匿名保护问题,但是在现实生活中,用户的位置受路网环境影响较大,同时,欧氏空间下的k-匿名算法在生成匿名区域后对该区域是否还处于敏感范围内未做考虑。因此提出了一种路网环境下敏感位置匿名区域的生成方法。该方法基于空间划分,首先按照路网L-差异性要求对路网交叉点生成维诺图单元;接着考虑用户所处位置的敏感度,对用户位置生成匿名区域。实验结果表明,与一般的k-匿名算法生成的匿名区域相比,提出的算法能较好地解决一般k-匿名算法生成的匿名区域仍然处于敏感范围内的问题,从而更好地保护用户的位置隐私。     

基于查询概率的位置隐私保护方法

现有的隐私保护技术较少考虑到查询概率、map数据、信息点（POI）语义等边信息,攻击者可以将边信息与位置数据相结合推断出用户的隐私信息,为此提出一种新的方法ARB来保护用户的位置隐私。该方法首先把空间划分为网格,根据历史查询数据计算出处于不同网格区域的用户提交查询的概率;然后结合相应单元格的查询概率来生成用户匿名区域,从而保护用户的位置隐私信息;最后采用位置信息熵作为隐私保护性能的度量指标。在真实数据集上与已有的两种方法进行对比来验证隐私保护方法的性能,结果显示该方法具体有较好的隐私保护效果和较低的时间复杂度。     

基于速度动态差异的位置服务匿名算法

随着基于位置服务应用的日益流行,其潜在的用户隐私泄露问题也成为制约其发展的一大挑战。用户位置数据的泄露,可能导致与用户生活相关的活动、住址等隐私信息泄露,隐私问题成为位置服务中人们普遍关注的热门话题。尤其是在连续查询场景下,查询间存在着密切的联系,这就使得用户的隐私面临更大的威胁。针对这一问题,文章提出了一种连续查询下的隐私保护算法,称为基于速度的动态匿名算法(V-DCA)。在匿名处理时,考虑了用户的运动特征和趋势,也就是速度和加速度,并且利用历史匿名集合来产生新的匿名集合,在抵御查询跟踪攻击、保护隐私的同时提供了良好的服务质量。文章设计了一种连续查询隐私保护算法——基于速度的动态匿名算法(V-DCA),将用户的速度、加速度作为匿名条件之一,有效地平衡了隐私和服务质量;为了评价匿名算法,分别从隐私保障、服务质量和匿名时间3个方面提出了多个度量指标;通过在真实地图及相同环境下与其他匿名算法进行比较实验,验证了V-DCA在隐私保障、服务质量和响应时间方面的良好表现。     

路网环境下的语义多样性位置隐私保护方法

针对位置服务中基于K-匿名方法构造的匿名集因未考虑语义信息导致语义推断攻击问题,提出了一种路网环境下的语义多样性位置隐私保护方法。该方法根据不同语义位置用户访问数量,利用欧氏距离选择具有相似特性的语义位置类型,构建最优语义位置类型集合。根据路段上属于该类型集的语义位置所占比例,选择最优路段构建匿名集,使得匿名集不仅满足语义多样性,而且增加了用户语义位置的不确定性。实验结果表明,与LSBASC算法相比,该方法在平均匿名时间上提高了27%,SDA算法的执行效率更好。在相对空间粒度上减小了21%,隐私泄露程度上降低了3%,SDA算法以更小的匿名空间提供更高的服务质量和隐私保护程度,能有效地保护用户语义位置隐私。     

一种新型的防范历史攻击的k-匿名算法

针对位置信息服务(LBS)中出现的连续查询的隐私问题,提出了一种新型的防范历史攻击的k-匿名算法。该算法根据周围用户的位置、移动速度和移动方向,预测这些用户将来的位置,利用这些位置计算出未来不同时间点上将某用户加入匿名集使匿名区域增大的面积,利用贪心算法优先选择增大面积之和最小的用户加入匿名集。在OPNET 14.5平台下进行了仿真实验,实验结果证明了该算法所形成的匿名区域大小适当,在历史攻击的情况下,既能保护用户的隐私,又能保证一定的服务质量。     

基于查询概率的假位置选择算法

位置服务(Location-based Service,LBS)已经成为日常生活的重要组成部分。用户在享受位置服务带来的巨大便利的同时,也面临着巨大的隐私泄露风险。针对传统的位置隐私保护中K-匿名机制没有考虑到攻击者具有背景知识或者边信息的问题,提出了一种改进的假位置选择算法来保护位置隐私。该方法首先对样本空间进行网格划分,并基于历史查询数据计算出每个位置单元的查询概率;再结合历史查询概率为用户寻找(K－1)个假位置,使得这(K－1)个假位置的历史查询概率与用户所在位置的历史查询概率尽量相同,并且使这K个位置尽量 分散。实验结果证明了该算法在位置隐私保护方面的有效性。     

位置大数据中一种基于Bloom Filter的匿名保护方法

位置大数据服务应用中存在大量的用户敏感信息,针对服务中海量数据分析的隐私泄露问题,提出一种基于Bloom Filter多哈希散列编码的位置匿名保护方法。采用启发式的隐私度量技术划分匿名区来隐藏真实的位置数据,保持欧氏距离上搜索目标的邻近关系以优化空间匿名框的面积,并在划分策略中引入查询服务相似性因子以减少空间碎片的产生。在移动用户和服务器之间构建可信的第三方位置匿名服务器,能有效地模糊目标节点,从而抵御恶意的隐私攻击。理论分析和仿真实验表明,新算法能有效优化匿名空间区域,提高隐私保护程度,并在海量数据集的构建过程中具有较优的时间复杂度。     

Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments

This paper tackles a privacy breach in current location-based services (LBS) where mobile users have to report their exact location information to an LBS provider in order to obtain their desired services. For example, a user who wants to issue a query asking about her nearest gas station has to report her exact location to an LBS provider. However, many recent research efforts have indicated that revealing private location information to potentially untrusted LBS providers may lead to major privacy breaches. To preserve user location privacy, spatial cloaking is the most commonly used privacy-enhancing technique in LBS. The basic idea of the spatial cloaking technique is to blur a user’s exact location into a cloaked area that satisfies the user specified privacy requirements. Unfortunately, existing spatial cloaking algorithms designed for LBS rely on fixed communication infrastructure, e.g., base stations, and centralized/distributed servers. Thus, these algorithms cannot be applied to a mobile peer-to-peer (P2P) environment where mobile users can only communicate with other peers through P2P multi-hop routing without any support of fixed communication infrastructure or servers. In this paper, we propose a spatial cloaking algorithm for mobile P2P environments. As mobile P2P environments have many unique limitations, e.g., user mobility, limited transmission range, multi-hop communication, scarce communication resources, and network partitions, we propose three key features to enhance our algorithm: (1) An information sharing scheme enables mobile users to share their gathered peer location information to reduce communication overhead; (2) A historical location scheme allows mobile users to utilize stale peer location information to overcome the network partition problem; and (3) A cloaked area adjustment scheme guarantees that our spatial cloaking algorithm is free from a “center-of-cloaked-area” privacy attack. Experimental results show that our P2P spatial cloaking algorithm is scalable while guaranteeing the user’s location privacy protection.     

k-Nearest neighbor query processing algorithm for cloaking regions towards user privacy protection in location-based services

Due to the advancement of wireless internet and mobile positioning technology, the application of location-based services (LBSs) has become popular for mobile users. Since users have to send their exact locations to obtain the service, it may lead to several privacy threats. To solve this problem, a cloaking method has been proposed to blur users’ exact locations into a cloaked spatial region with a required privacy threshold (k). With the cloaked region, an LBS server can carry out a k-nearest neighbor (k-NN) search algorithm. Some recent studies have proposed methods to search k-nearest POIs while protecting a user’s privacy. However, they have at least one major problem, such as inefficiency on query processing or low precision of retrieved result. To resolve these problems, in this paper, we propose a novel k-NN query processing algorithm for a cloaking region to satisfy both requirements of fast query processing time and high precision of the retrieved result. To achieve fast query processing time, we propose a new pruning technique based on a 2D-coodinate scheme. In addition, we make use of a Voronoi diagram for retrieving the nearest POIs efficiently. To satisfy the requirement of high precision of the retrieved result, we guarantee that our k-NN query processing algorithm always contains the exact set of k nearest neighbors. Our performance analysis shows that our algorithm achieves better performance in terms of query processing time and the number of candidate POIs compared with other algorithms.     

Privacy-Conscious Location-Based Queries in Mobile Environments

In location-based services, users with location-aware mobile devices are able to make queries about their surroundings anywhere and at any time. While this ubiquitous computing paradigm brings great convenience for information access, it also raises concerns over potential intrusion into user location privacy. To protect location privacy, one typical approach is to cloak user locations into spatial regions based on user-specified privacy requirements, and to transform location-based queries into region-based queries. In this paper, we identify and address three new issues concerning this location cloaking approach. First, we study the representation of cloaking regions and show that a circular region generally leads to a small result size for region-based queries. Second, we develop a mobility-aware location cloaking technique to resist trace analysis attacks. Two cloaking algorithms, namely MaxAccu_Cloak and MinComm_Cloak, are designed based on different performance objectives. Finally, we develop an efficient polynomial algorithm for evaluating circular-region-based kNN queries. Two query processing modes, namely bulk and progressive, are presented to return query results either all at once or in an incremental manner. Experimental results show that our proposed mobility-aware cloaking algorithms significantly improve the quality of location cloaking in terms of an entropy measure without compromising much on query latency or communication cost. Moreover, the progressive query processing mode achieves a shorter response time than the bulk mode by parallelizing the query evaluation and result transmission.     

针对LBS中非可信用户协作构建匿名域的研究

基于位置的服务作为一种不断发展的新型服务模式,为人们的生活带来了极大的便利。但另一方面,用户的位置隐私也受到了很大的威胁。从LBS位置隐私保护的实际应用出发,根据现有的位置隐私保护模型,分析了在用户协作构建匿名域的方式下,用户非完全可信时,位置隐私面临的威胁,提出了User-Cooperation Security（UCA）匿名算法,在P2P空间匿名算法的基础上引入数字签名技术,实现用户之间的身份认证,并且在通信过程中,用接收方的私钥加密位置信息,避免了攻击者窃取他们的位置信息。算法中还加入了用户可以容忍的最大等待时间这一参数,通过等待一段时间重新进行节点发现,有效地提高了匿名成功率。通过实验验证,该算法可以更好地保护用户的位置隐私。     

基于用户分布感知的移动P2P快速位置匿名算法

针对移动点对点（P2P）结构下位置隐私保护匿名区形成存在着通信开销大、匿名效率低以及成功率低等问题,提出了一种移动P2P结构下用户分布感知方案,用户在邻域内共享邻域加权密度参数,获取邻域用户实时分布信息,根据用户分布特征为用户推荐隐私参数及候选用户查找半径,帮助用户快速形成匿名区。仿真结果表明,该算法通信开销小,在满足移动P2P网络移动设备节能需求的同时,匿名区生成时间平均在500ms以下,平均成功率达到92%以上。     

两种基于Quad-Tree的匿名算法

基于位置的服务（LBS）给人们带来巨大便利的同时可能导致位置隐私的泄露。为了保护用户的位置隐私,一种有效的方法是将用户的精确位置匿名成一个空间区域,现有基于Quad-Tree的匿名算法导致匿名时间较长并且准确度较低。提出两种匿名算法QFC和SWC,与传统的匿名算法（Casper）相比,QFC算法在保持匿名准确度相同的情况下,可以减少CPU时间;SWC算法以牺牲一定的CPU时间为代价,可以达到较高的匿名准确度。     

An efficient method for privacy preserving location queries

Recently, the issue of privacy preserving location queries has attracted much research. However, there are few works focusing on the tradeoff between location privacy preservation and location query information collection. To tackle this kind of tradeoff, we propose the privacy persevering location query (PLQ), an efficient privacy preserving location query processing framework. This framework can enable the location-based query without revealing user location information. The framework can also facilitate location-based service providers to collect some information about the location based query, which is useful in practice. PLQ consists of three key components, namely, the location anonymizer at the client side, the privacy query processor at the server side, and an additional trusted third party connecting the client and server. The location anonymizer blurs the user location into a cloaked area based on a map-hierarchy. The map-hierarchy contains accurate regions that are partitioned according to real landforms. The privacy query processor deals with the requested nearest-neighbor (NN) location based query. A new convex hull of polygon (CHP) algorithm is proposed for nearest-neighbor queries using a polygon cloaked area. The experimental results show that our algorithms can efficiently process location based queries.     

Query-aware location anonymization for road networks

Recently, several techniques have been proposed to protect the user location privacy for location-based services in the Euclidean space. Applying these techniques directly to the road network environment would lead to privacy leakage and inefficient query processing. In this paper, we propose a new location anonymization algorithm that is designed specifically for the road network environment. Our algorithm relies on the commonly used concept of spatial cloaking, where a user location is cloaked into a set of connected road segments of a minimum total length L{\cal L} including at least K{\cal K} users. Our algorithm is “query-aware” as it takes into account the query execution cost at a database server and the query quality, i.e., the number of objects returned to users by the database server, during the location anonymization process. In particular, we develop a new cost function that balances between the query execution cost and the query quality. Then, we introduce two versions of our algorithm, namely, pure greedy and randomized greedy, that aim to minimize the developed cost function and satisfy the user specified privacy requirements. To accommodate intervals with a high workload, we introduce a shared execution paradigm that boosts the scalability of our location anonymization algorithm and the database server to support large numbers of queries received in a short time period. Extensive experimental results show that our algorithms are more efficient and scalable than the state-of-the-art technique, in terms of both query execution cost and query quality. The results also show that our algorithms have very strong resilience to two privacy attacks, namely, the replay attack and the center-of-cloaked-area attack.     

基于位置服务中防止敏感同质性攻击的个性化隐私保护

基于位置服务中的隐私保护方法存在只关注保护用户位置和标识信息的问题,当匿名集中提出的查询均属于敏感查询时,将产生敏感同质性攻击。针对此问题,提出了个性化(k,p)-敏感匿名模型。并基于此模型,提出了基于树型索引结构的匿名算法--PTreeCA。空间数据库中的树型索引具有两大特点：1)空间中的用户已根据位置邻近性在树中被大致分组;2)在树的中间节点中可以存储聚集信息。利用这两个特点,PTreeCA可以从查询用户所在叶子节点和其兄弟节点中寻找匿名集,提高了匿名算法的效率。最后,在模拟和真实数据集上进行了实验,所提算法平均匿名成功率可达100%,平均匿名时间只有4ms。当隐私级别较低和适中时,PTreeCA在匿名成功率、匿名时间和匿名代价方面均表现出良好性能。     

基于本地差分隐私的众包隐私保护方法

在移动互联网发展的今天,基于位置服务（LBS）技术在移动互联上取得显著进展。针对个人用户进行精确定位时,数据信息隐私存在着泄露风险的问题,本文提出一种基于本地化差分隐私的地理不可区分性的扰动方法。在用户的真实位置数据信息流出客户端前采用地理不可区分性位置扰动方式,作用于真实位置以得到近似位置数据,服务器端收到后制成二级区域网格图,之后采用差分隐私对该图的工人计数进行扰动,最后在空间范围查询下进行实验验证,并与满足ε-本地化差分隐私扰动算法进行对比,精确度提高2.7%,同时与平均划分隐私预算分配方式进行实验对比,提高区域计数精确度4.57%。