Garbled Circuits and GMW: Two Routes to General Multi-Party Computation and Their Trade-offs

Abstract

This article develops the two foundational constructions for general secure computation and the trade-off between them. Yao's garbled circuits let one party encrypt a boolean circuit gate by gate into a garbled form that the other party evaluates using input keys obtained through oblivious transfer, learning only the output; the protocol runs in a constant number of rounds but sends a large garbled table per gate. The GMW protocol instead secret-shares the inputs and evaluates the circuit gate by gate directly on the shares — exclusive-or gates handled locally and for free, and gates, done interactively via oblivious transfer — which generalizes to many parties and sends little per gate but takes a number of rounds proportional to the circuit's depth. It identifies oblivious transfer as the common cryptographic primitive both rely on, and oblivious-transfer extension as the advance that made both practical. The central engineering trade-off is rounds versus bandwidth: garbled circuits suit high-latency networks and deep circuits, GMW suits low-latency networks and shallow ones. It closes on modern hybrid practice and the AI stakes, where secure inference mixes both according to each layer's shape. The theme: any function can be computed securely by either garbling it whole or evaluating it gate by gate on shares, and the choice is a rounds-versus-bandwidth decision.

The remarkable fact that any function can be computed securely rests on two classic constructions from the 1980s, and nearly every modern secure-computation system descends from one or the other. Yao's garbled circuits encrypt the whole circuit once and evaluate it in a fixed number of communication rounds. The Goldreich-Micali-Wigderson (GMW) protocol secret-shares the inputs and walks the circuit gate by gate, generalizing naturally to many parties. They compute the same class of functions but with opposite communication profiles, and understanding their trade-off — rounds against bandwidth — is what lets an engineer choose the right one for a given network and computation.

Garbled circuits

Yao's garbled-circuit protocol is a two-party construction with a clear division of labor. One party, the garbler, takes the boolean circuit computing the agreed function and encrypts it: for each wire it picks two random keys, one representing zero and one representing one, and for each gate it builds a small encrypted table that, given the input-wire keys, yields the correct output-wire key and nothing else. The garbler sends this garbled circuit, together with the keys for its own inputs, to the other party.

The evaluator must obtain the keys corresponding to its own inputs without revealing what those inputs are and without learning the key for the other value. This is exactly what oblivious transfer provides: a two-message primitive in which the receiver learns the one message it selected and nothing about the other, while the sender learns nothing about which was chosen. Using oblivious transfer once per input bit, the evaluator gets precisely the keys for its actual inputs, then evaluates the garbled gates in order, decrypting its way from input keys to an output key, and finally decodes that key to the result.

The security is that the evaluator only ever sees one random key per wire and encrypted tables it can open along exactly one path, so it learns the output and nothing about the garbler's inputs or the intermediate values. The defining performance feature is round complexity: garbling and sending the circuit, doing the oblivious transfers, and evaluating take a constant number of rounds regardless of how deep the circuit is. The cost is bandwidth — each gate ships an encrypted table of several ciphertexts — so a garbled circuit is large.

The garbler encrypts the circuit; the evaluator obtains its input keys by oblivious transfer, evaluates gate by gate, and decodes the output.

\[\text{Oblivious transfer: receiver learns } m_b, \text{ not } m_{1-b}; \text{ sender does not learn } b\]

\[\text{Yao rounds} = O(1) \quad \text{(independent of circuit depth)}\]

The GMW protocol

GMW takes the opposite approach: rather than encrypting the whole circuit up front, it secret-shares the inputs among the parties and evaluates the circuit gate by gate directly on the shares, keeping every intermediate wire value secret-shared throughout. Each party holds a share of every wire, and the parties transform their shares as the computation proceeds, so no one ever sees a cleartext intermediate value. Only at the end do they combine shares of the output wires to reveal the result.

As with the sharing article, the two gate types cost very differently. Exclusive-or gates — the linear operation over bits — are computed locally: each party simply combines its own shares, with no communication at all. And gates — the non-linear operation — require the parties to interact, classically using oblivious transfer to compute a share of the product without revealing the shared bits. So the entire cost of a GMW computation is concentrated in the and gates, and specifically in the rounds of interaction they require.

The consequence is GMW's signature performance profile, the mirror image of Yao's. Because gates at the same depth can be handled together but successive layers must wait for the previous ones, the number of communication rounds is proportional to the multiplicative — the and — depth of the circuit. The bandwidth per gate, however, is small: no large garbled tables, just the short messages of an oblivious transfer. GMW also generalizes cleanly to any number of parties, where Yao's basic construction is two-party, which is why GMW-style share-based evaluation dominates multi-party settings.

\[\text{GMW: XOR gates local (free)}, \quad \text{AND gates interactive (OT)}\]

\[\text{GMW rounds} = O(\text{AND-depth of the circuit})\]

The rounds-versus-bandwidth trade-off

The two protocols compute the same functions but occupy opposite corners of the communication trade-off, and the table lays it out. Garbled circuits run in a constant number of rounds but send a large garbled table per gate, so their cost is bandwidth, not latency. GMW sends very little per gate but takes rounds proportional to circuit depth, so its cost is latency, not bandwidth. Neither is universally better; the right choice depends on the network and the circuit.

This makes the decision concrete. Over a high-latency link — parties in different data centers or across the internet, where each round trip is expensive — a constant-round garbled circuit wins, because GMW's many depth-proportional rounds would each pay the latency penalty. Over a low-latency link — machines in the same cluster — GMW's cheap rounds are nearly free and its low bandwidth wins, especially for shallow circuits. Deep circuits favor garbled circuits' round-independence; shallow, wide circuits favor GMW's low per-gate cost. The circuit's depth and the network's latency together point to one or the other.

