Secure and Efficient Asynchronous Broadcast Protocols

Christian Cachin; Klaus Kursawe; Frank Petzold; Victor Shoup

Paper 2001/006

Secure and Efficient Asynchronous Broadcast Protocols

Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup

Abstract

Reliable broadcast protocols are a fundamental building block for implementing replication in fault-tolerant distributed systems. This paper addresses secure service replication in an asynchronous environment with a static set of servers, where a malicious adversary may corrupt up to a threshold of servers and controls the network. We develop a formal model using concepts from modern cryptography, present modular definitions for several broadcast problems, including reliable, atomic, and secure causal broadcast, and present protocols implementing them. Reliable broadcast is a basic primitive, also known as the Byzantine generals problem, providing agreement on a delivered message. Atomic broadcast imposes additionally a total order on all delivered messages. We present a randomized atomic broadcast protocol based on a new, efficient multi-valued asynchronous Byzantine agreement primitive with an external validity condition. Apparently, no such efficient asynchronous atomic broadcast protocol maintaining liveness and safety in the Byzantine model has appeared previously in the literature. Secure causal broadcast extends atomic broadcast by encryption to guarantee a causal order among the delivered messages. Threshold-cryptographic protocols for signatures, encryption, and coin-tossing also play an important role.

Note: The revision of March 2001 fixes a few details in the model and contains updated terminology.

Metadata

Available format(s): PDF PS
Category: Cryptographic protocols
Publication info: Published elsewhere. Unknown where it was published
Keywords: reliable broadcast Byzantine agreement atomic broadcast distributed cryptography
Contact author(s): cca @ zurich ibm com
History: 2001-03-07: revised; 2001-01-26: received; See all versions
Short URL: https://ia.cr/2001/006
License: CC BY

BibTeX

@misc{cryptoeprint:2001/006,
      author = {Christian Cachin and Klaus Kursawe and Frank Petzold and Victor Shoup},
      title = {Secure and Efficient Asynchronous Broadcast Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2001/006},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/006}},
      url = {https://eprint.iacr.org/2001/006}
}