Ran Cohen's talk

[carmit...@gmail.com]

Dear all,

As promised, please find below the details of the talk given by Ran Cohen, which has moved to next Monday (and was originally BIU  GTACS program).

 

Best,

Carmit

 

 

Speaker: Ran Cohen (NEU) 

 

Title: Reaching Agreement Without Saying Much: Byzantine Agreement with Polylog Bits Per Party

 

Time: Monday, May 3rd, 16:00 (Israel time)

 

Link: https://us02web.zoom.us/j/85688299204

 

Abstract:

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.

 

This is a joint work with Elette Boyle and Aarushi Goel.