Technology Background: Garbled Circuits Part 1

This is the first in a series of blogs I and others will be writing on different types of technology used in Multi-Party Computation. The first one we will discuss is that of Garbled Circuits. These are the oldest form of MPC technology, going back to a seminal idea of Andrew Yao in the early 1980s. At first sight they seem highly inefficient, especially if looked through the lens of the state-of-the-art in the 1980s. But with modern processors and protocol improvements over the decades they form the workhorse of a number of real world deployments of MPC technology.

The basic idea is that two parties want to compute a function F(x,y) of their inputs, where party one holds x and party two holds y. We assume for this discussion that party one only will get the output, and that the parties are semi-honest; i.e. they follow the protocol but are interested in the other persons input. In follow up articles we will describe how to overcome these limitations, extend to more than two parties, and make the following protocol more efficient.

The first step is to write the function as a binary circuit, namely a function on binary data which only consists of XOR and AND (and possibly INVerter) gates. For any function F this can either be done by hand, or by using the tool chains used to produce microprocessors.

We take the two parties and divide them into an generator (which for us will be party one) and an evaluator (which for us will be party two). The generator goes first.

The generators goal is to “encrypt” the circuit. To do this he assigns to each wire w two cryptographic keys, k_{w,0} and k_{w,1}. The key k_{w,0} corresponds to a zero value on the wire, and the key k_{w,1} corresponds to a one value.

To encrypt a gate (say an AND gate) with input wires a and b, and output wire c, the generator uses a symmetric IND-CCA encryption scheme E((k0,k1),m) which takes two keys (k0,k1) and encrypts a message m. The gate is encrypted by forming the four ciphertexts

c_{0,0} = Enc( (k_{a,0}, k_{b,0}), k_{c,0} )

c_{1,0} = Enc( (k_{a,1}, k_{b,0}), k_{c,0} )

c_{0,1} = Enc( (k_{a,0}, k_{b,1}), k_{c,0} )

c_{1,1} = Enc( (k_{a,1}, k_{b,1}), k_{c,1} )

Notice how these ciphertexts correspond to the truth table of the AND gate. The four ciphertexts are now randomly permutated and published. We permute them so that the evaluator has no idea which of the four ciphertexts corresponds to c_{0,0}, which to c_{1,0} and so on. The set of four ciphertexts is called a Garbled Gate.

All the garbled gates are then given to the evaluator. The circuit generator, assuming they have input x to the function, also passes along the wire keys corresponding to their input. So for example if the first bit of x is 0 and this corresponds to wire a, then the generator sends the key k_{a,0} to the evaluator.

Now the evaluator needs to obtain the wire keys correspond to their input. They do this by using a protocol called Oblivious Transfer (OT). In such a protocol the generator/sender inputs two values k_{b,0} and k_{b,1} corresponding to the input wire keys for one of the evaluators/receivers’ inputs. The evaluator then inputs the value they want for their input (say c), and then the evaluator obtains k_{b,c}. In an OT protocol the sender does not send over a mapping table for the output wires, showing which key on which output wire corresponds to which value. Using this protocol, the evaluator learns the value of c, and the receiver does not learn the value of k_{b,1-c}.

The evaluator now has the keys for the chosen inputs on the input wires. They now propagate these inputs through the circuit. Every time they reach a garbled gate they decrypt the four ciphertexts. As it is an IND-CCA encryption scheme, only one of these ciphertexts will give a valid decryption with extremely high probability. It is this decryption which they take as the output of the garbled gate.

Finally the evaluator will obtain keys for all of the output wires. Since in our example player one (the generator) is only to get the output, the evaluator passes back the wire keys to the circuit generator. The circuit generator can then use the mapping he knows between the output wire keys and the output wire values to obtain the output of the function.

This might seem an incredibly complicated protocol, but modern Garbled Circuit protocols can evaluate functions consisting of billions of garbled gates in a matter of seconds.

In future articles we will remove the need for IND-CCA encryption by using signal bits, remove the need to garble XOR gates, allow the evaluator to obtain output, describe how to perform Oblivious Transfer and prevent attacks by malicious adversaries.