Asynchronous Data Dissemination and its Applications

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|+n2) 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| + κ n2) where κ is the size of the hash function output. This improves over the prior best scheme with communication cost O(n|M| + κ n2 łog 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(κ n2 łog n) to O(κ n2) without using any trusted setup.