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(n log n) communication complexity, which is asymptotically the same as the best previous algorithm but achieves O(1) round complexity, where n 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 im-plementation sorts 1 million 32-bit word secret-shared values in 197 seconds.