[Busec] Crypto Reading Group, Friday (Nov. 9th) 10:00am to 12:00pm
huijial at gmail.com
Wed Nov 7 17:38:47 EST 2012
This Friday, we will have Mahnush Movahedi from University of New Mexico
speaking. We will meet at our usual time *10:00am to 12:00pm Friday (Nov.
9th) *morning, and place *STATA G 825*.
Title: Breaking the $O(nm)$ Bit Barrier: Secure Multiparty Computation
with a Static Adversary
In this talk, we describe a new scalable algorithm that can solve
Secure Multi-Party Computation (SMPC) over n players, with strictly
less than a 1/3 fraction of the players controlled by a static
adversary, and synchronous communication. For any function that can be
computed by a circuit with m gates, our algorithm requires each player
to send a number of bits and perform an amount of computation that are
both soft-O((n+m)/n+√n). This result significantly improves over past
results, which require each player to send a number of messages and
perform computation that are both θ(nm). We also consider a model
where all players are selfish but rational. In this model, we describe
a protocol that is a Nash equilibrium, solves SMPC, and requires each
player to send a number of bits and perform an amount of computation
that is soft-O((n+m)/n). Currently, we are working on adapting our
algorithms to a fully asynchronous model, where at most a 1/4 fraction
of the players are bad.
This is joint work with Varsha Dani, Valerie King and Jared Saia
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Busec