Improvement of the protocol for millionaires’ problem

Abstract

As the basic problem that introduces the idea of secure multi-party computation (SMC), millionaires’ problem (MP) is one of the research highlights in the field of SMC. However, most of current protocols for MP are only secure in semi-honest model, which using public key cryptography schemes, and there are few secure schemes in malicious model exist security defects. Therefore, this paper analyzes the Li et al.’s protocol for MP that secure in malicious model. Firstly, we point out several behaviours that can be successfully implemented in Li et al.’s protocol. Secondly, by using the zero-knowledge proof (ZKP) for the equality of discrete logarithm (DL), cut-and-choose method etc. We propose the improved protocol and show how to detect malicious behaviours. Finally, we analyze the correctness and security against malicious behaviours of the improved protocol.