Byzantine agreement (BA), the task of n parties to agree on one of their input bits in the face of malicious agents, is a powerful primitive that lies at the core of a vast range of distributed protocols. Interestingly, in protocols with the best overall communication, the demands of the parties are highly unbalanced: the amortized cost is polylog(n) bits per party, but some parties must send \Omega(n) bits. In best known balanced protocols, the overall communication is sub-optimal, with each party communicating O(\sqrt n) bits. In this talk, we explore whether asymmetry is inherent for optimizing total communication. We show that this is not the case by presenting two BA protocols where every party communicates only polylog(n) bits; the constructions rely on a new flavor of distributed signatures and offer a tradeoff between setup assumptions and cryptographic assumptions. Next, we will discuss limitations and barriers of this approach, and conclude with open questions. Based on a joint work with Elette Boyle and Aarushi Goel.
Ran Cohen is a faculty member at Reichman University. Ran completed his Ph.D. in Computer Science at Bar-Ilan University and served as a postdoctoral researcher at Tel Aviv University, BU, and MIT. His research interests are in cryptography and its synergy with distributed computing, mainly focusing on secure multiparty computation and consensus protocols.