Detectable {B}yzantine {A}greement Secure Against Faulty Majorities

It is well-known that $n$ players, connected only by pairwise secure channels, can achieve Byzantine agreement only if the number $t$ of cheaters satisfies $t<n/3$, even with respect to computational security. However, for many applications it is sufficient to achieve \db}. With this primitive, broadcast is only guaranteed when all players are non-faulty (``honest''), but all non-faulty players always reach agreement on whether broadcast was achieved or not. We show that \db can be achieved regardless of the number of faulty players (i.e., for all $t<n$). We give a protocol which is unconditionally secure, as well as two more efficient protocols which are secure with respect to computational assumptions, and the existence of quantum channels, respectively.

These protocols allow for secure multi-party computation tolerating any $t<n$, assuming only pairwise authenticated channels. Moreover, they allow for the setup of public-key infrastructures that are consistent among all participants — using neither a trusted party nor broadcast channels.

Finally, we show that it is not even necessary for players to begin the protocol at the same time step. We give a ``detectable Firing Squad'' protocol which can be initiated by a single user at any time and such that either all honest players end up with synchronized clocks, or all honest players abort.