# Two-Threshold Broadcast and Detectable Multi-Party Computation

## Matthias Fitzi and Martin Hirt and 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$ {\sc 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$ {\sc 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$ {\sc 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$.