How MPC Security Is Actually Proven (Real/Ideal)

Why this matters

If someone hands you a protocol and says 'it's secure', the only honest response is 'against what, exactly?' MPC has a precise answer: a protocol is secure if anything an adversary can learn in the real protocol could have been simulated in an ideal world where inputs are handed to a trusted party and outputs are handed back. This is called the simulation paradigm — every real-world attack must be reproducible given only the ideal-world view, which means no extra information leaked. Without this framework, security claims are folk theorems. Every paper you read in this course will rest on a simulation proof somewhere.

Demo

Below is a toy coin-toss protocol (Blum, 1983) plus the shape of its simulator. Don't memorize the cryptography — memorize the structure: real view ↔ simulator output, and the simulator only gets to call the ideal functionality.

Real protocol (between Alice and Bob):
  1. Alice picks random bit a, sends hash(a, r_a) where r_a is fresh randomness.
  2. Bob picks random bit b, sends b.
  3. Alice reveals (a, r_a). Both output c = a XOR b.
 
Ideal world:
  1. Both parties send nothing to each other.
  2. A trusted functionality F_CoinToss picks c uniformly, sends it to both.
 
Security claim: a PPT adversary controlling Bob sees (commit, opening) in real,
but the simulator can produce an indistinguishable transcript knowing only c.
  - On input c from F_CoinToss, simulator picks a := c XOR b_sim,
    then produces a valid commitment to a with uniform randomness.
  - The real and simulated Bob-views differ only by the indistinguishability
    of the commitment scheme.
 
Why this matters in practice: every SPDZ MAC check, every ZK argument, every
OT composition lemma in this course is phrased as "here's a simulator."
If you can't write the simulator, you don't have a security proof.

Try it yourself

1. Write the simulator for the Alice-corrupted case — what does the simulator have to produce to make Alice's view indistinguishable from real? Which ideal-functionality query does it make?
2. Suppose the hash function is replaced with the identity function (hash(x) = x). Trace through where the simulation proof breaks — the protocol is now trivially broken; your simulator can't hide the bit.
3. Draw the three boxes — real world, ideal world, simulator — and label exactly what each party sees in each. If you can't draw this from memory, you don't yet understand any MPC security proof.
4. Find one MPC paper you're curious about (pick anything — Yao, GMW, SPDZ). Locate the simulation proof. Don't read it — just note the structure: what does the simulator get, what does it output, what hybrid argument closes the gap?

References

• Lindell — How to Simulate It
• Canetti — Security and Composition of Multi-party Protocols
• Goldreich — Foundations of Cryptography Vol 2, §7