Paper 2014/121

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

Koki Hamada, Dai Ikarashi, Koji Chida, and Katsumi Takahashi


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
secure multi-party computationMPCsorting algorithm
Contact author(s)
hamada koki @ lab ntt co jp
2014-02-28: revised
2014-02-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Koki Hamada and Dai Ikarashi and Koji Chida and Katsumi Takahashi},
      title = {Oblivious Radix Sort: An Efficient Sorting Algorithm for Practical Secure Multi-party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/121},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.