Paper 2013/480

Efficient Multiparty Protocols via Log-Depth Threshold Formulae

Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, and Ron D. Rothblum


We put forward a new approach for the design of efficient multiparty protocols: 1. 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. 2. 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 integers j,k such that m = (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.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2013
Multiparty computationMPCthreshold formulae
Contact author(s)
ron rothblum @ weizmann ac il
2013-08-14: received
Short URL
Creative Commons Attribution


      author = {Gil Cohen and Ivan Bjerre Damgård and Yuval Ishai and Jonas Kölker and Peter Bro Miltersen and Ran Raz and Ron D.  Rothblum},
      title = {Efficient Multiparty Protocols via Log-Depth Threshold Formulae},
      howpublished = {Cryptology ePrint Archive, Paper 2013/480},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.