[Resource Topic] 2021/777: Asynchronous Data Dissemination and its Applications

Welcome to the resource topic for 2021/777

Asynchronous Data Dissemination and its Applications

Authors: Sourav Das, Zhuolun Xiang, Ling Ren


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.

ePrint: https://eprint.iacr.org/2021/777

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .