Efficient Cryptographic protocol for Sorting with Data-oblivious

摘要

Sorting is a primitive operation in data processing. Multiparty sorting includes a set of players $mathcal{P}$ and a list $mathcal{L}$. Each element $a_{i}in mathcal{L}$ is shared among the players $P_{J}in mathcal{P}$ (sharing is done over a prime field $mathbb{F}_{p}$). The players collaboratively execute the sorting without computing the values of the elements. The existing multiparty sorting protocols are based on compare, swap and data-oblivious with more time complexity. The existing compare protocol use either the bit-decomposition or bit-sharing and complexity of these protocols depends on size of prime. Since these protocols provide the privacy to individual elements, they need large computation. Here, we design a multiparty sorting protocol with privacy and data-obliviousness based on multiparty compare protocol. This proposed compare protocol does not use bit-decomposition or bit-sharing and complexity of this protocol depends on number of players. The proposed multiparty sorting protocol incurs constant number of multiparty message exchanges that depends only on the number of elements in the list. Ours multiparty sorting protocol sorting the elements with less time complexity.