Near-Linear Unconditionally-Secure Multiparty Computation With a Dishonest Minority
Secure MultiParty Computation (MPC) allows a set of n players to compute any public function, given as an arithmetic circuit, on private inputs, so that privacy of the inputs as well as correctness of the output are guaranteed. Of special importance both in cryptography and in complexity theory is the setting of information-theoretic MPC, where (dishonest) players are unbounded, and no cryptographic assumptions are used. In this setting, it was known since the 1980's that an honest majority of players is both necessary and sufficient to achieve privacy and correctness. The main open question that was left in this area is to establish the exact communication complexity of MPC protocols that can tolerate malicious behavior of a minority of dishonest players.