Privacy-Preserving Minimum Spanning Tree Algorithms in Static Semi-honest Model

Abstract

In 1982, Andrew Yao introduced secure two-party computation (2PC) for the so-called millionaire’s
problem. The problem is about two millionaires Alice and Bob, interested to determine who is
wealthier without revealing their actual private property values. Goldreich generalized the secure
two-party computation and formalized the secure multi-party computation. Suppose two telephone
companies wish to merge to provide better services to end users. Each company has a cost function
for connecting any pair of houses. They want to connect every house with minimum cost in merged
company. Mathematically, given two graphs G1,G2 they want to compute MST(min(G1,G2)). Before
merging both companies they want to know whether merging will benefit them or not without reveling
cost function for any pair of houses. Based on the secure multi-party computation paradigm, we
propose new algorithms for privacy-preserving computation of minimum spanning tree. Our protocols
offers security against semi-honest adversaries.