Efficient Solutions to Two-Party and Multiparty Millionaires’ Problem

Abstract EN

The millionaires’ problem is the basis of secure multiparty computation and has many applications.

Using a vectorization method and the Paillier encryption scheme, we first propose a secure two-party solution to the millionaires’ problem, which can determine x=y, xy in one execution.

Subsequently, using the vectorization and secret splitting methods, we propose an information-theoretically secure protocol to solve the multiparty millionaires’ problem (a.k.a.

secure sorting problem), and this protocol can resist collusion attacks.

We analyze the accuracy and security of our protocols in the semihonest model and compare the computational and communication complexities between the proposed protocols and the existing ones.