1 Department of Computer Science, Science and Technology, Aarhus University2 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University3 Weizmann Institute4 Technion5 Department of Computer Science, Science and Technology, Aarhus University
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.
Lecture Notes in Computer Science: 33rd Annual Conference. Proceedings, Part II, 2013, p. 185-202
Main Research Area:
Lecture Notes in Computer Science
Advances in Cryptology – CRYPTO 2013International Cryptology Conference