Paper 2010/106

Perfectly Secure Multiparty Computation and the Computational Overhead of Cryptography

Ivan Damgård, Yuval Ishai, and Mikkel Krøigaard

Abstract

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 $$ players to evaluate an arithmetic circuit of size $$ by performing a total of $$ arithmetic operations, plus an additive term which depends (polynomially) on $$ and the circuit depth, but only logarithmically on $$. 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 $$ and $$. The protocol provides perfect security with guaranteed output delivery in the presence of an active, adaptive adversary corrupting a $$ fraction of the players, for an arbitrary constant $$ and sufficiently large $$. The best previous protocols in this setting could only offer computational security with a computational overhead of $$, where $$ is a computational security parameter, or perfect security with a computational overhead of $$. 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 $$ soundness error in which the amortized computational overhead per gate is only {\em polylogarithmic} in $$, improving over the $$ overhead of the best previous protocols. Under stronger cryptographic assumptions, we obtain similar results for general secure two-party computation.