Two-Threshold Broadcast and Detectable Multi-Party Computation

Matthias Fitzi, Martin Hirt, Thomas Holenstein, and Jürg Wullschleger

Advances in Cryptology — EUROCRYPT 2003, Lecture Notes in Computer Science, Springer-Verlag, vol. 2656, pp. 51–67, May 2003.

Classical distributed protocols like broadcast or multi-party computation provide security as long as the number of malicious players $f$ is bounded by some given threshold $t$ , i.e., $f \leq t$ . If $f$ exceeds $t$ then these protocols are completely insecure.

We relax this binary concept to the notion of two-threshold security: Such protocols guarantee full security as long as $f \leq t$ for some small threshold $t$ , and still provide some degraded security when $t < f \leq T$ for a larger threshold $T$ . In particular, we propose the following problems.

$\circ$ Broadcast with Extended Validity: Standard broadcast is achieved when $f \leq t$ . When $t < f \leq T$ , then either broadcast is achieved, or every player learns that there are too many faults. Furthermore, when the sender is honest, then broadcast is always achieved.

$\circ$ Broadcast with Extended Consistency: Standard broadcast is achieved when $f \leq t$ . When $t < f \leq T$ , then either broadcast is achieved, or every player learns that there are too many faults. Furthermore, the players agree on whether or not broadcast is achieved.

$\circ$ Detectable Multi-Party Computation: Secure computation is achieved when $f \leq t$ . When $t < f \leq T$ , then either the computation is secure, or all players detect that there are too many faults and abort.

The above protocols for $n$ players exist if and only if $t = 0$ or $t + 2 T < n$ .

BibTeX Citation

@inproceedings{FHHW03,
    author       = {Matthias Fitzi and Martin Hirt and Thomas Holenstein and Jürg Wullschleger},
    title        = {Two-Threshold Broadcast and Detectable Multi-Party Computation},
    editor       = {Eli Biham},
    booktitle    = {Advances in Cryptology --- EUROCRYPT 2003},
    pages        = {51--67},
    series       = {Lecture Notes in Computer Science},
    volume       = {2656},
    year         = {2003},
    month        = {5},
    publisher    = {Springer-Verlag},
}