Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary

Details Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary

2012-03-01

arxiv.org/abs/1203.0289v1

Computer Science

Data Structures and Algorithms

Scientific paper

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-\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 O((n+m)/n + \sqrt{n}) (where the O notation hides polylogarithmic factors) messages and perform O((n+m)/n + \sqrt{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 O((n+m)/n) messages and perform O((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 \theta(nm).

Affiliated with

Also associated with

No associations

Rating

Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-165336