International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Authenticated Byzantine Generals Strike Again

Anuj Gupta
Prasant Gopal
Piyush Bansal
Kannan Srinathan
Search ePrint
Search Google
Abstract: Pease {\em et al.}\/ introduced the problem of \emph{Authenticated Byzantine General} (ABG) where players could use digital signatures (or similar tools) to thwart the challenge posed by Byzantine faults in distributed protocols for agreement. Subsequently it is well known that ABG among $n$ players tolerating up to $t$ faults is (efficiently) possible if and only if $t < n$ (which is a huge improvement over the $n > 3t$ condition in the absence of authentication for the same functionality). However, in this paper we argue that the extant result of $n>t$ does not \emph{truly} simulate a broadcast channel as intended. Thus, we re-initiate the study of ABG. We show that in a completely connected synchronous network of $n$ players where up to any $t$ players are controlled by an adversary, ABG is possible if and only if $n > 2t-1$. The result is pleasantly surprising since it deviates from the standard template of ``$n > \beta t$" for some integer $\beta$, particularly $\beta = 1,2$ or $3$. The result uses new proof/design techniques which may be of independent interest.
  title={Authenticated Byzantine Generals Strike Again},
  booktitle={IACR Eprint archive},
  keywords={authenticated Byzantine General, colluding adversary},
  note={ 14056 received 25 Jun 2008},
  author={Anuj Gupta and Prasant Gopal and Piyush Bansal and Kannan Srinathan},