Abstract | ||
---|---|---|
We put forward a new approach for the design of efficient multiparty protocols: 1. Design a protocol p for a small number of parties (say, 3 or 4) which achieves security against a single corrupted party. Such protocols are typically easy to construct, as they may employ techniques that do not scale well with the number of corrupted parties. 2. Recursively compose p with itself to obtain an efficient n-party protocol which achieves security against a constant fraction of corrupted parties. The second step of our approach combines the "player emulation" technique of Hirt and Maurer (J. Cryptology, 2000) with constructions of logarithmic-depth formulae which compute threshold functions using only constant fan-in threshold gates. Using this approach, we simplify and improve on previous results in cryptography and distributed computing. In particular: -We provide conceptually simple constructions of efficient protocols for Secure Multiparty Computation (MPC) in the presence of an honest majority, as well as broadcast protocols from point-to-point channels and a 2-cast primitive. -We obtain new results on MPC over blackbox groups and other algebraic structures. The above results rely on the following complexity-theoretic contributions, which may be of independent interest: -We show that for every j, k is an element of N such that m =(Delta) k-1/j-1 is an integer, there is an explicit (poly(n)-time) construction of a logarithmic-depth formula which computes a good approximation of an (n/m)-out-of-n threshold function using only j-out-of-k threshold gates and no constants. - For the special case of n-bit majority from 3-bit majority gates, a non-explicit construction follows from the work of Valiant (J. Algorithms, 1984). For this special case, we provide an explicit construction with a better approximation than for the general threshold case, and also an exact explicit construction based on standard complexity-theoretic or cryptographic assumptions. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/978-3-642-40084-1_11 | ADVANCES IN CRYPTOLOGY - CRYPTO 2013, PT II |
DocType | Volume | ISSN |
Journal | 8043 | 0302-9743 |
Citations | PageRank | References |
4 | 0.39 | 39 |
Authors | ||
7 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gil Cohen | 1 | 119 | 16.43 |
Ivan Bjerre Damgård | 2 | 10 | 1.18 |
Yuval Ishai | 3 | 4364 | 246.22 |
jonas | 4 | 10 | 2.19 |
Peter Bro Miltersen | 5 | 1146 | 94.49 |
Ran Raz | 6 | 2772 | 180.87 |
Ron D. Rothblum | 7 | 132 | 12.48 |