Paper 2022/775

Asynchronous Verifiable Information Dispersal with Near-Optimal Communication

Nicolas Alhaddad, Boston University
Sourav Das, University of Illinois Urbana-Champaign
Sisi Duan, Tsinghua University
Ling Ren, University of Illinois Urbana-Champaign
Mayank Varia, Boston University
Zhuolun Xiang, University of Illinois Urbana-Champaign
Haibin Zhang, Beijing Institute of Technology

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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM PODC 2022
Asynchronous Networks Verifiable Information Dispersal Communication Complexity Lower Bounds
Contact author(s)
nhaddad @ bu edu
souravd2 @ illinois edu
duansisi @ tsinghua edu cn
renling @ illinois edu
varia @ bu edu
xiangzl @ illinois edu
haibin @ bit edu cn
2022-06-16: approved
2022-06-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicolas Alhaddad and Sourav Das and Sisi Duan and Ling Ren and Mayank Varia and Zhuolun Xiang and Haibin Zhang},
      title = {Asynchronous Verifiable Information Dispersal with Near-Optimal Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2022/775},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.