Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Practically Efficient Multi-party Sorting Protocols from Comparison Sort Algorithms

Koki Hamada, Ryo Kikuchi, Dai Ikarashi, Koji Chida, Katsumi Takahashi

Published Jan 1, 2013• 81 citations
Publisher
DOI
10.1007/978-3-642-37682-5_15

Related papers

The oblivious comparison sorting protocols for secure multi-party computation

Koteswararao Ch, Kunwar Singh, Anoop Kumar

Multimedia Tools and Applications•Jan 27, 2024•0 citations

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

Koji Chida, Koki Hamada, Dai Ikarashi +3 more

•Jan 1, 2019•14 citations

Secure Multi-party Sorting Protocol Based on Distributed Oblivious Transfer

Motahareh Dehghan, Babak Sadeghiyan

In the present paper, a secure multi-party protocol for sorting the private values, without disclosing them, is presented. We extend the Yao's millionaire problem to n parties. Secure comparison and sorting the wealth of n parties using the Yao's protocol requires running it n×(n-2)/2 times. For a wealth interval of N, the complexity the Yao's protocol execution for these n parties has an order of N × n2. The Secure Multi-party Computation method is utilized to develop the protocol of secure multi-party sorting. We also employ an easy knapsack problem to distinguish the corresponding indices of different participants. Moreover, a modified version of the distributed oblivious transfer protocol is proposed to improve our proposed protocol and reduce its overall compexity. The computational and communication complexities of our protocol for secure multiparty sorting based on the distributed oblivious transfer, are both equal to n. Finally, the security of the proposed protocol against adversaries of semi-honest type is proved.

International Conference on Computer and Knowledge Engineering•Oct 29, 2020•2 citations

Secure Merge with O(n log log n) Secure Operations

Brett Hemenway, Rafail Ostrovsky

Data-oblivious algorithms are a key component of many secure computation protocols. In this work, we show that advances in secure multiparty shuffling algorithms can be used to increase the efficiency of several key cryptographic tools. The key observation is that many secure computation protocols rely heavily on secure shuffles. The best data-oblivious shuffling algorithms require O(n log n), operations, but in the two-party or multiparty setting, secure shuffling can be achieved with only O(n) communication. Leveraging the efficiency of secure multiparty shuffling, we give novel, information-theoretic algorithms that improve the efficiency of securely sorting sparse lists, secure stable compaction, and securely merging two sorted lists. Securely sorting private lists is a key component of many larger secure computation protocols. The best data-oblivious sorting algorithms for sorting a list of n elements require O(n log n) comparisons. Using black-box access to a linear-communication secure shuffle, we give a secure algorithm for sorting a list of length n with t ≪ n nonzero elements with communication O(t log² n + n), which beats the best oblivious algorithms when the number of nonzero elements, t, satisfies t < n/log² n. Secure compaction is the problem of removing dummy elements from a list, and is essentially equivalent to sorting on 1-bit keys. The best oblivious compaction algorithms run in O(n)-time, but they are unstable, i.e., the order of the remaining elements is not preserved. Using black-box access to a linear-communication secure shuffle, we give an information-theoretic stable compaction algorithm with only O(n) communication. Our main result is a novel secure merge protocol. The best previous algorithms for securely merging two sorted lists into a sorted whole required O(n log n) secure operations. Using black-box access to an O(n)-communication secure shuffle, we give the first multi-party secure merge algorithm that requires only O(n log log n) communication. Our algorithm takes as input n secret-shared values, and outputs a secret-sharing of the sorted list. All our algorithms are generic, i.e., they can be implemented using generic secure computations techniques and make black-box access to a secure shuffle. Our techniques extend naturally to the multiparty situation (with a constant number of parties) as well as to handle malicious adversaries without changing the asymptotic efficiency. These algorithm have applications to securely computing database joins and order statistics on private data as well as multiparty Oblivious RAM protocols.

Leibniz international proceedings in informatics•Jan 1, 2021•5 citations

Oblivious stable sorting protocol and oblivious binary search protocol for secure multi-party computation

Koteswararao Ch, Kunwar Singh, Anoop Kumar

Multi-party computation (MPC) sorting and searching protocols are frequently used in different databases with varied applications, as in cooperative intrusion detection systems, private computation of set intersection and oblivious RAM. Ivan Damgard et al. have proposed two techniques i.e., bit-decomposition protocol and bit-wise less than protocol for MPC. These two protocols are used as building blocks and have proposed two oblivious MPC protocols. The proposed protocols are based on data-dependent algorithms such as insertion sort and binary search. The proposed multi-party sorting protocol takes the shares of the elements as input and outputs the shares of the elements in sorted order. The proposed protocol exhibits O ( 1 ) constant round complexity and O ( n log n ) communication complexity. The proposed multi-party binary search protocol takes two inputs. One is the shares of the elements in sorted order and the other one is the shares of the element to be searched. If the position of the search element exists, the protocol returns the corresponding shares, otherwise it returns shares of zero. The proposed multi-party binary search protocol exhibits O ( 1 ) round complexity and O ( n log n ) communication complexity. The proposed multi-party sorting protocol works better than the existing quicksort protocol when the input is in almost sorted order. The proposed multi-party searching protocol gives almost the same results, when compared to the general binary search algorithm.

