## 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

Short URL: ia.cr/2014/121

[ Cryptology ePrint archive ]