Name
Abstract | ||
|---|---|---|
This paper considers unconditionally secure protocols for reliable broadcast among a set of n players, where up to t of the players can be corrupted by a (Byzantine) adversary but the remaining h = n - t players remain honest. In the standard model with a complete, synchronous network of bilateral authenticated communication channels among the players, broadcast is achievable if and only if 2n/h < 3. We show that, by extending this model by the existence of partial broadcast channels among subsets of b players, global broadcast can be achieved if and only if the number h of honest players satisfies 2n/h < b + 1. Achievability is demonstrated by protocols with communication and computation complexities polynomial in the size of the network, i.e., in the number of partial broadcast channels. A respective characterization for the related consensus problem is also given. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/s00145-005-0308-x | J. Cryptology |
Keywords | Field | DocType |
Broadcast,Byzantine agreement | Consensus,Discrete mathematics,Broadcasting,Authentication,Polynomial,Computer science,Communication channel,Communication complexity,If and only if,Computation | Journal |
Volume | Issue | ISSN |
18 | 3 | 0933-2790 |
Citations | PageRank | References |
19 | 1.08 | 27 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| jeffrey considine | 1 | 314 | 19.62 |
| Matthias Fitzi | 2 | 512 | 28.44 |
| Matthew K. Franklin | 3 | 959 | 119.11 |
| Leonid A. Levin | 4 | 2031 | 349.38 |
| Ueli Maurer | 5 | 4526 | 505.09 |
| David Metcalf | 6 | 19 | 1.08 |