Title: Securely solving privacy preserving minimum spanning tree algorithms in semi-honest model

Authors: C.H. Koteswara Rao; Kunwar Singh

Addresses: Department of Computer Science and Engineering, National institute of Technology, Tamil Nadu, India ' Department of Computer Science and Engineering, National institute of Technology, Tamil Nadu, India

Abstract: Yao introduced secure 2PC for the so-called millionaire's problem. It is about two millionaires Alice and Bob, interested to determine who is wealthier without revealing their values. Goldreich generalised the secure 2PC and formalised the MPC. 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. Before merging both companies want to know whether merging will benefit them or not without revealing cost function. Based on the MPC paradigm, we propose new algorithms for privacy-preserving computation of MST. We also investigate how to solve the classical MST problem with the help of ABB operations. We propose two more algorithms for solving MST in semi-honest model with secure ABB in the secretly shared data environment. Our protocols offer perfect security against semi-honest adversaries.

Keywords: secure multiparty computation; privacy; arithmetic block-box; ABB; minimum spanning tree; MST; secure two-party computation; 2PC.

DOI: 10.1504/IJAHUC.2020.107501

International Journal of Ad Hoc and Ubiquitous Computing, 2020 Vol.34 No.1, pp.1 - 10

Received: 11 Feb 2019
Accepted: 15 Aug 2019

Published online: 31 May 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article