*15:17*[Pub][ePrint] Efficient Multiparty Protocols via Log-Depth Threshold Formulae, by Gil Cohen, Ivan Bjerre Damg{\\aa}rd, Yuval Ishai, Jonas K\\\"{o}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.