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

International Conference on Computer and Knowledge Engineering

Secure Multi-party Sorting Protocol Based on Distributed Oblivious Transfer

Motahareh Dehghan, Babak Sadeghiyan

Published Oct 29, 2020• 2 citations
Publisher

Abstract

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.

DOI
10.1109/iccke50421.2020.9303630

Related papers

An Efficient Secure Generalized Comparison Protocol

Motahareh Dehghan, Babak Sadeghiyan

In this paper, we present a protocol for generalized secure comparison problem. Yao's millionaire problem is for comparing the wealth of two parties by preserving their privacy. If$n$parties want to compare their wealth by using Yao's protocol, it should be run$n(n-1)$2 times; if their wealth interval is as large as N, the complexity of Yao's protocol for$n$parties is in order of N.$\mathbf{n}^{2}, \mathbf{i}.\mathbf{e}$.$\mathbf{O}\ (\mathbf{N}.\mathbf{n}^{2})$. In this paper, we present a generalized secure comparison protocol, which need not to be run by every two parties separately. We use an easy knapsack problem for distinguishing parties' indices. Our protocol computation and communication complexities are bounded by 0 (n).

Iranian Conference on Electrical Engineering•May 1, 2018•5 citations

Secure multi-party computation solution to Yao's millionaires' problem based on set-inclusion

Shundong Li, Dai Yiqi, You Qi-you

Secure multi-party computation is a focus of international cryptography in recent years. Protocols for Yao's millionaires' problem have become an important building block of many secure multi-party computation protocols. Their efficiency are crucial to the efficiency of many secure multi-party computation protocols. Unfortunately, known protocols for Yao's millionaries' problem have high computational complexity or communication complexity. In this study, based on the 1-out of-m oblivious transfer and set-inclusion problem, we propose a new protocol to solve this problem. This new protocol is very efficient in terms of both computational and communication complexities. Its privacy-preserving property is also proved by simulation patadigm which is generally accepted in the study of secure multi-party computation. We also compare the information leakage of our new protocol and the known protocols.

Progress in Natural Science Materials International•Sep 1, 2005•4 citations

Improved Protocol of Yao’s Millionaires Problem

Huiqiang Li, Zhengtao Jiang, Ting Yu +1 more

Secure multi-party computation is a hot research topic in cryptography in recent years, and has become an important research direction in cryptography. This paper studies the millionaires’ problem in secure multi-party computation, and its essence is a comparison issue about the size of two encrypted data. Yao offered a solution to the millionaires’ problem, but his protocol can’t accurately compare two numbers. We improved Yao’s protocol and proposed two generic protocols to solve the millionaires’ problem. Our first protocol has one more round of communication between participants than Yao’s, but our protocol can accurately compare the size of two numbers. The second protocol improved the first protocol, and only one round of communication is needed to get accurate comparison results. Finally, we realized the second protocol based on RSA encryption algorithm, and analyze the security under the semi-honest model.

IEEE/ACIS International Conference on Computer and Information Science (ICIS)•Jun 26, 2022•2 citations

A Study of Secure Multi-party Ranking Problem

Wen Liu, Shoushan Luo, Ping Chen

In this paper, we study a secure multi-party ranking problem: there are n parties, P1, P2, ... , Pn. Each party Pihas a secret input miisin {1, 2, ... ,N}. He wants to get the order of miin the ascending ranking sequence of the n parties' inputs, while not leaking the value of mi. This problem extends the famous Yao's millionaires' problem form two parties to n parties and is a multi-party Yao's Millionaires' problem. We propose a protocol for solving the secure multi-party ranking problem, using the encoding scheme and the El Gamal cryptosystem. We also prove the correctness and the security of our solution in the semi-honest model. The solution of secure multi-party ranking problem can make new-style electronic transactions, such as private bidding and auction, secret online transaction and so on, become better security.

ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD)•Jul 1, 2007•23 citations

An Efficient Solution to Yao's Millionaires' Problem

You Qi-you

AbstrcatThe protocols for Yao's Millionaires' problem have been building blocks of solutions to many secure multi-party computation problems.But known solutions are not efficient enough and thus affect the efficiency of many secure multi-party computation protocols.In this paper,we construct a new efficient solution to millionaires' problem based on length function and oblivious transfer.Compared with known solutions,our new solution has much less computational complexity.

Dianzi xuebao•Jan 1, 2005•7 citations

A two-party quantum private comparison of equality protocol with better performance in resisting outside attack

Xiao Feng, Zhe Zhang, Qing Wu +4 more

