Abstract
We put forward a new approach for the design of efficient multiparty protocols:
Design a protocol π 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.
Recursively compose π 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 ∈ ℕ such that m≜k−1j−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.
Design a protocol π 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.
Recursively compose π 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 ∈ ℕ such that m≜k−1j−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.
| Originalsprog | Engelsk |
|---|---|
| Titel | Advances in Cryptology – CRYPTO 2013 : 33rd Annual Conference. Proceedings, Part II |
| Redaktører | Ran Canetti, Juan A. Garay |
| Antal sider | 18 |
| Forlag | Springer VS |
| Publikationsdato | 1 jan. 2013 |
| Sider | 185-202 |
| ISBN (Trykt) | 978-3-642-40083-4 |
| ISBN (Elektronisk) | 978-3-642-40084-1 |
| DOI | |
| Status | Udgivet - 1 jan. 2013 |
| Begivenhed | Annual International Cryptology Conference: 33rd Annual Cryptology Conference - Santa Barbara, CA, USA Varighed: 18 aug. 2013 → 22 aug. 2013 Konferencens nummer: 33 |
Konference
| Konference | Annual International Cryptology Conference |
|---|---|
| Nummer | 33 |
| Land/Område | USA |
| By | Santa Barbara, CA |
| Periode | 18/08/2013 → 22/08/2013 |
| Navn | Lecture Notes in Computer Science |
|---|---|
| Vol/bind | 8043 |
| ISSN | 0302-9743 |