Introduction

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.

Who Is Richer?

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">
  Pick a secret wealth level for <b>Alice</b> and <b>Bob</b> (1–8). Press <b>Garble &amp; Evaluate</b> to run the secure comparison — neither party learns the other’s number, only who is richer.
</p>
<div class="inputs">
  <div class="party alice-side">
    <div class="label">Alice’s 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">(secret — Bob cannot see this)</div>
  </div>
  <div class="vs">VS</div>
  <div class="party bob-side">
    <div class="label">Bob’s 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">(secret — Alice cannot see this)</div>
  </div>
</div>
<button id="run-btn" type="button">Garble &amp; Evaluate</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Garbled Circuits — Yao’s Millionaires’ Problem (pedagogical simulation).
//
// Scheme: Point-and-Permute with output-bit encryption.
// Each wire has two labels: w0 (bit=0, color=0) and w1 (bit=1, color=1).
// The color bit (LSB of label) lets the evaluator pick the right garbled row without learning which bit it represents.
//
// Gate encryption: each row stores (outBit XOR PRF(La, Lb, gateIdx, rowIdx)).
// The evaluator decrypts the correct row using its held labels and recovers the output label — but cannot learn the underlying bit from the label alone.
//
// Circuit: 3-bit comparison a > b via:
//   NOT(b[i]), gt[i] = a[i] AND NOT(b[i]), eq[i] = XNOR(a[i], b[i])
//   result = gt[0] OR (eq[0] AND (gt[1] OR (eq[1] AND gt[2])))

const aliceSlider = document.getElementById('alice-slider');
const bobSlider   = document.getElementById('bob-slider');
const aliceValEl  = document.getElementById('alice-val');
const bobValEl    = document.getElementById('bob-val');
const runBtn      = document.getElementById('run-btn');
const circuitVis  = document.getElementById('circuit-vis');
const resultEl    = document.getElementById('result');

aliceSlider.addEventListener('input', () => { aliceValEl.textContent = aliceSlider.value; });
bobSlider.addEventListener('input',   () => { bobValEl.textContent   = bobSlider.value;   });

// --- Toy PRF (xorshift-based; real garbling uses AES) ---
function xorshift(s) {
  s = s >>> 0;
  s ^= s << 13; s ^= s >>> 17; s ^= s << 5;
  return s >>> 0;
}
function prf1bit(La, Lb, gateIdx, rowIdx) {
  // Returns a single pseudorandom bit from two label inputs + position
  let h = xorshift((La ^ 0xca5cad3e) >>> 0);
  h = xorshift((h ^ Lb ^ 0x5ec3e770) >>> 0);
  h = xorshift((h ^ ((gateIdx * 53 + rowIdx * 7) >>> 0)) >>> 0);
  return h & 1;
}

// --- Wire labels ---
// w0: color bit = 0 (even number), w1: color bit = 1 (odd number)
function freshWire() {
  const rnd = () => ((Math.random() * 0x7ffffffe | 0) + 1) >>> 0;
  return { w0: (rnd() & ~1) >>> 0, w1: (rnd() | 1) >>> 0 };
}

let gc = 0; // global gate counter

// Two-input garbled gate
function garbleGate(type, wireA, wireB) {
  const fns = {
    AND:  (a,b) => a & b,
    OR:   (a,b) => a | b,
    XOR:  (a,b) => a ^ b,
    XNOR: (a,b) => (~(a ^ b)) & 1
  };
  const fn = fns[type];
  const out = freshWire();
  const gateIdx = gc++;
  const table = new Array(4);
  for (let ia = 0; ia <= 1; ia++) {
    for (let ib = 0; ib <= 1; ib++) {
      const La = ia ? wireA.w1 : wireA.w0;
      const Lb = ib ? wireB.w1 : wireB.w0;
      const outBit = fn(ia, ib) & 1;
      const rowIdx = ((La & 1) << 1) | (Lb & 1);
      const pad = prf1bit(La, Lb, gateIdx, rowIdx);
      table[rowIdx] = (outBit ^ pad) & 1;
    }
  }
  return { table, outW0: out.w0, outW1: out.w1, gateIdx };
}

// One-input NOT gate
function garbleNOT(wireA) {
  const out = freshWire();
  const gateIdx = gc++;
  const table = new Array(2);
  for (let ia = 0; ia <= 1; ia++) {
    const La = ia ? wireA.w1 : wireA.w0;
    const outBit = (1 - ia) & 1;
    const rowIdx = La & 1;
    const pad = prf1bit(La, 0, gateIdx, rowIdx);
    table[rowIdx] = (outBit ^ pad) & 1;
  }
  return { table, outW0: out.w0, outW1: out.w1, gateIdx, isNOT: true };
}

function evalGate(gate, La, Lb) {
  const rowIdx = ((La & 1) << 1) | (Lb & 1);
  const pad = prf1bit(La, Lb, gate.gateIdx, rowIdx);
  const outBit = (gate.table[rowIdx] ^ pad) & 1;
  return outBit ? gate.outW1 : gate.outW0;
}

function evalNOT(gate, La) {
  const rowIdx = La & 1;
  const pad = prf1bit(La, 0, gate.gateIdx, rowIdx);
  const outBit = (gate.table[rowIdx] ^ pad) & 1;
  return outBit ? gate.outW1 : gate.outW0;
}

