Garbled Circuits

Imagine Alice and Bob want to settle a delicate question: who earns more? Neither wants to disclose their actual salary. A trusted referee could solve it instantly — but there is no trusted referee.

For decades this looked like a paradox. Then, in 1986, Andrew Yao presented a stunning answer: two parties can jointly evaluate any function on their private inputs, and at the end each learns only the output — nothing more. The technique is called garbled circuits.

The idea is audacious. A Boolean circuit is an exact recipe for a computation: AND gates, OR gates, NOT gates wired together. Yao showed how to encrypt every gate so that the evaluator can compute the circuit's output without ever knowing what values flow through its wires. The result is provably secure under standard cryptographic assumptions — a rare guarantee in a field full of heuristics.

Garbled circuits are the foundation of secure multi-party computation (MPC), a branch of cryptography that asks: what can mistrusting parties compute together, and what must forever stay hidden? The answer turns out to be: almost anything, and what stays hidden is everything except the agreed output.

This is Yao's Millionaires' Problem: Alice and Bob each pick a secret wealth level (1–8). The garbled circuit compares them and announces who is richer — without either party learning the other's number.

<p class="hint">
  {{hint}}
</p>
<div class="inputs">
  <div class="party alice-side">
    <div class="label">{{alice_wealth}}</div>
    <div class="slider-row">
      <input id="alice-slider" type="range" min="1" max="8" value="5" class="slider alice-slider">
      <span class="val-badge alice-badge" id="alice-val">5</span>
    </div>
    <div class="secret-hint">{{alice_secret}}</div>
  </div>
  <div class="vs">VS</div>
  <div class="party bob-side">
    <div class="label">{{bob_wealth}}</div>
    <div class="slider-row">
      <input id="bob-slider" type="range" min="1" max="8" value="3" class="slider bob-slider">
      <span class="val-badge bob-badge" id="bob-val">3</span>
    </div>
    <div class="secret-hint">{{bob_secret}}</div>
  </div>
