We show here an asynchronous BA protocol with subquadratic communication tolerating an adaptive adversary who can corrupt $f<(1-\epsilon)n/3$ of the parties (for any $\epsilon>0$). One variant of our protocol assumes initial setup done by a trusted dealer, after which an unbounded number of BA executions can be run; alternately, we can achieve subquadratic amortized communication with no prior setup. We also show that some form of setup is needed for (non-amortized) subquadratic BA tolerating $\Theta(n)$ corrupted parties.
As a contribution of independent interest, we show a secure-computation protocol in the same threat model that has $o(n^2)$ communication when computing no-input functionalities with short output (e.g., coin tossing).
Category / Keywords: byzantine agreement, subquadratic communication Original Publication (in the same form): IACR-TCC-2020 Date: received 8 Jul 2020, last revised 6 Oct 2020 Contact author: erblum at cs umd edu,jkatz2@gmail com,lichen@inf ethz ch,lossjulian@gmail com Available format(s): PDF | BibTeX Citation Version: 20201006:113634 (All versions of this report) Short URL: ia.cr/2020/851