Privacy Preserving Queries of Shortest Path Distances.

Consider a user with a very limited hardware and internet connection who wants to query a shortest path distance from a web service, but doesn’t want to reveal the source and destination to the server. Using state-of-the-art methods, we show that we can privately query shortest path distances in this case, if we are allowed to use three non-cooperating servers of moderate compute and communication power. We argue that this is not possible with classical shortest path algorithms. Finally, we give some experiments showing the feasibility of the approach.