</div>
<button id="run-btn" type="button">{{run_btn}}</button>
<div id="circuit-vis" class="circuit-vis hidden"></div>
<div id="result" class="result hidden"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px .5rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.inputs { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .9rem; }
.party { flex: 1; min-width: 140px; padding: .7rem .8rem; border-radius: 10px; }
.alice-side { background: #e8f0ff; border: 1px solid #b3c8f5; }
.bob-side   { background: #fff0e8; border: 1px solid #f5c8a0; }
.label { font-weight: 700; font-size: .95rem; margin-bottom: .4rem; }
.slider-row { display: flex; align-items: center; gap: .5rem; }
.slider { flex: 1; cursor: pointer; }
.alice-slider { accent-color: #3a6bc4; }
.bob-slider   { accent-color: #c47a3a; }
.val-badge { font: 700 1.1rem ui-monospace, monospace; min-width: 1.8rem; text-align: center;
             padding: .2rem .4rem; border-radius: 6px; }
.alice-badge { background: #3a6bc4; color: #fff; }
.bob-badge   { background: #c47a3a; color: #fff; }
.secret-hint { font-size: .75rem; color: #777; margin-top: .3rem; }
.vs { font: 700 1.1rem system-ui; color: #888; flex: 0; }
button { font: 600 14px system-ui; padding: .5rem 1.1rem; border: none;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; margin-bottom: .9rem; }
button:hover { background: #274d82; }
.hidden { display: none; }
.circuit-vis { background: #f4f6fa; border: 1px solid #d0d8e8; border-radius: 10px;
               padding: .7rem .8rem; margin-bottom: .7rem; font-size: .83rem; }
.circuit-vis h4 { margin: 0 0 .4rem; font-size: .9rem; color: #1d3557; }
.step { margin: .25rem 0; color: #333; line-height: 1.6; }
.step b { color: #1d3557; }
.bit-row { display: inline-flex; gap: .3rem; align-items: center; }
.chip { display: inline-block; width: 1.6rem; height: 1.6rem; line-height: 1.6rem;
        text-align: center; border-radius: 4px; font: 600 .75rem ui-monospace, monospace; }
.chip-enc { background: #dce8f0; color: #1d3557; border: 1px solid #b3c8d8; }
.chip-bit { background: #e8f0dc; color: #3a5a10; border: 1px solid #b3c8a0; }
.result { text-align: center; font-size: 1.1rem; font-weight: 700;
          padding: .7rem 1rem; border-radius: 10px; }
.result.alice-wins { background: #dbeafe; color: #1d4ed8; border: 1.5px solid #93c5fd; }
.result.bob-wins   { background: #ffedd5; color: #c2410c; border: 1.5px solid #fdba74; }
.result.tie        { background: #f0fdf4; color: #166534; border: 1.5px solid #86efac; }

// Code not found

Each wire in the circuit carries an encrypted label instead of a plain 0 or 1. Alice garbles the circuit (encrypts every gate); Bob evaluates it using only the labels he receives — he can decrypt the final output but cannot reverse-engineer Alice's input, and Alice never sees Bob's input at all. Only the comparison result is revealed.

How does the security actually work, and what does it cost?

The garbling construction. For each gate, Alice creates a truth table with the output wire's label for every combination of input labels. She then double-encrypts each row using the two input labels as keys, and randomly permutes the rows. Bob receives a garbled gate: he can decrypt exactly one row (using the labels he holds) and learns the output label — but the permutation hides which row, so he learns nothing about the underlying bits.

Oblivious Transfer. Bob needs the label that corresponds to his input bit without Alice learning which bit he chose. This is handled by Oblivious Transfer (OT): a cryptographic primitive in which Alice sends two messages and Bob receives exactly one, with neither party learning what the other did. OT is the only place where Bob's private input enters the protocol.

Security model. Yao's original proof covers semi-honest (honest-but-curious) adversaries — parties that follow the protocol but try to extract extra information. Extending to malicious adversaries (who may deviate) requires additional techniques such as cut-and-choose or authenticated garbling, at a moderate extra cost.

Efficiency. A garbled circuit grows linearly with the circuit size (number of gates). Key optimizations, proved secure after Yao's original work, dramatically reduce the cost:

• Free XOR (Kolesnikov & Schneider, 2008): XOR gates cost zero extra ciphertexts.
• Half Gates (Zahur, Rosulek & Evans, 2015): AND gates need only 2 ciphertexts instead of 4.

The result is a framework that is provably secure yet fast enough for real deployments — a rare combination. Compare this with factoring, where we rely on hardness without a proof, or P vs NP, which remains open. Garbled circuits sit in the happy middle: concrete security reductions, concrete efficiency.

Any time two parties must jointly compute on data they cannot share, garbled circuits (or close relatives) are the tool of choice:

• Private set intersection: two hospitals find patients in common without revealing their full patient lists — used for contact tracing and fraud detection.
• Private auctions: bidders submit sealed bids; the winner is determined without any bid ever being revealed — deployed in ad-auction research.
• Secure machine learning: a model owner and a data owner jointly run inference; the model weights and the user's query both stay private. Companies like Enveil and Duality Technologies build products on this.
• Genomic privacy: researchers compare genomic sequences across institutions without exposing individual genomes — active area in precision medicine.
• Financial compliance: banks check each other's transaction lists for money-laundering patterns without exposing customer data.

The common thread: computation is public, inputs are private. Garbled circuits encode the computation in a form that is executable without being readable. That distinction — between running a program and seeing its data — is the conceptual gift Yao gave to cryptography in 1986, and it keeps finding new applications.

Yao's garbled circuits answered a question that seemed paradoxical: two parties with no mutual trust can nevertheless jointly compute any function on their private inputs, and when they finish, each knows only what they agreed to learn.

The trick is elegant — encrypt a circuit gate by gate so the evaluator can run it blind — and it comes with a proof. Under standard cryptographic assumptions, the protocol leaks nothing beyond the output. Optimizations like Free XOR and Half Gates bring the cost low enough for production systems.

We live in an era of massive joint data analysis — medical consortia, financial networks, federated AI. Garbled circuits, and the broader field of secure multi-party computation they inspired, give those collaborations a mathematical guarantee: you can compute together without having to trust each other. That is a remarkable gift from theoretical cryptography to the practical world.