Garbled Circuit

Please read this blog, if you’ve never heard of GC.

Originally proposed by [Yao82][Yao82] for Secure general 2PC for arbitrary polynomial functions.

a	b	AND
0	0	0
0	1	0
1	0	0
1	1	1

AND gate: Two parties involved are Garbler/Evaluator: $A/B$ with individual inputs: $a,b$

• Fix an encryption function $\Pi :(\text{Gen,Enc,Dec})$, where $\text{Enc}:\mathcal{K}\times \mathcal{M}\to \mathcal{C},\text{Dec}:\mathcal{K}\times \mathcal{C}\to \mathcal{M}$.

• $A$ creates two key pairs $(K_L^0,K_R^0),(K_L^1,K_R^1)$

• Create garbled table:

  a	b	and
  $K_L^0$	$K_R^0$	$c_1=E(K_L^0,E(K_R^0,0))$
  $K_L^0$	$K_R^1$	$c_2=E(K_L^0,E(K_R^1,0))$
  $K_L^1$	$K_R^0$	$c_3=E(K_L^1,E(K_R^0,0))$
  $K_L^1$	$K_R^1$	$c_4=E(K_L^1,E(K_R^1,1))$

• Send $c_1,c_2,c_3,c_4$ and $K_L^b$ to $B$

• $A,B$ perform 1-2 OT for $K_R^{b^{\prime }}$ for bit $b^{\prime }$ of $B$.

• $B$ performs decryption of all ciphertexts, but only one of them is valid.

• Performs $a\wedge b$ and return output to $A$.

Security against:

• Semi-honest sender: sender only obtains output of OT and final $a\wedge b$. If OT is secure against malicious sender, then sender can only obtain information about a’s input which can be inferred from output $a\wedge b$.
• Semi-honest receiver: obtains $c_i,K_L^b,K_R^{b^{\prime }}$ from $A$. for CPA secure encryption, all ciphertext are indistinguishable to each other. $K_L^b,K_R^{b^{\prime }}$ is chosen uniformly, thus, receiver can’t gain any information from input about $A^{\prime }s$ bit.

General 2PC

Above protocol can be used to perform general computation on boolean circuits. For each input wire, create Key pairs, and a garbled table for each gate as follows:

a	b	AND
$K_L^0$	$K_R^0$	$c_1=E(K_L^0,E(K_R^0,K_{out}^0))$
$K_L^0$	$K_R^1$	$c_2=E(K_L^0,E(K_R^1,K_{out}^0))$
$K_L^1$	$K_R^0$	$c_3=E(K_L^1,E(K_R^0,K_{out}^0))$
$K_L^1$	$K_R^1$	$c_4=E(K_L^1,E(K_R^1,K_{out}^1))$

With ciphertexts and two decryption keys, one can decrypt to obtain key for the next intermediate gate. Final output wire decrypts to $0/1$.

• Compute: function $f:\{0,1{\}}^n\times \{0,1{\}}^n\to \{0,1{\}}^{\ast }$, with inputs $x,y$ with each party.
• Sender computes $4.n$ key pairs for $2n$ input wires.
• Garbles each gate and obtains $4.|G|$ ciphertexts, where $|G|$ denotes number of gates in the function.
• Sends $K_1^{x_1},\dots ,K_n^{x_n}$ to $B$.
• Perform n $1-2$ OT to obtain $K_1^{y_1},\dots ,K_n^{y_n}$.
• $B$ decrypts each gate to obtains keys for subsequent intermediate gate.
• $B$ learns final output $f(x,y)$ and sends it to $A$.

Refer to above protocol as $\Pi (C,x,y)$ with $C,x$ as sender’s private input, and $y$ as evaluator’s input. Round complexity of above protocol is same as complexity of underlying OT. Using a 2-round OT, one can securely compute any function where the circuit itself is private input to the evaluator.

More generally, a Garbling scheme $\mathcal{G}$ can be denoted using $(\text{Gb,En,ev,Ev,De})$:

