Paper Info
Title
Practically efficient multi-party sorting protocols from comparison sort algorithms
Abstract
Sorting is one of the most important primitives in various systems, for example, database systems, since it is often the dominant operation in the running time of an entire system. Therefore, there is a long list of work on improving its efficiency. It is also true in the context of secure multi-party computation (MPC), and several MPC sorting protocols have been proposed. However, all existing MPC sorting protocols are based on less efficient sorting algorithms, and the resultant protocols are also inefficient. This is because only a method for converting data-oblivious algorithms to corresponding MPC protocols is known, despite the fact that most efficient sorting algorithms such as quicksort and merge sort are not data-oblivious. We propose a simple and general approach of converting non-data-oblivious comparison sort algorithms, which include the above algorithms, into corresponding MPC protocols. We then construct an MPC sorting protocol from the well known efficient sorting algorithm, quicksort, with our approach. The resultant protocol is practically efficient since it significantly improved the running time compared to existing protocols in experiments.
Year
DOI
Venue
2012
10.1007/978-3-642-37682-5_15
ICISC
Keywords
Field
DocType
dominant operation,data-oblivious algorithm,resultant protocol,existing mpc,database system,efficient multi-party,general approach,entire system,non-data-oblivious comparison sort algorithm,corresponding mpc protocol,important primitive,comparison sort,secret sharing,sorting
Merge algorithm,Comparison sort,Counting sort,Computer science,Parallel computing,Insertion sort,Algorithm,Quicksort,Sorting,Theoretical computer science,External sorting,Sorting algorithm
Conference
Citations 
PageRank 
References 
14
0.58
27
Authors
5
Name
Order
Citations
PageRank
Koki Hamada16110.92
Ryo Kikuchi2469.37
Dai Ikarashi3276.33
Koji Chida47312.49
Katsumi Takahashi5255.02