Brief Announcement: Single-Round Broadcast: Impossibility, Feasibility, and More

We investigate the above research questions, and our results are summarized as follows.

There are limited works that consider broadcast with selective abort. As mentioned in Introduction, Goldwasser and Lindell proposed a 2-round broadcast protocol that is secure with selective abort in the plain model [17, 18] (hereafter, GL protocol). GL protocol is widely-used in MPC with abort (e.g. [13, 5]). In these MPC works, the authors are able to improve the communication complexity of GL protocol by introducing hash function [13] or utilizing the random linear combination technique [5]; however, to the best of knowledge, none of the previous works are able to reduce the round complexity of GL protocol.

We denote the security parameter by $\lambda \in \mathbb{N}$. A function $\mathrm{𝗇𝖾𝗀𝗅}:\mathbb{N}\to {ℝ}_{\ge 0}$ is negligible if for every polynomial $p(\cdot )$ there exists ${\lambda }_0$ such that for all $\lambda >{\lambda }_0$ we have . We write $\mathrm{PPT}$ for a probabilistic polynomial-time algorithm.

The digital signature scheme can ensure the integrity of a message. A digital signature scheme ($\mathrm{𝖣𝖲}$) consists of the following algorithms:

• $\mathrm{■}$

  $(\mathrm{𝗉𝗄},\mathrm{𝗌𝗄})\leftarrow \mathrm{𝖣𝖲}.\mathrm{𝖪𝖾𝗒𝖦𝖾𝗇}(1^{\lambda })$: It takes the security parameter $\lambda$ as input, and it outputs the public key $\mathrm{𝗉𝗄}$ and the signing key $\mathrm{𝗌𝗄}$.

• $\mathrm{■}$

  $\sigma \leftarrow \mathrm{𝖣𝖲}.\mathrm{𝖲𝗂𝗀𝗇}(\mathrm{𝗌𝗄},m)$: It takes the signing key $\mathrm{𝗌𝗄}$ and the message $m$ as inputs, and it outputs the signature $\sigma$ for the message $m$.

• $\mathrm{■}$

  $\{0,1\}\leftarrow \mathrm{𝖣𝖲}.\mathrm{𝖵𝖾𝗋𝗂𝖿𝗒}(\mathrm{𝗉𝗄},m,\sigma )$: It takes the public key $\mathrm{𝗉𝗄}$, the message $m$ and the signature $\sigma$ as inputs, and it outputs a bit $b\in \{0,1\}$ indicating the acceptance or rejection.

We require the digital signature scheme to be correct and existentially unforgeable under chosen message attacks (EUF-CMA). Formally, we have the following definitions.

In this work, we construct protocols and analyze their security in the Universal Composition (UC) framework by Canetti [9]. We refer readers to see details in [9].

In this subsection, we provide the ideal functionality for broadcast ${ℱ}_{\mathrm{𝖡𝖢}}$ in Figure 1, which is adapted from [18]. The functionality ${ℱ}_{\mathrm{𝖡𝖢}}$ interacts with a set of parties $P_1,\mathrm{\dots },P_n$ and the ideal-world adversary $𝒮$. Upon receiving the message $m$ from any party, ${ℱ}_{\mathrm{𝖡𝖢}}$ will forward the message $m$ to the rest receiving parties; however, $𝒮$ can cause any honest receiving party to abort. Notice that, in ${ℱ}_{\mathrm{𝖡𝖢}}$, $𝒮$ can make honest receiving parties abort, but $𝒮$ cannot make honest receiving parties output two distinct messages.

We introduce the notion of a consistent oracle (Definition 3) to model a variety of global-setup behaviours. This notion is adapted from the monotonically consistent oracle of [14], which was originally used to establish impossibility results for non-interactive commitment and zero-knowledge protocols in global setups (e.g., the global random oracle) within the generalized UC framework [10].

We prove that 1-round one-time broadcast is impossible to achieve using only consistent oracles, even in the presence of a static adversary. We use the method of proof by contradiction to prove the impossibility result. First of all, we assume there exists a 1-round one-time broadcast protocol using only secure P2P channels. Notice that, since we consider the simultaneous communication model, the sending party (say, $P_1$) is allowed to send messages to the receiving parties (say, $P_2,\mathrm{\dots },P_n$) via secure P2P channels, and the receiving parties are allowed to communicate with each other, and each parties’ messages should not depend on each other. Let us consider the case where the sending party $P_1$ gets corrupted. Let $m,m^{\prime }$ be two distinct messages, and let ${\mathrm{𝗌𝗆𝗌𝗀}}_i$ (resp. ${\mathrm{𝗌𝗆𝗌𝗀}}_i^{\prime }$) be the message that an honest sending party should send to the $i$-th honest receiving party $P_i$ on input $m$ (resp. $m^{\prime }$); note that, the message ${\mathrm{𝗌𝗆𝗌𝗀}}_i$ (resp. ${\mathrm{𝗌𝗆𝗌𝗀}}_i^{\prime }$) may contain $m$ (resp. $m^{\prime }$). Let ${\mathrm{𝗋𝗆𝗌𝗀}}_{i,j}$ be the message that an honest receiving party should send to the $j$-th honest receiving party $P_j$. Upon receiving ${\mathrm{𝗌𝗆𝗌𝗀}}_i$ (resp. ${\mathrm{𝗌𝗆𝗌𝗀}}_i^{\prime }$) and ${\{{\mathrm{𝗋𝗆𝗌𝗀}}_{i,j}\}}_{i\in [2,n]\setminus \{j\}}$, the $j$-th honest receiving party $P_j$ should output $m$ (resp. $m^{\prime }$). With above notations, we can consider the following adversary’s strategy: the adversary can instruct the corrupted sending party to query the consistent oracle to prepare ${\{{\mathrm{𝗌𝗆𝗌𝗀}}_i\}}_{i\in [2,n]}$ and ${\{{\mathrm{𝗌𝗆𝗌𝗀}}_i^{\prime }\}}_{i\in [2,n]}$; notice that, the corrupted sending party is capable of doing this by definition of the consistent oracle. Then the adversary can instruct the corrupted sending party to send ${\mathrm{𝗌𝗆𝗌𝗀}}_2$ to the first receiving party $P_2$, and send ${\{{\mathrm{𝗌𝗆𝗌𝗀}}_j^{\prime }\}}_{j\in [3,n]}$ to the rest receiving parties respectively; as a result, $P_2$ will output $m$ while other receiving parties will output $m^{\prime }$, which violates the consensus property of the one-time broadcast protocol.

Next, we provide the formal theorem statement and the proof is deferred in the full version.