• $\text{Gb}(1^n,f)\to (C,e,d)$: circuit $C$, encoding information $e$, decoding information $d$.
• $\text{ev}$: plaintext circuit evaluator $ev(C,x)=f(x)$
• $\text{En}(e,x)\to X$: on input encoding information $e:(K_i^0,K_i^1{)}_{i\in [1,n]}$ and input $x\in \{0,1{\}}^n$ gives garbled input $X$.
• $\text{Ev}(F,X)\to Z^{\prime }$: garbled evaluator that on input takes garbled circuit and inputs, and gives garbled output.
• $\text{De}(d,Z^{\prime })\to z$: takes the decoding information and gives plaintext output.

Security

Against semi-honest adversary:

$\mathrm{Pr}[\mathcal{D}(1^n,\Pi (C,x,y),y,\mathcal{A})=1]-\mathrm{Pr}[\mathcal{D}(1^n,S(C(x,y),y),\mathcal{A})=1]\le \text{negl}(n)$

For any given function $f:\{0,1{\}}^n\times \{0,1{\}}^n\to \{0,1\}$ implemented by a boolean circuit $C$, multi-Encryption CPA secure $\text{Enc}$ function, protocol $\Pi$ is secure if $\forall x,y\in \{0,1{\}}^n$, PPT adversary $\mathcal{A}$, there exists a PPT simulator $S$ such that no PPT distinguisher $\mathcal{D}$ can distinguish between real world and simulated protocol.

Informally, there should exists a simulator which can output the transcript of real world protocol from a circuit output $z=C(x,y)$, and evaluator’s input $y$.

First prove for a single gate, then since $\Pi$ can be used to build protocol for any polynomial function, the following proof holds.

${\Pi }_{\mathcal{S}}$ algorithm:

• Run $\text{Gen}$ of Enc to derive $k_1,\dots ,k_5$, where $k_5=k_z$ is the output key.

• Run ${\mathcal{S}}_{OT}$ on key $k_3$ to derive $y$ from the transcript.

• Garble the table as follows, and send permuted table.

  AND
  $E(k_1,E(k_3,k_z))$
  $E(k_1,E(k_4),00\dots 00)$
  $E(k_2,E(k_3,00\dots 0))$
  $E(k_2,E(k_4,00\dots 0))$

• send output map as $\varphi =(k_z:z,k_r:1-r)$, garbled table, and $k_1$ to $\mathcal{A}$.

Run 4 hybrid arguments and prove each’s probability is negligible:

• Substitute OT in $\Pi$ to ${\mathcal{S}}_{OT}$ that on input $y$ from evaluator outputs $k_{b,y}$, i.e. the output of ideal OT.
  • This is secure due to security of OT protocol.
• Substitute one of the three remaining inputs to $00\dots 0$, i.e. $E(k_1,E(k_4,00\dots 0))$, but the rest of the ciphertexts remain same, $E(k_i,E(k_{i+2},k_c^{0/1}))$
• Substitute next two ciphertexts.
  • Above hybrid proofs are secure, and can be proven using reduction proof. Adversary ${\mathcal{A}}^{\prime }$ breaks Enc if distinguisher ${\mathcal{D}}^{\ast }$ is able to output correct bit.¹

Security against malicious adversary:

$\mathrm{Pr}[\text{De}(d,\mathcal{A}(F,X))\notin \{f(x),\perp \}]\le \text{negl}(n)$

Authenticity: any PPT adversary on input garbled circuit $F$ and garbled input $X$ can only output correct plaintext output or aborts. This implies that even an actively corrupted adversary cannot cheat.

• Actively corrupted evaluator: Evaluator performs OT after receiving garbled circuit $F$, i.e. it has access to ciphertexts corresponding to each wire, and wiring information. It can then change the inputs in such a way to receive keys for ciphertexts of its choice, and then aborts the protocol, getting to know about x’s input during this phase.
  • How to prevent this? Change the order of ciphertext and OT, i.e perform OT before ciphertext communication.
• Actively corrupted garbler: Garbler can choose circuit $f$ such that it either outputs correct information or aborts (revealing partial information about Evaluator’s inputs).
  • Can be handled by randomly evaluating multiple encryptions of circuit by garbler, i.e. let $C_1,\dots ,C_k$ be k different encryptions of same circuit. Evaluator chooses either all but one approach, or majority cut-and-choose approach to check if the circuit is same or not.
  • Can abort OT such that $\text{Ev}$ fails for a wrong key, and garbler learns partial information about Evaluator’s input.

