Broadcast Amplification

A

d

-broadcast primitive is a communication primitive that allows a sender to send a value from a domain of size

d

to a set of parties. A broadcast protocol emulates the

d

-broadcast primitive using only point-to-point channels, even if some of the parties cheat, in the sense that all correct recipients agree on the same value

v

(consistency), and if the sender is correct, then

v

is the value sent by the sender (validity). A celebrated result by Pease, Shostak and Lamport states that such a broadcast protocol exists if and only if

t

 < 

n

/3, where

n

denotes the total number of parties and

t

denotes the upper bound on the number of cheaters.

This paper is concerned with broadcast protocols for any number of cheaters (

t

 < 

n

), which can be possible only if, in addition to point-to-point channels, another primitive is available. Broadcast amplification is the problem of achieving

d

-broadcast when

d

′-broadcast can be used once, for

d

′ < 

d

. Let

ϕ

n

(

d

) denote the minimal such

d

′ for domain size

d

.

We show that for

n

 = 3 parties, broadcast for any domain size is possible if only a single 3-broadcast is available, and broadcast of a single bit (

d

′ = 2) is not sufficient, i.e.,

ϕ

3

(

d

) = 3 for any

d

 ≥ 3. In contrast, for

n

 > 3 no broadcast amplification is possible, i.e.,

ϕ

n

(

d

) = 

d

for any

d

.

However, if other parties than the sender can also broadcast some short messages, then broadcast amplification is possible for

any

n

. Let

$\phi^*_n(d)$

denote the minimal

d

′ such that

d

-broadcast can be constructed from primitives

d

′

1

-broadcast,…,

d

′

k

-broadcast, where

d

′ = ∏ 

i

d

′

i

(i.e., log

d

′ = ∑ 

i

log

d

′

i

). Note that

$\phi^*_n(d)\leq\phi_n(d)$

. We show that broadcasting 8

n

log

n

bits in total suffices, independently of

d

, and that at least

n

 − 2 parties, including the sender, must broadcast at least one bit. Hence

$\min(\log d,n-2) \leq \log \phi^*_n(d) \leq 8n\log n$

.