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 ≤
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 ≤
t for some small threshold
t, and still provide some degraded security when
t <
f ≤
T for a larger threshold
T. In particular, we propose the following problems.
| – |
Broadcast with
Extended
Validity: Standard broadcast is achieved when f ≤ t. When t < f ≤ 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.
|
| – |
Broadcast with
Extended
Consistency: Standard broadcast is achieved when f ≤ t. When t < f ≤ 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.
|
| – |
Detectable
Multi-Party
Computation: Secure computation is achieved when f ≤ t. When t < f ≤ 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.
|
Partially supported by the Packard Foundation.
Supported by the Swiss National Science Foundation, project no. 2000-066716.01/1.