Multi-valued Byzantine Broadcast: The t < n Case

摘要: Byzantine broadcast is a distributed primitive that allows specific party to consistently distribute message among n parties in the presence of potential misbehavior up t parties. All known protocols implementing an l-bit from point-to-point channels tolerating any < corruptions have communication complexity at least Ω(ln 2). In this paper we give cryptographically secure and information-theoretically for communicate \(\mathcal{O}(\ell n)\) bits when l sufficiently large. This matches optimal bound protocol allowing messages. While with exist n/2, first present such n.