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

arXiv:1312.1160 · International Journal of Foundations of Computer Science

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

Dima Yu. Grigoriev, Vladimir Shpilrain

Published Jun 1, 2014• 10 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1142/s0129054114400036

Related papers

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

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

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.

International Journal of Foundations of Computer Science•Jun 1, 2017•9 citations

Decoy-based information security

Vladimir Shpilrain

Abstract In this survey, we discuss an emerging concept of decoy-based information security, or security without computational assumptions. In particular, we show how this concept can be implemented to provide security against (passive) computationally unbounded adversary in some public-key encryption protocols. In the world of symmetric cryptography, decoy-based security finds a wide range of applications, notably to secure delegation of computation to another party. We single out the scenario where a computationally limited party wants to send an encrypted message to a computationally superior party using the RSA protocol, thereby providing another kind of application of decoy ideas in a public-key setting. With typical RSA parameters, decoy-based method of delegation of computation improves the efficiency for the sender by several orders of magnitude.

journal of Groups complexity cryptology•Jan 1, 2014•0 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

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

Decoy-based information security.

Vladimir Shpilrain

Where does a wise man hide a leaf? In the forest. But what does he do if there is no forest? He grows a forest to hide it in. G. K. Chesterton, The Innocence of Father Brown Abstract. In this survey, we discuss an emerging concept of decoy-based information security, or security without computational assump-tions. In particular, we show how this concept can be implemented to provide security against (passive) computationally unbounded adver-sary in some public-key encryption protocols. In the world of symmetric cryptography, decoy-based security finds a wide range of applications, notably to secure delegation of computation to another party. We single out the scenario where a computationally limited party wants to send an encrypted message to a computationally superior party using the RSA protocol, thereby providing another kind of application of decoy ideas in a public-key setting. With typical RSA parameters, decoy-based method of delegation of computation improves the efficiency for the sender by several orders of magnitude. 1.

•Jan 1, 2014•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
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.
Abstract In this survey, we discuss an emerging concept of decoy-based information security, or security without computational assumptions. In particular, we show how this concept can be implemented to provide security against (passive) computationally unbounded adversary in some public-key encryption protocols. In the world of symmetric cryptography, decoy-based security finds a wide range of applications, notably to secure delegation of computation to another party. We single out the scenario where a computationally limited party wants to send an encrypted message to a computationally superior party using the RSA protocol, thereby providing another kind of application of decoy ideas in a public-key setting. With typical RSA parameters, decoy-based method of delegation of computation improves the efficiency for the sender by several orders of magnitude.
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
Where does a wise man hide a leaf? In the forest. But what does he do if there is no forest? He grows a forest to hide it in. G. K. Chesterton, The Innocence of Father Brown Abstract. In this survey, we discuss an emerging concept of decoy-based information security, or security without computational assump-tions. In particular, we show how this concept can be implemented to provide security against (passive) computationally unbounded adver-sary in some public-key encryption protocols. In the world of symmetric cryptography, decoy-based security finds a wide range of applications, notably to secure delegation of computation to another party. We single out the scenario where a computationally limited party wants to send an encrypted message to a computationally superior party using the RSA protocol, thereby providing another kind of application of decoy ideas in a public-key setting. With typical RSA parameters, decoy-based method of delegation of computation improves the efficiency for the sender by several orders of magnitude. 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.