Lecture Notes in Computer Science, 2002, Volume 2332/2002, 482-501, DOI: 10.1007/3-540-46035-7_32

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

Matthias Fitzi, Nicolas Gisin, Ueli Maurer and Oliver von Rotz

View Related Documents

Abstract

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 satisfies 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 first 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 first detection of such a time slot.

Key words  Byzantine agreement - multi-party computation - unconditional security

Fulltext Preview

Image of the first page of the fulltext document