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

Dima Grigoriev; Laszlo B.  Kish; Vladimir Shpilrain

Paper 2016/189

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

Dima Grigoriev, 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.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: Yao's millionaires' problem public-key encryption computationally unbounded adversary
Contact author(s): shpilrain @ yahoo com
History: 2017-02-05: last of 3 revisions; 2016-02-23: received; See all versions
Short URL: https://ia.cr/2016/189
License: CC BY

BibTeX

@misc{cryptoeprint:2016/189,
      author = {Dima Grigoriev and Laszlo B.  Kish and Vladimir Shpilrain},
      title = {Yao's millionaires' problem and public-key encryption without computational assumptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/189},
      year = {2016},
      url = {https://eprint.iacr.org/2016/189}
}