MPC Problem & Yao's Garbled Circuits

MPC allows n parties, each holding private input x_i, to jointly compute f(x_1,...,x_n) without revealing their inputs to each other — as if a trusted third party computed it.

Yao's 1982 Millionaires' Problem: Alice and Bob want to know who is richer without disclosing their wealth. No trusted third party. MPC solves this with cryptographic guarantees.

1. Privacy: parties learn only the output and what they can infer from it. 2. Correctness: the output is correct even if some parties are corrupt. 3. Variants exist for semi-honest vs malicious adversaries.

Any function can be expressed as a Boolean circuit (AND, XOR, NOT gates). MPC protocols often work at the circuit level, evaluating each gate securely.

Alice (garbler) assigns two random labels per wire: one for 0, one for 1. She encrypts each gate's truth table under the input wire labels. Bob (evaluator) learns only the labels for his inputs via Oblivious Transfer.

Bob receives garbled tables (4 encryptions per AND gate). He decrypts exactly one row using his input labels, obtaining the output label — without learning whether it represents 0 or 1.

Attach a random "select bit" to each label. Bob uses the select bits to find the correct garbled row in O(1) instead of trying all four decryptions. Reduces computation by 4×.

Kolesnikov & Schneider (2008): choose a global offset Δ. Then label_1 = label_0 ⊕ Δ for every wire. XOR gates become free (no encryption needed), saving ~30% bandwidth.

Zahur et al. (2015): each AND gate requires only 2 ciphertexts (down from 4). Combined with Free-XOR, this halves the bandwidth of standard garbled circuits.

Classic garbled circuits are 2-party. Multi-party extensions (e.g., BMR protocol) parallelize garbling across all parties but require O(n²) communication. Practical for small n.

In Yao's garbled circuit protocol, how does Bob obtain the wire labels corresponding to his private input bits?

MPC lets parties compute jointly without revealing inputs. Garbled circuits encode Boolean functions as encrypted truth tables. Optimisations (Free-XOR, Half-Gates, Point-and-Permute) make them practical. OT delivers Bob's input labels privately.