Privacy-Preserving Location Sharing Services for Social Networks

Privacy-Preserving Location Sharing Services for Social Networks


A common functionality of many location-based social networking applications is a location sharing service that allows a group of friends to share their locations. With a potentially untrusted server, such a location sharing service may threaten the privacy of users. Existing solutions for Privacy-Preserving Location Sharing Services (PPLSS) require a trusted third party that has access to the exact location of all users in the system or rely on expensive algorithms or protocols in terms of computational or communication overhead. Other solutions can only provide approximate query answers. To overcome these limitations, we propose a new encryption notion, called Order-Retrievable Encryption (ORE), for PPLSS for social networking applications. The distinguishing characteristics of our PPLSS are that it (1) allows a group of friends to share their exact locations without the need of any third party or leaking any location information to any server or users outside the group, (2) achieves low computational and communication cost by allowing users to receive the exact location of their friends without requiring any direct communication between users or multiple rounds of communication between a user and a server, (3) provides efficient query processing by designing an index structure for our ORE scheme, (4) supports dynamic location updates, and (5) provides personalized privacy protection within a group of friends by specifying a maximum distance where a user is willing to be located by his/her friends. Experimental results show that the computational and communication cost of our PPLSS is much better than the state-of-the-art solution.



  • Existing location-based social networking systems with location sharing services rely on a central server which receives location information from all users in the system.
  • Existing privacy-preserving location sharing schemes aim to protect the user location privacy against the central server, but they still allow the server to provide the user with the necessary services.
  • However, in some existing schemes, the central server still knows the user’s approximate location. Other schemes require several messages to be exchanged not only between the user and the central server but also directly between the user and the user’s friends, increasing the communication cost and making those schemes less practical.


  • The problem with this approach is that the central server can generate a detailed movement profile of each user (e.g., the location, time and frequency of each place which has been visited by each user) and that raises privacy concerns.
  • Other schemes only return approximate results, making them less useful.


  • In this paper, we propose a new encryption notion, called Order-Retrievable Encryption (ORE); a new cryptographic protocol that realizes our Privacy-Preserving Location Sharing Services (PPLSS) for social networking systems. In particular, our ORE scheme enables users to browse their friends’ exact locations within a certain distance without revealing any information about their locations to any other users or a social networking service provider.
  • The framework of our PPLSS consists of a database server (which is maintained by the social networking service provider) and users. The users send their location information in encrypted form to the database server according to our ORE scheme.
  • When a user wants to locate his/her friends in the vicinity, the user logs onto the social networking system, sends a location query (e.g., “Q1: Send me the location of my friends within 2 km of my current location”) to the database server, and obtains the requested location information in encrypted form based on our ORE scheme. The user then recovers the actual location of his/her friends from the encrypted information returned by the database server.


  • Secure location privacy. PPLSS does not disclose any location information of its users to a central server or an eavesdropper, not even an approximate location, and does not require any third party.
  • Low computational and communication cost. It allows a user to receive the exact location information of his/her friends without requiring direct communication between users or multiple rounds of communication between a user and a server.
  • Index structure.We design an index structure for our ORE scheme to index encrypted locations of a group of friends to improve the efficiency of location query processing.
  • Efficient data updates. Our scheme supports highly dynamic location updates from individual users efficiently.
  • Personalized privacy within a group of friends. Each user is able to specify a maximum distance defining a personalized privacy region so that only those friends who are within the region can locate the user.
  • The rationale behind such personalized privacy is that users may not want to share their locations with far-away friends as it might not be practical or necessary to share their location with friends at large distances.


Privacy-Preserving Location Sharing Services


  • Mobile Users
  • Location Based Server (LBS)
  • User Query
  • Check authenticity
  • User privacy



Consider N users who move in an area split into M discrete regions/locations. The mobility of each user u is a discrete-time Markov chain on the set of regions: The probability that user u, currently in region ri, will next visit region rj is denoted by pu(rj |ri). Let πu(ri) be the probability that user u is in region ri. Each user possesses a location-aware wireless device, capable of ad hoc device-to-device communication and of connecting to the wireless infrastructure (e.g., cellular and Wi-Fi networks). 


As users move between regions, they leverage the infrastructure to submit local-search queries to LBS. The information that the LBS provides expires periodically, in the sense that it is no longer valid. Note that information expiration is not equivalent to the user accessing the LBS: A user accesses the LBS when her information has expired and she wishes to receive the most up-to-date version of it. 


A seeker, essentially a user who does not have the sought information in her buffer, first broadcasts her query to her neighbors through the wireless ad hoc interface of the device. This a local query. Each user with valid information about a region is termed informed user for that region. Users interested in getting location-specific information about a region are called information seekers of that region.


The information the LBS provides is self-verifiable, i.e., users can verify the integrity and authenticity of the server responses. This can be done in different ways; in our system, the user device verifies a digital signature of the LBS on each reply by using the LBS provider’s public key. As a result, a compromised access point or mobile device cannot degrade the experience of users by altering replies or disseminating expired information.


In essence, a subset of users in every region has to contact the LBS to get the updated information, and the rest of the users benefit from the peer-to-peer collaboration. Intuitively, the higher the proportion of hidden user queries, the higher her location privacy is.



  • System : Pentium Dual Core.
  • Hard Disk : 120 GB.
  • Monitor : 15’’ LED
  • Input Devices : Keyboard, Mouse
  • Ram : 1 GB


  • Operating system : Windows 7.
  • Coding Language : Android,JAVA
  • Toolkit : Android 2.3 ABOVE
  • IDE :         Eclipse/Android Studio


Roman Schlegel, Member, IEEE, Chi-Yin Chow, Member, IEEE, Qiong Huang, Member, IEEE, and Duncan S. Wong, Member, IEEE, “Privacy-Preserving Location Sharing Services for Social Networks”, IEEE Transactions on Services Computing, 2016.

About the Author

Leave a Reply