A Survey on Anonymity in Location Based Services
---
paper_title: Privacy in Location Based Services: Primitives Toward the Solution

paper_content:

Location based services (LBS) are one of the most promising and innovative directions of convergence technologies resulting of emergence of several fields including database systems, mobile communication, Internet technology, and positioning systems. Although being initiated as early as middle of 1990's, it is only recently that the LBS received a systematic profound research interest due to its commercial and technological impact. As the LBS is related to the user's location which can be used to trace the user's activities, a strong privacy concern has been raised. To preserve the user's location, several intelligent works have been introduced though many challenges are still awaiting solutions. This paper introduces a survey on LBS systems considering both localization technologies, model and architectures guaranteeing privacy. We also overview cryptographic primitive to possibly use in preserving LBS's privacy followed by fruitful research directions basically concerned with the privacy issue.
---
paper_title: Blind Signatures for Untraceable Payments

paper_content:

Automation of the way we pay for goods and services is already underway, as can be seen by the variety and growth of electronic banking services available to consumers. The ultimate structure of the new electronic payments system may have a substantial impact on personal privacy as well as on the nature and extent of criminal use of payments. Ideally a new payments system should address both of these seemingly conflicting sets of concerns.
---
paper_title: Location Anonymity Based on Fake Queries in Continuous Location-Based Services

paper_content:

The large-scale deployment of location-based services (LBSs) brings about the potential abuse of their clients' personal information. Therefore, location privacy in LBSs is significant. Ensuring location privacy for mobile users is an effort to prevent semi-honest or dishonest service providers from abusing the location information. Though there exist several techniques to preserve location privacy of mobile users, these techniques cannot effectively protect the location privacy in continuous location-based services. In this paper, we propose a location anonymity scheme based on the fake queries in continuous location-based services. To prevent attackers from tracing a mobile user by his continuous queries, some fake continuous queries will be injected by some neighbors. These fake queries can produce equivalent fake paths similar to the user's mobile path, because they are generated according to the user's speed and mobile direction. It is so difficult for the attackers to distinguish the real continuous queries from other fake queries. Security analysis shows that our scheme can resist the continuous queries attack, maximum speed attack and abnormal points attack. Experimental results manifest that our scheme can provide stringent privacy guarantees and is beyond the limitation of existing algorithms based on K-anonymity technique.
---
paper_title: MobiCache: When k-anonymity meets cache

paper_content:

Location-Based Services (LBSs) are becoming increasingly popular in our daily life. In some scenarios, multiple users may seek data of same interest from a LBS server simultaneously or one by one, and they may need to provide their exact locations to the un-trusted LBS server in order to enjoy such a location-based service. Unfortunately, this will breach users' location privacy and security. To address this problem, we propose a novel collaborative system, MobiCache, which combines k-anonymity with caching together to protect user's location privacy while improving the cache hit ratio. Different from the traditional k-anonymity, our Dummy Selection Algorithm (DSA) chooses dummy locations which have not been queried before to increase the cache hit ratio. We also propose an enhanced-DSA to further improve the user's privacy as well as the cache hit ratio by assigning dummy locations which can make more contributions to cache hit ratio. Evaluation results show that the proposed DSA can increase the cache hit ratio and the enhanced-DSA can further improve the cache hit ratio as well as the user's privacy.
---
paper_title: An anonymous communication technique using dummies for location-based services

paper_content:

Recently, highly accurate positioning devices enable us to provide various types of location-based services. On the other hand, because such position data include deeply personal information, the protection of location privacy is one of the most significant problems in location-based services. In this paper, we propose an anonymous communication technique to protect the location privacy of the users of location-based services. In our proposed technique, such users generate several false position data (dummies) to send to service providers with the true position data of users. Because service providers cannot distinguish the true position data, user location privacy is protected. We also describe a cost reduction technique for communication between a client and a server. Moreover, we conducted performance study experiments on our proposed technique using practical position data. As a result of the experiments, we observed that our proposed technique protects the location privacy of people and can sufficiently reduce communication costs so that our communication techniques can be applied in practical location-based services.
---
paper_title: PAD: privacy-area aware, dummy-based location privacy in mobile services

