Efficient Multiparty Protocols via Log-Depth Threshold Formulae
by Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker,
Peter Bro Miltersen, Ran Raz, and Ron Rothblum
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).
We put forward a new approach for the design of efficient multiparty
The second step of our approach combines the player emulation technique of
Hirt and Maurer (J. Cryptology, 2000) with constructions of logarithmic-depth
formulae that compute threshold functions using only constant fan-in threshold
Using this approach, we simplify and improve on previous results in
cryptography and distributed computing. In particular:
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 n-party protocol
that achieves security against a constant fraction of corrupted parties.
The above results rely on the following complexity-theoretic contributions,
which may be of independent interest:
- 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.
- 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 that
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.
See ECCC TR13-107.
list of Oded's choices.