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 86

Ungarble my circuit

Due: April 19
Points: 3

The image below shows you Bob's view of a garbled circuit, where you see the encrypted gates, all the wires, and how they're connected. Note that Bob doesn't actually know the operation of each gate, just how to evaluate them if he has a value for each input wire.

Here, as in the in-class example, we are using the simple (not secure!) encryption defined by

\({\rm Enc}_k(x) = (x - k^2) \bmod 100\)

\({\rm Dec}_k(x) = (x + k^2) \bmod 100\)

And here are the encrypted truth table values for each gate.

Gate Encrypted truth table values
\(g_1\) [4, 24, 43, 91]
\(g_2\) [40, 53, 61, 80]
\(g_3\) [26, 47, 59, 81]

Bob is not supposed to ever be able to find out both the true and false values of every wire. That would allow him to do extra evaluations, and to figure out Alice's input that he's not supposed to know.

But suppose Bob nefariously discovers the complete table of wire values as follows:

Wire False value True value
\(w_1\) 0 8
\(w_2\) 0 4
\(w_3\) 4 0
\(w_4\) 5 7
\(w_5\) 4 7
\(w_6\) 2 5
\(w_7\) 0 1

Note that the value of \(w_7\), the output, is unencrypted.

Based on all this information, "un-garble" the circuit to discover the actual operation of each gate. Is each one an AND gate, OR gate, XOR, or what? You should be able to decrypt the truth tables and discover the operation of each gate.

Turn in your decrypted truth tables, and an accurate gate diagram of how the circuit looks (with actual gates).

Can you explain (in plain English) what this circuit does?