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:
  1. 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.
  2. 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: The above results rely on the following complexity-theoretic contributions, which may be of independent interest:

See ECCC TR13-107.

Back to list of Oded's choices.