Yao’s Garbled Circuit: An Introduction

Citation:

  1. “A Gentle Introduction to Yao’s Garbled Circuits” by Sophia Yakoubov
  2. UCLA CS 282A Notes by Rafail Ostrovsky, part 15

In this post, we will discuss some of the very basics of Yao’s Garbled Circuit, as it is indeed an important prerequisite that appears a lot in other protocols.

Problem:

Consider two people Ginny and Evan. Ginny and Evan wish to figure out whether they should collaborate or not, but neither of them wants the other person to know his/her attitude.

Setup:

In other word, let Ginny holds a bit g and let Evan holds a bit e. The bit has value 1 if he/she agrees to collaborate, or has value 0 if he/she disagrees. They want to design a protocol such that both of them learn the value of g \wedge e at the end of protocol, but neither Ginny or Evan learns the other person’s bit during the protocol. In this scenario, we call Ginny the “garbler”, who is in charge of “garbled gate generation”. We call Evan the “evaluator“, who is in charge of “garbled gate evalution“.

Garbled Gate Generation (by Ginny):

The idea is to design a “garbled gate” and generalize it into garbled circuit. Garbling basically means to obfuscate boolean gate truth table. Ginny picks four random strings as “labels“, each corresponds to one of g = 0, 1 or e = 0, 1.

step 1: encryption

We pick a label from the g side and a label from the e side to form a label pair. Now we have four labels pairs, and together they represent the boolean truth table. Each label pair is used as input for a key derivation function H, the output H(label 1, lable 2) is a symmetric encryption key, and the key is used to encrypt the output of g \wedge e. Hence now the garbled outputs (ciphertexts) takes the form Enc(H(label 1, label 2), g \wedge e) after obfuscation.

step 2: permutation

Simply permute the garbled outputs, so that the garbled gate appears to have random order.

Garbled Gate Evaluation (by Evan):

Evan now needs to decrypt the ciphertext corresponding to the real values of g and e, so he needs to receive those two labels with the real values of g and e from Ginny. We call these two labels “label(g)” and “label(e)” respectively.

step 1: sending label(g)

Since Ginny knows g, she knows which label is label(g). Since labels are just random strings picked by Ginny, Evan is not able to learn anything about g from label(g) itself. So Ginny could just send her label(g) to Evan.

step 2: sending label(e)

Since Ginny doesn’t know e this time, she doesn’t know which label is label(g). She can’t send both labels corresponding to e to Evan, because then Evan can decrypt two ciphertexts. Evan can’t just ask for the one he wants, since he doesn’t want Ginny to learn the value of e. Hence they choose to use “oblivious transfer (OT)” to pass label(e).

From Gates to Circuits:

In reality, Ginny and Evan may wish to compute much more complicated functions using this protocol. In this case, Ginny will garble the entire function circuit, instead of a single gate. Now garbled gate becomes garbled circuit.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s