论文标题
来自路径代数问题的平行隐私保护最短路径协议
A Parallel Privacy-Preserving Shortest Path Protocol from a Path Algebra Problem
论文作者
论文摘要
在本文中，我们为单源最短距离（SSSD）提供了一个安全的多方计算（SMC）协议，其中边缘的位置是公共的，但其长度是私有的。该协议在图形树的顶部的算术黑匣子（ABB）模型中起作用，如果图的子图具有小的分离器（例如平面图），则可以实现良好的时间复杂性；可实现的并行性明显高于在ABB之上实现的经典SSSD算法。 我们在Sharemind MPC平台之上实施协议，并在不同的网络环境上执行广泛的基准测试。我们将算法与从经典算法中挑选的基线进行比较 - 保护隐私的贝尔曼福音算法（具有公共边缘）。
In this paper, we present a secure multiparty computation (SMC) protocol for single-source shortest distances (SSSD) in undirected graphs, where the location of edges is public, but their length is private. The protocol works in the Arithmetic Black Box (ABB) model on top of the separator tree of the graph, achieving good time complexity if the subgraphs of the graph have small separators (which is the case for e.g. planar graphs); the achievable parallelism is significantly higher than that of classical SSSD algorithms implemented on top of an ABB. We implement our protocol on top of the Sharemind MPC platform, and perform extensive benchmarking over different network environments. We compare our algorithm against the baseline picked from classical algorithms - privacy-preserving Bellman-Ford algorithm (with public edges).
