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},
}