paper_content:

Location privacy in mobile services has the potential to become a serious concern for service providers and users. Existing privacy protection techniques that use k-anonymity convert an original query into an anonymous query that contains the locations of multiple users. Such techniques, however, generally fail in offering guaranteed large privacy regions at reasonable query processing costs. In this paper, we propose the PAD approach that is capable of offering privacy-region guarantees. To achieve this, PAD uses so-called dummy locations that are deliberately generated according to either a virtual grid or circle. These cover a user's actual location, and their spatial extents are controlled by the generation algorithms. The PAD approach only requires a lightweight server-side front-end in order for it to be integrated into an existing client/server mobile service system. In addition, query results are organized according to a compact format on the server, which not only reduces communication cost, but also facilitates the result refinement on the client side. An empirical study shows that our proposal is effective in terms of offering location privacy, and efficient in terms of computation and communication costs.
---
paper_title: Achieving k-anonymity in privacy-aware location-based services

paper_content:

Location-Based Service (LBS) has become a vital part of our daily life. While enjoying the convenience provided by LBS, users may lose privacy since the untrusted LBS server has all the information about users in LBS and it may track them in various ways or release their personal data to third parties. To address the privacy issue, we propose a Dummy- Location Selection (DLS) algorithm to achieve k-anonymity for users in LBS. Different from existing approaches, the DLS algorithm carefully selects dummy locations considering that side information may be exploited by adversaries. We first choose these dummy locations based on the entropy metric, and then propose an enhanced-DLS algorithm, to make sure that the selected dummy locations are spread as far as possible. Evaluation results show that the proposed DLS algorithm can significantly improve the privacy level in terms of entropy. The enhanced-DLS algorithm can enlarge the cloaking region while keeping similar privacy level as the DLS algorithm. I. INTRODUCTION With the rapid development of mobile devices and social networks, Location-Based Service (LBS) has become a vital part in our daily activities in recent years. With smartphones or tablets, users can download location-based applications from Apple Store or Google Play Store. With the help of these
---
paper_title: Privacy-Aware Cloaking Technique in Location-Based Services

paper_content:

The explosive growth of location-detection devices, such as GPS (Global Positioning System), continuously increasing users' privacy threat in location-based services (LBSs). However, in order to enjoy such services, the user must precisely disclose his/her exact location to the LBS. So, it is a key challenge to efficiently preserve user's privacy while accessing LBS. For this, the existing method employs a 2PASS cloaking framework that not only hides the actual user location but also reduces bandwidth consumption. However, it suffers from privacy attack. Therefore, we wish to provide the solution which can preserve user privacy by utilizing k-anonymity mechanism. In this paper, we propose a weighted adjacency graph based k -anonymous cloaking technique that can ensure users privacy protection and also reduce bandwidth usages. Our cloaking approach efficiently supports k-nearest neighbor queries without revealing private information of the query initiator. We demonstrate via experimental results that our algorithm yields much better performance than the existing one.
---
paper_title: Preventing Location-Based Identity Inference in Anonymous Spatial Queries

paper_content:

The increasing trend of embedding positioning capabilities (for example, GPS) in mobile devices facilitates the widespread use of location-based services. For such applications to succeed, privacy and confidentiality are essential. Existing privacy-enhancing techniques rely on encryption to safeguard communication channels, and on pseudonyms to protect user identities. Nevertheless, the query contents may disclose the physical location of the user. In this paper, we present a framework for preventing location-based identity inference of users who issue spatial queries to location-based services. We propose transformations based on the well-established K-anonymity concept to compute exact answers for range and nearest neighbor search, without revealing the query source. Our methods optimize the entire process of anonymizing the requests and processing the transformed spatial queries. Extensive experimental studies suggest that the proposed techniques are applicable to real-life scenarios with numerous mobile users.
---
paper_title: Location anonymity in continuous location-based services

