iGPS: Privacy-Preserving Geo-Proximity Services in Location-based Social Networks

The convergence of smartphone technologies and social networking utilities has opened up an entirely new application area: location-based social networking. A basic service in location- based social networks is the geo-proximity service, which alerts a mobile user when any of his/her friends is in the geographical vicinity, so as to enrich social activities such as collaborative working and information sharing. To realize such services, existing systems collect location information from mobile users for proximity computation. However, the disclosure of private location information to the service provider raises severe privacy concerns.1 For example, by knowing that a user is in a specialized clinic, an adversary may infer that the user is a disease sufferer. Therefore, there is an urgent need to develop more sophisticated location update and query techniques that can support these geo-proximity services while preserving the location privacy of mobile users.

In the proposed project, we will build on our research experience in location privacy protection to investigate privacy-preserving query and monitoring techniques for mobile geo-proximity services. In contrast to most existing research (including our own previous work), which is concerned with the location privacy of only the query issuer, a unique requirement of geo- proximity services is to protect the location privacy of mutual parties — not only for the query issuer but also for whoever serves as the query result (e.g., nearby friends). In consideration of this new mutual privacy requirement, the conventional location-cloaking-based privacy techniques suffer from several limitations. First, the location privacy is not completely protected, as the cloaking approach needs to expose coarse-grained user location information to the service provider. Second, with coarse-grained location information, the service provider is unable to resolve geo-proximity queries accurately, which impairs the service quality. Furthermore, the challenge of how to efficiently update user locations for monitoring services remains.

To address these issues, we will first identify the mutual privacy requirements for typical geo- proximity services such as distance-based proximity queries and nearest-friend queries. We need the location privacy of mobile users to be completely protected against the service provider, as well as among themselves, except when they are in proximity. Based on these privacy requirements, we will propose and develop a series of novel privacy-preserving solutions for geo-proximity query and monitoring services, including i) a dynamic-grid-overlay solution for distance-based proximity queries; ii) a secure-line-computation solution for vicinity-region-based proximity queries; iii) efficient location update and query re-evaluation strategies for monitoring proximity services; and iv) secure algorithms for nearest-friend queries without disclosing location information to any party. Finally, a prototype system will be developed to demonstrate the security, feasibility and effectiveness of the proposed solutions and algorithms.

This project is highly relevant to Hong Kong where the smartphone penetration rate (35% as of August 2011) is among the highest in the world. We believe that the research findings resulting from this project will benefit the 3G mobile market and mobile users in Hong Kong.

Remark: In Hong Kong, the funding threshold for GRF grants is higher than 4.0 (out of 5). In other words, a research proposal will NOT be granted if the average rating is not significantly higher than “Very Good”.