Oblivious Graph Algorithms for Solving TSP and VRP Using FHE and MPC

As the world is starting to realize the necessity and potential of privacy-friendly data processing, various questions need to be answered regarding potential solutions. Especially for the developing field of fully homomorphic encryption (FHE), which aims to offer the best privacy protection at a high computational cost, there are big expectations for future applications, but the question of practicability remains a major issue. Can this technology compete with more mature and efficient technologies like multiparty computation (MPC)? Can current state-of-the-art FHE schemes and libraries be deployed in realistic applications? In this paper we attempt to gain further insights into the current status of FHE as a privacy-enhancing technology, by studying a use case related to route planning in transport and logistics. In this application, a central computing server is tasked with (obliviously) computing a short tour along various destinations (known as the traveling salesman problem, or TSP), without seeing the privacy-sensitive input data of the user, namely which destinations the user wishes to visit. We also study a generalization of this problem with multiple tours being planned, each departing from the same central depot (known as the vehicle routing problem, or VRP). Finally, we aim to assess how solutions for TSP and VRP using FHE compare to solutions using MPC.