FedRoad: Secure and Efficient Road Network Queries over Traffic Data Federation

Federated computing has emerged as a promising approach to address the data isolation problem, enabling multiple data owners to utilize secure multi-party computation (MPC) to collaboratively process queries while keeping the data decentralized, private, and secret. However, existing studies primarily focused on federated queries over structural data, which does not apply to non-structural road network queries prevalent in daily travel scenarios. To tackle this limitation, this paper proposes FedRoad, the first traffic data federation with secure and efficient road network shortest-path queries over it. In this context, the network topology is shared while each silo (e.g., mobility services platform) holds an individual traffic observation of edge weights (e.g., vehicle speeds), where we search the path with minimum joint weights (e.g., the least traveling time). To ensure security, we implement a secret-sharing-based MPC operator to secretly compare joint path weights and achieve a secure federated shortest-path search based on it. To improve the efficiency over road network structures, we (1) first minimize the search iterations by proposing federated shortcut indices and effective federated lower-bound estimation methods, (2) then reduce the cost in each iteration by designing a priority queue structure dedicated to minimizing the expensive MPC comparison operations. Extensive experiments demonstrate that FedRoad significantly outperforms the baselines$(100\times \text{faster})$and is practical for usage (sub-second level running time).