How Yao’s Garbled Circuits Enable Secure Two‑Party Computation: A Step‑by‑Step Guide

Secure Multi‑Party Computation (MPC)

Secure Multi‑Party Computation (MPC) allows multiple participants to jointly compute a function while guaranteeing correctness, privacy, and fairness of the computation.

Secure Two‑Party Computation

Secure Two‑Party Computation is a special case of MPC involving exactly two parties. Each party provides private inputs x and y, computes a function f(x, y) without a third party, and learns only the output z = f(x, y).

Boolean Circuit

A Boolean circuit consists of gates (AND, OR, NOT) connected by wires without cycles. The circuit size is the number of gates; the depth is the longest path from an input wire to an output wire, reflecting the time needed for a single computation.

Any polynomial‑time algorithm can be transformed into a polynomial‑size Boolean circuit, so the function f in the two‑party setting can be represented as such a circuit.

Yao’s Garbled Circuit

Yao’s garbled circuit encrypts each gate’s truth table. Every wire carries a garbled value representing 0 or 1, chosen from a random symmetric key (e.g., a 128‑bit key). The garbled value itself reveals no information about the underlying bit.

To garble a gate, the truth table is encrypted under the two input garbled values, producing a garbled table that retains only the encrypted output column and shuffles the rows.

Protocol Based on Garbled Circuits

The protocol proceeds as follows:

Alice constructs a Boolean circuit for the desired function f.

Alice garbles each gate, producing a garbled table that keeps only the encrypted output column and randomises the row order.

Alice sends the garbled table together with her garbled input values to Bob.

Alice reveals to Bob which garbled value corresponds to her actual input.

Bob evaluates the garbled circuit using his garbled inputs, decrypts the unique row that succeeds, obtains the encrypted output, and sends this ciphertext back to Alice, who decrypts it to recover the plaintext result.

Example: Millionaire Problem

Two parties, Alice and Bob, each hold a 1‑bit wealth value (0 or 1). They want to learn whether Alice is richer without revealing their values.

The Boolean circuit for comparing x (Alice) and y (Bob) outputs z = 1 if x > y, otherwise z = 0. The truth table and the corresponding garbled table are shown below.

AES‑256 is used as the symmetric encryption algorithm; the random keys are shown in the figure below.

Following the protocol, Alice sends the shuffled garbled table to Bob, reveals her chosen garbled value (representing 0), and Bob selects his garbled value (representing 1). After evaluating the garbled circuit, Bob obtains a ciphertext that decrypts to z = 0, indicating that Alice is not richer than Bob.

Throughout the process, neither party learns the other’s private input, yet they jointly compute the correct comparison result.

Although this protocol demonstrates the basic principle of garbled‑circuit based secure computation, further research is required to improve its security guarantees and computational efficiency for real‑world applications.