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.