Extending Asynchronous Byzantine Agreement with Crusader Agreement

In this work, we study multivalued byzantine agreement (BA) in an asynchronous network of $n$ parties where up to $t<\frac{n}{3}$ parties are byzantine. We present a new reduction from multivalued BA to binary BA. It allows one to achieve BA on $\mathrm{\ell }$-bit inputs with one instance of binary BA, one instance of crusader agreement (CA) on $\mathrm{\ell }$-bit inputs and $\mathrm{\Theta }(\mathrm{\ell }n+n^2)$ bits of additional communication. As our reduction uses multivalued CA, we also design two new information-theoretic CA protocols for $\mathrm{\ell }$-bit inputs. In the first one, we use almost-universal hashing to achieve statistical security with probability $1-2^{-\lambda }$ against $t<\frac{n}{3}$ faults with $\mathrm{\Theta }(\mathrm{\ell }n+n^2(\lambda +\log n))$ bits of communication. Following this, we replace the hashes with error correcting code symbols and add a preliminary step based on the synchronous multivalued BA protocol COOL [DISC '21] to obtain a second, perfectly secure CA protocol that can for any $\epsilon >0$ be set to tolerate $t\le \frac{n}{3+\epsilon }$ faults with $\mathcal{O}(\frac{\mathrm{\ell }n}{\min (1,{\epsilon }^2)}+n^2\max (1,\log \frac{1}{\epsilon }\left)\right)$ bits of communication. Our CA protocols allow one to extend binary BA to multivalued BA with a constant round overhead, a quadratic-in-$n$ communication overhead, and information-theoretic security.