### Asynchronous Data Dissemination and its Applications

Sourav Das, 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.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2021
Keywords
Data DisseminationAsynchronous NetworksReliable BroadcastVerifiable Secret SharingDistributed Key GenerationCommunication Complexity.
Contact author(s)
souravd2 @ illinois edu
xiangzl @ illinois edu
renling @ illinois edu
History
2021-10-02: last of 2 revisions
See all versions
Short URL
https://ia.cr/2021/777

CC BY

BibTeX

@misc{cryptoeprint:2021/777,
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{https://eprint.iacr.org/2021/777}},
url = {https://eprint.iacr.org/2021/777}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.