paper_content:

A major concern for large-scale deployment of location-based services (LBSs) is the potential abuse of their client location data, which may imply sensitive personal information. Location privacy protection is challenging because a location itself may reveal a subject's identity. To support location anonymity, existing research reduces location resolution by ensuring each location reported to a service provider is a cloaking area that contains at least K mobile nodes. This strategy is effective when each location update can be considered as an independent event. In this paper, we investigate location anonymity in the context of continuous LBSs, which require frequent location updates from service users. Knowing that a user is inside a cloaking area constrains its position in the next cloaking area. Thus, simply ensuring each cloaking area contains at least K users does not give a user K-anonymity protection. We propose to measure the anonymity degree of a cloaking area using entropy, which takes into account not only the number of the entities inside, but also their anonymity probability distribution. To find a cloaking area that can provide a given level of anonymity protection and is also as small as possible, we present a novel technique with a polynomial time complexity. The effectiveness of our techniques is studied under various conditions using location data synthetically generated using real road maps and traffic volume data. The results show that our techniques can indeed protect user anonymity at a desired level, and at the same time, minimize the size of each cloaking area, allowing users to receive high quality services.
---
paper_title: Exploring Historical Location Data for Anonymity Preservation in Location-Based Services

paper_content:

We present a new approach for if-anonymity protection in Location-Based Services (LBSs). Specifically, we depersonalize location information by ensuring that each location reported for LBSs is a cloaking area that contains K different footprints-historical locations of different mobile nodes. Therefore, the exact identity and location of the service requestor remain anonymous from LBS service providers. Existing techniques, on the other hand, compute the cloaking area using current locations of K neighboring hosts of the service requestor. Because of this difference, our approach significantly reduces the cloaking area, which in turn decreases query processing and communication overhead for returning query results to the requesting host. In addition, existing techniques also require frequent location updates from all nodes, regardless of whether or not these nodes are requesting LBSs. Most importantly, our approach is the first practical solution that provides K-anonymity trajectory protection needed to ensure anonymity when a mobile host requests LBSs continuously as it moves. Our solution depersonalizes a user's trajectory (a time-series of the user's locations) based on the historical trajectories of other users. We evaluate our techniques under various conditions using location data synthetically generated based on real road maps. The results show that our techniques can provide K-anonymity trajectory protection using a minimized cloaking area.
---
paper_title: Protecting Location Privacy with Personalized k-Anonymity: Architecture and Algorithms

paper_content:

Continued advances in mobile networks and positioning technologies have created a strong market push for location-based applications. Examples include location-aware emergency response, location-based advertisement, and location-based entertainment. An important challenge in the wide deployment of location-based services (LBSs) is the privacy-aware management of location information, providing safeguards for location privacy of mobile clients against vulnerabilities for abuse. This paper describes a scalable architecture for protecting the location privacy from various privacy threats resulting from uncontrolled usage of LBSs. This architecture includes the development of a personalized location anonymization model and a suite of location perturbation algorithms. A unique characteristic of our location privacy architecture is the use of a flexible privacy personalization framework to support location k-anonymity for a wide range of mobile clients with context-sensitive privacy requirements. This framework enables each mobile client to specify the minimum level of anonymity that it desires and the maximum temporal and spatial tolerances that it is willing to accept when requesting k-anonymity-preserving LBSs. We devise an efficient message perturbation engine to implement the proposed location privacy framework. The prototype that we develop is designed to be run by the anonymity server on a trusted platform and performs location anonymization on LBS request messages of mobile clients such as identity removal and spatio-temporal cloaking of the location information. We study the effectiveness of our location cloaking algorithms under various conditions by using realistic location data that is synthetically generated from real road maps and traffic volume data. Our experiments show that the personalized location k-anonymity model, together with our location perturbation engine, can achieve high resilience to location privacy threats without introducing any significant performance penalty.
---
paper_title: Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking

