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

Category / Keywords: cryptographic protocols / threshold cryptography, distributed cryptography, asynchronous protocols, reliable broadcast, AVSS, ADKG

Date: received 9 Jun 2021, last revised 10 Jun 2021

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

Available format(s): PDF | BibTeX Citation

Version: 20210611:032912 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]