Cryptology ePrint Archive: Report 2019/695

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

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

Abstract: 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.

Category / Keywords: cryptographic protocols / sorting; secret sharing; three-party computation; honest majority;

Date: received 12 Jun 2019

Contact author: kikuchi_ryo at fw ipsj or jp

Available format(s): PDF | BibTeX Citation

Version: 20190612:185831 (All versions of this report)

Short URL: ia.cr/2019/695


[ Cryptology ePrint archive ]