Paper 2019/695

An Efficient Secure Three-Party Sorting Protocol with an Honest Majority

Koji Chida, Koki Hamada, Dai Ikarashi, Ryo Kikuchi, Naoto Kiribuchi, and Benny Pinkas


We present a novel three-party sorting protocol secure against passive adversaries in the honest majority setting. The protocol can be easily combined with other secure protocols which work on shared data, and thus enable different data analysis tasks, such as data deduplication, set intersection, and computing percentiles. The new sorting protocol is based on radix sort. It is asymptotically better compared to previous sorting protocols since it does not need to shuffle the entire length of the items after each comparison step. We further improve the concrete efficiency by using not only optimizations but also novel protocols, which are independent of interest. We implemented our sorting protocol with those optimizations and protocols. Our experiments show that our implementation is concretely fast. For example, sorting one million $20$-bit items takes 4.6 seconds in 1G connection. It enables a new set of applications on large-scale datasets since the known implementations handle thousands of items about 10 seconds.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
sortingsecret sharingthree-party computationhonest majority
Contact author(s)
kikuchi_ryo @ fw ipsj or jp
2019-06-12: received
Short URL
Creative Commons Attribution


      author = {Koji Chida and Koki Hamada and Dai Ikarashi and Ryo Kikuchi and Naoto Kiribuchi and Benny Pinkas},
      title = {An Efficient Secure Three-Party Sorting Protocol with an Honest Majority},
      howpublished = {Cryptology ePrint Archive, Paper 2019/695},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.