Cryptology ePrint Archive: Report 2014/121

Oblivious Radix Sort: An Efficient Sorting Algorithm for Practical Secure Multi-party Computation

Koki Hamada and Dai Ikarashi and Koji Chida and Katsumi Takahashi

Abstract: We propose a simple and efficient sorting algorithm for secure multi-party computation (MPC). The algorithm is designed to be efficient when the number of parties and the size of the underlying field are small. For a constant number of parties and a field with a constant size, the algorithm has $O(\gm\log\gm)$ communication complexity, which is asymptotically the same as the best previous algorithm but achieves $O(1)$ round complexity, where $\gm$ is the number of items. The algorithm is constructed with the help of a new technique called ``shuffle-and-reveal.'' This technique can be seen as an analogue of the frequently used technique of ``add random number and reveal.'' The feasibility of our algorithm is demonstrated by an implementation on an MPC scheme based on Shamir's secret-sharing scheme with three parties and corruption tolerance of $1$. Our implementation sorts 1 million 32-bit word secret-shared values in 197 seconds.

Category / Keywords: cryptographic protocols / secure multi-party computation, MPC, sorting algorithm

Date: received 16 Feb 2014, last revised 28 Feb 2014

Contact author: hamada koki at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20140228:105846 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]