Cryptology ePrint Archive: Report 2014/384

Yao's millionaires' problem and decoy-based public key encryption by classical physics

Dima Grigoriev and Vladimir Shpilrain

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.

Category / Keywords: cryptographic protocols / Yao's millionaires' problem, decoy-based cryptography, computationally unbounded adversary

Date: received 28 May 2014

Contact author: shpilrain at yahoo com

Available format(s): PDF | BibTeX Citation

Version: 20140528:164403 (All versions of this report)

Short URL: ia.cr/2014/384

Discussion forum: Show discussion | Start new discussion