- “A Gentle Introduction to Yao’s Garbled Circuits” by Sophia Yakoubov
- 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.
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.
In other word, let Ginny holds a bit and let Evan holds a bit . 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 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 or .
step 1: encryption
We pick a label from the side and a label from the 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 , the output is a symmetric encryption key, and the key is used to encrypt the output of . Hence now the garbled outputs (ciphertexts) takes the form 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 and , so he needs to receive those two labels with the real values of and from Ginny. We call these two labels “label(g)” and “label(e)” respectively.
step 1: sending label(g)
Since Ginny knows , she knows which label is label(g). Since labels are just random strings picked by Ginny, Evan is not able to learn anything about from label(g) itself. So Ginny could just send her label(g) to Evan.
step 2: sending label(e)
Since Ginny doesn’t know this time, she doesn’t know which label is label(g). She can’t send both labels corresponding to 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 . 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.