# Machinations

Efficient Secure Multiparty Computation
February 27, 2012, 10:31 pm
Filed under: Uncategorized | Tags: , , ,

Attached is a paper on a problem we’ve been working on for a while: an efficient algorithm for Secure Multiparty Computation (SMPC) against a static adversary.

In the SMPC problem, n players each have a private input, and their goal is to compute the value of a n-ary function, f, over the inputs, without revealing any information about the inputs. The problem is complicated by the fact that a hidden subset of the players are controlled by an adversary that actively tries to subvert this goal.

SMPC abstracts several important problems in distributed security, and so, not surprisingly, there have been thousands of papers written
in the last several decades addressing it. However, there is a striking barrier that prevents wide-spread use: current algorithms to solve SMPC are not resource efficient. In particular, if there are n players involved in the computation and the function f can be computed by a circuit with m gates, then most algorithms require each player to send a number of messages and perform a number of computations that is $\Omega(mn)$

We describe scalable algorithms for SMPC against a static adversary. We assume a partially 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-\epsilon$ fraction are controlled by an adversary, for $\epsilon$ any positive constant. We describe a SMPC algorithm for this model that requires each player to send $\tilde{O}(\frac{n+m}{n} + \sqrt n)$ messagesand perform $\tilde{O}(\frac{n+m}{n} + \sqrt n)$ computations to compute any function f, where m is the size of a circuit to compute f.