Private Comparison (PC) is an extension of Yao's millionaire problem: two millionaires want to know if their wealth is equal, but they don't want to reveal their specific wealth. In classical cryptography, this problem has been well studied. However, the security issues of these protocols are based on computational complexity assumptions, which means they cannot resist powerful quantum computing. In this paper, a quantum private comparison of equality with better performance in resisting outside attack is proposed based on two parties. Compared with the previous protocol, our protocol greatly reduce the total probability of obtaining the wrong result. And it also can compare successfully even if the two hash value string are short and close. Meanwhile, our protocol can be implemented easily without using entanglement, joint measurements and quantum memory and so on. Finally, we show that our protocol can be secure against the attacks from both the outside eavesdroppers and the inside participants.

Journal of Physics Conference Series•Mar 1, 2019•0 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.
In this paper, we present a protocol for generalized secure comparison problem. Yao's millionaire problem is for comparing the wealth of two parties by preserving their privacy. Ifnnnparties want to compare their wealth by using Yao's protocol, it should be run$n(n-1)2times;iftheirwealthintervalisaslargeasN,thecomplexityofYao′sprotocolfor2 times; if their wealth interval is as large as N, the complexity of Yao's protocol for2times;iftheirwealthintervalisaslargeasN,thecomplexityofYao′sprotocolfornpartiesisinorderofN.parties is in order of N.partiesisinorderofN.\mathbf{n}^{2}, \mathbf{i}.\mathbf{e}...\mathbf{O}\ (\mathbf{N}.\mathbf{n}^{2})$. In this paper, we present a generalized secure comparison protocol, which need not to be run by every two parties separately. We use an easy knapsack problem for distinguishing parties' indices. Our protocol computation and communication complexities are bounded by 0 (n).
Secure multi-party computation is a focus of international cryptography in recent years. Protocols for Yao's millionaires' problem have become an important building block of many secure multi-party computation protocols. Their efficiency are crucial to the efficiency of many secure multi-party computation protocols. Unfortunately, known protocols for Yao's millionaries' problem have high computational complexity or communication complexity. In this study, based on the 1-out of-m oblivious transfer and set-inclusion problem, we propose a new protocol to solve this problem. This new protocol is very efficient in terms of both computational and communication complexities. Its privacy-preserving property is also proved by simulation patadigm which is generally accepted in the study of secure multi-party computation. We also compare the information leakage of our new protocol and the known protocols.
Secure multi-party computation is a hot research topic in cryptography in recent years, and has become an important research direction in cryptography. This paper studies the millionaires’ problem in secure multi-party computation, and its essence is a comparison issue about the size of two encrypted data. Yao offered a solution to the millionaires’ problem, but his protocol can’t accurately compare two numbers. We improved Yao’s protocol and proposed two generic protocols to solve the millionaires’ problem. Our first protocol has one more round of communication between participants than Yao’s, but our protocol can accurately compare the size of two numbers. The second protocol improved the first protocol, and only one round of communication is needed to get accurate comparison results. Finally, we realized the second protocol based on RSA encryption algorithm, and analyze the security under the semi-honest model.
In this paper, we study a secure multi-party ranking problem: there are n parties, P1, P2, ... , Pn. Each party Pihas a secret input miisin {1, 2, ... ,N}. He wants to get the order of miin the ascending ranking sequence of the n parties' inputs, while not leaking the value of mi. This problem extends the famous Yao's millionaires' problem form two parties to n parties and is a multi-party Yao's Millionaires' problem. We propose a protocol for solving the secure multi-party ranking problem, using the encoding scheme and the El Gamal cryptosystem. We also prove the correctness and the security of our solution in the semi-honest model. The solution of secure multi-party ranking problem can make new-style electronic transactions, such as private bidding and auction, secret online transaction and so on, become better security.
Private Comparison (PC) is an extension of Yao's millionaire problem: two millionaires want to know if their wealth is equal, but they don't want to reveal their specific wealth. In classical cryptography, this problem has been well studied. However, the security issues of these protocols are based on computational complexity assumptions, which means they cannot resist powerful quantum computing. In this paper, a quantum private comparison of equality with better performance in resisting outside attack is proposed based on two parties. Compared with the previous protocol, our protocol greatly reduce the total probability of obtaining the wrong result. And it also can compare successfully even if the two hash value string are short and close. Meanwhile, our protocol can be implemented easily without using entanglement, joint measurements and quantum memory and so on. Finally, we show that our protocol can be secure against the attacks from both the outside eavesdroppers and the inside participants.