# 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$.