GMW Protocol & Oblivious Transfer

The Goldreich-Micali-Wigderson (GMW) protocol evaluates Boolean circuits using XOR secret shares. Each wire value is split among all parties; they interact gate-by-gate.

Party i holds share s_i such that s_1 ⊕ s_2 ⊕ ... ⊕ s_n = w (the true wire value). XOR gates are free: each party locally XORs their shares.

For an AND gate on wires a,b: computing (a_1⊕a_2)(b_1⊕b_2) expands to cross-terms. Evaluating the cross-term a_i·b_j between parties i≠j requires Oblivious Transfer.

In a 1-out-of-2 OT, sender has messages (m_0, m_1), receiver has choice bit c. Receiver gets m_c; sender learns nothing about c; receiver learns nothing about m_{1-c}.

Based on Diffie-Hellman: receiver generates two public keys such that she knows the discrete log of only one. Sender encrypts each message under one key. Receiver decrypts only her chosen ciphertext.

Ishai et al. (2003): from k base OTs, generate m >> k OTs using only symmetric-key operations. IKNP extension reduces OT cost to ~3 AES calls per OT after a one-time setup.

Each AND gate needs one OT per party pair. With OT extension, pre-computing all OTs in an offline phase allows the online phase to be a single XOR exchange per gate.

Semi-honest GMW can be made malicious-secure using zero-knowledge proofs or cut-and-choose OT. The cost increases by 3-8× but guarantees security against cheating parties.

MASCOT (Keller et al.) extends OT to produce authenticated AND triples in the malicious model, enabling the SPDZ protocol — covered in the next lesson.

EMP-toolkit and MOTION implement GMW with OT extension. They achieve millions of AND gates per second between two parties over a LAN, making real applications feasible.

Why do XOR gates in the GMW protocol require no communication between parties?

GMW uses XOR secret shares over Boolean circuits. XOR gates are free; AND gates need OT. OT extension makes OT cheap. Malicious security adds ZKPs or cut-and-choose. Libraries like EMP achieve practical throughput for real applications.