Paper 2021/777

Asynchronous Data Dissemination and its Applications

Sourav Das, Zhuolun Xiang, and Ling Ren


In this paper, we introduce the problem of Asynchronous Data Dissemination (ADD). Intuitively, an ADD protocol disseminates a message to all honest nodes in an asynchronous network, given that at least $t+1$ honest nodes initially hold the message where $t$ is the maximum number of malicious nodes. We design a simple and efficient ADD protocol for $n$ parties that is information-theoretically secure, tolerates up to one-third malicious nodes, and has a communication cost of $O(n|M|+n^2)$ for disseminating a message $M$. We then use our ADD protocol to improve many important primitives in cryptography and distributed computing. For asynchronous reliable broadcast (RBC), assuming collision-resistant hash functions, we give a RBC protocol with communication cost $O(n|M| + \kappa n^2)$ where $\kappa$ is the size of the hash function output. This improves over the prior best scheme with communication cost $O(n|M| + \kappa n^2 \log n)$ under the same setting. Our improved RBC protocol immediately improves the communication cost of asynchronous atomic broadcast and Asynchronous Distributed Key Generation~(ADKG) protocols. We also use our improved \rbc\ protocol along with additional new techniques to improve the communication cost of Asynchronous Verifiable Secret Sharing (AVSS), Asynchronous Complete Secret Sharing (ACSS), and dual-threshold \acss\ from $O(\kappa n^2 \log n)$ to $O(\kappa n^2)$ without using any trusted setup.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2021
Data DisseminationAsynchronous NetworksReliable BroadcastVerifiable Secret SharingDistributed Key GenerationCommunication Complexity.
Contact author(s)
souravd2 @ illinois edu
xiangzl @ illinois edu
renling @ illinois edu
2021-10-02: last of 2 revisions
2021-06-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sourav Das and Zhuolun Xiang and Ling Ren},
      title = {Asynchronous Data Dissemination and its Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/777},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.