Scalable and Unconditionally Secure Multiparty Computation

We present a multiparty computation protocol that is unconditionally secure against adaptive and active adversaries, with communication complexity

$\mathcal{O}(\mathcal{C} n) k + \mathcal{O}(D n^2) k + {\rm poly}(n \kappa)$

, where

$\mathcal{C}$

is the number of gates in the circuit,

n

is the number of parties,

k

is the bit-length of the elements of the field over which the computation is carried out,

D

is the multiplicative depth of the circuit, and

κ

is the security parameter. The corruption threshold is

t

 < 

n

/3. For passive security the corruption threshold is

t

 < 

n

/2 and the communication complexity is

$\mathcal{O}(n \mathcal{C}) k$

. These are the first unconditionally secure protocols where the part of the communication complexity that depends on the circuit size is linear in

n

. We also present a protocol with threshold

t

 < 

n

/2 and complexity

$\mathcal{O}(\mathcal{C} n) k + {\rm poly}(n \kappa)$

based on a complexity assumption which, however, only has to hold

during

the execution of the protocol – that is, the protocol has so called everlasting security.