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
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 n-party 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 logarithmic-depth
formulae that 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 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.
Back to
list of Oded's choices.