Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary
Varsha Dani, Valerie Jean King, Mahnush Movahedi, Jared Saia · 2012
We describe scalable algorithms for secure multiparty computation (SMPC). We assume a synchronous message passing communication model, but unlike most related work, we do not assume the existence of a broadcast channel. Our main result holds for the case where there are n players, of which a 1/3 − fraction are controlled by an adversary, for any positive constant. We describe a SMPC algorithm for this model that requires each player to send Õ(n+mn + n) messages and perform Õ(n+mn + n) computations to compute any function f, where m is the size of a circuit to compute f. We also consider a model where all players are selfish but rational. In this model, we describe a Nash equilibrium protocol that solve SMPC and requires each player to send Õ(n+mn) messages and perform Õ( n+m n) computations. These results significantly improve over past results for SMPC which require each player to send a number of bits and perform a number of computations that is θ(nm). ar X iv