Cryptology ePrint Archive: Report 2016/189

Yao's millionaires' problem and public-key encryption without computational assumptions

Dima Grigoriev and Laszlo B. Kish and Vladimir Shpilrain

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.

Category / Keywords: Yao's millionaires' problem, public-key encryption, computationally unbounded adversary

Date: received 23 Feb 2016, last revised 5 Feb 2017

Contact author: shpilrain at yahoo com

Available format(s): PDF | BibTeX Citation

Version: 20170205:160310 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]