Securely solving privacy preserving minimum spanning tree algorithms in semi-honest model. (28th May 2020)

• Record Type: Journal Article
• Authors: Rao, C.H. Koteswara; Singh, Kunwar
• Is Part Of: International journal of ad hoc and ubiquitous computing. Volume 34:Number 1(2020)
• Page Start: 1
• Page End: 10
• Publication Date: 2020-05-28
• Subjects: secure multiparty computation -- privacy -- arithmetic block-box -- ABB -- minimum spanning tree -- MST -- secure two-party computation -- 2PC; Ubiquitous computing -- Periodicals; Embedded computer systems -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Wireless communication systems -- Periodicals; Computer architecture -- Periodicals; 004.2
• Languages: English
• ISSNs: 1743-8225

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.