Journal of High Speed Networks•Mar 19, 2021•1 citation

Secure Multiparty Sorting Protocols with Covert Privacy

Peeter Laud, Martin Pettai

Lecture notes in computer science•Jan 1, 2016•10 citations
In the present paper, a secure multi-party protocol for sorting the private values, without disclosing them, is presented. We extend the Yao's millionaire problem to n parties. Secure comparison and sorting the wealth of n parties using the Yao's protocol requires running it n×(n-2)/2 times. For a wealth interval of N, the complexity the Yao's protocol execution for these n parties has an order of N × n2. The Secure Multi-party Computation method is utilized to develop the protocol of secure multi-party sorting. We also employ an easy knapsack problem to distinguish the corresponding indices of different participants. Moreover, a modified version of the distributed oblivious transfer protocol is proposed to improve our proposed protocol and reduce its overall compexity. The computational and communication complexities of our protocol for secure multiparty sorting based on the distributed oblivious transfer, are both equal to n. Finally, the security of the proposed protocol against adversaries of semi-honest type is proved.
Data-oblivious algorithms are a key component of many secure computation protocols. In this work, we show that advances in secure multiparty shuffling algorithms can be used to increase the efficiency of several key cryptographic tools. The key observation is that many secure computation protocols rely heavily on secure shuffles. The best data-oblivious shuffling algorithms require O(n log n), operations, but in the two-party or multiparty setting, secure shuffling can be achieved with only O(n) communication. Leveraging the efficiency of secure multiparty shuffling, we give novel, information-theoretic algorithms that improve the efficiency of securely sorting sparse lists, secure stable compaction, and securely merging two sorted lists. Securely sorting private lists is a key component of many larger secure computation protocols. The best data-oblivious sorting algorithms for sorting a list of n elements require O(n log n) comparisons. Using black-box access to a linear-communication secure shuffle, we give a secure algorithm for sorting a list of length n with t ≪ n nonzero elements with communication O(t log² n + n), which beats the best oblivious algorithms when the number of nonzero elements, t, satisfies t < n/log² n. Secure compaction is the problem of removing dummy elements from a list, and is essentially equivalent to sorting on 1-bit keys. The best oblivious compaction algorithms run in O(n)-time, but they are unstable, i.e., the order of the remaining elements is not preserved. Using black-box access to a linear-communication secure shuffle, we give an information-theoretic stable compaction algorithm with only O(n) communication. Our main result is a novel secure merge protocol. The best previous algorithms for securely merging two sorted lists into a sorted whole required O(n log n) secure operations. Using black-box access to an O(n)-communication secure shuffle, we give the first multi-party secure merge algorithm that requires only O(n log log n) communication. Our algorithm takes as input n secret-shared values, and outputs a secret-sharing of the sorted list. All our algorithms are generic, i.e., they can be implemented using generic secure computations techniques and make black-box access to a secure shuffle. Our techniques extend naturally to the multiparty situation (with a constant number of parties) as well as to handle malicious adversaries without changing the asymptotic efficiency. These algorithm have applications to securely computing database joins and order statistics on private data as well as multiparty Oblivious RAM protocols.
Multi-party computation (MPC) sorting and searching protocols are frequently used in different databases with varied applications, as in cooperative intrusion detection systems, private computation of set intersection and oblivious RAM. Ivan Damgard et al. have proposed two techniques i.e., bit-decomposition protocol and bit-wise less than protocol for MPC. These two protocols are used as building blocks and have proposed two oblivious MPC protocols. The proposed protocols are based on data-dependent algorithms such as insertion sort and binary search. The proposed multi-party sorting protocol takes the shares of the elements as input and outputs the shares of the elements in sorted order. The proposed protocol exhibits O ( 1 ) constant round complexity and O ( n log n ) communication complexity. The proposed multi-party binary search protocol takes two inputs. One is the shares of the elements in sorted order and the other one is the shares of the element to be searched. If the position of the search element exists, the protocol returns the corresponding shares, otherwise it returns shares of zero. The proposed multi-party binary search protocol exhibits O ( 1 ) round complexity and O ( n log n ) communication complexity. The proposed multi-party sorting protocol works better than the existing quicksort protocol when the input is in almost sorted order. The proposed multi-party searching protocol gives almost the same results, when compared to the general binary search algorithm.