function gateWire(g) { return { w0: g.outW0, w1: g.outW1 }; }
function toHex(n) { return (n >>> 0).toString(16).padStart(8, '0'); }
function chip(cls, txt) { return '<span class="chip ' + cls + '">' + txt + '</span>'; }

runBtn.addEventListener('click', () => {
  gc = 0;
  const a = parseInt(aliceSlider.value); // 1-8
  const b = parseInt(bobSlider.value);   // 1-8

  // 3-bit big-endian (values 0-7)
  const aBits = [(a-1)>>2 & 1, (a-1)>>1 & 1, (a-1) & 1];
  const bBits = [(b-1)>>2 & 1, (b-1)>>1 & 1, (b-1) & 1];

  // Alice creates input wires
  const aWires = aBits.map(() => freshWire());
  const bWires = bBits.map(() => freshWire());

  // Build circuit
  const notBGates   = bWires.map(w => garbleNOT(w));
  const gtGates     = aWires.map((w, i) => garbleGate('AND',  w,                   gateWire(notBGates[i])));
  const eqGates     = aWires.map((w, i) => garbleGate('XNOR', w,                   bWires[i]));
  const innerGate   = garbleGate('AND', gateWire(eqGates[1]),  gateWire(gtGates[2]));
  const midGate     = garbleGate('OR',  gateWire(gtGates[1]),  gateWire(innerGate));
  const leftAndGate = garbleGate('AND', gateWire(eqGates[0]),  gateWire(midGate));
  const finalGate   = garbleGate('OR',  gateWire(gtGates[0]),  gateWire(leftAndGate));

  // Input labels: Alice uses her held labels; Bob receives his via OT
  const aliceHeld = aBits.map((bit, i) => bit ? aWires[i].w1 : aWires[i].w0);
  const bobHeld   = bBits.map((bit, i) => bit ? bWires[i].w1 : bWires[i].w0);

  // Bob evaluates
  const notB_ev    = notBGates.map((g, i) => evalNOT(g, bobHeld[i]));
  const gt_ev      = gtGates.map((g, i)   => evalGate(g, aliceHeld[i], notB_ev[i]));
  const eq_ev      = eqGates.map((g, i)   => evalGate(g, aliceHeld[i], bobHeld[i]));
  const inner_ev   = evalGate(innerGate,   eq_ev[1],   gt_ev[2]);
  const mid_ev     = evalGate(midGate,     gt_ev[1],   inner_ev);
  const leftAnd_ev = evalGate(leftAndGate, eq_ev[0],   mid_ev);
  const final_ev   = evalGate(finalGate,   gt_ev[0],   leftAnd_ev);

  // Alice reveals both output labels; Bob decodes
  const aWins = (final_ev === finalGate.outW1);
  const truth = (a > b);

  // Build trace display
  const encA  = aliceHeld.map(l => chip('chip-enc', toHex(l).slice(0,4))).join(' ');
  const encB  = bobHeld.map(l   => chip('chip-enc', toHex(l).slice(0,4))).join(' ');
  const gtB   = gt_ev.map((v, i)  => chip('chip-bit', v === gtGates[i].outW1  ? 1 : 0)).join(' ');
  const eqB   = eq_ev.map((v, i)  => chip('chip-bit', v === eqGates[i].outW1  ? 1 : 0)).join(' ');

  circuitVis.classList.remove('hidden');
  resultEl.classList.remove('hidden');

  circuitVis.innerHTML =
    fmt('<h4>Circuit evaluation trace</h4><div class="step">Alice’s wire labels (opaque to Bob):&nbsp;<span class="bit-row">%encA%</span></div><div class="step">Bob’s labels received via Oblivious Transfer:&nbsp;<span class="bit-row">%encB%</span></div><div class="step">a[i] > b[i] gate outputs:&nbsp;<span class="bit-row">%gtB%</span></div><div class="step">a[i] == b[i] (XNOR) outputs:&nbsp;<span class="bit-row">%eqB%</span></div><div class="step">Final garbled label: <b>%toHex%</b> → Alice reveals it means <b>%v%</b></div><div class="step" style="font-size:.78rem;color:#666;margin-top:.3rem">✓ Verified correct: circuit computed a > b = <b>%truth%</b>. Labels are opaque — the evaluator sees only encrypted values until the final reveal.</div>', { encA: encA, encB: encB, gtB: gtB, eqB: eqB, toHex: toHex(final_ev).slice(0,8), v: aWins ? '1 (Alice wins)' : '0 (not Alice)', truth: truth });

  if (a === b) {
    resultEl.className = 'result tie';
    resultEl.textContent = fmt('It’s a tie — both chose %a%. Circuit outputs 0 (not strictly greater).', { a: a });
  } else if (aWins) {
    resultEl.className = 'result alice-wins';
    resultEl.textContent = fmt('Alice is richer (%a% > %b%). Bob never learned Alice’s number.', { a: a, b: b });
  } else {
    resultEl.className = 'result bob-wins';
    resultEl.textContent = fmt('Bob is richer (%b% > %a%). Alice never learned Bob’s number.', { b: b, a: a });
  }

  console.log('a=%d b=%d truth=%s circuit=%s match=%s', a, b, truth, aWins, truth === aWins);
});
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/garbled-circuits/Content licensed under CC BY-NC 4.0.