IACR News item: 14 August 2013
Gil Cohen, Ivan Bjerre Damg{\\aa}rd, Yuval Ishai, Jonas K\\\"{o}lker, Peter Bro Miltersen, Ran Raz, Ron D. Rothblum
ePrint Report1. 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.
Additional news items may be found on the IACR news page.