The millionaires' problem sounds like a party trick, but it is a stand-in for a large family of real needs. Two hospitals want to compute a statistic across their combined patient records without merging the records. Two companies want to find the customers they share without exposing their full customer lists. A phone wants to check whether any of your contacts already use a service, without handing the service your address book. Each of these is a computation over data that neither side is willing to reveal. Garbled circuits is one of the oldest and most direct ways to do it.
Any computation is a circuit
The starting observation is that any function you can compute can be written as a Boolean circuit: a graph of AND, XOR, and NOT gates wired together, taking input bits and producing output bits. Comparing two numbers, adding them, hashing them, running a small machine-learning model over them, all of it reduces to gates. Once a task is expressed as a circuit, the problem becomes narrow and mechanical: how do two parties evaluate this fixed circuit when one holds some of the input bits and the other holds the rest, and neither should see the other's bits or any intermediate wire value?
In Yao's protocol the two roles are asymmetric. One party, the garbler, encrypts the circuit. The other, the evaluator, runs the encrypted version and reads off the result. The trick is arranging the encryption so the evaluator can compute the correct output while learning nothing about the wires along the way.
Garbling a single gate
For every wire in the circuit, the garbler picks two random keys, called labels. One label secretly stands for the bit 0 on that wire, the other for the bit 1. Crucially, the labels look like random noise. Holding a label tells you nothing about whether it means 0 or 1.
Now take one gate, say an AND gate with input wires a and b and output wire c. The garbler writes out the gate's truth table and, for each of the four input combinations, encrypts the correct output label under the two matching input labels:
- Encrypt C₀ under (A₀, B₀) because 0 AND 0 = 0
- Encrypt C₀ under (A₀, B₁) because 0 AND 1 = 0
- Encrypt C₀ under (A₁, B₀) because 1 AND 0 = 0
- Encrypt C₁ under (A₁, B₁) because 1 AND 1 = 1
The garbler shuffles these four ciphertexts into a random order, so their position leaks nothing, and sends the pile to the evaluator. This shuffled set is the garbled gate. The evaluator, holding exactly one label for wire a and one for wire b, can decrypt exactly one of the four rows, and it yields exactly one label for wire c. The evaluator does not know whether that output label means 0 or 1. It just feeds it into the next gate. Do this gate by gate through the whole circuit and the evaluator ends up holding output labels for the final wires, which the garbler can translate back into real bits.
The evaluator only ever sees random-looking labels and can decrypt one row per gate. It never learns which bit any label represents, so intermediate values stay hidden. The garbler, having sent everything up front, sees no responses and learns nothing about the evaluator's inputs. Each side finishes knowing only the agreed output.
Oblivious transfer, the other half
One problem remains. The evaluator needs the labels for its own input bits, but those labels are known only to the garbler, and the garbler must not learn which bits the evaluator has. The garbler cannot simply send both labels for each input wire, because then the evaluator could try every combination. The answer is a second primitive: 1-out-of-2 oblivious transfer.
Oblivious transfer lets the garbler offer two values while the evaluator picks exactly one, with two guarantees. The evaluator receives only the value it chose and learns nothing about the other. The garbler never learns which value was chosen. Run once per input bit the evaluator holds, oblivious transfer delivers the right labels without exposing the evaluator's inputs. It is the piece that makes the asymmetry work, and it is a deep enough tool to carry secure computation on its own.
From a 1982 idea to something you can run
The plain version is expensive. A gate needs four ciphertexts, and real circuits have millions of gates. Decades of work drove that cost down:
- Point-and-permute lets the evaluator jump straight to the right row instead of trying to decrypt all four, using a couple of select bits attached to each label.
- Free-XOR makes every XOR gate cost nothing at all, by giving all label pairs a shared secret offset so XOR becomes a simple combination of labels.
- Half-gates cut an AND gate down to two ciphertexts instead of four, roughly halving the bandwidth of the expensive gates.
- Oblivious transfer extension turns a small number of real, costly transfers into millions of cheap ones, so input handling stops being the bottleneck.
There is also the question of what happens when a party cheats. The description above assumes both sides follow the protocol honestly and are only curious about what they can infer, the so-called semi-honest model. Defending against a party that actively deviates, the malicious model, costs more, and techniques like cut-and-choose exist to get there. Choosing the threat model is a real engineering decision, not a detail.
Where it fits among the privacy tools
Garbled circuits is one branch of a larger tree. It is a specific, efficient approach to two-party secure multiparty computation. Where it shines is arbitrary two-party functions with a fixed, known circuit. Other tools trade off differently:
| Tool | Best at | Cost profile |
|---|---|---|
| Garbled circuits | General two-party functions, low round count | Bandwidth-heavy, one big message |
| Homomorphic encryption | Outsourced computation on one party's ciphertext | Compute-heavy on the server |
| Private set intersection | Finding shared elements between two sets | Specialized and fast for that one job |
| Zero-knowledge proofs | Proving a statement without revealing why | One-directional, prover to verifier |
In production, garbled circuits and its relatives show up in private contact discovery, privacy-preserving auctions where bids stay sealed, fraud checks across banks that never pool their data, and inference on a model where the input and the weights belong to different owners. The common thread is a computation that has to happen across a trust boundary that neither side wants to dissolve.
For a secure messenger, the relevance is indirect but real. The hard problem of letting you find which of your contacts already use a service, without uploading your whole address book, lives in exactly this family of techniques. The design goal we hold to, at Haven and across this space, is to keep the amount of data that has to cross that boundary as small as the math allows. A forty-year-old thought experiment about two cagey millionaires turned out to be a surprisingly durable answer to that question.