Privacy preserving route planning

Abstract

The number of location-aware mobile devices has been rising for several years. As this trend continues, these devices may be able to use their location information to provide interesting applications for their owners. Possible applications for such devices include: i) planning a route that brings the owner near a coffee shop or ii) a route that would allow the owner to intersect one of their friends' own route. The difficulty with such computations is that the owners of the devices will not want their devices to be sending their location (or future locations) to some random server to compute the functions. In this paper, we look at computing distance functions of routes in a private manner; we propose using Secure Multi-party Computation (SMC) techniques to solve these computational geometry problems. In this paper we propose protocols for three such problems: i) the distance between a point and a line segment, ii) the distance between two moving points each defined by a parametric equation (with constant velocity), and iii) the distance between two line segments.