Garbled Circuits & Yao's Two-Party Computation (2PC) Studio
Explore secure multi-party computation. Step through Alice (Garbler) and Bob (Evaluator) executing Yao's 2PC protocol, trace wire label double encryptions, simulate 1-out-of-2 Oblivious Transfer key delivery, and verify that neither party leaks their private input.
1. Target Function & Private Inputs
2. Yao's 3-Phase Execution Pipeline
3. State of the Art: Garbled Circuit Optimizations
| TECHNIQUE | AND GATE SIZE | XOR GATE SIZE | BENEFIT |
|---|---|---|---|
| Classic Yao (1986) | 4 Ciphertexts (64B) | 4 Ciphertexts (64B) | Baseline protocol |
| Point & Permute (1990) | 4 Ciphertexts | 4 Ciphertexts | Eliminates trial decryption; direct indexing |
| Free-XOR (2008) | 4 Ciphertexts | 0 Bytes (FREE!) | XOR gates require ZERO network transfer |
| Half-Gates (2015) | 2 Ciphertexts (32B) | 0 Bytes (FREE!) | Optimal theoretical 2-ciphertext bound |
⚠️ 5 Fatal Traps in Garbled Circuit Implementations
1. The Malicious Garbler Circuit Substitution Attack
In semi-honest Yao 2PC, Bob assumes Alice generates the agreed-upon circuit f(x,y). If Alice is malicious, she can silently garble a Trojan circuit that directly outputs Bob's private input y. Securing against malicious garblers requires expensive Cut-and-Choose or Dual Execution verification.
2. Reusing Wire Keys Across Multiple Protocol Runs
Wire keys W_0 and W_1 MUST be one-time pads. If Alice uses the same wire keys to evaluate two different inputs with Bob, Bob can combine the wire keys he received across both executions to decrypt multiple rows of the garbled table, recovering Alice's secret inputs.
3. Free-XOR Correlation Circularity Flaws
In Free-XOR, all wire keys satisfy W_1 = W_0 ^ R with a static global offset R. If the hash function used to encrypt AND gate ciphertexts is modeled as standard SHA-256 rather than a circular correlation-robust hash (e.g. CCR hash via AES), Bob can exploit key relations to extract R.
4. Oblivious Transfer Extension Base-OT Leakage
IKNP03 OT Extension uses ~128 public-key base OTs to generate millions of symmetric OTs. If the base OTs fail to enforce public-key subgroup validation or use insecure curve parameters, a malicious receiver can manipulate base matrices to learn Alice's input wire selections.
5. Boolean Circuit Gate Explosion in Integer Arithmetic
Compiling floating point math or 64-bit integer division into boolean gates produces millions of gates. For complex arithmetic, Arithmetic Secret Sharing (Beaver Triples / SPDZ) is orders of magnitude faster than Garbled Circuits. Garbled circuits excel primarily for non-linear operations (comparisons, AES, SHA).