"Once Upon a Place": Compute Your Meeting Location Privately

Popular services such as Doodle Mobile and Tymelie are extremely useful planning tools that enable mobile-phone users to determine common meeting time(s) for events. Similar planning tools for determining optimal meeting locations, based on the location preferences of the users, are highly desirable for event planning and management in popular mobile phone applications, such as taxi sharing, route planning and mobile participatory sensing. Yet, they have received very little attention by researchers. An important, and often overlooked, facet of such planning applications is the privacy of the participating users and their preferences; users want to agree on a meeting location without necessarily revealing their location preferences to the service provider or to the other users. In this paper, we address the problem of privacy-preserving optimal meeting-location computation, especially focusing on its applicability to current mobile devices and applications. We first define the notion of privacy in such computations. Second, we model the problem of optimal meeting-location computation as a privacy-preserving k-center problem and we design two solutions; both solutions take advantage of the homomorphic properties of well-known cryptosystems by Boneh-Goh-Nissim, ElGamal and Paillier in order to perform oblivious computations. Third, we implement the proposed solutions on a testbed of the latest generation Nokia mobile devices and study their performance. Finally, we assess the utility and expectations, in terms of privacy and usability, of the proposed solutions by means of a targeted survey and user-study of mobile-phone users.