Paper 2025/1794

Going Faster: Privacy-Preserving Shortest paths from Start to End

Abstract

Finding shortest paths in graphs is one of the fundamental combinatorial optimization problems with numerous applications. Privacy constraints in these applications have lead to an extensive line of research on the so-called privacy-preserving (length of) shortest path problem. A Secure Multi-Party Computation (SMPC) protocol that solves this problem computes the lengths of shortest paths on a secret graph in a distributed fashion while ensuring that the graph remains secret. While many such protocols have been proposed in the past, they only compute the length of the shortest paths and not the paths themselves. In this paper, we address this shortcoming but also propose a novel adaptable protocol design that chooses between different sub-protocols for the building blocks it uses depending on input size, the network delay and bandwidth, and the security model the protocol operates in. Our protocol thus finds the run-time optimal combination of sub-protocols for a given environment. We compare the resulting adaptive protocol to a less flexible baseline protocol in an extensive evaluation using the MP-SPDZ framework, spanning multiple network and security settings. Compared to the baseline protocol, the adaptivity of our optimized path construction leads to speedups from 4% to 32% in the overall time to find the shortest path. Further, we find and fix a small leakage in two prior (length of) shortest path protocols, and report multiple observations that can be used to improve the practical runtime of other SMPC protocols.