Crypto Seminar

Thursday, June 17, 2021 - 4:30pm to 5:30pm


Virtual Presentation - ET Remote Access - Zoom


JULIAN LOSS, Postdoctoral Researcher

Gossiping For Communication-Efficient Broadcast

Broadcast (BC) is a crucial ingredient for a plethora of cryptographic protocols such as secret sharing and multiparty computation. In this paper we apply \emph{gossiping} (propagating a message by sending to a few random parties who in turn do the same, until the message is delivered) to design new randomized BC protocols with improved communication complexity and which are secure against an adversary controlling the majority of parties. We make progress on two fronts. First, we propose a protocol for single-sender BC in the static model of corruption that achieves Õ(n2 · κ2) bits of communication and where no trusted setup is required---parties just need to generate their own cryptographic keys. All prior protocols in this setting exhibit O(n3 · κ) communication. Using insights from our single-sender BC protocol, we then propose the first adaptively-secure parallel BC protocol with Õ(n2 · κ4) communication complexity, significantly improving existing parallel BC protocols of Õ(n3) communication. To the best of our knowledge, our parallel BC protocol is the first non-trivial one, i.e., one that is not using a single-sender BC protocol n times and in a black box fashion, thus leading to the improved complexity.

Zoom Participation. See announcement.

Event Website:

For More Information, Contact:


Seminar Series