Enhanced TDP ⇒ MPC with honest majority ($t<n/2$) (GMW)

Free reduction · standard model · GMW87, Gol04

Statement

If enhanced trapdoor permutations exist, every $n$-party functionality has a protocol over authenticated channels with broadcast that is computationally secure with guaranteed output delivery against a malicious adversary corrupting $t<n/2$ parties; private channels are emulated by public-key encryption, so no secure channels are assumed. This is GMW87’s completeness theorem for protocols with an honest majority — GMW87; the full statement and proof, for the second malicious model of Gol04, are in Gol04.

Notes

• Over secure channels the same guarantees hold unconditionally: against $t<n/3$ with perfect security (BGW) — BGW88 — and against $t<n/2$ with statistical security, given broadcast (Rabin–Ben-Or) — RB89.
• Without an honest majority, the same compiler gives only security with abort (GMW compiler), and complete fairness is impossible for some functionalities (no fair MPC from authenticated channels) — GMW87, Cle86.