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 91

Garbled circuit simplification?

Due: April 26
Points: 2

In the Yao's garbled circuit construction we learned, Alice not only computes the garbled circuit and all the wire values, but she also sends Bob the encrypted wire values corresponding to her own inputs.

There is a potential for Alice to do some precomputation on the bits that she knows, basically simplifying the circuit before encrypting the gates and sending them to Bob.

For example, the circuit example we did in class is computing the function

\(f(a_1, a_2, b_1, b_2) = (a_1 \wedge b_1) \vee (a_2 \wedge b_2)\)

Depending on the values of \(a_1\) and \(a_2\) that Alice knows, she might be able to simplify the circuit and remove some gates before encrypting the truth tables and sending them to Bob. This would save her time in computing the truth tables and in evaluating the circuit. Hooray!

However, if Alice simplifies the circuit "too much", it might leak some information to Bob about her values. For example, in the circuit above, if \(a_1 = 0\) and \(a_2 = 0\), then Alice knows the function result will always be 0. So she could technically remove all the gates from the circuit entirely! But that would also reveal to Bob that her inputs were both 0's, so that would be bad.

For this problem, I want you to describe in general terms and using some clear examples what kind of circuit simplifications would be "safe" for Alice to perform without tipping Bob off as to her inputs. Then describe the circuit that Alice should actually send to Bob for the example above when \(a_1 = 0\) and \(a_2 = 1\).