Yao's Millionaires' Problem and Public-Key Encryption Without Computational Assumptions Academic Article uri icon

abstract

  • We offer efficient and practical solutions of Yaos 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.

published proceedings

  • INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

author list (cited authors)

  • Grigoriev, D., Kish, L. B., & Shpilrain, V.

citation count

  • 5

complete list of authors

  • Grigoriev, Dima||Kish, Laszlo B||Shpilrain, Vladimir

publication date

  • June 2017