Semi-honest MPC + OWF ⇒ MPC (GMW compiler)
Statement
If every functionality has a protocol secure against semi-honest adversaries corrupting any number of parties and one-way functions exist, then every functionality has a protocol secure with abort against malicious adversaries corrupting any number of parties — GMW87.
Sketch
Each party commits to its input with a zero-knowledge proof of knowledge of it, the parties generate each party’s random tape by coin tossing into the well, so that the party learns its tape and the others hold a commitment to it, and every message of the semi-honest protocol is accompanied by a zero-knowledge proof that it is consistent with the committed input, the committed tape and the messages so far. Commitments, coin tossing and zero-knowledge proofs for all follow from one-way functions, and a malicious party is thereby forced to behave semi-honestly or be caught — Gol04.
Notes
- Semi-honest protocols for every functionality follow from semi-honest OT (OT ⇒ MPC) — GMW87 — and from enhanced trapdoor permutations, through enhanced TDP ⇒ OT — EGL85, Gol04.
- With a dishonest majority, complete fairness cannot be guaranteed for every functionality: two-party coin flipping cannot be made fair — Cle86. With an honest majority, the compiled protocol can be made to guarantee output delivery — GMW87.