Construct garbled circuits
Cryptographic protocols, Autumn 2008, 2nd home exercise
Consider the two-party functionality min(x,y), where the first
party inputs x, the second party inputs y and both learn the
minimum of those two. Let the two parties use Yao's “garbled
circuits” protocol to securely evaluate that functionality (first
party garbles, second party evaluates). Construct
a circuit C for the functionality min (assume that both
inputs, as well as the output are two bits long) and draw the garbled
circuit. Also draw the simulated circuits for the following two cases:
Show that the simulated circuits are indistinguishable from the actual one.
- second party's input is y=01, the output is 01;
- second party's input is y=11, the output is 10.