Garbled Circuits

Following our discussion on Oblivious Transfer (OT), it's time to see how this fundamental building block is used to construct a complete Secure Multiparty Computation (SMC) protocol. We'll explore the classic and ingenious solution for two-party computation (2PC): Yao's Garbled Circuits.

This protocol provides a generic solution to the famous "Millionaires' Problem," where two millionaires want to know who is richer without revealing their actual wealth. More powerfully, it can be used to securely compute any function that can be represented as a boolean circuit.

The Core Idea

Imagine you have a function, say, a simple AND gate. You want a friend to compute the output of this gate using your input and their input, but without either of you revealing your inputs to the other.

Yao's protocol solves this by "garbling" the circuit. Think of it like this:

The creator of the circuit (the Garbler) builds a box for each gate. Each box has multiple locks corresponding to the input wires. The Garbler provides the other party (the Evaluator) with exactly one key for each input wire—the key that represents their secret input bit. The Evaluator can only open the one correct lock combination on the first box, which then reveals the key for the next box in the circuit. They proceed through this chain of locked boxes until they reach the final one, which contains the result.

At no point does the Evaluator know what the intermediate values are, as they are just random-looking keys. And the Garbler never knows which keys the Evaluator used.

The Protocol in Detail

Let's assume Alice is the Garbler and Bob is the Evaluator. They have agreed on a function $f(x_A, x_B)$ to compute, where $x_A$ is Alice's private input and $x_B$ is Bob's.

1. Setup

First, the function $f$ is expressed as a boolean circuit, composed of gates like AND, OR, and XOR. This is a standard representation for any computable function.

2. Garbling (Alice's Role)

Alice takes the circuit and performs the following steps to garble it:

a. Create Wire Keys: For every wire $w$ in the circuit, Alice generates two random, distinct cryptographic keys:

• $k_w^0$: represents the value 0 on that wire.
• $k_w^1$: represents the value 1 on that wire.

b. Create Garbled Tables: For each gate in the circuit (e.g., an AND gate with input wires $a$, $b$ and output wire $c$), Alice creates a "garbled table." This table has an encrypted entry for each of the four possible input combinations.

Let's say the gate computes $v = g(v_a, v_b)$. The output wire $c$ will have the key $k_c^v$. Alice constructs the table by double-encrypting the output wire key with the corresponding pair of input wire keys.

For an AND gate, the table would look like this before permutation:

Here, $E_k(m)$ denotes the encryption of message $m$ with key $k$.

c. Permute and Send: Alice randomly shuffles the four rows of each garbled table. This is crucial, as it prevents Bob from learning anything from the position of the entry he successfully decrypts. Alice then sends the entire garbled circuit, including all the shuffled garbled tables, to Bob.

3. Input Transfer (Alice and Bob's Interaction)

Now, Bob needs the keys corresponding to the circuit's input wires.

• Alice's Inputs: For her own input bits $x_A$, Alice simply sends the corresponding keys to Bob. For example, if her input is 101, she sends Bob the keys $k_{w_1}^1, k_{w_2}^0, k_{w_3}^1$. This reveals nothing, as the keys are just random strings to Bob.
• Bob's Inputs: This is where our previous topic comes in. Bob cannot simply tell Alice his inputs. Instead, for each of his input bits $b_i$ for wire $w_i$, they perform a 1-out-of-2 Oblivious Transfer.
  • Alice's input to the OT: The pair of keys for the wire $(k_{w_i}^0, k_{w_i}^1)$.
  • Bob's choice for the OT: His private input bit $b_i$.
  • Result: Bob receives the key $k_{w_i}^{b_i}$ corresponding to his input. Alice learns nothing about Bob's choice $b_i$.

4. Evaluation (Bob's Role)

Bob now has everything he needs:

1. All the garbled tables for the circuit.
2. The input keys corresponding to Alice's private inputs.
3. The input keys corresponding to his own private inputs (obtained via OT).

He evaluates the circuit gate by gate:

• For the first gate, he takes his two input wire keys (e.g., $k_a^{v_a}$ and $k_b^{v_b}$).
• He tries to use this pair of keys to decrypt all four entries in the corresponding garbled table. Because of how symmetric encryption works, only one of the four entries will decrypt successfully.
• The result of the successful decryption is the output wire key for that gate (e.g., $k_c^{v_c}$).
• He repeats this process for the next gate, using the key he just obtained as one of the new input keys.

He continues this process until he reaches the final output wires of the circuit, at which point he will hold the final set of keys (e.g., $k_{out}^v$).

5. Revealing the Output

The final key Bob holds, $k_{out}^v$, is still just a random string. It doesn't mean "0" or "1" on its own. To get the final result, Alice sends a simple mapping table that reveals the meaning of the output keys, for example: $(k_{out}^0 \to 0, k_{out}^1 \to 1)$. Bob can now look up his key and get the final, plaintext result of the computation.

Security Guarantees

The privacy of the protocol relies on two key properties:

1. Bob's Privacy: Alice never learns Bob's inputs. This is guaranteed by the security of the Oblivious Transfer protocol used for the input transfer phase.
2. Alice's Privacy: Bob learns nothing about Alice's inputs or any of the intermediate values in the computation. He only gets one key per wire, which prevents him from exploring other computational paths. The garbled tables look like random, meaningless ciphertexts to him. All he learns is the final output.

Illustrative Example

Here is a more complex example using a two-gate circuit that computes the function $f(A, B, C) = (A \text{ AND } B) \text{ XOR } C$.

In this scenario, Alice has inputs $A$ and $C$, and Bob has input $B$.

The Circuit

The function is broken down into two gates:

1. Gate 1 (AND): Takes inputs from wire $a$ (Alice's $A$) and wire $b$ (Bob's $B$). Its output goes to wire $d$.
2. Gate 2 (XOR): Takes inputs from wire $d$ (the intermediate result) and wire $c$ (Alice's $C$). Its output goes to wire $e$.

1. Garbling (Alice)

a. Generate Wire Keys:
Alice generates two random keys for every wire in the circuit: $a, b, c, d, e$.

• Wire $a$: $(k_a^0, k_a^1)$
• Wire $b$: $(k_b^0, k_b^1)$
• Wire $c$: $(k_c^0, k_c^1)$
• Wire $d$: $(k_d^0, k_d^1)$
• Wire $e$: $(k_e^0, k_e^1)$

b. Create Garbled Tables:

Garbled Table for Gate 1 (AND):
The output for this gate is the key for wire $d$, corresponding to the result of $A \land B$.

Garbled Table for Gate 2 (XOR):
The output is the key for wire $e$, corresponding to the result of $D \oplus C$.

Alice shuffles the rows in both tables and sends them to Bob, along with the final output mapping: $(k_e^0 \to 0, k_e^1 \to 1)$.

2. Input Transfer

Let's assume Alice's inputs are $A=1, C=0$, and Bob's input is $B=1$.

• Alice's Keys: Alice directly sends Bob the keys corresponding to her inputs: $k_a^1$ and $k_c^0$.
• Bob's Key (via OT): Bob needs the key for his input $B=1$. They use Oblivious Transfer. Alice provides the pair $(k_b^0, k_b^1)$, Bob chooses index $1$, and he receives the key $k_b^1$.

At the end of this stage, Bob holds three starting keys: $k_a^1$, $k_c^0$, and $k_b^1$.

3. Evaluation (Bob)

Bob evaluates the circuit one gate at a time.

a. Evaluate Gate 1 (AND):

• Bob has the input keys for this gate: $k_a^1$ and $k_b^1$.
• He tries to decrypt the four entries of the first garbled table with this key pair.
• Only the entry corresponding to the input $(1, 1)$ will decrypt successfully.
• The result of the decryption is the output key $k_d^1$. This makes sense, as $1 \land 1 = 1$.

b. Evaluate Gate 2 (XOR):

• Bob now has the input keys for the second gate: $k_d^1$ (from the previous step) and $k_c^0$ (which Alice sent him directly).
• He uses this pair to decrypt the four entries of the second garbled table.
• Only the entry corresponding to the input $(1, 0)$ will decrypt successfully.
• The result of this decryption is the final output key $k_e^1$. This also makes sense, as $1 \oplus 0 = 1$

4. Reveal Output

Bob is left with the final key, $k_e^1$. He uses the output mapping Alice sent:

• $(k_e^0 \to 0, k_e^1 \to 1)$

He finds that his key maps to the value 1.

The computation is correct: $(A \land B) \oplus C = (1 \land 1) \oplus 0 = 1 \oplus 0 = 1$. Bob learned the final answer without ever knowing Alice's individual inputs, and Alice learned nothing about Bob's input or the result.

Conclusion

Yao's Garbled Circuits protocol is a seminal achievement in cryptography, providing a complete and generic solution for two-party secure function evaluation (SFE). By representing any function f(xA​,xB​) as a boolean circuit, the protocol allows a Garbler to construct an encrypted equivalent that an Evaluator can process without learning anything beyond the final output.

The entire security framework rests on two pillars:

1. Circuit Privacy: The garbled tables, which encode the logic of each gate, are opaque to the Evaluator. Since each wire key is a random string, the intermediate values are computationally indistinguishable from noise, perfectly hiding the Garbler's inputs and the function's internal state.
2. Input Privacy: The Evaluator's input privacy is fundamentally guaranteed by 1-out-of-2 Oblivious Transfer. As we detailed in the previous post, this primitive is the lynchpin that allows the Evaluator to select the keys corresponding to their secret inputs without revealing their choices to the Garbler.

While the original construction was a landmark theoretical result, modern advancements have made it a practical tool. Key optimizations, such as the Free-XOR technique (which allows XOR gates to be evaluated with zero cryptographic cost) and the massive efficiency gains from OT Extension protocols, have transformed Garbled Circuits from a conceptual model into a high-performance engine for real-world privacy-preserving applications.

Ultimately, Yao's protocol elegantly reduces the complex problem of secure computation to a composition of well-understood primitives: symmetric-key encryption and Oblivious Transfer. It remains a cornerstone of 2PC and a conceptual launchpad for understanding more complex, multi-party computation schemes.