Paper 2022/775
Asynchronous Verifiable Information Dispersal with Near-Optimal Communication
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. ACM PODC 2022
- Keywords
- 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 - History
- 2022-06-16: approved
- 2022-06-15: received
- See all versions
- Short URL
- https://ia.cr/2022/775
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/775,
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{https://eprint.iacr.org/2022/775}},
url = {https://eprint.iacr.org/2022/775}
}
