International Association for Cryptologic Research

International Association
for Cryptologic Research


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
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2023
Abstract: 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 with optimal resiliency in the asynchronous setting (with eventual message delivery). This apparent hole in the literature is particularly problematic, as multi-valued OCC is implicitly or explicitly used in several constructions. In this paper, we present the first information-theoretic multi-valued OCC protocol in the asynchronous setting with optimal resiliency, i.e., tolerating t
  title={Concurrent Asynchronous Byzantine Agreement in Expected-Constant Rounds, Revisited},
  author={Ran Cohen and Pouyan Forghani and Juan Garay and Rutvik Patel and Vassilis Zikas},