This is a post in COSIC’s Guide to Crypto! In this series, researchers from COSIC will be informally writing about different concepts in cryptography. Our aim is to introduce the reader to these concepts with explanations, illustrations and examples; so let’s get started!

Introduction to Garbled Circuit

Before actually getting into the idea of garbled circuits, let’s consider the following question. Suppose there are two cryptographers, George and Emma, and they want to figure out who has a higher salary. But, being cryptographers, they want to answer the question without revealing their actual salary to each other. This is exactly Yao’s Millionaires’ Problem. To solve this problem (any other problems that can be expressed by a function), we need to use secure multiparty computation, where multiple parties compute the output of a function without revealing the inputs to each other. Garbled circuit is a technique to do secure multiparty computation for two parties and this is the topic of this blog post.

Before starting, we need to establish, that to express any function, it is enough to have access to a universal set of logic gates. For example, {NAND} and {AND, XOR}. As such, it’s possible to come up with a circuit that outputs a 0 or a 1 depending on who has a higher salary.

We consider two parties, George (for garbler) and Emma (for evaluator). Both parties are honest-but-curious, meaning that they will follow the protocol to create and evaluate the circuit, but they might try to learn extra information from the message exchanges. The high level idea is that George will create a garbled circuit (an encrypted version of the original circuit) and then send it to Emma. Then, Emma will ask for the “encrypted” inputs of George and herself. Having all the inputs, Emma can securely evaluate the circuit to obtain the plaintext output.

Garbling

First, we consider how to garble a single gate, which is the role of George. This process is also known as creating a garbled table. Suppose we have an AND gate with the truth table below, where \(a, b\) and \(c\) are wires.

To create a garbled version of it, George generates a random key for every possible value of \(a\),\(b\) and \(c\) from the table above. That is 6 keys.  The key needs to be suitable for use with an authenticated symmetric key cipher, such as AES-GCM. Then, he encrypts the output keys using the input keys as shown below.

The notation \(E_k\) denotes an encryption using the key \(k\). Since it’s symmetric \(D_k(E_k(m)) = m\), where \(D_k\) means decryption using the same key. Note that the decryption fails if the key is wrong (a property of authenticated encryption), we make use of this property in the evaluation phase later. George creates a table like this for every gate ensuring the gates are “chained” together. That is, if the wire \(c\) is used as an input of another gate. Then \(k^c\) needs to be used to create the new garbled table. Finally, when all the tables are created, George randomly permutes the entry of every table and sends the last column (the encrypted keys) of every tables to Emma.

Evaluation

Evaluation is the job of Emma. She needs the keys that correspond to her input and George’s input to evaluate the circuit. Getting George’s keys are easy. He can simply send them to Emma because he knows the relationship between the keys and bits. Doing so won’t leak any information on George’s input bits because the keys are generated at random. The harder part is for George to give Emma her keys. Emma cannot tell George her input bits because that completely reveals them, defeating the purpose of garbled circuit. Instead, Emma and George run an oblivious transfer (OT) protocol. Getting into the details of OT is a topic for another blog post. But it allows George to obliviously send Emma the key that she’s interested in. In other words, Emma obtains the right key and George learns no information on which key she obtained. When Emma has all the keys, the evaluation is straightforward.

For instance, she is given the following table and two keys \(k^a_1, k^b_1\).

We mentioned earlier that decryption fails when the wrong key is used. So she tries to decrypt row by row until she sees a successful decryption and obtains \(D_{k^a_1}(D_{k^b_1}(e_{1,1})) = k^c_1\). Note that it is not necessarily the last decryption that she tries because the table is permuted. For the other gates, she follows the circuit topologically and performs the same steps for every gate. Eventually, she obtains the output keys and then asks George for the corresponding bits.

Correctness and Security

Let’s think about why this protocol is correct and why it’s secure. The correctness is obvious because if Emma obtains the right keys for the inputs, then there is only one row in each table that she can possibly decrypt. If George created the tables correctly (which he must have because we’re not considering a malicious adversary), then Emma will eventually decrypt the keys that correspond to the output bits. Security in this case means the parties learn nothing about each other’s input bits. George cannot learn anything from Emma due to OT. Emma cannot learn anything from George because the keys that he sends to her are randomly generated. Further, she also cannot infer any information from the evaluation. That’s because the entries in the garbled tables are shuffled by George. Further, she is only able to decrypt one row in every table, revealing nothing about the output bit. If she can decrypt two entries in, for example, an AND gate, and the decryption happens to be the same, then she knows for sure the output key corresponds to a 0.

Optimization

The protocol described above is Yao’s original protocol from 1986. Since then, researchers has found many improvements and we will outline a few of them below. In the description above, we used trial-decryption, which on average needs 2.5 decryptions per table. Using a technique called point-and-permute, Emma only needs to do 1 decryption. The basic idea is that the output key will have a “hint” bit that points to the right row to decrypt in the next table. The Free-XOR technique allows XOR gates to be “free”, where George doesn’t need to create a garbled table for XOR gates. This is done by (at a very high level) setting the output key of an XOR gate to be the XOR of the two input keys. Finally, garbled circuit can be generalized to multiple parties too, where parties work together to create the GC, each contributing a share of the key used in garbling. For the readers who want to know more, the lecture video from Simons Institute has a great overview of the optimization techniques. A more detailed description of garbled circuit can be found in the book A Pragmatic Introduction to Secure Multi-Party Computation. It does not cover all the optimization techniques but it does describe the multiparty version of garbled circuit called BMR.