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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2013
Keywords
Multiparty computationMPCthreshold formulae
Contact author(s)
ron rothblum @ weizmann ac il
History
2013-08-14: received
Short URL
https://ia.cr/2013/480
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/480,
      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{https://eprint.iacr.org/2013/480}},
      url = {https://eprint.iacr.org/2013/480}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.