[Yao82] Protocols for Secure Computations

Authors: Andrew C. Yao | Venue: FOCS 1982 | Source

Abstract

The following problem is studied: two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth. This problem is referred to as the Millionaires’ Problem, and a protocol for its solution is described. Following this is a discussion of how the protocol applies to the more general problem of computing any information that is a function of the inputs of two parties while keeping those inputs secret. This is called the Two-Party Secure Computation Problem. It is shown that any function of the inputs of two parties can be computed obliviously. The paper also introduces the technique of garbled circuits.

BibTeX

Copy

@inproceedings{Yao82,
  author    = {Andrew C. Yao},
  title     = {Protocols for Secure Computations},
  booktitle = {23rd Annual Symposium on Foundations of Computer Science (FOCS 1982)},
  pages     = {160--164},
  year      = {1982}
}