Asynchronous Verifiable Information Dispersal with Near-Optimal Communication

Nicolas Alhaddad; Sourav Das; Sisi Duan; Ling Ren; Mayank Varia; Zhuolun Xiang; Haibin Zhang

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

Abstract

We present a near-optimal asynchronous verifiable information dispersal (AVID) protocol. The total dispersal cost of our AVID protocol is , and the retrieval cost per client is . 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 in comparison to of prior best. Moreover, each node in our AVID protocol incurs a storage cost of bits, in comparison to 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 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},
      url = {https://eprint.iacr.org/2022/775}
}