A New Look at Composition of Authenticated Byzantine Generals
Preprint
Abstract
The problem of Authenticated Byzantine Generals (ABG) aims to simulate a virtual reliable broadcast channel from the General to all the players via a protocol over a real (point-to-point) network in the presence of faults. We propose a new model to study the self-composition of ABG protocols. The central dogma of our approach can be phrased as follows: Consider a player who diligently executes (only) the delegated protocol but the adversary steals some private information from him. Should such a player be considered faulty? With respect to ABG protocols, we argue that the answer has to be no. In the new model we show that in spite of using unique session identifiers, if $n < 2t$, there cannot exist any ABG protocol that composes in parallel even twice. Further, for $n \geq 2t$, we design ABG protocols that compose for any number of parallel executions. Besides investigating the composition of ABG under a new light, our work also brings out several new insights into Canetti's Universal Composability framework. Specifically, we show that there are several undesirable effects if one deviates from our dogma. This provides further evidence as to why our dogma is the right framework to study the composition of ABG protocols.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Polynomial Runtime and ComposabilityJournal of Cryptology, 2012
- Universally Composable Symbolic Security AnalysisJournal of Cryptology, 2010
- On expected constant-round protocols for Byzantine agreementJournal of Computer and System Sciences, 2009
- Universally composable security: a new paradigm for cryptographic protocols2001
- Security and Composition of Multiparty Cryptographic ProtocolsJournal of Cryptology, 2000
- Levels of authentication in distributed agreement1996
- On the number of authenticated rounds in Byzantine Agreement1995
- Definitions and properties of zero-knowledge proof systemsJournal of Cryptology, 1994
- Simulating authenticated broadcasts to derive simple fault-tolerant algorithmsDistributed Computing, 1987
- The Byzantine generals strike againJournal of Algorithms, 1982