Garbled Circuits

2-Party Secure Function Evaluation

The problem above is the Millionaires problem [9] and it is solved by the use of 2-party secure function evaluation (SFE). The general idea [4] is that you have a function f which takes as input x and y. This function is garbled by one of the two parties into f' and the inputs are garbled into x' and y' by each of the parties. f'(x', y') == f(x,y) but does not leak any of the inputs, because x and y were obfuscated.

In other words...

1. Alice and Bob agree on a function (i.e., circuit) f(a,b).
2. Alice garbles the function (cough circuit) f and her input a.
3. Alice sends f' and a' to Bob.
4. Bob gets his input b garbled into b'.
5. Bob evaluates f'(a', b').
6. This reveals the result of f(a,b) to Bob, but does not reveal Alice's input.

Garbling a gate

How does Alice actually... 'garble' a circuit? It sounds kinda dirty.

Each gate (OR, AND, XOR, etc) has two inputs. Stick with me. Each input is encrypted. Keeping up? So you need a key to use each gate. It gets better. But if you have the keys, you don't know which key corresponds with a 1 or a 0 so you can compute a function without knowing the actual values you put in. Whoa.

Let's use the OR gate as an example.

Remember truth-tables for OR? Here's a reminder:

This table is going to be important for Alice's part of this dance.

Extending the garbled gate

Note

The UTF-8 Padlock symbol doesn't render on my browser because I seem to have gone back in the time to the late 90s. Being stuck in the past, we have to comprmise. The ⛨ symbol is meant to represent a lock and the ⚿ represents a key.

Multiple gates can be connected together to build more complicated circuits. One important difference is that while each intermediate circuit still has four cipher-texts, for the four outcomes of a truth-table, those decrypt to a key and not a 1 or 0. The only gates which decrypt to a plain-text of 0 or 1 are output gates, not the intermediate gates.

Note

PSST Check out the end of this post for a GAME!

Problems with garbled circuits

There are a few important flaws in the security of garbled circuits as they have been described. The first is that although Alice and Bob agree on a circuit to garble there is no guarantee that the circuit one is evaluating (if you're Bob) is the circuit you agreed upon.

For example:

1. Alice and Bob 'agree' on a function f(a,b).
2. Alice creates her own function g(a,b).
3. Alice garbles g and her input a and sends it to Bob as f' and a'.
4. Bob evaluates g'(a',b') and reveals the output to Alice. Alice now knows something other than than Bob agreed to.

Improvements on garbled circuit security

To prevent the above adversarial attack we do something called "Cut-and-Choose". This is when Bob checks Alice's work to make sure she's not cheating.

Remember that Alice and Bob agreed on a given circuit.

1. Alice generates M garbled circuits for the agreed upon function where M > 1.
2. All secrets for a randomly chosen N circuits are revealed where 1 ≤ N < M, the circuits are "opened".
3. Bob selects one of the remaining M-N circuits to evaluate as outlined earlier.

This ensures that Alice is not nefarious to some statistical certainty. She had control over how the circuits were garbled but she does not have control over which are revealed or evaluated. If she made one (or two or three...) nefarious circuits that bad behavior is probably revealed in step 2, if all the checked circuits are good Alice is probably being honest.

This doesn't break garbled circuits for the following reasons:

• While Alice reveals the secrets of the N circuits, she doesn't reveal anything about her input. We are only un-garbling the circuit not the inputs (revealing all possible inputs, not Alice's).
• We're not un-garbling the M-N circuits which may be evaluated, so those are still secret.

As M grows and N approaches M this method gets more secure at the cost of computation cycles and bandwidth in transferring the garbled circuits.

The "Free XOR" Optimization

I'm definitely not a circuits person. You can show me a circuit diagram and I'll say "Yep, that's a circuit. What's it do?" I couldn't even even identify which gate is which without Wikipedia.

I was told during my research for this post that XOR gates are very popular with garbled circuit design, and more broadly circuit design in general. This was shared to me in the form of a cryptic hint so I figured I'd investigate and share my findings here.

As it turns out the Wikipedia page notes that this XOR optimization exists and even cites the original paper published on the topic. [6]

The jist of this optimization is that one can very efficiently garble an XOR gate such that the output of the gate is encoded as the XOR of the keys used to unlock the gate and some known global constant. This is in contrast with the implementations discussed in the beginning where each gate had to be decrypted with two cipher-texts and revealed another key.

Basically using XOR, which is pretty fast, we can avoid generating four keys per gate and instead craft 1 key which is produced as the result of 'unlocking' a gate.

Put a bit more formally:

Given a gate G with input wires A and B and output wire C and a random string R, the garbled gate is obtained by XORing the garbled gates inputs C¹ = C⁰ ⊕ R:

C⁰ = A⁰ ⊕ B⁰ = (A⁰ ⊕ R ) ⊕ (B⁰ ⊕ R) = A¹ ⊕ B¹

C¹ = C⁰ ⊕ R = A⁰ (B⁰ ⊕ R ) = A⁰ ⊕ B¹ = (A⁰ ⊕ R) ⊕ B⁰ = A¹ ⊕ B⁰

This isn't super intuitive, and honestly I just put those equations up there to prove that I read a paper about this.

The main takeaway is that 'free XOR' saves us computation generating and processing cryptographic keys by simply performing the XOR operation. This optimization is so powerful that using mostly XOR gates makes garbled circuits notably faster and more useful for secure computation. [8]

Annotated Bibliography

Foundations of Garbled Circuits [2]

This is by far the most thorough academic source I have. If I had a better foundation in academic reading this might be the perfect paper but most of it went way over my head. That said the overview of each section was fairly human-readable and gave me a good rough overview for many of the topics covered in this post.

A Brief History of Practical Garbled Circuits [8]

This was the first source I checked out to get a feel for how difficult garbled circuits are as a topic. It quickly glanced at the basics of garbled circuits and then quickly went into the optimizations on garbled circuits. This was overwhelming, but as I started to learn more about garbled circuits and filled in the knowledge gaps it gained significant value.

It's a great talk about Garbled Circuits which wasn't ideal for beginners, but did give me a good breadth of the topic and what I could dive into.

Improved garbled Circuit: Free XOR Gates and Applications [6]

This paper was useful in giving me an academic preview of the XOR optimization in Garbled Circuits. I quickly started looking at the many other papers referenced by this one, kind of like following down the Wikipedia wormhole, but with more PDFs and less pictures.

SFE: Yao's Garbled Circuit [1]

This slide-deck was very useful as a reference for basic GCs and securing GC's with cut-and-choose. It wasn't a great initial source for this material, but it was useful after I had a basic understanding of a topic to solidify it with pretty pictures and Comic Sans.

Mike Rosulek on Stack Exchange [3] [7]

This is more of a shout-out than a citation. Mike Rosulek's posts on crypto.stackexchange.com were very helpful in breaking down core concepts like what garbled circuits are and why XOR is "free". They also provided a good list of further reading which was helpful in addition to the resources provided in the syllabus.

Errata