2
$\begingroup$

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: wikiprotocol

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!

$\endgroup$
  • $\begingroup$ Of the six steps on the Wiki page, which do you have issues with? $\endgroup$ – Mark Apr 10 at 1:21
  • $\begingroup$ I have updated the question. Thanks! $\endgroup$ – Hasan Iqbal Apr 10 at 16:02
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
2
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.