Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC

Shortest distance computation is a fundamental problem in graph data analysis, with critical applications in financial fraud detection, website ranking, and social network analysis. In real-world settings, however, graph data is often distributed across multiple mutually untrusted organizations, making accurate shortest path computation under strict privacy constraints a major challenge. Existing solutions face two key limitations: (1) traditional distributed algorithms lack privacy protection; and (2) secure multi-party computation (MPC)-based methods, though privacy-preserving, suffer from high computational overhead and poor scalability, restricting them to graphs with only tens of thousands of nodes. To address these challenges, we propose PrivHop, a novel algorithm that integrates 2-hop labeling with MPC in a two-phase framework. In the offline phase, PrivHop constructs an optimized boundary graph index to reduce global queries to small-scale boundary graph queries. In the online phase, it introduces a privacy-aware dynamic pruning strategy based on differential privacy to substantially reduce iteration complexity with privacy guarantees. Extensive experiments on eight real-world datasets show that PrivHop preserves privacy while scaling to million-node graphs, achieving up to 10 6 x reductions in both runtime and communication compared to state-of-the-art methods.