Cryptology ePrint Archive: Report 2021/777

Asynchronous Data Dissemination and its Applications

Sourav Das and Zhuolun Xiang and Ling Ren

Abstract: 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.

Category / Keywords: cryptographic protocols / Data Dissemination; Asynchronous Networks; Reliable Broadcast; Verifiable Secret Sharing; Distributed Key Generation; Communication Complexity.

Original Publication (in the same form): ACM CCS 2021

Date: received 9 Jun 2021, last revised 2 Oct 2021

Contact author: souravd2 at illinois edu, xiangzl at illinois edu, renling at illinois edu

Available format(s): PDF | BibTeX Citation

Version: 20211002:175517 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]