Paper 2024/1420 Original: eprint.iacr.org/2024/1420 ↗

Privacy-Preserving Breadth-First-Search and Maximal-Flow

Abstract

We present novel Secure Multi-Party Computation (SMPC) protocols to perform Breadth-First-Searches (BFSs) and determine maximal flows on dense secret-shared graphs. In particular, we introduce a novel BFS protocol that requires only $\mathcal{O}(\log n)$ communication rounds on graphs with $n$ nodes, which is a big step from prior work that requires $\mathcal{O}(n \log n)$ rounds. This BFS protocol is then used in a maximal flow protocol based on the Edmonds-Karp algorithm, which requires $\mathcal{O}(n^3 \log n)$ rounds. We further optimize the protocol for cases where an upper bound $U$ on the capacities is publicly known by using a capacity scaling approach. This yields a new protocol which requires $\mathcal{O}(n^2 \log n \log U)$ rounds. Finally, we introduce a novel max flow protocol based on algorithms by Dinic and Tarjan with round complexity $\mathcal{O}(n^3)$. All protocols presented in this paper use SMPC primitives as a black-box, allowing our protocols to be used as building blocks in a wide range of settings and applications. We evaluate our protocols with semi-honest and malicious security in different network settings. Our logarithmic BFS protocol is up to 69 times faster than prior protocols on small graphs with less than 100 nodes, but is outperformed by protocols with lower computational complexity on graphs with thousands of nodes. Further, we find our Dinic-Tarjan protocol to be faster than the Edmonds-Karp and capacity scaling protocols in our evaluation, albeit trends indicating capacity scaling protocols to be faster on graph sizes not reached in our evaluation.