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

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

Advances in Cryptology — EUROCRYPT 2002, Lecture Notes in Computer Science, Springer-Verlag, vol. 2332, pp. 482–501, May 2002.

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.

BibTeX Citation

@inproceedings{FGMR02,
    author       = {Matthias Fitzi and Nicolas Gisin and Ueli Maurer and Oliver von Rotz},
    title        = {Unconditional {B}yzantine Agreement and Multi-Party Computation Secure Against Dishonest Minorities from Scratch},
    editor       = {Lars Knudsen},
    booktitle    = {Advances in Cryptology --- EUROCRYPT 2002},
    pages        = 482--501,
    series       = {Lecture Notes in Computer Science},
    volume       = 2332,
    year         = 2002,
    month        = 5,
    publisher    = {Springer-Verlag},
}