Seminars

View all Seminars  |  Download ICal for this event

Communication Complexity of Byzantine Agreement, Revisited

Series: Department Seminar

Speaker: Dr. Kartik Nayak Assistant Professor Department of Computer Science Duke Un

Date/Time: Jan 10 11:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Faculty Advisor:

Abstract:
As Byzantine Agreement (BA) protocols find application in largescale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how to achieve subquadratic BA under an adaptive adversary. Intriguingly, they all make a common relaxation about the adaptivity of the attacker, that is, if an honest node sends a message and then gets corrupted in some round, the adversary cannot erase the message that was already sent — henceforth we say that such an adversary cannot perform “after-the-fact removal”. By contrast, many (super-)quadratic BA protocols in the literature can tolerate after-the-fact removal. It turns out, as shown in our work, that disallowing after-the-fact removal is necessary for achieving subquadratic-communication BA. In this talk, I will first present a simple quadratic BA protocol. Next, I will show a new subquadratic binary BA construction (of course, assuming no after-the-fact removal) that achieves near-optimal resilience and expected constant rounds under standard cryptographic assumptions and a public-key infrastructure (PKI). In comparison, all known subquadratic protocols make additional strong assumptions such as random oracles or the ability of honest nodes to erase secrets from memory, and even with these strong assumptions, no prior work can achieve the above properties.

Speaker Bio:
Kartik Nayak is an assistant professor in the Department of Computer Science at Duke University. He works in the areas of security, applied cryptography, distributed computing, and blockchains. Before joining Duke University, he spent a year as a postdoctoral researcher at VMware Research. Before that, he graduated from the University of Maryland, College Park under the supervision of Professor Jonathan Katz and Professor Elaine Shi. Kartik is a recipient of the 2016 Google Ph.D. fellowship in Security.

Host Faculty: Dr. Arpita Patra