paper_content:

Advances in sensing and tracking technology enable location-based applications but they also create significant privacy risks. Anonymity can provide a high degree of privacy, save service users from dealing with service providers’ privacy policies, and reduce the service providers’ requirements for safeguarding private information. However, guaranteeing anonymous usage of location-based services requires that the precise location information transmitted by a user cannot be easily used to re-identify the subject. This paper presents a middleware architecture and algorithms that can be used by a centralized location broker service. The adaptive algorithms adjust the resolution of location information along spatial or temporal dimensions to meet specified anonymity constraints based on the entities who may be using location services within a given area. Using a model based on automotive traffic counts and cartographic material, we estimate the realistically expected spatial resolution for different anonymity constraints. The median resolution generated by our algorithms is 125 meters. Thus, anonymous location-based requests for urban areas would have the same accuracy currently needed for E-911 services; this would provide sufficient resolution for wayfinding, automated bus routing services and similar location-dependent services.
---
paper_title: A dynamic spatial cloaking algorithm for location privacy

paper_content:

With the growing popularity of Global Positioning System (GPS) enabled mobile devices, a widespread using of Location-Based Service (LBS) has become reality. Due to untrusted service providers, reporting private location information may lead to several security threats. Traditional K-anonymity algorithm deals with location privacy protection problem by a cloaking region. Inspired by this idea, we propose Dynamic Cloaking Algorithm, which runs on anonymity server and turns user's location into a dynamic cloaking region before sending to LBS Database Server. The cloaking region is generated randomly according to user's velocity and this process is proved irreversible. Experimental results show the our algorithm obviously improves the success rate and scalability of cloaking region constructing. Our algorithm decreases the payload at LBS Database Server and has a better anonymity.
---
paper_title: MobiHide : A Mobile Peer-to-Peer System for Anonymous Location-Based Queries

paper_content:

Modern mobile phones and PDAs are equipped with positioning capabilities (e.g., GPS). Users can access public location-based services (e.g., Google Maps) and ask spatial queries. Although communication is encrypted, privacy and confidentiality remain major concerns, since the queries may disclose the location and identity of the user. Commonly, spatial K-anonymity is employed to hide the query initiator among a group of K users. However, existing work either fails to guarantee privacy, or exhibits unacceptably long response time. ::: ::: In this paper we propose MobiHide, a Peer-to-Peer system for anonymous location-based queries, which addresses these problems. MobiHide employs the Hilbert space-filling curve to map the 2-D locations of mobile users to 1-D space. The transformed locations are indexed by a Chord-based distributed hash table, which is formed by the mobile devices. The resulting Peer-to-Peer system is used to anonymize a query by mapping it to a random group of K users that are consecutive in the 1-D space. Compared to existing state-of-the-art, MobiHide does not provide theoretical anonymity guarantees for skewed query distributions. Nevertheless, it achieves strong anonymity in practice, and it eliminates system hotspots. Our experimental evaluation shows that MobiHide has good load balancing and fault tolerance properties, and is applicable to real-life scenarios with numerous mobile users.
---
paper_title: PRIVE: anonymous location-based queries in distributed mobile systems

paper_content:

