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 Web Information Systems and Mining (WISM)

Research on Secure Multi-party Ranking Problem and Secure Selection Problem

Cheng Chao, Yonglong Luo, Caixia Chen, Xiao-kong Zhao

Published Oct 1, 2010• 5 citations
Publisher

Abstract

In this paper, the problems of secure multi-party ranking and secure selection were studied. Two protocols were proposed. They were both based on Secure Sum protocol. Secure multi-party ranking problem is an extended problem from millionaires' problem. It can be applied to many fields, such as auctions, commercial enterprises and so on. Secure Sum protocol was used to calculate the sum of vectors. The security and complexity were analyzed in the semi-honest model. In some cases this protocol is better. This paper also studied the problem of secure selection and proposed a protocol using the protocols of Secure Sum and 1-n oblivious transfer. We analyzed the worst case and the average case.

DOI
10.1109/wism.2010.119

Related papers

Research on the Problem of Secure Multi-party Ranking Under Semi-honest Model

Bo Wu

Secure multi-party ranking is a problem generalized from the millionaires' problem,which can be used by n people to know about their secrets' order among all their inputs without leaking further information.Through the study on millionaires' protocol,we presented a secure two-party ranking protocol under semi-honest model based on homomorphic encryption.Then we generalized it to secure multi-party ranking,and we presented two algorithms whose efficiency are both improved.Finally,we gave a secure multi-party ranking protocol based on fuzzy nearness degree,and we analyzed the efficiency and security of these protocols.

Dianzi xuebao•Jan 1, 2008•3 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•24 citations

Research of quantum secure multi-party ranking protocol

Liu Wen, Yongbin Wang

Secure multi-party ranking problem is used to rank n private integers without leaking further information. It is an extended problem of secure two-party comparing problem. A secure multi-party quantum ranking protocol in semi-honest model is presented based on the a quantum implicit module n+1 addition. The security for multi-parties of the protocol is analyzed.

Acta Physica Sinica•Jan 1, 2011•2 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

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

Improvement and extension of secure vector dominance protocol

Zhengtao Jiang, Ting Yu, Huiqiang Li +1 more

The millionaire’s problem is the origin of secure multi-party computation. This problem has always been the focus of scholars' research, and it is also the design basis and important part of other secure multi-party computation protocols. An in-depth study of the millionaires’ problem is of great significance to promote the further development of secure multi-party computation. Based on millionaires’ problem and secure vector dominance protocol, we propose an improved protocol and an extended protocol. The improved protocol solves the problem of coarse granularity when comparing elements in the original protocol, and can realize that two parties can compare the relationships of greater than, equal to or less than between their elements by executing the protocol once. The improved protocol and the extended protocol are further applied to solve the problem of finding the cardinality of the intersection of the two-party sets in two cases. In addition, based on the integer division problem, we give a method to privately evaluate the greatest common factor of two integers.

International Conference on Computer Information Science and Application Technology (CISAT)•Oct 20, 2022•0 citations
In this paper, the problems of secure multi-party ranking and secure selection were studied. Two protocols were proposed. They were both based on Secure Sum protocol. Secure multi-party ranking problem is an extended problem from millionaires' problem. It can be applied to many fields, such as auctions, commercial enterprises and so on. Secure Sum protocol was used to calculate the sum of vectors. The security and complexity were analyzed in the semi-honest model. In some cases this protocol is better. This paper also studied the problem of secure selection and proposed a protocol using the protocols of Secure Sum and 1-n oblivious transfer. We analyzed the worst case and the average case.
Secure multi-party ranking is a problem generalized from the millionaires' problem,which can be used by n people to know about their secrets' order among all their inputs without leaking further information.Through the study on millionaires' protocol,we presented a secure two-party ranking protocol under semi-honest model based on homomorphic encryption.Then we generalized it to secure multi-party ranking,and we presented two algorithms whose efficiency are both improved.Finally,we gave a secure multi-party ranking protocol based on fuzzy nearness degree,and we analyzed the efficiency and security of these protocols.
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.
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 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.
The millionaire’s problem is the origin of secure multi-party computation. This problem has always been the focus of scholars' research, and it is also the design basis and important part of other secure multi-party computation protocols. An in-depth study of the millionaires’ problem is of great significance to promote the further development of secure multi-party computation. Based on millionaires’ problem and secure vector dominance protocol, we propose an improved protocol and an extended protocol. The improved protocol solves the problem of coarse granularity when comparing elements in the original protocol, and can realize that two parties can compare the relationships of greater than, equal to or less than between their elements by executing the protocol once. The improved protocol and the extended protocol are further applied to solve the problem of finding the cardinality of the intersection of the two-party sets in two cases. In addition, based on the integer division problem, we give a method to privately evaluate the greatest common factor of two integers.