eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2023/1003

Concurrent Asynchronous Byzantine Agreement in Expected-Constant Rounds, Revisited

Ran Cohen, Reichman University
Pouyan Forghani, Texas A&M University
Juan Garay, Texas A&M University
Rutvik Patel, Texas A&M University
Vassilis Zikas, Purdue University West Lafayette

It is well known that without randomization, Byzantine agreement (BA) requires a linear number of rounds in the synchronous setting, while it is flat out impossible in the asynchronous setting. The primitive which allows to bypass the above limitation is known as oblivious common coin (OCC). It allows parties to agree with constant probability on a random coin, where agreement is oblivious, i.e., players are not aware whether or not agreement has been achieved. The starting point of our work is the observation that no known protocol exists for information-theoretic multi-valued OCC---i.e., OCC where the coin might take a value from a domain of cardinality larger than 2---with optimal resiliency in the asynchronous (with eventual message delivery) setting. This apparent hole in the literature is particularly problematic, as multi-valued OCC is implicitly or explicitly used in several constructions. (In fact, it is often falsely attributed to the asynchronous BA result by Canetti and Rabin [STOC ’93], which, however, only achieves binary OCC and does not translate to a multi-valued OCC protocol.) In this paper, we present the first information-theoretic multi-valued OCC protocol in the asynchronous setting with optimal resiliency, i.e., tolerating $t<n/3$ corruptions, thereby filling this important gap. Further, our protocol efficiently implements OCC with an exponential-size domain, a property which is not even achieved by known constructions in the simpler, synchronous setting. We then turn to the problem of round-preserving parallel composition of asynchronous BA. A protocol for this task was proposed by Ben-Or and El-Yaniv [Distributed Computing ’03]. Their construction, however, is flawed in several ways: For starters, it relies on multi-valued OCC instantiated by Canetti and Rabin's result (which, as mentioned above, only provides binary OCC). This shortcoming can be repaired by plugging in our above multi-valued OCC construction. However, as we show, even with this fix it remains unclear whether the protocol of Ben-Or and El-Yaniv achieves its goal of expected-constant-round parallel asynchronous BA, as the proof is incorrect. Thus, as a second contribution, we provide a simpler, more modular protocol for the above task. Finally, and as a contribution of independent interest, we provide proofs in Canetti's Universal Composability framework; this makes our work the first one offering composability guarantees, which are important as BA is a core building block of secure multi-party computation protocols.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2023
Byzantine agreementasynchronous networksconcurrent composition(multi-valued) oblivious common coin
Contact author(s)
rancoen @ gmail com
pouyan forghani @ tamu edu
juan a garay @ gmail com
rsp7 @ tamu edu
vassilis zikas @ gmail com
2023-12-22: revised
2023-06-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ran Cohen and Pouyan Forghani and Juan Garay and Rutvik Patel and Vassilis Zikas},
      title = {Concurrent Asynchronous Byzantine Agreement in Expected-Constant Rounds, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1003},
      year = {2023},
      doi = {10.1007/978-3-031-48624-1_16},
      note = {\url{https://eprint.iacr.org/2023/1003}},
      url = {https://eprint.iacr.org/2023/1003}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.