Nowadays, mobile users with global positioning devices canaccess Location Based Services (LBS) and query about pointsof interest in their proximity. For such applications to succeed,privacy and confidentiality are essential. Encryptionalone is not adequate; although it safeguards the systemagainst eavesdroppers, the queries themselves may disclosethe location and identity of the user. Recently, there havebeen proposed centralized architectures based on K-anonymity,which utilize an intermediate anonymizer between themobile users and the LBS. However, the anonymizer mustbe updated continuously with the current locations of allusers. Moreover, the complete knowledge of the entire systemposes a security threat, if the anonymizer is compromised.In this paper we address two issues: (i) We show thatexisting approaches may fail to provide spatial anonymityfor some distributions of user locations and describe a noveltechnique which solves this problem. (ii) We propose Prive,a decentralized architecture for preserving the anonymityof users issuing spatial queries to LBS. Mobile users self-organizeinto an overlay network with good fault toleranceand load balancing properties. Prive avoids the bottleneckcaused by centralized techniques both in terms of anonymizationand location updates. Moreover, the system state isdistributed in numerous users, rendering Prive resilient toattacks. Extensive experimental studies suggest that Priveis applicable to real-life scenarios with large populations ofmobile users.
---
paper_title: Towards Achieving Anonymity in LBS: A Cloud Based Untrusted Middleware

paper_content:

Technological advancements in mobile technology and cloud computing open the door for another paradigm known as Mobile Cloud Computing (MCC). This integration of cloud computing and mobile technology gives numerous facilities to a mobile user, such as the ubiquitous availability of Location Based Services (LBS). The utilization of these LBS services require the knowledge of a user's location, hence threatens the privacy of a user. In this paper we take advantages of ultra-fast processing and reliability of cloud computing and aim to solve the privacy threat issue faced by a mobile user while getting LBS services. We propose a model that utilizes a cloud based server which helps in making of a cloaking region. We highlight that how our model utilizes an untrusted cloud based server and eliminates the use of a trusted anonymizer while providing LBS services to a user securely and anonymously.
---
paper_title: Spatial Cloaking for Anonymous Location-based Services in Mobile Peer-to-Peer Environments

paper_content:

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.
---
paper_title: Track me if you can: Transparent obfuscation for Location based Services

paper_content:

Although Location-based Services (LBSs) offer evident advantages to their users, many privacy concerns are sought when user tracking data are shared with the service provider. Existing privacy enhancing solutions (e.g. k-anonymity) usually degrade service precision, and also require the collaboration of the service provider-this latter one not always willing to lose control over the user's location data. In this paper, we propose a solution that is able to obfuscate the user's path to the service provider, while preserving (for the LBS) the capability to compute a few functions-useful for the user-over the obfuscated path. In particular, we provide several contributions: first, we formalize the concept of obfuscation function, and we propose a solution that provides user privacy while allowing users to continue leveraging the services offered by the service provider. Moreover, we formally prove the privacy preserving properties of our approach. Finally, an extensive experimental campaign supports the feasibility of our approach, showing that the proposed solution can be efficiently implemented over mobile device.
---
paper_title: A Novel Time-Obfuscated Algorithm for Trajectory Privacy Protection

paper_content:

Location-based services (LBS) which bring so much convenience to our daily life have been intensively studied over the years. Generally, an LBS query processing can be categorized into snapshot and continuous queries which access user location information and return search results to the users. An LBS has full control of the location information, causing user privacy concerns. If an LBS provider has a malicious intention to breach the user privacy by tracking the users' routes to their destinations, it incurs a serious threat. Most existing techniques have addressed privacy protection mainly for snapshot queries. However, providing privacy protection for continuous queries is of importance, since a malicious LBS can easily obtain complete user privacy information by observing a sequence of successive query requests. In this paper, we propose a comprehensive trajectory privacy technique and combine ambient conditions to cloak location information based on the user privacy profile to avoid a malicious LBS reconstructing a user trajectory. We first propose an $r$ -anonymity mechanism which preprocesses a set of similar trajectories $R$ to blur the actual trajectory of a service user. We then combine $k$ -anonymity with $s$ road segments to protect the user's privacy. We introduce a novel time-obfuscated technique which breaks the sequence of the query issuing time for a service user to confuse the LBS so it does not know the user trajectory, by sending a query randomly from a set of locations residing at the different trajectories in $R$ . Despite the randomness incurred from the obfuscation process for providing strong trajectory privacy protection, the experimental results show that our trajectory privacy technique maintains the correctness of the query results at a competitive computational cost.
---
paper_title: Location Privacy Protection Through Obfuscation-Based Techniques

