Welcome to the resource topic for
**2002/053**

**Title:**

Extended Validity and Consistency in Byzantine Agreement

**Authors:**
Matthias Fitzi, Martin Hirt, Thomas Holenstein, Jürg Wullschleger

**Abstract:**

A broadcast protocol allows a sender to distribute a value among a set of

players such that it is guaranteed that all players receive the same

value (consistency), and if the sender is honest, then all players

receive the sender’s value (validity). Classical broadcast protocols for

n players provide security with respect to a fixed threshold t<n/3,

where both consistency and validity are guaranteed as long as at most t

players are corrupted, and no security at all is guaranteed as soon as

t+1 players are corrupted. Depending on the environment, validity or

consistency may be the more important property.

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.

**ePrint:**
https://eprint.iacr.org/2002/053

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .