Perfectly Secure Multiparty Computation and the Computational Overhead of Cryptography

We study the following two related questions:

What are the minimal computational resources required for general secure multiparty computation in the presence of an honest majority?

What are the minimal resources required for two-party primitives such as zero-knowledge proofs and general secure two-party computation?

We obtain a nearly tight answer to the first question by presenting a

perfectly

secure protocol which allows

n

players to evaluate an arithmetic circuit of size

s

by performing a total of

$\mathcal{O}(s\log s\log^2 n)$

arithmetic operations, plus an additive term which depends (polynomially) on

n

and the circuit depth, but only logarithmically on

s

. Thus, for typical large-scale computations whose circuit width is much bigger than their depth and the number of players, the amortized overhead is just polylogarithmic in

n

and

s

. The protocol provides perfect security with guaranteed output delivery in the presence of an active, adaptive adversary corrupting a (1/3 − 

ε

) fraction of the players, for an arbitrary constant

ε

> 0 and sufficiently large

n

. The best previous protocols in this setting could only offer

computational

security with a computational overhead of poly(

k

,log

n

,log

s

), where

k

is a computational security parameter, or perfect security with a computational overhead of

$\mathcal{O}(n\log n)$

.

We then apply the above result towards making progress on the second question. Concretely, under standard cryptographic assumptions, we obtain zero-knowledge proofs for circuit satisfiability with 2

− 

k

soundness error in which the amortized computational overhead per gate is only

polylogarithmic

in

k

, improving over the

ω

(

k

) overhead of the best previous protocols. Under stronger cryptographic assumptions, we obtain similar results for general secure two-party computation.