Brief announcement: breaking the O(nm) bit barrier, secure multiparty computation with a static adversary
Varsha Dani, Valerie King, Mahnush Movahedi +1 more
We describe scalable algorithms for secure multiparty computation (SMPC). We assume a synchronous message passing communication model, but 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 an 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 rational. In this model, we describe a Nash equilibrium protocol that solves SMPC and requires each player to send Õ(⁄n+mn) messages and perform Õ(⁄n+mn) 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 Θ(n, m)
ACM Symposium on Principles of Distributed Computing (PODC)•Jul 16, 2012•26 citations