Unconditional Byzantine Agreement and Multi-Party Computation Secure against Dishonest Minorities from Scratch

It is well-known that n players, connected only by pairwise secure channels, can achieve unconditional broadcast if and only if the number t of cheaters satis es t < n=3. In this paper, we show that this bound can be improved | at the sole price that the adversary can prevent successful completion of the protocol, but in which case all players will have agreement about this fact. Moreover, a rst time slot during which the adversary forgets to cheat can be reliably detected and exploited in order to allow for future broadcasts with t < n=2. This even allows for secure multi-party computation with t < n=2 after the rst detection of such a time slot.