Two-Threshold Broadcast and Detectable Multi-Party Computation
Matthias Fitzi, Martin Hirt, Thomas Holenstein, and Jürg Wullschleger
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\le 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\le t$ for some small threshold $t$, and still provide some degraded security when $t<f\le T$ for a larger threshold $T$. In particular, we propose the following problems.
$\circ$ Broadcast with Extended Validity: Standard broadcast is achieved when $f\le t$. When $t<f\le 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\le t$. When $t<f\le 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\le t$. When $t<f\le 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+2T<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},
}