Authenticated Byzantine Fault Tolerance Without Public-Key …

Short Description
cryptography. The optimization replaces public-key signatures …… public-key cryptography bottleneck completely without. increasing the number of message …

Website: www.pmg.lcs.mit.edu | Filesize: 585kb

Content
Appears as Technical Memo MIT/LCS/TM-589, MIT Laboratory for Computer Science, June 1999
Authenticated Byzantine Fault ToleranceWithout Public-Key Cryptography
Miguel Castro and Barbara Liskov
Laboratory for Computer Science,
Massachusetts Institute of Technology,
545 Technology Square, Cambridge, MA 02139
castro,liskov @lcs.mit.edu
Abstract
We have developed a practical state-machine replication
algorithm that tolerates Byzantine faults: it works correctly
in asynchronous systems like the Internet and it incorporates
several optimizations that improve the response time of previous
algorithms by more than an order of magnitude. This paper
describes the most important of these optimizations. It explains
how to modify the base algorithm to eliminate the major
performance bottleneck in previous systems - public-key
cryptography. The optimization replaces public-key signatures
by vectors of message authentication codes during normal
operation, and it overcomes a fundamental limitation on the
power of message authentication codes relative to digital
signatures - the inability to prove that a message is authentic
to a third party. As a result, authentication is more than two
orders of magnitude faster while providing the same level of
security.
1 Introduction
The growing reliance of industry and government on
online information services makes malicious…