Information Security and Cryptography Research Group

Byzantine Agreement Secure Against General Adversaries in the Dual Failure Model

Bernd Altmann, Matthias Fitzi, and Ueli Maurer

International Symposium on Distributed Computing — DISC '99, Lecture Notes in Computer Science, Springer-Verlag, vol. 1693, pp. 123–137, Sep 1999.

This paper introduces a new adversary model for Byzantine agreement and broadcast among a set $P$ of players in which the adversary may perform two different types of player corruption: active (Byzantine) corruption and fail-corruption (crash). As a strict generalization of the results of Garay and Perry, who proved tight bounds on the maximal number of actively and fail-corrupted players, the adversary's capability is characterized by a set ${\mathcal Z}$ of pairs $(A,F)$ of subsets of $P$ where the adversary may select an arbitrary such pair $(A_i,F_i)$ from ${\mathcal Z}$ and corrupt the players in $A_i$ actively and fail-corrupt the players in $F_i$.

For this model we prove that the exact condition on ${\mathcal Z}$ for which perfectly secure agreement and broadcast are achievable is that for no three pairs $(A_i,F_i)$, $(A_j,F_j)$, and $(A_k,F_k)$ in ${\mathcal Z}$ we have $A_i\cup A_j\cup A_k\cup (F_i\cap F_j\cap F_k)=P$. Achievability is demonstrated by efficient protocols. Moreover, for a slightly stronger condition on ${\mathcal Z}$, which covers the previous mixed (active and fail-corruption) threshold condition and the previous purely-active non-threshold condition, we demonstrate agreement and broadcast protocols that are substantially more efficient than all previous protocols for these two settings.

Key words: Broadcast, Byzantine agreement, unconditional security, active adversary, fail-corruption.

BibTeX Citation

    author       = {Bernd Altmann and Matthias Fitzi and Ueli Maurer},
    title        = {{B}yzantine Agreement Secure Against General Adversaries in the Dual Failure Model},
    editor       = {Prasad Jayanti},
    booktitle    = {International Symposium on Distributed Computing --- DISC~'99},
    pages        = {123--137},
    series       = {Lecture Notes in Computer Science},
    volume       = {1693},
    year         = {1999},
    month        = {9},
    publisher    = {Springer-Verlag},

Files and Links