da1729's Blog

cryptography, digital design, embedded, rf, ...

• Updated: December 4, 2025

Yao's Garbled Circuits

#Cryptography #Secure Computing

Ok, let’s continue…

The major reference for this blog is “A Pragmatic Introduction to Secure Multi-Party Computation” by D. Evans, V. Kolesnikov, M. Rosulek.

Yao’s Garbled Circuits

Let’s set the ground first. We wish to evaluate the function $\mathcal{F}(x, y)$, where party $P_1$ holds $x \in X$ and second party $P_2$ holds $y \in Y$, where $X$ and $Y$ are respective domains for the inputs from the corresponding party (node).

Yao’s Garbled Circuits (GC) is basically the celebrity of MPC. It is historically significant and usually the go-to performance benchmark. The killer feature here is that it runs in constant rounds. Unlike other protocols (like GMW) where network latency kills you because communication rounds scale with the circuit depth, Yao’s GC essentially lets you send the whole “computer” over the wire in one go.

GC Intuition: The Look-up Table

Imagine our function $\mathcal{F}$ has a tiny input domain. We could literally just write down every possible result in a table $T$ where rows are indexed by $(x, y)$.

To make this secure, $P_1$ (the generator) creates random keys. For every possible input $x$, they generate a key $k_x$. For every $y$, a key $k_y$. Then, they encrypt the answer $T_{x,y}$ using those two keys.
$$\text{Enc}_{k_x, k_y}(T_{x,y})$$
$P_1$ shuffles this table randomly and sends it to $P_2$. Now, if $P_2$ can somehow get the specific keys corresponding to the actual inputs, they can decrypt exactly one row and get the answer. They learn nothing else because they don’t have the keys for the other rows.

Here is how a basic entry encryption might look in c++:

1
2
3
4
5
6
7
8
struct table_entry {
    std::vector<uint8_t> encrypted_data;
};

table_entry encrypt_row(std::string k_x, std::string k_y, std::string value) {
    std::string combined_key = hash(k_x + k_y);
    return { xor_encrypt(value, combined_key) };
}

Point-and-Permute

If $P_1$ just sends a shuffled bag of encrypted rows, $P_2$ has a problem. They have two keys, but they don’t know which row those keys open. Trying to decrypt every single row is inefficient (especially when we scale up).

The solution is point-and-permute. We append a random “pointer bit” (let’s call it $\sigma$) to the keys.
If we have a key $k$, the last bit is the pointer. When $P_1$ generates the keys, they ensure the pointer bits don’t collide. Now, $P_2$ looks at the pointer bit of their $x$-key and $y$-key (say, $0$ and $1$) and knows exactly that they need to decrypt the row indexed $0,1$ in the permuted table.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct wire_label {
    std::string key;
    uint8_t pointer;
};

struct garbled_table {
    std::vector<std::vector<std::string>> rows;
};

garbled_table create_table(int size) {
    garbled_table t;
    t.rows.resize(size, std::vector<std::string>(size));
    return t;
}

void insert_entry(garbled_table& t, wire_label lx, wire_label ly, std::string enc_val) {
    t.rows[lx.pointer][ly.pointer] = enc_val;
}

Managing Table Size: The Circuit View

Obviously, a giant look-up table for complex functions is impossible. It scales exponentially. So, we represent the function $\mathcal{F}$ as a Boolean Circuit.

Instead of one giant table, we have many tiny tables—one for each logic gate (AND, OR, XOR).
For every wire $w_i$ in the circuit, $P_1$ generates two keys: $k_i^0$ (representing 0) and $k_i^1$ (representing 1). We call these wire labels.

For a gate $G$ with input wires $w_i, w_j$ and output wire $w_t$, $P_1$ creates a table with 4 entries. The entry for input combination $(v_i, v_j)$ encrypts the output label $k_t^{G(v_i, v_j)}$.

$$T_G = \begin{pmatrix} \text{Enc}_{k_i^0, k_j^0}(k_t^{G(0,0)}) \\ \text{Enc}_{k_i^0, k_j^1}(k_t^{G(0,1)}) \\ \text{Enc}_{k_i^1, k_j^0}(k_t^{G(1,0)}) \\ \text{Enc}_{k_i^1, k_j^1}(k_t^{G(1,1)}) \end{pmatrix}$$

Crucially, the “message” inside the encryption is the key for the next wire. This allows $P_2$ to chain decryptions through the circuit without ever knowing if they are holding a logical 0 or 1. They just hold keys.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct gate {
    std::string encrypted_outputs[2][2];
};

gate garble_and_gate(wire_label in_a[2], wire_label in_b[2], wire_label out[2]) {
    gate g;
    for(int i = 0; i < 2; ++i) {
        for(int j = 0; j < 2; ++j) {
            int res = i & j;
            std::string key = hash(in_a[i].key + in_b[j].key);
            g.encrypted_outputs[in_a[i].pointer][in_b[j].pointer] = 
                xor_encrypt(out[res].key, key);
        }
    }
    return g;
}

The Protocol Flow

So how does the actual exchange happen?

  1. Garbling: $P_1$ (Generator) creates the circuit topology, generates all wire labels, and builds the garbled tables for every gate.
  2. Sending Tables: $P_1$ sends all garbled tables to $P_2$.
  3. Sending Keys (P1’s Input): $P_1$ knows their own input $x$. If the $i$-th bit of $x$ is 1, they just send the label $k_i^1$ to $P_2$.
  4. Sending Keys (P2’s Input): This is tricky. $P_1$ has the labels for $P_2$’s input wires, but doesn’t know $P_2$’s input $y$. $P_2$ needs the labels but shouldn’t tell $P_1$ their input $y$. We use Oblivious Transfer (OT) here. $P_2$ receives the correct labels for their input without revealing $y$ to $P_1$.
  5. Evaluation: $P_2$ now has the tables and the input wire labels. They go gate by gate, decrypting one entry per gate to get the output label, until they reach the end.
  6. Decryption: For the final output wires, $P_1$ provides a mapping (decoding table) so $P_2$ can map the final random string back to a True/False.
1
2
3
4
5
6
7
8
9
void evaluator_step(gate g, wire_label wa, wire_label wb) {
    int idx_a = wa.pointer;
    int idx_b = wb.pointer;
    
    std::string ciphertext = g.encrypted_outputs[idx_a][idx_b];
    std::string combined_key = hash(wa.key + wb.key);
    
    std::string output_key = xor_decrypt(ciphertext, combined_key);
}

Security relies on the fact that $P_2$ never possesses both $k^0$ and $k^1$ for the same wire simultaneously. If they did, they could decrypt everything. But since they only start with one set of keys and only recover one key per gate, the invariant holds.

There are massive optimizations for this, like “Free XOR” and “Half Gates” which drastically reduce the size of these tables, but that’s for another post.

peace. da1729