1/14: Garbled Circuits

• Chapter 23.3 of https://toc.cryptobook.us/book.pdf
• Chapter 3.1 of https://www.cs.virginia.edu/~evans/pragmaticmpc/pragmaticmpc.pdf
• https://infossm.github.io/blog/2021/02/20/Multi-Party-Computation-1/

First Idea - Lookup Table + Oblivious Transfer

If one wants to compute \(f(x, y)\) where \(x\) is supplied by \(P_1\) and \(y\) is supplied by \(P_2\), we can do this as follows. For each possible input \(x\), \(P_1\) selects a key \(k_x\). This is done similarly for \(y\). Then, \(P_1\) computes, for all \(\lvert X \rvert \cdot \lvert Y \rvert\) possible combinations, the value \(\text{Enc}_{k_x, k_y}(f(x, y))\).

\(P_1\) then sends this encryption table to \(P_2\). Also, \(P_1\) sends the \(k_x\) corresponding to its input \(x\). The hard part arises from \(P_1\) having to send \(k_y\) corresponding to the \(P_2\)'s input \(y\), without knowing \(y\) itself. This can be done via 1-out-of-\(\lvert Y \rvert\) Oblivious Transfer. Once \(P_2\) receives \(k_y\), they can try to decrypt all encryptions, with only success being \(f(x, y)\) if the encryption is authenticated. This is a quite unoptimized protocol, but one that provides MPC.

To allow this lookup table idea to work, we only work with 2-party boolean circuits.

Additional Idea: Point-and-Permute

The main source of wasteful computation is \(P_2\) having to decrypt all encryptions. To prevent this, we could add make the last bit of \(k_x, k_y\) to be a pointer to the encryption table.

This way, it is possible for \(P_2\) to perform a single decryption.

Final Garbled Circuits Protocol

For each wire \(w_i\) of the circuit, \(P_1\) randomly selects wire labels

\[w_i^b = (k_i^b \in \{0, 1\}^\kappa, p_i^b \in \{0, 1\}), \quad p_i^0 + p_i^1 = 1\]

then, if \(G_i\) is a boolean gate implementing \(w_c = g_i(w_a, w_b)\), the garbled table is

\[e_{v_a, v_b} = H(k_a^{v_a} || k_b^{v_b} || i) \oplus w_c^{g_i(v_a, v_b)}\]

with the \(p_a^{v_a}, p_b^{v_b}\) being the according table pointer for \(e_{v_a, v_b}\).

For each output wire \(w_i\), the garbled output table is

\[e_v = H(k_i^v || \text{OUT} || i) \oplus v\]

with the \(p_i^v\) being the according table pointer for \(e_v\).

After this, \(P_1\) sends to \(P_2\) the active wire labels for wires in which \(P_1\) provides the input.

Then, for each wire where \(P_2\) provides the input, an 1-out-of-2 Oblivious Transfer protocol is used so that \(P_1\) sends \(P_2\) the correct wire label without \(P_1\) knowing the actual input value.

With all active wire labels, \(P_2\) begins the evaluation - by computing

\[(k_c, p_c) = w_c = H(k_a || k_b || i) \oplus e_{p_a, p_b}\]

note how \(P_2\) doesn't know or care about \(v_a, v_b\) and so on.

Similarly, for the output, \(P_2\) computes

\[v = H(k_i || \text{OUT} || i) \oplus e_{p_i}\]

and returns \(v\) to be the final output. This is then sent to \(P_1\).