Optimisations

• Point-and-permute: prevent decryption of 4 ciphertext, and pass additional data in keys so that evaluator determines which ciphertext to decrypt.
  • Choose a select bit $p\in \{0,1\}$ and set $p$ as LSB of keys: $K_0^0=K_0^0\Vert p,K_0^1=K_0^1\Vert (1\oplus p)$, similarly for $K_1^{\{0,1\}}$.
  • Encrypt as $H(K_i^{\{0,1\}},K_j^{\{0,1\}})\oplus K_k^{\{0,1\}}$.
  • Permute the table canonically by select bits: $\text{LSB}(K_i^{\{0,1\}}),\text{LSB}(K_j^{\{0,1\}})$.
  • Evaluator on receiving ciphertexts and key, checks LSB of key and choose the respective ciphertext from the table.
• Free-XOR: select a random difference delta $\Delta$, and create keys as $K^0=k,K^1=\Delta \oplus k$. Using this, XOR gates can be evaluated independently as $K_L^0\oplus K_R^0=K_L^1\oplus K_R^1,K_L^0\oplus K_R^1=K_L^1\oplus K_R^0$.
  • For Free-XOR to be compatible with Point-and-permute (only when no extra select bit is chosen) $\text{LSB}(\Delta )=1$.
• Garbled Row-reduction 3: Eliminate one ciphertext by picking one key such that ciphertext for that key is 0.
  • Suppose from Free-XOR, first key is $c_0=H(K_L^1,K_R^0)=H(K_L\oplus \Delta ,K_R)$. Set this ciphertext to 0, and xor all other ciphertext with $c_0$.
  • Evaluator can directly compute the key, if select bits evaluate to 0.
• Garbled Row-Reduction 2: Use polynomial interpolation instead of one-time decryption to get output keys.
  • For odd gates (OR, AND): ciphertexts corresponding to output bit 0 can be used to form a quadratic polynomial $P$. y-intercept of this polynomial gives $P(0)=c_0$. And extrapolating the polynomial to get 2 more points $P(5),P(6)$. Form a new polynomial $Q=(K_1,P(5),P(6))$, y-intercept of this polynomial $Q(0)=c_1$.
  • For even gates (XOR, NXOR): create a linear polynomial $P$ using $(1,K_1),(4,K_4)$. Set $K_3^0=P(0)$, set $P(5)$ in garbled table as per select permutation bit. Similarly, create polynomial $Q$ as $(2,K_2),(3,K_3)$. Set $K_3^1=Q(0)$. set $Q(5)$ in remaining garbled table row.
• Fle-XOR: have more offset instead of one like Free-XOR. Using this, one can make a xor gate more flexible by converting offset on the fly. For a unary gate, let $A,A\oplus {\Delta }_1$ be the input. To convert this to $A^{\ast },A^{\ast }\oplus {\Delta }_2$, set as $A^{\ast }=E_A^{-1}(0^n)$ and send $E_{A\oplus {\Delta }_1}(A^{\ast }\oplus {\Delta }_2)$ as ciphertext. Evaluator on getting key using OT, can generate the key accordingly.
  • This can be generalised to binary gate using $\{0,1,2\}$ ciphertexts depending on whether differences of key pairs $(A,A\oplus {\Delta }_A),(B,B\oplus {\Delta }_B),(C,C\oplus {\Delta }_C)$ match. If none match, then $2$ ciphertexts need to be sent for XOR.
• Half gate:
• Garbled Gadgets:

References

• CS355: Lecture 6
• CS498: Lecture 22
• Secure Computation Lecture Series
• Rafail’s Lecture notes: 14
• Orlandi’s CryCom: Lecture 5
• A Gentle Introduction to Yao’s Garbled Circuits
• Ben Lynn notes: Yao’s SFE
• Mina Book: Garbled Circuits
• Mike Rosulek’s talk on GC optimisations

Footnotes

1. https://courses.grainger.illinois.edu/cs498ac3/fa2020/Files/Lecture_23_Scribe.pdf ↩