Secure Two Party Computation

Yao’S Protocol

Let f be a polynomial-time functionality (assume for now that it is deterministic), and let x and y be the parties' respective inputs. The first step is to view the function as a Boolean circuit C. In order to describe Yao's protocol, it is helpful to first recall how such a circuit is computed. Let x and y be the parties' inputs. Then, the circuit C (x; y) is computed gate-by-gate, from the input wires to the output wires. Once the incoming wires to a gate g have obtained values α, β {0,1}, it is possible to give the outgoing wires of the gate the value g(α ; β). The output of the circuit is given by the values obtained in the output wires of the circuit. Thus, essentially, computing a circuit involves allocating appropriate zero-one values to the wires of the circuit. In the description below, we refer to four different types of wires in a circuit: circuit-input wires (that receive the input values x and y), circuit-output wires (that carry the value C (x; y)), gate-input wires (that enter some gate g), and gate-output wires (that leave some gate g).