Efficient Multiparty Protocols via LogDepth Threshold Formulae
by Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker,
Peter Bro Miltersen, Ran Raz, and Ron Rothblum
Oded's comments
A point I wish to highlight regarding the second step in the
construction is that while Hirt and Maurer employed the
player emulation idea to a formula that arises naturally
in their setting (i.e., a formula that describes the access
structure for which security is to hold), here the formula
is an artificial construct (since threshold functions
are evident without relying on a formula that describes them).
The abstract
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) that
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 nparty protocol
that 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 logarithmicdepth
formulae that compute threshold functions using only constant fanin 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 pointtopoint channels
and a 2cast primitive.
 We obtain new results on MPC over blackbox groups
and other algebraic structures.
The above results rely on the following complexitytheoretic contributions,
which may be of independent interest:
 We show that for every integers j,k
such that $m = (k1)/(j1)$ is an integer,
there is an explicit (poly(n)time) construction
of a logarithmicdepth formula that
computes a good approximation of an (n/m)outofn threshold function
using only joutofk threshold gates and no constants.
 For the special case of nbit majority from 3bit majority gates,
a nonexplicit 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 complexitytheoretic or cryptographic assumptions.
See ECCC TR13107.
Back to
list of Oded's choices.