paper_content:

The widespread adoption of mobile communication devices combined with technical improvements of location technologies are fostering the development of a new wave of applications that manage physical positions of individuals to offer location-based services for business, social or informational purposes. As an effect of such innovative services, however, privacy concerns are increasing, calling for more sophisticated solutions for providing users with different and manageable levels of privacy. In this work, we propose a way to express users privacy preferences on location information in a straightforward and intuitive way. Then, based on such location privacy preferences, we discuss a new solution, based on obfuscation techniques, which permits us to achieve, and quantitatively estimate through a metric, different degrees of location privacy.
---
paper_title: Matlock: A location obfuscation technique for accuracy-restricted applications

paper_content:

Location-based information systems (LBIS) have shown growth in the last years thanks to the popularization of cheap GPS-enabled mobile devices with connectivity to the Internet. At the same time, users have made their locations more available than ever, representing a major privacy problem, as attackers could easily determine their victims' common paths or actual locations. As a result, some techniques have been designed to protect the users' private information while allowing Location Based Service systems (LBS) to continue growing. Location obfuscation is a technique that alters, substitutes, or generalizes the real location of the users to protect them against malicious attacks. Moreover, there are activities that require a high level of accuracy while also maintaining the protection of the location, such as fleet management or transportation of valuables. In this work, a light-weight and fully reversible location obfuscation technique named Matlock is presented. Matlock, based on matrix obfuscation, requires low computation per operation and hides the location in both spatial and temporal dimensions. The performance evaluation shows how this technique alters the location of paths from different geographical regions, produces a non-morphologically similar path to the original path, and generates increasing distance functions between the original and the obfuscated paths, which together should reduce the probability of using estimation techniques to perform deobfuscation of the information.
---
paper_title: A novel privacy preserving authentication and access control scheme for pervasive computing environments

paper_content:

Privacy and security are two important but seemingly contradictory objectives in a pervasive computing environment (PCE). On one hand, service providers want to authenticate legitimate users and make sure they are accessing their authorized services in a legal way. On the other hand, users want to maintain the necessary privacy without being tracked down for wherever they are and whatever they are doing. In this paper, a novel privacy preserving authentication and access control scheme to secure the interactions between mobile users and services in PCEs is proposed. The proposed scheme seamlessly integrates two underlying cryptographic primitives, namely blind signature and hash chain, into a highly flexible and lightweight authentication and key establishment protocol. The scheme provides explicit mutual authentication between a user and a service while allowing the user to anonymously interact with the service. Differentiated service access control is also enabled in the proposed scheme by classifying mobile users into different service groups. The correctness of the proposed authentication and key establishment protocol is formally verified based on Burrows-Abadi-Needham logic
---
paper_title: An Anonymous Authentication Protocol for Privacy Protection in Location Based Services

paper_content:

Privacy protection is particularly challenging in location based services (LBS). On one hand, service providers want to authenticate legitimate users. On the other hand, mobile users would prefer not to expose any information which enables anyone, including service providers, to get some clue regarding their whereabouts. To resolve this dilemma, we propose an anonymous authentication protocol to protect mobile users' privacy during the interactions between users and service providers in LBS. In this protocol, the service providers use blind signature to generate an authorized anonymous ID for the user, and then the user uses ring signature to mix the anonymous ID into a group of authorized IDs. We formally verify the correctness of the authentication and key establishment procedure in the protocol. In some practical situations, our protocol provides an efficient mechanism for balancing users' need for high-quality information services against their need for privacy protection.
---
paper_title: Protection of mobile location privacy by using blind signature

paper_content:

