  In this work we present hbAVSS, the Honey Badger of Asynchronous Verifiable
Secret Sharing (AVSS) protocols - an AVSS protocol that guarantees linear
amortized communication overhead even in the worst case. The best prior work
can achieve linear overhead only at a suboptimal resilience level (t < n/4) or
by relying on optimism (falling back to quadratic overhead in case of network
asynchrony or Byzantine faults). Our protocol therefore closes this gap,
showing that linear communication overhead is possible without these
compromises. The main idea behind our protocol is what we call the
encrypt-and-disperse paradigm: by first applying ordinary public key encryption
to the secret shares, we can make use of highly efficient (but not
confidentiality preserving) information dispersal primitives. We prove our
protocol is secure under a static computationally bounded Byzantine adversary
model.
