Longitude : Centralized privacy-preserving computation of users' proximity

A "friend finder" is a Location Based Service (LBS) that informs users about the presence of participants in a geographical area. In particular, one of the functionalities of this kind of application, reveals the users that are in proximity. Several implementations of the friend finder service already exist but, to the best of our knowledge, none of them provides a satisfactory technique to protect users' privacy. While several techniques have been proposed to protect users' privacy for other types of spatial queries, these techniques are not appropriate for range queries over moving objects, like those used in friend finders. Solutions based on cryptography in decentralized architectures have been proposed, but we show that a centralized service has several advantages in terms of communication costs, in addition to support current business models. In this paper, we propose a privacy-aware centralized solution based on an efficient three-party secure computation protocol, named Longitude. The protocol allows a user to know if any of her contacts is close-by without revealing any location information to the service provider. The protocol also ensures that user-defined minimum privacy requirements with respect to the location information revealed to other buddies are satisfied. Finally, we present an extensive experimental work that shows the applicability of the proposed technique and the advantages over alternative proposals. \ua9 2009 Springer Berlin Heidelberg