Efficient Byzantine Agreement with Faulty Minority

Zuzana Beerliova-Trubiniova and Martin Hirt and Micha Riser

Byzantine Agreement (BA) among $n$ players allows the players to agree on a
value, even when up to $t$ of the players are faulty.

In the broadcast variant of BA, one dedicated player holds a message, and
all players shall learn this message. In the consensus variant of BA,
every player holds (presumably the same) message, and the players shall
agree on this message.
  
BA is the probably most important primitive in distributed protocols,
hence its efficiency is of particular importance.
 
BA from scratch, i.e., without a trusted setup, is possible only for
$t<n/3$. In this setting, the known BA protocols are highly efficient
($\O(n^2)$ bits of communication) and provide information-theoretic
security.

When a trusted setup is available, then BA is possible for $t<n/2$
(consensus), respectively for $t<n$ (broadcast). In this setting, only
computationally secure BA protocols are reasonably efficient
($\O(n^3\kappa)$ bits). When information-theoretic security is required,
the most efficient known BA protocols require $\O(n^{17}\kappa)$ bits of
communication per BA, where $\kappa$ denotes a security parameter.  The
main reason for this huge communication is that in the
information-theoretic world, parts of the setup are \emph{consumed} with
every invocation to BA, and hence the setup must be refreshed.  This
refresh operation is highly complex and communication-intensive.
  
In this paper we present BA protocols (both broadcast and consensus) with
information-theoretic security for $t<n/2$, communicating $\O(n^5\kappa)$
bits per BA.