In 1982, secure two-party computation (2PC) was introduced for problems that are
boolean predicates, e.g.
Yao’s Millionaires'
Problem
that
asks whether \(a \ge b\) is true without revealing the actual values of
\(a\) and \(b\).
Andrew Yao generalized 2PC for any feasible computation in 1986. Goldreich,
Micali and Wigderson later generalized it to secure multiparty communication.
Yao-based protocols requires that the function to be securely evaluated be
represented as a circuit, but an efficient transformation is not trivial. The
Fairplay system transforms a program in a high-level language into a boolean
circuit representation, garbles that circuit and then executes a protocol to
evaluate the garbled circuit. AES’s circuit has \(\approx 50K\) gates, while
the 4095-bit edit distance function has \(\approx 6B\) gates.
Timeline of Secure Multi-Party Communication
In 1982, secure two-party computation (2PC) was introduced for problems that are boolean predicates, e.g. Yao’s Millionaires' Problem that asks whether \(a \ge b\) is true without revealing the actual values of \(a\) and \(b\).
Andrew Yao generalized 2PC for any feasible computation in 1986. Goldreich, Micali and Wigderson later generalized it to secure multiparty communication.
Yao-based protocols requires that the function to be securely evaluated be represented as a circuit, but an efficient transformation is not trivial. The Fairplay system transforms a program in a high-level language into a boolean circuit representation, garbles that circuit and then executes a protocol to evaluate the garbled circuit. AES’s circuit has \(\approx 50K\) gates, while the 4095-bit edit distance function has \(\approx 6B\) gates.
...