## CryptoDB

### Paper: Authenticated Byzantine Generals Strike Again

Authors: Anuj Gupta Prasant Gopal Piyush Bansal Kannan Srinathan URL: http://eprint.iacr.org/2008/287 Search ePrint Search Google 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.
##### BibTeX
@misc{eprint-2008-17964,
title={Authenticated Byzantine Generals Strike Again},
booktitle={IACR Eprint archive},