Welcome to the resource topic for 2010/106
Title:
Perfectly Secure Multiparty Computation and the Computational Overhead of Cryptography
Authors: Ivan Damgård, Yuval Ishai, 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 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.
ePrint: https://eprint.iacr.org/2010/106
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .