# Information Security and Cryptography Research Group

## From Partial Consistency to Global Broadcast

### Matthias Fitzi and Ueli Maurer

Proc. 32nd ACM Symposium on Theory of Computing — STOC 2000, ACM, pp. 494–503, May 2000.

This paper considers unconditionally secure protocols for reliable broadcast among a set of $n$ players, some of which may be corrupted by an active (Byzantine) adversary. In the standard model with a complete, synchronous network of pairwise authentic communication channels among the players, broadcast is achievable if and only if the number of corrupted players is less than $n/3$. We show that, by extending this model only by the existence of a broadcast channel among three players, global broadcast is achievable if and only if the number of corrupted players is less than $n/2$. Moreover, for this an even weaker primitive than broadcast among three players is sufficient. All protocols are efficient.

## BibTeX Citation

@inproceedings{FitMau00,
author       = {Matthias Fitzi and Ueli Maurer},
title        = {From Partial Consistency to Global Broadcast},
editor       = {Frances Yao},
booktitle    = {Proc.~32nd ACM Symposium on Theory of Computing --- STOC 2000},
pages        = 494--503,
year         = 2000,
month        = 5,
publisher    = {ACM},
}