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

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

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.     

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

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

Location privacy: going beyond K-anonymity,cloaking and anonymizers

With many location-based services, it is implicitly assumed that the location server receives actual users locations to respond to their spatial queries. Consequently, information customized to their locations, such as nearest points of interest can be provided. However, there is a major privacy concern over sharing such sensitive information with potentially malicious servers, jeopardizing users’ private information. The anonymity- and cloaking-based approaches proposed to address this problem cannot provide stringent privacy guarantees without incurring costly computation and communication overhead. Furthermore, they require a trusted intermediate anonymizer to protect user locations during query processing. This paper proposes a fundamental approach based on private information retrieval to process range and K-nearest neighbor queries, the prevalent queries used in many location-based services, with stronger privacy guarantees compared to those of the cloaking and anonymity approaches. We performed extensive experiments on both real-world and synthetic datasets to confirm the effectiveness of our approaches.     

EDA: an enhanced dual-active algorithm for location privacy preservation inmobile P2P networks

Various solutions have been proposed to enable mobile users to access location-based services while preserving their location privacy. Some of these solutions are based on a centralized architecture with the participation of a trustworthy third party, whereas some other approaches are based on a mobile peer-to-peer (P2P) architecture. The former approaches suffer from the scalability problem when networks grow large, while the latter have to endure either low anonymization success rates or high communication overheads. To address these issues, this paper deals with an enhanced dual-active spatial cloaking algorithm (EDA) for preserving location privacy in mobile P2P networks. The proposed EDA allows mobile users to collect and actively disseminate their location information to other users. Moreover, to deal with the challenging characteristics of mobile P2P networks, e.g., constrained network resources and user mobility, EDA enables users (1) to perform a negotiation process to minimize the number of duplicate locations to be shared so as to significantly reduce the communication overhead among users, (2) to predict user locations based on the latest available information so as to eliminate the inaccuracy problem introduced by using some out-of-date locations, and (3) to use a latest-record-highest-priority (LRHP) strategy to reduce the probability of broadcasting fewer useful locations. Extensive simulations are conducted for a range of P2P network scenarios to evaluate the performance of EDA in comparison with the existing solutions. Experimental results demonstrate that the proposed EDA can improve the performance in terms of anonymity and service time with minimized communication overhead.     

k-Nearest Neighbor Query Processing Algorithms for a Query Region in Road Networks

Recent development of wireless communication technologies and the popularity of smart phones are making location-based services (LBS) popular. However, requesting queries to LBS servers with users’ exact locations may threat the privacy of users. Therefore, there have been many researches on generating a cloaked query region for user privacy protection. Consequently, an effcient query processing algorithm for a query region is required. So, in this paper, we propose k-nearest neighbor query (k-NN) processing algorithms for a query region in road networks. To effciently retrieve k-NN points of interest (POIs), we make use of the Island index. We also propose a method that generates an adaptive Island index to improve the query processing performance and storage usage. Finally, we show by our performance analysis that our k-NN query processing algorithms outperform the existing k-Range Nearest Neighbor (kRNN) algorithm in terms of network expansion cost and query processing time.     

Preserving location privacy without exact locations in mobile services

Privacy preservation has recently received considerable attention in location-based services (LBSs). A large number of location cloaking algorithms have been proposed for protecting the location privacy of mobile users. However, most existing cloaking approaches assume that mobile users are trusted. And exact locations are required to protect location privacy, which is exactly the information mobile users want to hide. In this paper, we propose a p-anti-conspiration privacy model to anonymize over semi-honest users. Furthermore, two k*NNG-based cloaking algorithms, vk*NNCA and ek*NNCA, are proposed to protect location privacy without exact locations. The efficiency and effectiveness of the proposed algorithms are validated by a series of carefully designed experiments. The experimental results show that the price paid for location privacy protection without exact locations is small.     

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在匿名成功率、匿名时间和匿名代价方面均表现出良好性能。     

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空间匿名算法的基础上引入数字签名技术,实现用户之间的身份认证,并且在通信过程中,用接收方的私钥加密位置信息,避免了攻击者窃取他们的位置信息。算法中还加入了用户可以容忍的最大等待时间这一参数,通过等待一段时间重新进行节点发现,有效地提高了匿名成功率。通过实验验证,该算法可以更好地保护用户的位置隐私。     

基于网格划分空间的位置匿名算法

现有的位置匿名算法的匿名时间较长,匿名后的空间区域较大,严重影响查询的服务质量。为了解决这些问题,提出了一种基于网格划分空间的位置匿名算法,该算法基于位置k-匿名模型,采用网格结构划分空间后对用户位置进行位置匿名。实验结果表明,该算法在满足用户位置隐私需求的前提下,位置匿名时间更短,用户的平均匿名空间减小,从而大幅度提升用户查询的服务质量。     

Buddy tracking — efficient proximity detection among mobile friends

