ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

{B}yzantine Agreement Secure Against General Adversaries in the Dual Failure Model

Bernd Altmann and Matthias Fitzi and Ueli Maurer

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 ${\cal Z}$ of pairs $(A,F)$ of subsets of $P$ where the adversary may select an arbitrary such pair $(A_i,F_i)$ from ${\cal 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 ${\cal 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 ${\cal 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 ${\cal 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.