User-Defined Privacy Grid System for Continuous Location-Based Services

User-Defined Privacy Grid System for Continuous Location-Based Services


Location-based services (LBS) require users to continuously report their location to a potentially untrusted server to obtain services based on their location, which can expose them to privacy risks. Unfortunately, existing privacy-preserving techniques for LBS have several limitations, such as requiring a fully-trusted third party, offering limited privacy guarantees and incurring high communication overhead. In this paper, we propose a user-defined privacy grid system called dynamic grid system (DGS); the first holistic system that fulfills four essential requirements for privacy-preserving snapshot and continuous LBS. (1) The system only requires a semi-trusted third party, responsible for carrying out simple matching operations correctly. This semi-trusted third party does not have any information about a user’s location. (2) Secure snapshot and continuous location privacy is guaranteed under our defined adversary models. (3) The communication cost for the user does not depend on the user’s desired privacy level, it only depends on the number of relevant points of interest in the vicinity of the user. (4) Although we only focus on range and k-nearest-neighbor queries in this work, our system can be easily extended to support other spatial queries without changing the algorithms run by the semi-trusted third party and the database server, provided the required search area of a spatial query can be abstracted into spatial regions. Experimental results show that our DGS is more efficient than the state-of-the-art privacy-preserving technique for continuous LBS.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):


  • Spatial cloaking techniques have been widely used to preserve user location privacy in LBS. Most of the existing spatial cloaking techniques rely on a fully-trusted third party (TTP), usually termed location anonymizer that is required between the user and the service provider.
  • When a user subscribes to LBS, the location anonymizer will blur the user’s exact location into a cloaked area such that the cloaked area includes at least k – 1 other users to satisfy k-anonymity.
  • In a system with such regional location privacy it is difficult for the user to specify personalized privacy requirements. The feeling based approach alleviates this issue by finding a cloaked area based on the number of its visitors that is at least as popular as the user’s specified public region. Although some spatial clocking techniques can be applied to peer-to-peer environments, these techniques still rely on the k-anonymity privacy requirement and can only achieve regional location privacy.
  • Furthermore, these techniques require users to trust each other, as they have to reveal their locations to other peers and rely on other peers’ locations to blur their locations, another distributed method was proposed that does not require users to trust each other, but it still uses multiple TTPs.
  • Another family of algorithms uses incremental nearest neighbor queries, where a query starts at an “anchor” location which is different from the real location of a user and iteratively retrieves more points of interest until the query is satisfied. While it does not require a trusted third party, the approximate location of a user can still be learned; hence only regional location privacy is achieved.


  • The TTP model has four major drawbacks.
  • It is difficult to find a third party that can be fully trusted.
  • All users need to continuously update their locations with the location anonymizer, even when they are not subscribed to any LBS, so that the location anonymizer has enough information to compute cloaked areas.
  • Because the location anonymizer stores the exact location information of all users, compromising the location anonymizer exposes their locations.
  • k-anonymity typically reveals the approximate location of a user and the location privacy depends on the user distribution.


  • In this paper, we propose a user-defined privacy grid system called dynamic grid system (DGS) to provide privacy-preserving snapshot and continuous
  • The main idea is to place a semi trusted third party, termed query server (QS), between the user and the service provider (SP). QS only needs to be semi-trusted because it will not collect/store or even have access to any user location information.
  • Semi-trusted in this context means that while QS will try to determine the location of a user, it still correctly carries out the simple matching operations required in the protocol, i.e., it does not modify or drop messages or create new messages. An untrusted QS would arbitrarily modify and drop messages as well as inject fake messages, which is why our system depends on a semi-trusted
  • The main idea of our DGS. In DGS, a querying user first determines a query area, where the user is comfortable to reveal the fact that she is somewhere within this query area. The query area is divided into equal-sized grid cells based on the dynamic grid structure specified by the user. Then, the user encrypts a query that includes the information of the query area and the dynamic grid structure, and encrypts the identity of each grid cell intersecting the required search area of the spatial query to produce a set of encrypted identifiers.
  • Next, the user sends a request including (1) the encrypted query and (2) the encrypted identifiers to QS, which is a semi-trusted party located between the user and SP. QS stores the encrypted identifiers and forwards he encrypted query to SP specified by the user. SP decrypts the query and selects the POIs within the query area from its database.


  • For each selected POI, SP encrypts its information, using the dynamic grid structure specified by the user to find a grid cell covering the POI, and encrypts the cell identity to produce the encrypted identifier for that POI.
  • The encrypted POIs with their corresponding encrypted identifiers are returned to QS. QS stores the set of encrypted POIs and only returns to the user a subset of encrypted POIs whose corresponding identifiers match any one of the encrypted identifiers initially sent by the user.
  • After the user receives the encrypted POIs, she decrypts them to get their exact locations and computes a query answer.


user d



  • System :         Pentium IV 2.4 GHz.
  • Hard Disk :         40 GB.
  • Floppy Drive : 44 Mb.
  • Monitor : 15 VGA Colour.
  • Mouse :
  • Ram : 512 Mb.


  • Operating system : Windows 7.
  • Coding Language : Java 1.7
  • Tool Kit : Android 2.3 ABOVE
  • IDE : Eclipse


Roman Schlegel, Member, IEEE, Chi-Yin Chow, Member, IEEE, Qiong Huang, Member, IEEE, and Duncan S. Wong, Member, IEEE, “User-Defined Privacy Grid System for Continuous Location-Based Services”, IEEE Transactions on Mobile Computing 2015.

About the Author

Leave a Reply