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

Iranian Conference on Electrical Engineering

An Efficient Secure Generalized Comparison Protocol

Motahareh Dehghan, Babak Sadeghiyan

Published May 1, 2018• 5 citations
Publisher

Abstract

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).

DOI
10.1109/icee.2018.8472437

Related papers

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 two party comparison over encrypted data

Parisa Kaghazgaran, Sadeghyan Babak

Yao's classical millionaires' problem is about securely determining whether x>y, given two input values x, y, which are held as private inputs by two parties, respectively. The output which is result of comparison becomes known to both parties. In this paper we consider a variant of comparison problem in which the inputs x, y are encrypted and the actual values are not known to the parties. Our first solution deals with single comparison; however, in many applications, we encounter situations where it is necessary to make multiple comparisons to find the maximum among several encrypted data, so we make a modification to our first protocol to solve the multiple comparisons problem. Such a secure comparison is an important building block for applications like privacy preserving data mining and secure business. Our second protocol is based on Homomorphic encryption which achieves very low communication and computational complexities. Also our protocols can be performed in constant rounds and do not use general circuit evaluation techniques so they are more efficient than circuit based ones but not general. Implementation is easy and fast.

World Congress on Information and Communication Technologies•Dec 1, 2011•10 citations

Secure Comparison Under Ideal/Real Simulation Paradigm

Chuan Zhao, Shengnan Zhao, Bo Zhang +3 more

Secure comparison problem, also known as Yao's Millionaires' problem, was introduced by Andrew Yao in 1982. It is a fundamental problem in secure multi-party computation. In this problem, two millionaires are interested in determining the richer one between them without revealing their actual wealth. Yao's millionaires' problem is a classic and fundamental problem in cryptography. The design of secure and efficient solutions to this problem provides effective building blocks for secure multi-party computation. However, only a few of the solutions in the literature have succeeded in resisting attacks of malicious adversaries, and none of these solutions has been proven secure in malicious model under ideal/real simulation paradigm. In this paper, we propose two secure solutions to Yao's millionaires' problem in the malicious model. One solution has full simulation security, and the other solution achieves onesided simulation security. Both protocols are only based on symmetric cryptography. Experimental results indicate that our protocols can securely solve Yao's millionaires' problem with high efficiency and scalability. Furthermore, our solutions show better performance than the state-of-the-art solutions in terms of complexity and security. Specifically, our solutions only require O(|U|) symmetric operations at most to achieve simulation-based security against malicious adversaries, where U denotes the universal set and |U| denotes the size of U.

IEEE Access•Jan 1, 2018•1 citation

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 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

New Protocols for Secure Equality Test and Comparison

Geoffroy Couteau

Protocols for securely comparing private values are among the most fundamental building blocks of multiparty computation. introduced by Yao under the name millionaire’s problem, they have found numerous applications in a variety of privacy-preserving protocols; however, due to their inherent non-arithmetic structure, existing construction often remain an important bottleneck in large-scale secure protocols.

•Jan 1, 2016•2 citations
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 runn(n−1)n(n-1)n(n−1)2 times; if their wealth interval is as large as N, the complexity of Yao's protocol fornnnparties is in order of N.n2,i.e\mathbf{n}^{2}, \mathbf{i}.\mathbf{e}n2,i.e.O (N.n2)\mathbf{O}\ (\mathbf{N}.\mathbf{n}^{2})O (N.n2). 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).
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.
Yao's classical millionaires' problem is about securely determining whether x>y, given two input values x, y, which are held as private inputs by two parties, respectively. The output which is result of comparison becomes known to both parties. In this paper we consider a variant of comparison problem in which the inputs x, y are encrypted and the actual values are not known to the parties. Our first solution deals with single comparison; however, in many applications, we encounter situations where it is necessary to make multiple comparisons to find the maximum among several encrypted data, so we make a modification to our first protocol to solve the multiple comparisons problem. Such a secure comparison is an important building block for applications like privacy preserving data mining and secure business. Our second protocol is based on Homomorphic encryption which achieves very low communication and computational complexities. Also our protocols can be performed in constant rounds and do not use general circuit evaluation techniques so they are more efficient than circuit based ones but not general. Implementation is easy and fast.
Secure comparison problem, also known as Yao's Millionaires' problem, was introduced by Andrew Yao in 1982. It is a fundamental problem in secure multi-party computation. In this problem, two millionaires are interested in determining the richer one between them without revealing their actual wealth. Yao's millionaires' problem is a classic and fundamental problem in cryptography. The design of secure and efficient solutions to this problem provides effective building blocks for secure multi-party computation. However, only a few of the solutions in the literature have succeeded in resisting attacks of malicious adversaries, and none of these solutions has been proven secure in malicious model under ideal/real simulation paradigm. In this paper, we propose two secure solutions to Yao's millionaires' problem in the malicious model. One solution has full simulation security, and the other solution achieves onesided simulation security. Both protocols are only based on symmetric cryptography. Experimental results indicate that our protocols can securely solve Yao's millionaires' problem with high efficiency and scalability. Furthermore, our solutions show better performance than the state-of-the-art solutions in terms of complexity and security. Specifically, our solutions only require O(|U|) symmetric operations at most to achieve simulation-based security against malicious adversaries, where U denotes the universal set and |U| denotes the size of U.
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.
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.