TY - GEN

T1 - Perfectly secure multiparty computation and the computational overhead of cryptography

AU - Damgård, I.

AU - Ishai, Y.

AU - Krøigård, M.

PY - 2010

Y1 - 2010

N2 - 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 $\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-\epsilon)$ fraction of the players, for an arbitrary constant $\epsilon>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 $\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 {\em polylogarithmic} in $k$, improving over the $\omega(k)$ overhead of the best previous protocols. Under stronger cryptographic assumptions, we obtain similar results for general secure two-party computation.

AB - 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 $\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-\epsilon)$ fraction of the players, for an arbitrary constant $\epsilon>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 $\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 {\em polylogarithmic} in $k$, improving over the $\omega(k)$ overhead of the best previous protocols. Under stronger cryptographic assumptions, we obtain similar results for general secure two-party computation.

U2 - 10.1007/978-3-642-13190-5_23

DO - 10.1007/978-3-642-13190-5_23

M3 - Conference contribution

SN - 978-3-642-13189-9

T3 - Lecture Notes in Computer Science

SP - 445

EP - 465

BT - Advances in Cryptology - Eurocrypt 2010 (29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Nice, France, May 30-June 3, 2010. Proceedings)

A2 - Gilbert, H.

PB - Springer

CY - Berlin

ER -