Authenticated channels ⇒ Broadcast against $t<n/3$ (Lamport–Shostak–Pease)

Free reduction · standard model · LSP82, PSL80 · security loss: none (perfect security)

Statement

Over a synchronous network of authenticated point-to-point channels, with no broadcast channel and no setup, interactive consistency, in which the honest parties agree on a vector holding a value for every party and each honest party’s entry is its own input, is solvable for $n\ge 3t+1$ — PSL80. Agreeing on the sender’s entry gives broadcast — standard. For every $n$ and every $t<n/3$, the oral-messages algorithm $\mathrm{OM}(t)$ is a perfectly secure broadcast protocol against $t$ corruptions (broadcast against $t<n/3$) — LSP82; it runs in $t+1$ rounds — standard.

Sketch

$\mathrm{OM}(0)$: the sender sends its value to every party, and each party outputs the value it received, or a default. $\mathrm{OM}(m)$: the sender sends its value to every party; each party then acts as the sender in $\mathrm{OM}(m-1)$ of the value it received, towards the other $n-2$ parties; each party outputs the majority of the $n-1$ values it obtained, the sender’s and the $n-2$ relayed ones — LSP82.

Notes

• $\mathrm{OM}(t)$ sends $n^{O(t)}$ messages, exponential in $t$ — standard. A deterministic protocol with $t+1$ rounds and polynomial communication exists for $n>3t$ — GM93.
• Deterministic protocols need $t+1$ rounds, even with authentication — DS83; deterministic protocols without authentication send $\Omega (nt)$ messages — DR82.
• Over private channels, a randomized protocol reaches agreement in an expected constant number of rounds against $t<n/3$ — FM88.
• The threshold is optimal: for $t\ge n/3$ no broadcast protocol exists over authenticated channels without setup (no reduction from authenticated channels to Byzantine broadcast) — FLM85.