Garbled Circuits

Introduction

• Gabled circuits express the function to be computed as an “encrypted” boolean circuit, e.g. with ANDs, ORs, XORs, etc
• Garbled circuits are more efficient than for 2-party joint processing setups. They get too complex for more parties.
• In this post, we will look at Yao's Garbled Circuits

Given two parties computations, Alice and Bob, they want to compute a function \(f(x,y)\) where \(x\) is Alice's input and \(y\) is Bob's input. After the computation, \(x\) and \(y\) remain private unless revealed by the function \(f\).

One Gate Garbled Circuit

WLOG, we consider a \(\text{AND}\) gate in this section, i.e., \(f(x,y)=x\land y\). Alice will be the circuit garbler, and Bob will be the circuit evaluator. Denote the input bit of Alice and Bob as \(a,b\).

Step by step

1. Alice compiles \(f\). into an acyclic boolean circuit, composed of logic gates like AND, OR, XOR etc.
2. Alice generates random keys \(k[A,0]\), \(k[A,1]\), \(k[B,0]\), \(k[B,1]\), \(k[C,0]\), \(k[C,1]\), each of which corresponds to a bit of a wire.
   • For example, \(k[A,0]\) for wire A, bit \(0\); \(k[C,1]\) for wire C, bit \(1\)
3. Alice garbles the circuit to produce a garbled circuit, essentially each gate will carry out its operation on encrypted input bits producing an encrypted output bit.
   • For example, the AND garbled truth table entry for wire A input \(1\) and wire B input \(0\), is key \(k[C,0]\) doubly-encrypted by \(k[A,1]\) and \(k[B,0]\) \[\text{GT}[1,0]=E_{k[A,1],k[B,0]}(k[C,\text{AND}(1,0)])=E_{k[A,1],k[B,0]}(k[C,0])\]
4. Alice randomly permutates the the entries of the Garbled Table, since the truth-table order will leak information that could be used to learn Alice’s input.
5. Alice sends the permutated garbled gate table plus the encrypted bits for its input and a decryption mapping table that allows Bob to map the encrypted output of the circuit to its plaintext.
   • For example, if \(a=1\), Alice will send \(k[A,1]\) to Bob. Bob won't know the value of \(a\) since all wire keys are random
   • The mapping should be \(k[C,0]\Rightarrow0\),\(k[C,1]\Rightarrow1\)
6. Bob runs a 1-from-2 oblivious transfer (OT) protocol with Alice for Bob input bits. Bob will get the keys that corresponds to \(b\) from Alice without Alice learning \(b\).
   • For example, if \(b=1\), Bob will get \(k[B,1]\). Bob won't know \(k[B,0]\) and Alice won't know \(b=1\).
7. Bob doubly decrypts the garbled gate entry to learn the final encrypted result \(k[C,\text{AND}(a,b)]\) and uses the decryption mapping table to map \(k[C,\text{AND}(a,b)]\) to its plaintext bit \(\text{AND}(a,b)\). Bob sends this to Alice.

1-from-2 Oblivious Transfer protocol

Here is an illustrative example for 1-from-2 OT. There are many others protocols. What's more, 1-from-2 OT can be extended to k-from-n OT. WLOG, we assume that Alice has two messages \(m_1,m_2\) and Bob wants to know \(m_1\).

Step by step

1. Alice has two messages \(m_1,m_2\)
2. Alice generates two public-private key pairs \(\text{(Pub1,Priv1)}\), \(\text{(Pub2,Priv2)}\).
3. Alice \(\rightarrow\) Bob: \(\text{Pub1,Pub2}\)
4. Bob generates a symmetric key \(k\) and chooses \(\text{Pub1}\).
5. Bob \(\rightarrow\) Alice: \(c=E_{\text{Pub1}}(k)\)
6. Alice does \(D_{\text{Priv1}}(c)=k\), \(D_{\text{Priv2}}(c)=u\neq k\)
7. Alice \(\rightarrow\) Bob: \(c_1=E_k(m_1)\), \(c_2=E_u(m_2)\)
8. Bob does \(D_k(c_1)=D_k(E_k(m_1))=m_1\) and \(D_k(c_2)=D_k(E_u(m_2))=\text{non sense}\)

Conclusion

• Bob learns \(m_1\) in this example.
• Alice doesn't know which message Bob knows.
• Alice's messages need to have a structure that Bob can recognise to distinguish the good message \(m_1\) from the gibberish message.

Point-and-Permutate p-bit

In the Step 7, Bob doubly decrypts the garbled gate entry to learn the final encrypted result. Bob could decrypt each entry if the underlying encryption method makes it obvious when decrypting which is the “correct” ciphertext. This is both inefficient and inelegant. The following trick is to pair a random point-and-permutate bit and its inverse to each of the keys of the wire (the \(0\) key and \(1\) key).

For example, if wire A has keys \(k[A,0],k[A,1]\), we would now have \((k[A,0],\text{pA})\), \((k[A,1],\text{not pA})\).

Here is the equivalent pseudo-code to show how Alice generates the point-and-permutate garbled table.

1
2
3
4
5
6
7
8

for each permutated PGT with input wires A, B and output wire C
    for a in [0,1] for b in [0,1]
        x = a xor pbit[A]
        y = b xor pbit[B]
        z = GATE(x,y) # e.g. AND, OR, XOR, NAND ...
        k[C,z] = GATE(k[A,x], k[B,y])
        zl = z xor pbit[C]
        PGT[a][b] = E[k[A,x], k[B,y]](k[C,z], zl) # double encrypt

In Step 5, Alice sends both the encrypted bits and the pbit for its input. In Step 6, Bob obtains both his key and the pbit of his key by running OT. As a result, Bob learns \(k[A,a], \text{pA or not pA}\) and \(k[B,b], \text{pB or not pB}\). Then Bob can directly doubly decrypts \(\text{PGT[pA][pB]}\) to learn \(k[C,z], z^{\prime}\).

Example

Bob learns \(k[A,0],1\) and \(k[B,1],1\). He locates and doubly decrypts \(\text{PGT[1,1]}\) with \(k[A,0],k[B,1]\) to learn \(k[C,0], 0\). Finally, he uses the decryption mapping table to map \(k[C,0]\) to its plaintext \(0\).

Garbled circuit performance

• Runs in a constant number of rounds.
• Computation cost dominated by encryption function used. Typically hardware-assisted AES is used.
• High communication costs - time to transfer circuit, plus time to complete oblivious transfers (later can be done in parallel).
• Both Alice and Bob could cheat at various stages. Techniques such as zero-knowledge proofs and cut-and-choose can be used but have high overheads.