Efficient secure comparison in the dishonest majority model

Abstract

Secure comparison (SC) is an essential primitive in Secure Multiparty Computation (SMC) and a fundamental building block in Privacy-Preserving Data Analytics (PPDA). Although secure comparison has been studied since the introduction of SMC in the early 80s and many protocols have been proposed, there is still room for improvement, especially providing security against malicious adversaries who form the majority among the participating parties. It is not hard to develop an SC protocol secure against malicious majority based on the current state-of-the-art SPDZ framework. SPDZ is designed to work for arbitrary polynomially-bounded functionalities; it may not provide the most efficient SMC implementation for a specific task, such as SC. In this thesis, we propose a novel and efficient compiler specifically designed to convert most existing SC protocols with semi-honest security into the ones secure against the dishonest majority (malicious majority). We analyze the security of the proposed solutions using the real-ideal paradigm. Moreover, we provide computation and communication complexity analysis. Comparing to the current state-of-the-art SC protocols Rabbit and edaBits, our design offers significant performance gain. The empirical results show that the proposed solution is at least 5 and 10 times more efficient than Rabbit in run-time and communication cost respectively.