[Resource Topic] 2022/775: Asynchronous Verifiable Information Dispersal with Near-Optimal Communication

Welcome to the resource topic for 2022/775

Asynchronous Verifiable Information Dispersal with Near-Optimal Communication

Authors: Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, and Haibin Zhang


We present a near-optimal asynchronous verifiable information dispersal (AVID) protocol. The total dispersal cost of our AVID protocol is O(|M|+\kappa n^2), and the retrieval cost per client is O(|M|+\kappa n). Unlike prior works, our AVID protocol only assumes the existence of collision-resistant hash functions. Also, in our AVID protocol, the dispersing client incurs a communication cost of O(|M|+\kappa n) in comparison to O(|M|+\kappa n\log n) of prior best. Moreover, each node in our AVID protocol incurs a storage cost of O(|M|/n+\kappa) bits, in comparison to O(|M|/n+\kappa \log n) bits of prior best. Finally, we present lower bound results on communication cost and show that our AVID protocol has near-optimal communication costs – only a factor of O(\kappa) gap from the lower bounds.

ePrint: https://eprint.iacr.org/2022/775

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 .