Secure channels ⇒ MPC with honest majority ($t<n/3$) (BGW)

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

Statement

Over a synchronous complete network of secure point-to-point channels, every $n$-party functionality has a protocol that is perfectly secure, with guaranteed output delivery, against a malicious adversary corrupting any $t<n/3$ of the parties — 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 (Secure channels ⇒ Semi-honest MPC with honest majority ($t<n/2$)); both thresholds are optimal for perfect security — BGW88.
• Unconditionally secure MPC for $t<n/3$ with exponentially small error was obtained concurrently and independently (Chaum–Crépeau–Damgård) — CCD88.
• The BGW protocol has a complete simulation-based proof, whose final version also derives security against adaptive corruptions and in the UC framework — AL17.
• For $t<n/3$ a broadcast channel can be emulated over the point-to-point channels in time polynomial in $n$, so the theorem needs none — GM93.
• Against a malicious adversary corrupting $t<n/2$ parties, statistical security is achievable given a broadcast channel — RB89 (Secure channels ⇒ MPC with honest majority ($t<n/2$)).
• 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.
• Against adaptive active corruptions with $t<n/3$, statistical security is achievable with $O(|C|n)k+O(D{n}^2)k+\mathrm{poly}(n\lambda )$ bits of communication for a circuit of $|C|$ gates and multiplicative depth $D$ over a field of $k$-bit elements — DN07; perfect security with $O(n)$ field elements per multiplication, against $\Omega (n^3)$ for earlier perfectly secure protocols (Beerliová-Trubíniová–Hirt) — BH08.
• For a general adversary structure, perfectly secure MPC against active adversaries exists if and only if no three corruptible sets cover all parties — HM97. MPC can be based efficiently on any linear secret-sharing scheme whose access structure allows it, and for some adversary structures the resulting protocols are polynomial in $n$ where every earlier approach for non-threshold adversaries is provably super-polynomial (Cramer–Damgård–Maurer) — CDM00.