Dependable Computing and Fault Tolerant Systems, Volume 10.
From Dependable Computing for Critical Applications---5.
Edited by Ravishankar K. Iyer, Michele Morganti, W. Kent Fuchs and Virgil Gligor.
IEEE Computer Society, Champaign, IL.
September, 1995.
Pages 139–157.

We show that the assumptions required of the authentication mechanism in Byzantine agreement protocols that use ``signed messages'' are stronger than generally realized, and require more than simple digital signatures. The protocols may fail if these assumptions are violated. We then present new protocols for Byzantine agreement that add authentication to ``oral message'' protocols so that additional resilience is obtained with authentication, but with no assumptions required about the security of authentication when the number and kind of faults present are within the resilience of the unauthenticated protocol.

Our analysis is performed under a ``hybrid'' fault model that admits manifest (e.g., crash) and symmetric faults as well as arbitrary (i.e., Byzantine) faults. We also extend the classical signed messages protocol to this fault model, and show that its fault-tolerance is matched by one of our new protocols. We then explore the behavior of these various protocols under the combination of hybrid processor faults and communications link faults. Using formal state-exploration techniques, we examine cases beyond those guaranteed by simple worst-case bounds and find that the resilience of one of the new protocols exceeds that of the others in these regions.

The new protocols are superior to other known protocols in properties and measures of practical interest, and we recommend them for general use. They are particularly attractive in security-critical systems where authentication may be subjected to sophisticated cryptographic attack, and in safety-critical embedded systems where it may be necessary to use very short signatures, but where maximum resilience is required.

@inproceedings{Gong-Lincoln-Rushby:DCCA95,
    AUTHOR = {Li Gong and Patrick Lincoln and John Rushby},
    TITLE = {Byzantine Agreement with Authentication: Observations and Applications in Tolerating Hybrid and Link Faults},
    BOOKTITLE = {Dependable Computing for Critical Applications---5},
    YEAR = {1995},
    EDITOR = {Ravishankar {K.} Iyer and Michele Morganti and {W.} Kent Fuchs and Virgil Gligor},
    SERIES = {Dependable Computing and Fault Tolerant Systems},
    VOLUME = {10},
    PAGES = {139--157},
    ADDRESS = {Champaign, {IL}},
    MONTH = {sep},
    PUBLISHER = {{IEEE} Computer Society},
    URL = {http://www.csl.sri.com/papers/dcca95/}
}

• dcca95.dvi
• dcca95.pdf
• dcca95.ps