Two-Threshold Broadcast and Detectable Multi-party Computation

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 withExtendedValidity: 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 withExtendedConsistency: 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.DetectableMulti-PartyComputation: 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.