This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

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.