Secure channels ⇒ MPC with honest majority ($t<n/2$) (Rabin–Ben-Or)

Free reduction · standard model · RB89

Statement

Over a synchronous network of secure point-to-point channels with a broadcast channel, every $n$-party functionality has a protocol that is statistically secure, with guaranteed output delivery, against a malicious adversary corrupting any $t<n/2$ of the parties — RB89.

Notes

• The protocol rests on a VSS with negligible error for $t<n/2$, given broadcast, built on information checking, which authenticates messages without cryptographic assumptions — RB89.
• Without a setup, the broadcast channel can be emulated over the point-to-point channels only for $t<n/3$ — LSP82.
• Concurrently, over secure communication lines, Beaver gave protocols tolerating any $t<n/2$ corrupted parties against a computationally unbounded adversary, improving the $t<n/3$ of BGW88 and CCD88 — Bea89.
• For $t<n/3$, perfect security against a malicious adversary is achievable without broadcast — BGW88; see Secure channels ⇒ MPC with honest majority ($t<n/3$).
• Rounds: over a complete network of private channels with broadcast, players with private inputs can evaluate any function in a constant number of rounds, independent of its circuit, assuming a one-way function and that a majority of the players follow the protocol; the players jointly compute a garbled circuit — BMR90.
• Computationally, enhanced trapdoor permutations give guaranteed output delivery against $t<n/2$ over authenticated channels with broadcast (GMW) — GMW87.