Paper 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.