Asynchronous Data Dissemination and its Applications, by Sourav Das and Zhuolun Xiang and Ling Ren

In this paper, we introduce the problem of Asynchronous Data Dissemination (ADD). Intuitively, an ADD protocol replicates 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 yet 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 replicating a message $M$.

We then use our ADD protocol to improve many important primitives in cryptography and distributed computing. For reliable broadcast, assuming the existence of collision resistance hash functions, we present a protocol with communication cost $O(n|M| + kappa n^2)$ where $kappa$ is the size of the hash function output. This is an improvement over the best-known complexity of $O(n|M| + kappa n^2 log n)$ under the same setting. Next, we use our ADD protocol along with additional new techniques to improve the communication complexity of Asynchronous Verifiable Secret Sharing~(AVSS) and Asynchronous Complete Secret Sharing~(ACSS) with no trusted setup from $O(kappa n^2 log n)$ to $O(kappa n^2)$. Furthermore, we use ADD and a publicly-verifiable secret sharing scheme to improve dual-threshold ACSS and Asynchronous Distributed Key Generation~(ADKG).