Asynchronous Verifiable Information Dispersal

Christian Cachin and Stefano Tessaro

Proceedings of the 24th Symposium on Reliable Distributed Systems — SRDS 2005, pp. 191–202, Oct 2005.

Information dispersal addresses the question of storing a file by distributing it among a set of servers in a storage-efficient way. We introduce the problem of verifiable information dispersal in an asynchronous network, where up to one third of the servers as well as an arbitrary number of clients might exhibit Byzantine faults. Verifiability ensures that the stored information is consistent despite such faults. We present a storage- and communication-efficient scheme for asynchronous verifiable information dispersal that achieves an asymptotically optimal storage blow-up. Additionally, we show how to guarantee the secrecy of the stored data with respect to an adversary that may mount adaptive attacks. Our technique also yields a new protocol for asynchronous reliable broadcast that improves the communication complexity by an order of magnitude on large inputs.

BibTeX Citation

@inproceedings{CacTes05,
    author       = {Christian Cachin and Stefano Tessaro},
    title        = {Asynchronous Verifiable Information Dispersal},
    booktitle    = {Proceedings of the 24th Symposium on Reliable Distributed Systems --- SRDS 2005},
    pages        = {191--202},
    year         = {2005},
    month        = {10},
}

Files and Links

There are currently no associated files available.