Global positioning systems (GPS) and mobile phone networks make it possible to track individual users with an increasing accuracy. It is natural to ask whether this information can be used to maintain social networks. In such a network each user wishes to be informed whenever one of a list of other users, called the user’s friends, appears in the user’s vicinity. In contrast to more traditional positioning based algorithms, the computation here depends not only on the user’s own position on a static map, but also on the dynamic position of the user’s friends. Hence it requires both communication and computation resources. The computation can be carried out either between the individual users in a peer-to-peer fashion or by centralized servers where computation and data can be collected at one central location. In the peer-to-peer model, a novel algorithm for minimizing the number of location update messages between pairs of friends is presented. We also present an efficient algorithm for the centralized model, based on region hierarchy and quadtrees. The paper provides an analysis of the two algorithms, compares them with a naive approach, and evaluates them on user motions generated by the IBM City Simulator system.     

A multi-agent based user context Bayesian neural network analysis system

The increasing user mobility demands placed upon IT services necessitates an environment that enables users to access optimal services at any time and in any place. This study presents research conducted to develop a system that is capable of analyzing user IT service patterns and tendencies and provides the necessary service resources by sharing each user’s context information. First, each user’s context information is gathered to provide the multi-agent software training data necessary to describe user operations in a hybrid peer-to-peer (P2P) structured communication environment. Next, the data collected about each user’s mobile device is analyzed through a Bayesian based neural network system to identify the user’s tendency and extract essential service information. This information provides a communication configuration allowing the user access to the best communication service between the user’s mobile device and the local server at any time and in any place, thereby enhancing the ubiquitous computing environment.     

Protecting personalized privacy against sensitivity homogeneity attacks over road networks in mobile services

Privacy preservation has recently received considerable attention for location-based mobile services. A lot of location cloaking approaches focus on identity and location protection, but few algorithms pay attention to prevent sensitive information disclosure using query semantics. In terms of personalized privacy requirements, all queries in a cloaking set, from some user’s point of view, are sensitive. These users regard the privacy is breached. This attack is called as the sensitivity homogeneity attack. We show that none of the existing location cloaking approaches can effectively resolve this problem over road networks. We propose a (K, L, P)-anonymity model and a personalized privacy protection cloaking algorithm over road networks, aiming at protecting the identity, location and sensitive information for each user. The main idea of our method is first to partition users into different groups as anonymity requirements. Then, unsafe groups are adjusted by inserting relaxed conservative users considering sensitivity requirements. Finally, segments covered by each group are published to protect location information. The efficiency and effectiveness of the method are validated by a series of carefully designed experiments. The experimental results also show that the price paid for defending against sensitivity homogeneity attacks is small.     

面向基于位置服务的一种改进型隐私感知虚假位置选择机制

基于位置的服务已经逐渐成为人们生活中的重要部分,然而在无线信道中传输位置信息容易受到各种攻击,导致严重的隐私泄露问题。为此,本文考虑隐私保护等级以及实际虚假位置区域,将虚假位置选择问题建模为多目标优化问题,进而提出一种低复杂度的隐私程度可控的虚假位置选择机制。本文首先从候选虚假位置中选择出请求率差异在指定范围内的虚假位置,保护一定的隐私等级,然后从中找出K-1个虚假位置,最大化总泛化面积。为了更准确确定总泛化面积,本文推导出两位置区域的相交面积。安全分析验证了本文提出的算法可以对抗主动攻击以及被动攻击。与其他算法相比,仿真结果也证明了本文提出的算法可以在保护用户隐私等级的情况下增大总泛化面积。     

LBS中基于移动终端的连续查询用户轨迹隐匿方法*

为减少现有LBS(基于位置的服务)机制给用户位置信息和个人隐私泄露带来的威胁,提出并实现了一个基于移动智能终端的连续查询用户运动轨迹保护方案.该方法利用移动终端来规划虚拟路径,以减少用户在连续查询中的隐私泄露,且不需要第三方服务器提供位置匿名服务,由用户自主决定何时启动位置隐匿机制.实验证明,提出的方法有效地隐匿了连续查询用户的位置及轨迹信息.     

移动用户位置隐私保护方案研究

随着基于位置的服务（ LBS）的发展,如何保证用户在使用位置服务时的隐私安全,已成为一个亟待解决的问题。文中对主流的位置隐私保护技术进行了分析和比较。在此基础上,针对移动用户的位置隐私保护,提出了一种基于中心服务器的位置隐私保护方案。该方案针对隐私保护需求的差异性,考虑区域的敏感等级,对敏感区域采用K-匿名和假名进行保护,同时运用脚印来辅助匿名。该方案能在不降低位置服务质量的前提下,有效地保护移动用户位置隐私。     

L2P2: A location-label based approach for privacy preserving in LBS

The developments in positioning and mobile communication technology have made the location-based service (LBS) applications more and more popular. For privacy reasons and due to lack of trust in the LBS providers, k-anonymity and l-diversity techniques have been widely used to preserve privacy of users in distributed LBS architectures in Internet of Things (IoT). However, in reality, there are scenarios where the locations of users are identical or similar/near each other in IoT. In such scenarios the k locations selected by k-anonymity technique are the same and location privacy can be easily compromised or leaked. To address the issue of privacy preservation, in this paper, we introduce the location labels to distinguish locations of mobile users to sensitive and ordinary locations. We design a location-label based (LLB) algorithm for protecting location privacy of users while minimizing the response time for LBS requests. We also evaluate the performance and validate the correctness of the proposed algorithm through extensive simulations.     

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

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