Concrete Example of AND Gate Using Garbled Circuit

Question

Most of the resources online like the wiki presents the beautiful idea of Garbled circuit in a rather unnecessarily abstract manner. This is the screenshot of Wiki's protocol:

What would be an example of step 2? How does Alice garbles the circuit? Using any public-key crypto or private? Could anyone please give me a concrete example of any gate, say AND using this primitive? Like, at the bitstring level. For example, let's say Alice has bit $0$, Bob has bit $1$. They would like to compute the AND. Thanks!

Answer 1

The main conceptual idea behind garbling is to "label" Boolean values on wires in the circuit with keys of a (symmetric key) encryption scheme. Computations are then done in terms of these labels, instead of the underlying Boolean values. Throughout the rest of this, I will use $\mathsf{in}_0, \mathsf{in}_1, \mathsf{out}$ to denote the two input wires of the AND gate, and the (single) output wire. If we view these as directly taking Boolean values, these satisfy the equation:

$$\mathsf{in}_0\land \mathsf{in}_1 = \mathsf{out}$$ In particular, given $\mathsf{in}_0, \mathsf{in}_1$, we can compute $\mathsf{out}$ using this formula.

One way to make this computation "private" would be if instead of directly having $\mathsf{in}_i$ and $\mathsf{out}$ take Boolean values, we "obfuscate" things somewhat. Generate the keys $k_{\mathsf{in}_0, 0}, k_{\mathsf{in}_0, 1}, k_{\mathsf{in}_1, 0}, k_{\mathsf{in}_1, 1}, k_{\mathsf{out}, 0}, k_{\mathsf{out}, 1}$. Note that there are precisely 6 keys --- for each of the (three) wires in the circuit, we generate a key for each of the possible values the wire can take.

Now if someone gives me two keys $k_{\mathsf{in}_0, i}, k_{\mathsf{in}_1, j}$, I don't know what the "values" underlying the keys $i$ and $j$ are. But I also don't know how to compute the AND of the keys, meaning I can't yet compute $k_{\mathsf{out}, i\land j}$. If I could somehow (without learning the values $i$ and $j$ directly) we'd be done.

Garbling allows us to do this by computing the four ciphertexts $C_{i, j} = \mathsf{Enc}_{k_{\mathsf{in}_0, i}}(\mathsf{Enc}_{k_{\mathsf{in}_1, j}}(k_{\mathsf{out}, i\land j}))$. If we know both keys $k_{\mathsf{in}_0, i}$ and $k_{\mathsf{in}_1, j}$, we can decrypt the ciphertext $C_{i, j}$ to learn $k_{\mathsf{out}, i\land j}$. But if I don't know those keys, by the security of the underling encryption scheme I cannot decrypt $C_{i, j}$, keeping "the rest" of the possible computations "private".

So Alice's job (in the garbling step) is to generate all of the above information:

1. Two keys for each wire in the circuit.
2. $2k$ ciphertexts for each $k$-arity gate in the circuit.

This process is called "garbling" the circuit.

Answer 2

$ \newcommand{\AK}{\mathsf{K}} \newcommand{\AE}{\mathsf{E}} \newcommand{\AD}{\mathsf{D}} \newcommand{\out}{\leftarrow} $

For Step 2, Yao's original construction [Y] relied on a symmetric encryption scheme $(\AK,\AE,\AD)$. The high level idea is to associate each wire $w$ in the circuit with a pair of keys $k_w^0,k_w^1\out\AK$ and then compute on the keys. To carry this out, we construct a "garbling table" for each gate, which intuitively is the encryption of the truth table of the gate.

Let's for the time being assume that the circuit comprises only of the AND gate. Let $a$ and $b$ denote its input wires and $c$ denote its output wire. The garbling table consists of the following four ciphertexts: $$\begin{matrix} c_{00}=\AE_{k_a^0}\left(\AE_{k_b^0}(k_c^0)\right) & c_{01}=\AE_{k_a^0}\left(\AE_{k_b^1}(k_c^0)\right) \\ c_{10}=\AE_{k_a^1}\left(\AE_{k_b^0}(k_c^0)\right) & c_{11}=\AE_{k_a^1}\left(\AE_{k_b^1}(k_c^1)\right)\end{matrix}$$ The garbling of the circuit (AND) consists of the garbling table $\mathbf{c}=\{c_{00},c_{01},c_{10},c_{11}\}$ and an output map $(k_c^{0}\mapsto 0,k_c^1\mapsto 1)$.

Now, let's see how Alice, with input $x$, and Bob, with input $y$, jointly compute $x\wedge y$. Alice computes the garbled circuit (viz., the ciphertexts and the output map) as described above (Step 2). Next, she sends the garbled circuit along with the key $k_a^x$ (her input encrypted) to Bob (Step 3). Bob then obtains his garbled input $k_b^y$ via the oblivious transfer (Step 4). Bob now "ungarbles" by performing $$\AD_{k_b^y}\left(\AD_{k_a^x}(c_i)\right)$$ for each ciphertext $c_i\in\mathbf{c}$, compares the result with the output map, and outputs the bit that matches (Step 5). Note that Bob will be able to properly decrypt only one of the ciphertexts, the one corresponding to the correct inputs (keys $k_a^x$ and $k_b^y$).

In general, the garbling table of a (Boolean) gate $g:\{0,1\}^2\rightarrow\{0,1\}$, consists of the ciphertexts $$\begin{matrix} c_{00}=\AE_{k_a^0}\left(\AE_{k_b^0}(k_c^{g(0,0)})\right) & c_{01}=\AE_{k_a^0}\left(\AE_{k_b^1}(k_c^{g(0,1)})\right) \\ c_{10}=\AE_{k_a^1}\left(\AE_{k_b^0}(k_c^{g(1,0)})\right) & c_{11}=\AE_{k_a^1}\left(\AE_{k_b^1}(k_c^{g(1,1)})\right)\end{matrix}$$ Whereas, to garble an arbitrary circuit, one simply garbles its constituent gates. Why is the construction complete? Because the underlying encryption scheme is complete. Why is it secure? From Alice's point of view, given the key $k_a^x$ and the ciphertexts $\mathbf{c}$, her input $x$ is computationally hidden to Bob thanks to the encryption scheme. The (selective) security was formally argued much later with an mild additional assumption on the symmetric encryption scheme [LP].

[Y] Yao, Protocols for secure computations, FOCS 1982.

[LP] Lindell and Pinkas. A proof of security of Yao’s protocol for two-party computation, JoC 2009.