MiniCast: Minimizing the communication complexity of reliable broadcast with Victor Shoup

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

More from the a16z crypto team
Subscribe to our 'web3 weekly newsletter': a16zcrypto.substack.com
Listen to our 'web3 with a16z' podcast: a16zcrypto.com/web3-with-a16z-podcast/
Read more of our work: a16zcrypto.com