MiniCast: Minimizing the communication complexity of reliable broadcast

Victor Shoup (NYU and Offchain Labs) gives a new protocol for reliable broadcast with improved communication complexity for long messages. Namely, to reliably broadcast a message a message m over an asynchronous network to a set of n parties, of which fewer than n/3 may be corrupt, our protocol achieves a communication complexity of 1.5|m|n + O(k n^2 log(n)), where k is the output length of a collision-resistant hash function. This result improves on the previously best known bound for long messages of 2|m|n + O(k n^2 log(n)).

This is joint work with Thomas Locher (Dfinity).

About the presenter

Victor is currently a research scientist at Offchain Labs and Professor Emeritus at New York University. He has been working in the fields of cryptography and computational number theory. He has made many research contributions in diverse areas such as public key cryptographic primitives, secure distributed protocols, and algorithms for factoring polynomials and related problems. He has written two textbooks, and has developed two high-performance software libraries. He obtained a PhD from UW-Madison and has worked at the IBM Zurich Research Lab, New York University, the IBM T. J. Watson Research Center, and Dfinity. About a16z crypto research a16z crypto research is a multidisciplinary lab that works closely with our portfolio companies and others toward solving the important problems in the space, and toward advancing the science and technology of the next generation of the internet.

More about us:

a16z.com/2022/04/21/announcing-a16z-crypto-research