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 Journal of Foundations of Computer Science

Yao’s Millionaires’ Problem and Public-Key Encryption Without Computational Assumptions

Dima Yu. Grigoriev, László B. Kish, Vladimir Shpilrain

Published Jun 1, 2017• 9 citations
Publisher

Abstract

We offer efficient and practical solutions of Yao’s millionaires’ problem without using any one-way functions. Some of the solutions involve physical principles, while others are purely mathematical. One of our solutions (based on physical principles) yields a public-key encryption protocol secure against (passive) computationally unbounded adversary. In that protocol, the legitimate parties are not assumed to be computationally unbounded.

DOI
10.1142/s012905411750023x

Related papers

YAO'S MILLIONAIRES' PROBLEM AND DECOY-BASED PUBLIC KEY ENCRYPTION BY CLASSICAL PHYSICS

Dima Yu. Grigoriev, Vladimir Shpilrain

We use various laws of classical physics to offer several solutions of Yao's millionaires' problem without using any one-way functions. We also describe several informationally secure public key encryption protocols, i.e., protocols secure against passive computationally unbounded adversary. This introduces a new paradigm of decoy-based cryptography, as opposed to “traditional” complexity-based cryptography. In particular, our protocols do not employ any one-way functions.

arXiv:1312.1160•International Journal of Foundations of Computer Science•Jun 1, 2014•10 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

Secure information transmission based on physical principles

Dima Yu. Grigoriev, Vladimir Shpilrain

Abstract. We employ physical properties of the real world to design a protocol for secure information transmission where one of the parties is able to transmit secret information to another party over an insecure channel, without any prior secret arrangements between the parties. The distinctive feature of this protocol, compared to all known public-key cryptographic protocols, is that neither party uses a one-way function. In particular, our protocol is secure against (passive) computationally unbounded adversary. 1

•Jan 1, 2013•0 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

Some Efficient Solutions to Yao's Millionaire Problem

Ashish Kumar, Anupam Gupta

We present three simple and efficient protocol constructions to solve Yao's Millionaire Problem when the parties involved are non-colluding and semi-honest. The first construction uses a partially homomorphic Encryption Scheme and is a 4-round scheme using 2 encryptions, 2 homomorphic circuit evaluations (subtraction and XOR) and a single decryption. The second construction uses an untrusted third party and achieves a communication overhead linear in input bit-size with the help of an order preserving function.Moreover, the second construction does not require an apriori input bound and can work on inputs of different bit-sizes. The third construction does not use a third party and, even though, it has a quadratic communication overhead, it is a fairly simple construction.

arXiv:1310.8063•Oct 30, 2013•5 citations

Symmetric Encryption Solutions to Millionaire's Problem and Its Extension

Shundong Li, Dai Yiqi, Wang Daoshun +1 more

Millionaire's problem is the base of secure multiparty computation, and its solutions have become basic blocks of many secure multi-party computation solutions. Unfortunately, most solutions to millionaire's problem are based on public key cryptography, and thus are inefficient. Furthermore, all solutions are designed to solve millionaire's problem for natural number case to privately determine which natural number is larger. If the numbers are real, these solutions do not directly work. In this paper, we first propose a symmetric key cryptographic solution to millionaire's problem for natural numbers case, and then generalize it to the case of real numbers, that is to privately determine which real number is larger. We further prove, by simulation paradigm, that these solutions are private. These solutions are really efficient.

International Conference on Digital Information Management•Apr 1, 2007•4 citations
We offer efficient and practical solutions of Yao’s millionaires’ problem without using any one-way functions. Some of the solutions involve physical principles, while others are purely mathematical. One of our solutions (based on physical principles) yields a public-key encryption protocol secure against (passive) computationally unbounded adversary. In that protocol, the legitimate parties are not assumed to be computationally unbounded.
Abstract. We employ physical properties of the real world to design a protocol for secure information transmission where one of the parties is able to transmit secret information to another party over an insecure channel, without any prior secret arrangements between the parties. The distinctive feature of this protocol, compared to all known public-key cryptographic protocols, is that neither party uses a one-way function. In particular, our protocol is secure against (passive) computationally unbounded adversary. 1
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.
We present three simple and efficient protocol constructions to solve Yao's Millionaire Problem when the parties involved are non-colluding and semi-honest. The first construction uses a partially homomorphic Encryption Scheme and is a 4-round scheme using 2 encryptions, 2 homomorphic circuit evaluations (subtraction and XOR) and a single decryption. The second construction uses an untrusted third party and achieves a communication overhead linear in input bit-size with the help of an order preserving function.Moreover, the second construction does not require an apriori input bound and can work on inputs of different bit-sizes. The third construction does not use a third party and, even though, it has a quadratic communication overhead, it is a fairly simple construction.
Millionaire's problem is the base of secure multiparty computation, and its solutions have become basic blocks of many secure multi-party computation solutions. Unfortunately, most solutions to millionaire's problem are based on public key cryptography, and thus are inefficient. Furthermore, all solutions are designed to solve millionaire's problem for natural number case to privately determine which natural number is larger. If the numbers are real, these solutions do not directly work. In this paper, we first propose a symmetric key cryptographic solution to millionaire's problem for natural numbers case, and then generalize it to the case of real numbers, that is to privately determine which real number is larger. We further prove, by simulation paradigm, that these solutions are private. These solutions are really efficient.