# 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:
- second party's input is
*y*=01, the output is 01;
- second party's input is
*y*=11, the output is 10.

Show that the simulated circuits are indistinguishable from the actual one.