Protocols for Secure Computations

URL: https://ieeexplore.ieee.org/document/4568388 Authors: Andrew C. Yao

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.