A Study of Secure Multi-party Ranking Problem

In this paper, we study a secure multi-party ranking problem: there are n parties, P₁, P₂, ... , P_n. Each party P_i has a secret input m_i isin {1, 2, ... ,N}. He wants to get the order of m_i in the ascending ranking sequence of the n parties´ inputs, while not leaking the value of m_i. This problem extends the famous Yao´s millionaires´ problem form two parties to n parties and is a multi-party Yao´s Millionaires´ problem. We propose a protocol for solving the secure multi-party ranking problem, using the encoding scheme and the El Gamal cryptosystem. We also prove the correctness and the security of our solution in the semi-honest model. The solution of secure multi-party ranking problem can make new-style electronic transactions, such as private bidding and auction, secret online transaction and so on, become better security.