Paper 2008/287

Authenticated Byzantine Generals in Dual Failure Model

Anuj Gupta, Prasant Gopal, Piyush Bansal, and Kannan Srinathan

Abstract

Pease {\em et al.}\/ introduced the problem of Byzantine Generals (BGP) to study the effects of Byzantine faults in distributed protocols for reliable broadcast. It is well known that BGP among $n$ players tolerating up to $t$ faults is (efficiently) possible if and only if $n > 3t$. To overcome this severe limitation, Pease {\em et al.} introduced a variant of BGP, \emph{Authenticated Byzantine General} (ABG). Here players are supplemented with digital signatures (or similar tools) to thwart the challenge posed by Byzantine faults. Subsequently, they proved that with the use of authentication, fault tolerance of protocols for reliable broadcast can be amazingly increased to $n > t$ (which is a huge improvement over the $n > 3t$). Byzantine faults are the most generic form of faults. In a network not {\em all} faults are always malicious. Some faulty nodes may only leak their data while others are malicious. Motivated from this, we study the problem of ABG in ($t_b$,$t_p$)-mixed adversary model where the adversary can corrupt up to any $t_b$ players actively and control up to any other $t_p$ players passively. We prove that in such a setting, ABG over a completely connected synchronous network of $n$ nodes tolerating a ($t_b$,$t_p$)-adversary is possible if and only if $n > 2t_b$+min($t_b,t_p$) when $t_p > 0$. Interestingly, our results can also be seen as an attempt to unify the extant literature on BGP and ABG.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. To appear in proceedings of 11th International Conference on Distributed Computing and Networking (ICDCN 2010)
Keywords
Reliable broadcastAuthenticated Byzantine GeneralMixed adversary
Contact author(s)
anujgupta @ research iiit ac in
History
2009-10-12: last of 6 revisions
2008-07-03: received
See all versions
Short URL
https://ia.cr/2008/287
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/287,
      author = {Anuj Gupta and Prasant Gopal and Piyush Bansal and Kannan Srinathan},
      title = {Authenticated Byzantine Generals in Dual Failure Model},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/287},
      year = {2008},
      url = {https://eprint.iacr.org/2008/287}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.