We generalize the notion of broadcast by introducing an additional threshold $t^+\ge t$. In a {\em broadcast protocol with extended validity}, both consistency and validity are achieved when no more than $t$ players are corrupted, and validity is achieved even when up to $t^+$ players are corrupted. Similarly, we define {\em broadcast with extended consistency}. We prove that broadcast with extended validity as well as broadcast with extended consistency is achievable if and only if $t+2t^+<n$ (or $t=0$). For example, six players can achieve broadcast when at most one player is corrupted (this result was known to be optimal), but they can even achieve consistency (or validity) when two players are corrupted.
Furthermore, our protocols achieve {\em detection} in case of failure, i.e., if at most $t$ players are corrupted then broadcast is achieved, and if at most $t^+$ players are corrupted then broadcast is achieved or every player learns that the protocol failed. This protocol can be employed in the precomputation of a secure multi-party computation protocol, resulting in {\em detectable multi-party computation}, where up to $t$ corruptions can be tolerated and up to $t^+$ corruptions can either be tolerated or detected in the precomputation, for any $t,t^+$ with $t+2t^+<n$.
Category / Keywords: cryptographic protocols / Byzantine agreement, detectable precomputation, multi-party computation, unconditional security Date: received 26 Apr 2002 Contact author: hirt at inf ethz ch Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20020426:165404 (All versions of this report) Short URL: ia.cr/2002/053 Discussion forum: Show discussion | Start new discussion