Privacy preserving shortest path routing with an application to navigation

Mobile navigation is a frequently used application, especially with the increasing proliferation of online geographical data. However, the origin and destination are often private information closely tied to a user's personal life. Sharing those with an online map provider greatly increases the chance of the user being profiled. Contrary to existing location privacy problems, the origin and the destination are essential for finding the shortest path in a realtime traffic setting. In this paper, we show that the problem can be solved with Private Information Retrieval (PIR) techniques without disclosing the origin or the destination. We analyze the cost associated with this approach and propose a practical solution with the assumption of a semi-honest third party to improve the efficiency. The proposed practical solution only introduces encryption overhead over the plain scenario where the path is returned by knowing the origin and destination.