In Part 1 of our Garbled Circuits series, we found a problem-specific solution for rescuing our shipwrecked friends. However, the solution didn't provide a general approach for computing functions privately (without revealing their inputs). One way to construct a general solution for evaluating a particular function f(x) is to design a circuit that maps the possible inputs x to the possible outputs f(x). For example, consider a NAND gate:
The gate maps all possible values of its input wires ({0,1}, {0,1}) to a value of its output wire {0,1}. However, in order to find the value of the output wire, the evaluator must know the values of the input wires. Our target problems require that the input wires remain private, so we need to modify this approach.
Garbled Circuits
The general solution was given in 1986 by Turing Award laureate Andrew Yao [1]. Incredibly, Yao proved that any polynomial-time function can be computed securely (without disclosing a player’s inputs) in polynomial time by “garbling” regular circuits. In this introduction, we will consider the simplest case where there are only two participants, Alice and Bob. Each has a private input bit that should not be disclosed to the other, and each would like to learn the result of NAND(Alice Input, Bob Input). Since any function can be constructed from NAND gates, it is sufficient to show how to garble only this gate. We will have Alice generate (construct) the garbled circuit, and Bob will evaluate the garbled circuit to recover the result.
Generator Steps (Alice)
The first step for the generator is to replace the wire inputs {0,1} with an independent and identically distributed (i.i.d.) random value K. These random values will be used as encryption keys for a symmetric cipher, such as AES. In our notation, the binary value {0,1} that K maps to is the superscript, while the input wire {1,2} that K corresponds to is the subscript. In our example, Alice will provide the input to Wire 1, and Bob will provide the input to Wire 2.
Next, the values of the output wire are encrypted using the key K corresponding to the appropriate input values:
Applying this to the NAND gate in our running example, the Generator produces this garbled circuit:
As Alice (Wire 1) knows her input bit b, she simply removes her other key corresponding to 1-b. However, how will Alice send Bob the key corresponding to his input bit?
There are issues with the obvious solutions:
To understand why sending both keys reveals additional information, consider an example where Alice’s input bit is 0 and Bob’s input bit is 0. The output of NAND(0,0) is 1. If Bob only knows that his input bit is 0 and the result is 0, then Alice’s input bit could be either 0 or 1. However, if Bob was given the ability to evaluate the gate on both 0 and 1, he would discover NAND(A,0)=1 and NAND(A,1)=1, which reveals that Alice’s input bit must be 0. This is an unnecessary disclosure of Alice’s private input bit.
Since Bob can’t ask for his input key, and Alice can’t give him both possible keys, we need a solution where Bob receives only the key for his input bit, and Alice doesn’t know which one she sent to Bob. Impossible? We'll find out in Part 3 of our #garbledcircuits blog series!
