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.