Underneath both sits the same enabling primitive, oblivious transfer, and the same advance that made both practical. Oblivious transfer looks like it needs expensive public-key operations for every instance, which would be crippling for circuits with millions of gates. Oblivious-transfer extension removes that: a small number of true public-key oblivious transfers can be stretched into arbitrarily many cheap ones using only symmetric cryptography, so the per-gate cost of both Yao and GMW dropped by orders of magnitude. This shared foundation is why the two constructions are best seen as two strategies over a common primitive rather than unrelated designs.

Garbled circuits pay in bandwidth for constant rounds; GMW pays in rounds for low bandwidth per gate.

The two classic constructions compared.
Property	Garbled circuits (Yao)	GMW
Rounds	constant	proportional to circuit depth
Bandwidth	high (table per gate)	low (small per gate)
Parties	classically two	naturally multi-party
Best network	high-latency links	low-latency links

Modern practice, and the AI stakes

Real systems do not choose one construction dogmatically; they mix them. A protocol can garble the deep, latency-sensitive part of a computation while using GMW-style share evaluation for the shallow, bandwidth-sensitive part, and mixed frameworks convert between garbled and shared representations mid-computation to use whichever is cheaper for each segment. Oblivious-transfer extension underpins all of it, making the per-gate cryptography cheap enough that the remaining bottleneck is the rounds-versus-bandwidth balance the engineer tunes.

The same trade-off governs secure machine learning directly, because a neural network is a circuit with a characteristic shape. Its linear layers are wide and, in arithmetic form, shallow — well suited to low-round, share-based evaluation — while its non-linear activations are the deep, comparison-heavy parts that constant-round garbling handles more gracefully. Practical secure-inference systems therefore combine the two: shares for the matrix multiplications, garbled circuits for the non-linearities, converting between them at the layer boundaries. The rounds-versus-bandwidth decision is made per layer, not once for the whole model.

For collaborative AI this is the machinery that turns the MPC guarantee of the first article into running code. Two or more parties can jointly evaluate a model on their combined private inputs by expressing the inference as a circuit and evaluating it with garbled circuits, GMW, or a hybrid, revealing only the result. The choice of construction is a performance decision layered on top of the security guarantee, which either route provides equally. Understanding both — that any function can be computed securely either by garbling it whole or by evaluating it gate by gate on shares, at a rounds-versus-bandwidth trade-off mediated by oblivious transfer — is what lets a designer build collaborative machine learning that is not only secure but fast enough to use, which is the subject the remaining articles turn to.

📌

Two routes, one trade-off. Garbled circuits (garble once, evaluate) run in constant rounds but high bandwidth; GMW (secret-share, evaluate gate by gate) runs in low bandwidth but depth-many rounds. Both rest on oblivious transfer, made cheap by OT extension. Deep circuits and high-latency links favor garbling; shallow circuits and low-latency links favor GMW; real systems mix them.

Key takeaways

Yao's garbled circuits: one party encrypts the circuit gate by gate, the other evaluates it using input keys from oblivious transfer, in a constant number of rounds.
GMW: secret-share the inputs and evaluate gate by gate — XOR gates local and free, AND gates interactive via oblivious transfer — generalizing to many parties.
The trade-off is rounds versus bandwidth: garbling is constant-round but bandwidth-heavy; GMW is low-bandwidth but takes rounds proportional to circuit depth.
High-latency links and deep circuits favor garbled circuits; low-latency links and shallow circuits favor GMW.
Both rest on oblivious transfer, and oblivious-transfer extension made both practical by replacing per-gate public-key operations with cheap symmetric ones.
Secure ML inference mixes them per layer — shares for wide linear layers, garbling for deep non-linearities — realizing the MPC guarantee for collaborative AI.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

✅Choosing a secure-computation constructionchecklist

Questions that pick Yao, GMW, or a hybrid.

Is the network high-latency (favor constant-round garbling) or low-latency (favor GMW)?
Is the circuit deep (favor garbling) or shallow and wide (favor GMW)?
Are there two parties (Yao natural) or many (GMW natural)?
Is bandwidth or round-trip latency the binding constraint?
Would a hybrid — shares for linear layers, garbling for non-linearities — fit the model best?

🚀The two-construction mental modelquickstart

Three facts to hold onto.

Garbled circuits: constant rounds, high bandwidth, classically two-party.
GMW: depth-many rounds, low bandwidth, naturally multi-party.
Both use oblivious transfer, made cheap by OT extension.

🔒Construction-selection stancepolicy

A stub recording the Yao/GMW decision.

secure_computation:
  constructions:
    garbled_circuits: { rounds: constant, bandwidth: high, parties: two }
    gmw: { rounds: depth, bandwidth: low, parties: many }
  shared_primitive: oblivious_transfer
  optimization: ot_extension
  ml_inference:
    linear_layers: gmw_shares
    non_linearities: garbled_circuits

Illustrative documentation template, not a product config.

Glossary

Garbled circuit (Yao): A two-party protocol where one party encrypts a boolean circuit gate by gate and the other evaluates it, in constant rounds.
GMW protocol: A multi-party protocol that secret-shares inputs and evaluates a circuit gate by gate on the shares, with rounds proportional to depth.
Oblivious transfer (OT): A primitive where the receiver learns one of two messages of its choice and nothing about the other, and the sender learns nothing about the choice.
OT extension: A technique that stretches a few public-key oblivious transfers into many cheap symmetric-key ones, making Yao and GMW practical.
Round complexity: The number of sequential communication rounds a protocol requires; constant for Yao, depth-proportional for GMW.
AND-depth: The number of AND (multiplicative) gates in series in a circuit, which drives GMW's round count.