International Association
for Cryptologic Research

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 a computationally unbounded adversary. In that protocol, the legitimate parties are not assumed to be computationally unbounded.