Secure channels ⇒ MPC with honest majority () from linear secret sharing (Cramer–Damgård–Maurer)
Statement
Verifiable secret sharing and secure multi-party computation can be based efficiently on any linear secret-sharing scheme (LSSS) for the parties, provided its access structure allows VSS or MPC at all, through a generic construction of a multiplicative LSSS for the same access structure and a generic construction that builds verifiability into any LSSS; the approach applies to the information-theoretic and to the cryptographic setting — CDM00. In the information-theoretic setting over secure point-to-point channels, applied to the threshold structure with and Shamir’s scheme, this gives MPC with guaranteed output delivery against a malicious adversary corrupting any of the parties — CDM00. The LSSS is a parameter of the construction: Shamir’s scheme exists unconditionally — Sha79.
Notes
- The protocols are polynomial in the size of the LSSS — CDM00.
- For a general adversary structure, perfectly secure MPC exists against active adversaries if and only if no three corruptible sets cover all parties, and against passive adversaries if and only if no two do — HM97. For some adversary structures the LSSS-based protocols are polynomial in , while every earlier approach to MPC for non-threshold adversaries is provably super-polynomial — CDM00.