ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Unconditional {B}yzantine Agreement and Multi-Party Computation Secure Against Dishonest Minorities from Scratch

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

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.