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?


1 Answer 1


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}$.

Generally speaking, classical results that require honest majority will generalize to any Q2 corruption pattern. Results that require honest two-thirds majority generalize to Q3.

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.

Regarding the question about broadcast, the actual tight bound depends very heavily on the model (poly-time vs information-theoretic, [im]perfect security, PKI setup). Also agreement, consensus, and broadcast are all slightly different. But in general, information-theoretic broadcast with no setup requires honest 2/3rds majority (Q3 corruptions).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.