MPC Techniques Series, Part 6: Secure two-party computation with Garbled Circuits
By Ivan Damgård, Professor and Chief Cryptographer at Partisia
In cryptography, a circuit is a way in which a computation can be represented, consisting of operations on bits. A garbled circuit, however, is a method to encrypt a computation that only reveals the output of the computation itself, without giving away anything regarding the inputs or the values of the computation. In this blog post I will explain garbled circuits, which was the very first approach used in secure computation, and it was suggested by Andrew Yao in the late 1980s.
Before discussing the computation part, let’s talk about encryption. Say that we have two encryption keys K1 and K2 and a message x. Then this notation: c= E(K1,K2)(x), means that we encrypt x by first using K2 and then K1, which obtains ciphertext c as a result. You may have heard about encryption algorithms like AES and this could well be the actual cryptosystem used to do this. We will need three important properties from such encryptions, as follows:
- If you have c and you know both K1 and K2, then you can easily decrypt and get x.
- If you have c but only one of K1 and K2, or none of them, you will have no idea what x is.
- Suppose someone gives you two mystery keys, L1 and L2, that may or may not be the right keys, K1 and K2. We assume that you can check if you have the right keys by trying to decrypt c and then checking the result. One way to make this happen would be to encrypt not just x, but x followed by a string of 0-bits. Now, decryption via a wrong key is very unlikely to produce only 0-s at the end.
Now, let’s discuss the actual secure computation. For this example, let’s say that we have two characters: Greg the Garbler and Eva the Evaluator (the reason for the titles will become clear later).
In our first (simplified) scenario, we assume that Greg has a function, f, that he wants to compute. But he does not yet have the input, x, and he knows that when he gets the input, he will not have enough computing power to do the computation himself. Therefore, he wants Eva to do it for him when the time comes, but he does not want Eva to learn the input or the output. So what he does, on a high level, is the following:
- Greg writes down an encrypted or garbled specification of the function f, called G(f), and sends this to Eva who stores it for later. G(f) is called a garbled circuit.
- When Greg gets the input x, he can turn this into a garbled input G(x) while doing almost no computation. He sends this to Eva, which turns out to be fine, as G(x) does not reveal anything about x.
- Now the magic happens: using G(f) and G(x), Eva can evaluate the function f, and obtain a garbled representation G(y) of the output y= f(x). But she will learn nothing new in the process.
- Eva sends G(y) to Greg who can easily compute y.
Now, let’s see how we actually do this, using the fancy encryption tool we outlined above. Let’s start with a really simple function that takes two input bits B1, B2, and outputs the AND, or the product of the bits: f(B1,B2) = B1 B2. It is helpful to think of the AND operation as an “AND-gate”, that is, a component with a left and a right input wire, and one output wire. If you put B1 on the left and B2 on the right input wire, the AND gate will compute B1 B2 and put this bit on the output wire.
What the AND gate does can be specified as a table:
Greg now does the following: he chooses 6 random keys for the cryptosystem: R0, R1, L0, L1, U0, U1. The idea is that (L0, L1) will be assigned to the left input wire, where L0 will represent input bit 0, and L1 represents input bit 1. Similarly, (R0, R1) is assigned to the right input wire and (U0,U1) to the output wire. Now, Greg takes the above table for the AND gate and transforms it into the following set of 4 ciphertexts:
Notice how the indices of the keys correspond to the bits in the AND-table. Also, note that if you know L0 and R0, for instance, you can decrypt the first entry and get U0, but only that entry. Likewise, the only way to get U1 is if you know L1 and R1.
So, Greg remembers his keys, R0, R1, L0, L1, U0, U1, and what they represent, and he sends the table with 4 ciphertexts to Eva. This table serves as the garbled representation of the AND function. When Greg gets the input, say x= (b1, b2) = (0,1), he will send the garbled input G(b1,b2) = G(0,1)= L0, R1 to Eva. To her, this is just two random keys; she has no idea which bits they stand for. Now, by our assumptions on the cryptosystem, she will be able to spot the one ciphertext in the table that she can decrypt, namely E(L0,R1)(U0) and she will get U0 as a result. This is also a random key, which she sends to Greg who knows that U0 stands for output 0. Hopefully, you can convince yourself that by following this protocol, Greg will always get back the key that represents the correct output.
There is one issue, which you may have spotted already: if Greg sends the ciphertexts to Eva in the order we listed above, Eva could figure out that the input was (0,1), from the fact that she can decrypt the second entry. So therefore Greg randomly reorders or permutes the ciphertexts before sending them, and this solves the problem.
Obviously, in this example the function to compute is so simple that it makes no sense for Greg to outsource the computation to Eva. However, we can write any function by stringing together several operations on bits, where the output bits from (some of) the operations are used as inputs to other operations. This is called a Boolean circuit, see the Figure below, where we have two AND gates and one XOR gate (that just adds the input bits modulo 2). Note that output wires of the AND gates serve as input wires for the XOR. Greg can garble such a circuit by assigning a pair of keys to each wire and then follow the recipe we already saw, to produce 4 ciphertexts for each gate. To evaluate, Eva will work her way through the circuit gate by gate, starting from the inputs. She will learn exactly one key for each wire because she will be able to decrypt exactly one ciphertext per gate. This continues until she has keys that represent the output.
Finally, let me explain how this can be turned into general two-party secure computation. In this setting both Greg and Eva should be allowed to supply inputs to the function in question. We think of this as a Boolean circuit C where Greg “owns” some of the input wires that he chooses the bits for, and Eva owns the rest. We will start just like before: Greg garbles the circuit and sends the result, G(C), to Eva, as well as keys representing his input bits. If Eva could now go through the circuit as before to get keys for the output, she could send these keys to Bob who could tell her the result — and we would be done.
However, the problem is that Eva also needs to know the keys representing her input bits. But only Greg knows these keys. Say these keys are X0, X1 for a particular input bit that Eva should choose. Of course, Eva cannot just say “give me X0”, as this would reveal her secret input. On the other hand, Greg cannot send both X0 and X1 to Eva to let her choose on her own. This would allow Eva to learn too much information. For instance, she might learn one of Greg’s input bits: Say Eva chooses one input bit to an AND gate and Greg chooses the other one. Remember that Eva gets one key from Greg representing his input bit. If Eva now gets both keys for her input wire she can decrypt two of the four ciphertexts. If the two decryptions return different keys, Eva knows that Greg’s input bit was 1 — had it been 0, the AND gate would output 0 regardless of Eva’s input, and so Eva would see the same key coming out of both encryptions.
The solution to this problem is called Oblivious Transfer (OT) and was described in last week’s blog post, titled ‘What is Oblivious Transfer, and why should you care?’. Using OT, Greg can “send” X0 and X1 to Eva, in such a way that Eva can choose to receive either X0 or X1 depending on which input bit she wants, but not both. Moreover, Greg does not learn Eva’s choice.
This finally solves the problem, and we can do secure 2-party computation with passive security, where we assume that the parties follow the protocol. Active security, where parties may be malicious, is harder to achieve: what if Greg garbles the wrong circuit? This problem can be solved in many ways, but that is a story for another blog post.
About the author
Ivan is professor and head of the research group in cryptography at Aarhus University. Ivan is co-founder of Cryptomathic, Partisia and Sepior. He is one of the top cited and publishing researchers in cryptography, is a fellow of the IACR (International Association for Cryptologic Research), and received the 2015 RSA Award for Excellence in the Field of Mathematics.