TR13-107 Authors: Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum

Publication: 9th August 2013 10:40

Downloads: 2936

Keywords:

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.