Location privacy means a user keeps his/her geographical location secret. If location information falls into the wrong hands, an adversary can physically locate a person. To address this privacy issue, Qi et al. (2004a; 2004b) proposed a special and feasible architecture, using blind signature to generate an authorized anonymous ID replacing the real ID of a legitimate mobile user. The original purpose of his architecture was to eliminate the relationship of authorized anonymous ID and real ID. We present an algorithm to break out Qi’s registration and re-confusion protocol, and then propose a new mechanism based on bilinear pairings to protect location privacy. Moreover we show that the administrator or third parity cannot obtain information on the legitimate user’s authorized anonymous ID and real ID in our proposed protocols.
---
paper_title: Binomial-Mix-Based Location Anonymizer System with Global Dummy Generation to Preserve User Location Privacy in Location-Based Services

paper_content:

We propose a binomial-mix-based location anonymizer system with global dummy generation to protect user location privacy in location-based services in the face of attacks from a global active adversary and even with untrusted location-based service providers. Our proposed system overcomes the disadvantages of high latency in general-purpose mix-net systems when they are applied to location-based services, and the imprecision of query result or inefficiency due to large number of candidates in query result of existing obfuscation or spatial cloaking techniques. In our system, dummies (false locations) are generated globally in order to reduce the latency of requests to location-based services. A centralized dummy generation mechanism exploits all users' activities to optimize the system's behavior and performance. Because of the randomness provided by a binomial mix, our system prevents an adversary from determining with certainty whether a user is at a specific location. Our system also lets users define and update their personal location privacy maps and satisfies a probabilistic real-time condition that ensures delivery of any request within a predefined duration with high probability.
---
paper_title: Efficient Oblivious Augmented Maps: Location-Based Services with a Payment Broker

paper_content:

Secure processing of location data in location-based services (LBS) can be implemented with cryptographic protocols. We propose a protocol based on oblivious transfer and homomorphic encryption. Its properties are the avoidance of personal information on the services side, and a fair revenue distribution scheme. We discuss this in contrast to other LBS solutions that seek to anonymize information as well as possible towards the services. For this purpose, we introduce a proxy party. The proxy interacts with multiple services and collects money from subscribing users. Later on, the proxy distributes the collected payment to the services based on the number of subscriptions to each service. Neither the proxy nor the services learn the exact relation between users and the services they are subscribed to.
---

Title: A Survey on Anonymity in Location Based Services
Section 1: Introduction
Description 1: This section should introduce Location Based Services (LBS) and explain the importance of maintaining user privacy in these services.

Section 2: Classification of Solutions
Description 2: This section should describe the classification method for solutions that provide anonymity in LBS based on architecture and techniques used.

Section 3: Architectures to Provide Anonymity
Description 3: This section should present the different architectural approaches to providing anonymity in LBS, including non-cooperative, centralized trust third party, and peer-to-peer architectures.

Section 4: Non-cryptographic Approaches
Description 4: This section should describe non-cryptographic techniques for anonymity, such as fake location information, cloaking techniques, and obfuscation techniques.

Section 5: Cryptographic Approaches
Description 5: This section should introduce cryptographic methods to ensure anonymity, including blind signatures, mix nets, and oblivious transfer.

Section 6: Proposed Solutions Using Non-cryptographic Approach
Description 6: This section should elaborate on specific solutions that use non-cryptographic approaches to enhance anonymity in LBS.

Section 7: Spatial Cloaking
Description 7: This section should detail the spatial cloaking technique and its sub-categories based on the architectural approach used.

Section 8: Obfuscation Techniques
Description 8: This section should explain solutions that use obfuscation techniques to provide anonymity by introducing perturbations to location data.

Section 9: Blind Signatures
Description 9: This section should discuss solutions that use blind signature schemes to achieve anonymity in LBS.

Section 10: Mix Nets
Description 10: This section should focus on the role of mix nets in providing anonymous communication for LBS.

Section 11: Oblivious Transfer
Description 11: This section should describe how oblivious transfer techniques are used to protect user location privacy.

Section 12: Conclusions
Description 12: This section should summarize the need for new models to address emerging threats and propose a combination of various techniques to enhance user privacy in LBS.