# Problem 88

# Make a garbled circuit

**Due**: April 19

**Points**: 4

This is like the previous problem, except now you are taking the role of "Alice". So you will create the circuit, choose random wire values (true and false values for each wire), then compute the encrypted truth tables for each gate.

The circuit I want you to compute is a "two-bit comparison" circuit for the "less-than" operator. That is, there will be 4 bits of input on wires \(w_1\), \(w_2\), \(w_3\), and \(w_4\). The output will be a single bit, which should be 1 if and only if the two-bit number \(w_1w_2\) is less than the two-bit number \(w_3w_4\).

(Note: *you* have to come up with the gates for how this circuit will work. As a hint, I'll say that you can definitely do it with only 5 gates.)

For example, if the input bits are \(w_1=1, w_2=0, w_3=1, w_4=1\), then the output should be 1 since the first 2-bit number `10`

(binary for 2) is less than the second the second 2-bit number `11`

(binary for 3). Note: we are talking "strict" less-than here, so if the two numbers are the same, you should output 0.

Use `openssl`

and blowfish encryption as in Problem 87. This means that every wire value will be a 6-digit random number, except the last output wire, which should be 0 for false and 1 for true.

Turn in **on paper** a diagram of your circuit with all gates and wires labeled. Turn in **electronically** a file called `garbled.txt`

listing all the wire values (both true and false for each wire), and the four garbled truth table entries for each gate.

Submit your program according to the instructions on the submit page.