The oblivious comparison sorting protocols for secure multi-party computation

The oblivious comparison sorting protocols for secure multi-party computation

연구 분야: Networking

학회: Multimedia Tools and Applications

Sorting data is a crucial function in many systems, including database systems, because it frequently influences total system performance due to its importance in execution time. As a result, there is a to-do list for increasing its effectiveness. This also holds true for safe multi-party computation (MPC), for which a number of sorting protocols for MPC have been put forth. In the contest of MPC some sorting protocols are proposed. MPC sorting protocols are frequently used in different databases and have many applications, for example in cooperative intrusion detection systems, private computation of set intersection, oblivious RAM, parallel and distributed environment. The existing MPC sorting protocols are based on less efficient sorting algorithms and the resultant protocols are also inefficient. This is because we currently possess a known method for transforming data-oblivious algorithms into their respective MPC protocols, even though notable efficient sorting algorithms like quick-sort and merge sort are not inherently designed to be data-oblivious. Ivan Damgard et al. proposed naive techniques bit-decomposition protocol and bit-wise less than protocol for MPC. We propose two oblivious MPC sorting protocols by considering the naive techniques. The proposed sorting protocols take input as shares of the distributed elements. The outputs are the shares of elements in sorted order. The proposed protocols have O(n n) communication complexity and O(n) constant number of rounds. The proposed protocols work better than the existing quick sort protocol, when the input is in almost sorted order.