Broadcast and Consensus in Cryptographic Protocols

Speaker: Juan Garay

  Part I - 11:30 - 13:00, 8th January, 2018
  Part II - 14:30 - 16:00, 8th January, 2018

Broadcast and its closely related variant consensus are fundamental instances of -- and basic building blocks for -- secure multi-party computation (MPC) and cryptographic protocols in general, where they realize a "broadcast channel" or bulletin board functionality while running on a point-to-point channel network. In a nutshell, they guarantee that honest parties would output a value consistent with the parties' inputs (from a distinguished sender, or everybody, depending on the problem's variant), despite the potentially malicious behavior of some of them. Since the problems' formulation in the early '80s by Lamport, Shostak and Pease, their feasibility and achievable efficiency with respect to several quality measures have been extensively studied in various models.

In this lecture, we will start with a brief historical recap of broadcast and consensus protocols and impossibility results in the information-theoretic setting leading to fast (i.e., expected-constant-round) and optimally resilient protocols, by using randomization and allowing the parties to terminate in different rounds. We will then tackle the latter probabilistic termination aspect, of composability of such protocols as being used by higher-level cryptographic protocols, resulting in expected-constant-round parallel broadcast, and perfectly secure MPC with round complexity independent of the number parties. Finally, stepping beyond the information-theoretic realm, we will conclude with a consensus "taxonomy" showing contrasting results brought forward by the advent of blockchain protocols.

Speaker Bio
Juan A. Garay is a full professor at Texas A&M University's Department of Computer Science and Engineering. Previously, after receiving his PhD in Computer Science from Penn State, he was a postdoc at the Weizmann Institute of Science (Israel), and held research positions at the IBM T.J. Watson Research Center, Bell Labs, AT&T Labs--Research, and Yahoo Research. His research interests include both foundational and applied aspects of cryptography and information security. He has published extensively in the areas of cryptography, network security, distributed computing, and algorithms; has been involved in the design, analysis and implementation of a variety of secure systems; and is the recipient of over two dozen patents. Dr. Garay has served on the program committees of numerous conferences and international panels---including co-chairing Crypto 2013 and 2014, the discipline's premier conference.