Honest majority ($t<n/3$) ⇒ MPC

Free reduction · standard model · BGW88 · security loss: none (perfect security)

Statement

In the secure-channels model, every $n$-party functionality has an MPC protocol that is perfectly secure against a malicious adversary corrupting any $t<n/3$ of the parties (honest majority) — BGW88.

Sketch

Each party Shamir-shares its input with a degree-$t$ polynomial; addition gates are local, and at a multiplication gate each party shares the product of its two shares and the parties take the Lagrange combination of these sub-sharings, a degree-$t$ sharing of the product. Against malicious parties every sharing is verifiable and every product sharing is checked, and opening a degree-$t$ sharing with $t$ corrupted shares is Reed–Solomon decoding, which needs $n\ge 3t+1$.

Notes

• Against a semi-honest adversary, perfect security holds for $t<n/2$ in the same model; both thresholds are optimal for perfect security — BGW88.
• Unconditionally secure MPC for $t<n/3$ with exponentially small error was obtained concurrently and independently — CCD88.
• The BGW protocol has a complete simulation-based proof — AL17.
• Against a malicious adversary corrupting $t<n/2$ parties, statistical security is achievable given a broadcast channel — RB89 (Honest majority ($t<n/2$) ⇒ MPC).
• Efficiency: additions are local. In the semi-honest protocol each multiplication gate needs a degree-reduction step in which every party sends one share to every other, $O(n^2)$ field elements, and the number of rounds grows with the multiplicative depth of the circuit — standard. Against malicious adversaries a multiplication also needs verifiable subsharing and checks that every party shared its correct local product; the full BGW multiplication protocol then costs $O(n^6)$ field elements over point-to-point channels and broadcast in the worst case — ALR11.