# Under what conditions is broadcast possible? (Cryptographically, and in the model of Maurer 2006)

In this paper, Ueli Maurer uses a very cool model to generalize a number of results about broadcast, secret sharing and secure multiparty computation. Rather than talking about an adversary being either active (malicious) or passive (semi-honest) and having a threshold on the number of parties it controls, instead there are sets of sets of nodes $$\Delta$$ and $$\Sigma$$ such that the adversary may have active control of any set $$A \in \Delta$$ and passive control of any set $$B$$ such that $$A \cup B \in \Sigma$$.

Maurer states (Theorem 1) that:

"The simulation of a broadcast channel is secure against a $$(\Sigma,\Delta)$$-adversary is possible if and only if $$P \notin \Delta \sqcup \Delta \sqcup \Delta$$."

Here $$P$$ is the set of all nodes and $$X\sqcup Y = \{x \in X, y\in Y : x \cup y\}$$.

A corollary of this is that for a fixed threshold, we require $$t < |P|/3$$, where $$t$$ is the maximum number of nodes that may be actively controlled by the adversary.

Is Maurer just referring to the information theoretic case? Because I seem to remember reading somewhere that assuming cryptographic signatures you can have broadcast with up to $$t < |P|/2$$ malicious parties.

If so what is the tight limit for broadcast using Maurer's notation in the case of a polynomially-bound adversary, secure signatures and some public key infrastructure?

This is a somewhat standard method for generalizing results based on threshold adversaries. Let $$n$$ be the number of parties and let $$\mathcal{C} \subseteq 2^{[n]}$$ denote the family of subsets that the adversary can corrupt. For example, in the case of honest majority, $$\mathcal{C} = \{ C \subseteq [n] : |C| < n/2 \}$$.
• $$\mathcal{C}$$ has the Q2 property if no two corruptible sets $$A, B \in \mathcal{C}$$ satisfy $$A \cup B = [n]$$. In Maurer's notation, $$[n] \not\in \mathcal{C} \sqcup \mathcal{C}$$.
• $$\mathcal{C}$$ has the Q3 property if no three corruptible sets $$A, B,C \in \mathcal{C}$$ satisfy $$A \cup B \cup C = [n]$$. In Maurer's notation, $$[n] \not\in \mathcal{C} \sqcup \mathcal{C} \sqcup \mathcal{C}$$.
I think the first appearance of this generalization is in Complete Characterization of Adversaries Tolerable in Secure Multi-Party Computation by Hirt & Maurer. It's generalized even farther in MPC vs. SFE: Perfect Security in a Unified Corruption Model by Beerliova-Trubiniova et al. They consider an adversary that can corrupt any $$S \in \mathcal{P}$$ passively, or corrupt any $$S \in \mathcal{A}$$ actively, or corrupt any $$S \in \mathcal{F}$$ in a fail-stop way. These results are harder to state in a stackexchange answer.