Paper 2014/121 Original: eprint.iacr.org/2014/121 ↗

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

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.