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
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- sortingsecret sharingthree-party computationhonest majority
- Contact author(s)
- kikuchi_ryo @ fw ipsj or jp
- History
- 2019-06-12: received
- Short URL
- https://ia.cr/2019/695
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/695,
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{https://eprint.iacr.org/2019/695}},
url = {https://eprint.iacr.org/2019/695}
}
