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.

Advertisements

Leave a Comment so far
Leave a comment



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: