Yao’s Millionaires’ Problem and Public-Key Encryption Without Computational Assumptions
Dima Grigoriev, László B. Kish, Vladimir Shpilrain · International Journal of Foundations of Computer Science · 2017
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.