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).

By admin