eventually pass the threshold $|R_{i}|\geq n-t$ and A-Cast $R_{i}^{(n-t)}$.

Whenever an honest party $P_{h}$ adds $P_{j}$ to $R_{h}$, any other honest
party $P_{i}$ will eventually add $P_{j}$ to $R_{i}$. This is because $P_{h}$
received some $G_{j}^{\prime}$ from $P_{j}$’s A-Cast, where
$|G_{j}^{\prime}|=n-t$ and $G_{j}^{\prime}\subseteq G_{h}$, so eventually
$P_{i}$ will receive the same $G_{j}^{\prime}$, and following the analysis
above it will eventually hold that $G_{j}^{\prime}\subseteq G_{i}$ as well.
Since every honest party $P_{h}$ eventually A-Casts $R_{h}^{(n-t)}$, every
honest party $P_{i}$ will eventually receive at least $n-t$ A-Casts
$R_{j}^{\prime}$ satisfying $|R_{j}^{\prime}|=n-t$ and
$R_{j}^{\prime}\subseteq R_{i}$. Thus, every honest party $P_{i}$ will
eventually pass the threshold $|S_{i}|\geq n-t$ and record $Z_{i}$.

For each honest party $P_{i}$, every $P_{j}\in Z_{i}$ will eventually be added
to $G_{h}$ by any other honest party $P_{h}$. Thus, all honest parties will
eventually start the reconstruction of all the secrets attached to every
$P_{j}\in Z_{i}$, and $P_{i}$ will eventually be able to compute each tally
$v_{j}$ that it needs to determine its output $z_{i}$. In actuality, this
reasoning does not take into account the termination of parties; this is
resolved via the termination procedure at the end of the protocol. An honest
party $P_{i}$ who is able to compute $z_{i}$ on its own does not terminate
immediately, but rather A-Casts $z_{i}$ and continues to participate in the
protocol (in particular, in the reconstruction of secrets). Eventually $P_{i}$
will receive at least $n-t$ A-Casts $z_{j}^{\prime}$, at which point it can
safely terminate with the knowledge than any other honest party $P_{h}$ will
eventually receive those same A-Casts (even if $P_{h}$ is unable to compute
$z_{h}$). By taking the mode of these $n-t$ values, the majority of which must
have been suggested by honest parties, it is guaranteed that all honest
parties will output the same value in the case of a successful coin toss.

In summary, the protocol $\Pi_{\mathsf{a\mathchar 45\relax occ}}$ ensures
termination by guaranteeing that each honest party eventually satisfies the
required thresholds and proceeds to the necessary phases of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}$. This guarantees eventual
output generation without any deadlocks, preserving the perfect
indistinguishability of the real and ideal worlds.

We now claim that the overall round complexity of $\Pi_{\mathsf{a\mathchar
45\relax occ}}$ is constant. The protocol consists of a constant number of
steps, each involving constant-round operations. Note that by ensuring that
the underlying building blocks $\mathcal{F}_{\mathsf{a\mathchar 45\relax
cast}}$ and $\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}$ have constant-
round realizations, we are able to preserve the overall constant round
complexity of protocol $\Pi_{\mathsf{a\mathchar 45\relax occ}}$ even after
replacing $\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ and
$\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}$ with actual protocols
realizing them.

We can conclude that the executions of $\Pi_{\mathsf{a\mathchar 45\relax
occ}}^{V}$ with $\mathcal{A}$ and $\mathcal{F}_{\mathsf{a\mathchar 45\relax
occ}}^{V,p}$ with $\mathcal{S}$ are perfectly indistinguishable to any
environment $\mathcal{Z}$. This ensures that $\Pi_{\mathsf{a\mathchar 45\relax
occ}}^{V}$ UC-realizes $\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}^{V,p}$
with perfect security. ∎

##  5 Concurrent A-BA in Expected-Constant Rounds

Concurrent A-BA plays a significant role in existing asynchronous MPC
protocols, including those described in [7, 14, 57, 13, 58, 31, 25, 19, 63].
Its primary purpose is to address the lack of coordination among the parties,
which is amplified in the asynchronous setting. Specifically, it enables
parties to reach agreement on a common subset of input providers (the “core
set” [7]). This capability is essential in various applications within
asynchronous networks, where the different delays experienced by each party
can lead to discrepancies in their respective views.

In this section, we dive into the important problem of achieving concurrent
A-BA in an expected-constant number of rounds. As discussed in the
Introduction, Ben-Or and El-Yaniv [9] highlighted the potential issue of
running multiple executions of a probabilistic-termination protocol in
parallel, which could lead to an increase in the expected number of rounds
required for _all_ executions to terminate. The concurrent A-BA protocol
proposed in [9] relies on A-OLE and multi-valued A-BA, which can be
instantiated using our A-OCC protocol from Section 4 and the extended A-BA
protocol from [34, 70], respectively. However, during our analysis, we
discovered certain issues in their analysis that cast doubt on the expected-
constant round complexity of one of their main building blocks and,
consequently, their concurrent A-BA protocol. For a more comprehensive
presentation of these issues, see Appendix A. It is unclear how to address
these issues without modifying the protocol itself.

To rectify these concerns, we modify the underlying message distribution
mechanism and incorporate an additional layer of message validation. These
changes not only resolve the identified issues, but also significantly
simplify the protocol. It is worth emphasizing that our revised concurrent
A-BA protocol achieves a level of simplicity that is comparable to the
synchronous version proposed in [9]. This accomplishment is significant
because when designing an asynchronous counterpart to a synchronous protocol,
achieving a level of simplicity on par with the synchronous version is often
considered the ideal outcome. In the following, we present an ideal
functionality for concurrent A-BA, describe our protocol, an ideal
functionality for concurrent A-BA, and its required building blocks, and
provide a security proof.

###  5.1 Concurrent A-BA Ideal Functionality

Concurrent A-BA, as the name suggests, refers to a primitive that enables
parties to solve $N$ instances of A-BA concurrently. We are primarily
interested in the case $N=n$, corresponding to the emulation of $n$ ideal A-BA
primitives, commonly used in asynchronous MPC protocols to form the core set
and overcome low message dispersion. However, in our study, we consider a more
general version that allows for a broader range of values for $N$. In this
setting, each party $P_{i}$ initiates the concurrent A-BA by providing $N$
values, namely $v_{i,1},\ldots,v_{i,N}$. Subsequently, all parties receive the
same set of $N$ output values, denoted as $y_{1},\ldots,y_{N}$. Each
individual output value $y_{j}$ is computed based on the input values
$v_{1,j},\ldots,v_{n,j}$, following the prescribed procedure outlined in the
standard A-BA primitive. Specifically, if $n-2t$ input values are identical,
that common value (which we require to be unique) is selected as the output;
otherwise, the output is determined by the adversary. We capture the task of
concurrent A-BA using the ideal functionality
$\mathcal{F}_{\mathsf{conc\mathchar 45\relax a\mathchar 45\relax ba}}$, shown
in Figure 7. Since we are able to achieve non-intrusion validity (i.e., for
each instance, the corresponding output must be either $\bot$ or the
corresponding input of an honest party), we present an _intrusion-tolerant_
concurrent A-BA functionality.

Functionality $\mathcal{F}_{\mathsf{conc\mathchar 45\relax a\mathchar 45\relax
ba}}^{V,N}$ The functionality is parameterized by a set $V$ of values and a
positive integer $N$ representing the number of concurrent instances, and
proceeds as follows. At the first activation, verify that
$\mathsf{sid}=(\mathcal{P},\mathsf{sid}^{\prime})$, where $\mathcal{P}$ is a
player set of size $n$. For each $P_{i}\in\mathcal{P}$, initialize
$v_{i,1},\ldots,v_{i,N}$ to a default value $\bot$,
$\mathsf{participated}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=0$,
and delay values
$D^{\mathrm{input}}_{i}=D^{\mathrm{output}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$.
Also initialize $y_{1},\ldots,y_{N}$ to $\bot^{\prime}$ and
$a_{1},\ldots,a_{N}$ to $\bot$, and
$t\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\lceil\frac{n}{3}\rceil-1$.
Upon receiving $(\texttt{delay},\mathsf{sid},P_{i},\mathsf{type},D)$ from the
adversary for $P_{i}\in\mathcal{P}$,
$\mathsf{type}\in\\{\mathrm{input},\mathrm{output}\\}$, and $D\in\mathbb{Z}$
represented in unary notation, update
$D^{\mathsf{type}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\max(1,D^{\mathsf{type}}_{i}+D)$
and send $(\texttt{delay-set},\mathsf{sid})$ to the adversary. Upon receiving
$(\texttt{input},\mathsf{sid},(v_{1},\ldots,v_{N}))$ from
$P_{i}\in\mathcal{P}$ (or the adversary on behalf of corrupted $P_{i}$), run
the Input Submission Procedure and send
$(\texttt{leakage},\mathsf{sid},P_{i},(v_{1},\ldots,v_{N}))$ to the adversary.
Upon receiving $(\texttt{replace},\mathsf{sid},(v_{1},\ldots,v_{N}))$ from the
adversary, record
$(a_{1},\ldots,a_{N})\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(v_{1},\ldots,v_{N})$.
Upon receiving $(\texttt{fetch},\mathsf{sid})$ from $P_{i}\in\mathcal{P}$ (or
the adversary on behalf of corrupted $P_{i}$), run the Input Submission and
Output Release Procedures, and send $(\texttt{fetched},\mathsf{sid},P_{i})$ to
the adversary and any messages set by the Output Release Procedure to $P_{i}$.
Input Submission Procedure: If $\mathsf{participated}_{i}=0$ and
$(\texttt{input},\mathsf{sid},(v_{1},\ldots,v_{N}))$ was previously received
from $P_{i}$, then do: 1. Update
$D^{\mathrm{input}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D^{\mathrm{input}}_{i}-1$.
2. If $D^{\mathrm{input}}_{i}=0$, then set
$\mathsf{participated}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$
and record
$(v_{i,1},\ldots,v_{i,N})\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(v_{1},\ldots,v_{N})$.
Output Release Procedure: If $\sum_{j=1}^{n}\mathsf{participated}_{j}\geq n-t$
then do: 1. Update
$D^{\mathrm{output}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D^{\mathrm{output}}_{i}-1$.
2. If $D^{\mathrm{output}}_{i}=0$, then do the following. For each $j\in[N]$
do: if $y_{j}=\bot^{\prime}$, then set
$y_{j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=x$ if there
exists a unique value $x\in V$ such that $x=v_{k,j}$ for at least $n-2t$
inputs $v_{k,j}$; else if $a_{j}=\bot$ or $a_{j}\in V$ was provided by at
least one honest party, then set
$y_{j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=a_{j}$; else set
$y_{j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bot$.
Additionally, set $(\texttt{output},\mathsf{sid},(y_{1},\ldots,y_{N}))$ to be
sent to $P_{i}$.

Figure 7: The (intrusion-tolerant) concurrent A-BA functionality.

###  5.2 The Simplified Concurrent A-BA Protocol

#### Building blocks.

Our concurrent A-BA protocol relies on A-Cast as the fundamental communication
primitive due to its enhanced guarantees compared to basic message
distribution mechanisms. The ideal functionality
$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$, which models the A-Cast
primitive, was described in Section 3.2.

As another crucial building block, our protocol incorporates asynchronous
oblivious leader election (A-OLE) as a coordination mechanism among the
parties. A-OLE enables parties to randomly elect a leader from among
themselves. The term “oblivious” indicates that parties are unaware of whether
or not agreement on a random leader has been achieved. In our concurrent A-BA
protocol, similar to the approach described in [9], there comes a point where
all parties suggest outputs, and A-OLE assists them in reaching agreement on
the output by adopting the suggestion of the elected leader. To capture the
task of A-OLE, we parameterize the A-OCC functionality
$\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$, given in Section 4.1, by a
domain with size equal to the number of parties. This yields an ideal
functionality for A-OLE, denoted as $\mathcal{F}_{\mathsf{a\mathchar 45\relax
ole}}$, which is defined as $\mathcal{F}_{\mathsf{a\mathchar 45\relax
occ}}^{[n],p}$ for appropriate $p\in\Theta(1)$. Recall from Theorem 1 that
$\mathcal{F}_{\mathsf{a\mathchar 45\relax ole}}$ can be realized using
protocol $\Pi_{\mathsf{a\mathchar 45\relax occ}}^{[n]}$.

Our concurrent A-BA protocol leverages both binary and multi-valued A-BA.
Binary A-BA is employed to achieve agreement on a critical decision within the
protocol, namely whether to continue a particular iteration. On the other
hand, the use of multi-valued A-BA addresses the inherent obliviousness of the
A-OLE primitive by providing a means for parties to reach an agreement on the
output, and it doubly serves as an agreement on termination. The ideal
functionality for A-BA was described in Section 3.2.

As in [9], another essential component in our concurrent A-BA protocol is
truncated executions of an A-BA protocol limited to a predefined number of
iterations, consequently implying a fixed number of rounds. In the spirit of
[23], we model those executions with the ideal functionality
$\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax ba}}$,
defined in Figure 8. $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar
45\relax ba}}$ is parameterized with $V$, $p$, and $\mathsf{itr}$, where $V$
denotes the domain, $p$ represents the termination probability in each
iteration, and $\mathsf{itr}$ indicates the maximum number of iterations in
the execution.

This ideal functionality also encapsulates a “1-shift” property for
termination, meaning that all honest parties produce the output within two
consecutive iterations. We note that the adversary has the discretion to
determine which parties discover the output first. Unlike a traditional A-BA
functionality that outputs a single value,
$\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax ba}}$
produces a vector of values that includes the output after each iteration of
the execution. Modeling the 1-shift property and providing outputs for all
iterations is crucial since our concurrent A-BA protocol relies on those
properties of truncated executions of A-BA.

Functionality $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar
45\relax ba}}^{V,p,\mathsf{itr}}$ The functionality is parameterized by a set
$V$ of values, a probability $p$, and an integer $\mathsf{itr}$ representing
the number of iterations to run for, and proceeds as follows. At the first
activation, verify that $\mathsf{sid}=(\mathcal{P},\mathsf{sid}^{\prime})$,
where $\mathcal{P}$ is a player set of size $n$. For each
$P_{i}\in\mathcal{P}$, initialize value $v_{i}$ and vector $y_{i}$ to a
default value $\bot$,
$\mathsf{participated}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=0$,
and delay values
$D^{\mathrm{input}}_{i}=D^{\mathrm{output}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$.
Also initialize values $y$, $a$, and $r$ to $\bot$, the set $\mathcal{E}$ of
parties receiving output earlier to $\mathcal{P}$, and
$t\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\lceil\frac{n}{3}\rceil-1$.
Upon receiving $(\texttt{delay},\mathsf{sid},P_{i},\mathsf{type},D)$ from the
adversary for $P_{i}\in\mathcal{P}$,
$\mathsf{type}\in\\{\mathrm{input},\mathrm{output}\\}$, and $D\in\mathbb{Z}$
represented in unary notation, update
$D^{\mathsf{type}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\max(1,D^{\mathsf{type}}_{i}+D)$
and send $(\texttt{delay-set},\mathsf{sid})$ to the adversary. Upon receiving
$(\texttt{early},\mathsf{sid},\mathcal{R})$ from the adversary, update
$\mathcal{E}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\mathcal{R}$.
Upon receiving $(\texttt{input},\mathsf{sid},v)$ from $P_{i}\in\mathcal{P}$
(or the adversary on behalf of corrupted $P_{i}$), run the Input Submission
Procedure and send $(\texttt{leakage},\mathsf{sid},P_{i},v)$ to the adversary.
Upon receiving $(\texttt{replace},\mathsf{sid},v)$ from the adversary, record
$a\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=v$. Upon receiving
$(\texttt{fetch},\mathsf{sid})$ from $P_{i}\in\mathcal{P}$ (or the adversary
on behalf of corrupted $P_{i}$), run the Input Submission and Output Release
Procedures, and send $(\texttt{fetched},\mathsf{sid},P_{i})$ to the adversary
and any messages set by the Output Release Procedure to $P_{i}$. Input
Submission Procedure: If $\mathsf{participated}_{i}=0$ and
$(\texttt{input},\mathsf{sid},v)$ was previously received from $P_{i}$, then
do: 1. Update
$D^{\mathrm{input}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D^{\mathrm{input}}_{i}-1$.
2. If $D^{\mathrm{input}}_{i}=0$, then set
$\mathsf{participated}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$
and record $v_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=v$.
Output Release Procedure: If $\sum_{j=1}^{n}\mathsf{participated}_{j}\geq n-t$
then do: 1. Update
$D^{\mathrm{output}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D^{\mathrm{output}}_{i}-1$.
2. If $D^{\mathrm{output}}_{i}=0$, then do the following. If $r=\bot$, then
sample $r\leftarrow\mathrm{Geometric}(p)$202020Recall that the geometric
distribution corresponds to the termination probability in expected-constant-
round A-BA protocols. Moreover, by adjusting this distribution, the
functionality can be generalized to accommodate other A-BA protocols. and set
$y\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=x$ if there exists a
unique value $x\in V$ such that $x=v_{k}$ for at least $n-2t$ inputs $v_{k}$;
else if $a=\bot$ or $a\in V$ was provided by at least one honest party, then
set $y\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=a$; else set
$y\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bot$. If
$y_{i}=\bot$ then do: If $P_{i}\in\mathcal{E}$, then for $1\leq k<r$ let
$y_{i,k}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\lambda$ (the
empty string) and for $r\leq k\leq\mathsf{itr}$ let
$y_{i,k}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=y$. If
$P_{i}\notin\mathcal{E}$, then for $1\leq k\leq r$ let
$y_{i,k}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\lambda$ and
for $r<k\leq\mathsf{itr}$ let
$y_{i,k}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=y$. Set
$y_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(y_{i,1},\ldots,y_{i,\mathsf{itr}})$.
Additionally, set $(\texttt{output},\mathsf{sid},y_{i})$ to be sent to
$P_{i}$.

Figure 8: The (intrusion-tolerant) truncated A-BA functionality with the
1-shift property.

It is worth mentioning that $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax
a\mathchar 45\relax ba}}^{V,p,\mathsf{itr}}$ can be implemented by executing
any intrusion-tolerant A-BA protocol with the 1-shift property and a
termination probability of $p$ in each iteration, precisely for $\mathsf{itr}$
iterations, and concatenating the output of all iterations to get the final
output (with $\lambda$ representing iterations without output). Canetti and
Rabin’s binary A-BA protocol [34] possesses the desired properties of
intrusion tolerance and terminating with a constant probability in each
iteration. However, using Bracha’s technique for termination [16] in Canetti
and Rabin’s binary A-BA protocol does not admit the 1-shift property. The main
reason is that parties may take the shortcut and use Bracha termination
messages to generate the output in their very early iterations. Fortunately,
Bracha’s termination procedure is unnecessary in the truncated execution of
Canetti and Rabin’s binary A-BA protocol. This is primarily due to the fact
that all parties will naturally terminate after a fixed number of iterations.
With this adjustment, Canetti and Rabin’s binary A-BA protocol also
successfully attains the 1-shift property. Moreover, Mostéfaoui and Raynal’s
multi-valued A-BA protocol [70] offers intrusion tolerance, the 1-shift
property, and terminating with a constant probability in each iteration if the
underlying binary A-BA used in their construction also exhibits these
characteristics. Thus, we can formulate the following proposition about
realizing $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax
ba}}^{V,p,\mathsf{itr}}$.

######  Proposition 5.

For some constant probability $p$, any domain $V$, and any integer
$\mathsf{itr}$, $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar
45\relax ba}}^{V,p,\mathsf{itr}}$ can be UC-realized with statistical security
in the $\mathcal{F}_{\mathsf{a\mathchar 45\relax smt}}$-hybrid model, in
constant rounds and in the presence of an adaptive and malicious
$t$-adversary, provided $t<n/3$.

The above statement guarantees statistical security since the A-BA protocols
we consider rely on the A-VSS primitive, which can only be realized with
statistical security when $t<n/3$. In fact, by working in the
$\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}$-hybrid model, we can achieve
perfectly secure $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar
45\relax ba}}$. We remark that the intrusion tolerance of
$\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax ba}}$ is not
a requirement in our concurrent A-BA protocol; however, employing a non-
intrusion-tolerant version of truncated A-BA will naturally lead to a non-
intrusion-tolerant concurrent A-BA protocol.

#### The new concurrent A-BA protocol.

Our protocol builds on the core ideas presented in [9]. In addition to
instantiating the missing OLE building block using our OCC protocol from
Section 4, we address the issue in the analysis by redesigning the message
distribution phase. Our revised message distribution mechanism not only
resolves the issue in the proof but also provides stronger guarantees, which
in turn simplifies the final protocol design. In fact, apart from the message
distribution phase, the overall structure of our protocol closely resembles
the synchronous version of the protocol described in [9], as illustrated in
Figure 9.

Figure 9: Side-by-side comparison of our simplified concurrent A-BA protocol
(left) and Ben-Or and El-Yaniv’s concurrent (synchronous) BA protocol (right).

Before diving into the high-level description of our protocol, we highlight
the choices we made in the message distribution mechanism and discuss some
alternative approaches that fail to meet our requirements. In the eventual-
delivery model, at least $n-t$ parties will receive each other’s messages if
they wait for a sufficient duration, as messages from honest parties will
eventually be delivered to one another, but determining the exact waiting time
required is not straightforward. One possible approach is to instruct parties
to A-Cast the identities of the parties from which they have received
messages. After constructing a graph with parties as vertices and adding edges
between parties that have reported message receipts from each other, we can
look for a clique of size $n-t$; however, finding a maximum clique is known to
be NP-complete and also difficult to approximate [43].

To overcome this challenge, one possible approach is to investigate
alternative structures that offer weaker guarantees regarding message
dispersion but can be efficiently identified [7, 14, 20, 72]. However, it is
important to note that this approach does not guarantee the precise message
dispersion required for our specific application. In our analysis, it is
crucial that _all_ honest parties receive messages from a linear fraction of
other parties. Even finding a clique of size $n-t$ does not guarantee this
level of message dispersion, rendering this approach unsuitable for our
protocol. Thus, we adopt another approach that has been used in prior works
[41, 34], and extend it by incorporating a precondition check before the
process and introducing a validation layer during the execution. These
additions enhance the guarantees, making them more suitable and effective for
our specific purpose. We proceed to explain our protocol.

Similar to the (synchronous) protocol described in [9], in our concurrent A-BA
protocol, each party initiates for every A-BA instance a batch of $m$
executions of the A-BA protocol (over the same inputs) for a fixed number of
iterations, denoted as $\mathsf{itr}$. If the A-BA protocol has a termination
probability of at least a constant value $p$ in each iteration, which is the
case for most existing A-BA protocols, suitable values of $m$ and
$\mathsf{itr}$ can be determined so that each party obtains at least one
output value for each batch. Each party then selects an output for each
instance and forms a suggestion for the final output. The next paragraph,
which explains the mechanism for distributing suggestions among parties, is
our main modification to the protocol. Then, for the remaining part, we can
use a similar structure as the synchronous version of the protocol.

Firstly, parties initiate a binary A-BA protocol to determine a specific
condition that allows for choosing and validating suggested outputs later in
the execution. Based on the outcome of this binary A-BA, parties decide
whether to continue or start over. In the case of continuation, parties
perform A-Cast operations to distribute their suggestions and wait to receive
suggestions from other parties. Each party only accepts an A-Cast message
containing a suggested output if the value is consistent with the outputs
obtained from its own truncated A-BA executions. This validation step is
crucial as it ensures that even corrupted parties provide acceptable (correct)
suggestions. The validation is based on the 1-shift property of A-BA that
ensures all honest parties terminate within two consecutive iterations.
Parties wait to accept A-Casts of suggested outputs from at least $n-t$
parties and then A-Cast the set of all these $n-t$ suggestions along with the
identities of the corresponding senders.212121In fact, it suffices to A-Cast
the identities alone. We primarily use this observation to simplify the
description of the protocol, though it also reduces the communication
complexity. They continue accepting A-Casts of suggestions and sets until they
receive at least $n-t$ sets that are fully contained within their accepted
suggestions. At this point, a sufficient number of messages have been
exchanged, and using a counting argument similar to the one in [41, 34], it
can be deduced that at least $n-2t>n/3$ parties have their suggested outputs
received by all honest parties.

After the message distribution phase described above, our protocol proceeds
similarly to the synchronous protocol presented in [9]. Specifically, parties
execute OLE to elect a random leader to adopt its suggested output.
Subsequently, a multi-valued A-BA is performed on the adopted output to
address the oblivious nature of OLE. Depending on whether agreement on a non-
default output is reached, this results in the termination or restarting of
the protocol. The intrusion-tolerance property of multi-valued A-BA is crucial
to make sure that the common output is not provided by a corrupted party
alone. It is worth noting that the favorable scenario occurs when the leader
is among the $n-2t$ parties whose suggested outputs have been accepted by all
honest parties. If the leader is elected randomly, this event happens with a
probability of $1/3$. In this case, all parties adopt the same output,
resulting in termination.

It is worth noting that the set of $n-2t$ parties whose suggested outputs have
been accepted by all honest parties may only contain a single honest party.
This single honest party can only be elected with a probability of $O(1/n)$ by
the OLE. However, due to the validation step in the message-distribution
phase, there is no longer a need to ensure that an honest leader is elected,
as the suggested values from corrupted parties are considered valid outputs.
Refer to Figure 10 for a formal description of protocol
$\Pi_{\mathsf{conc\mathchar 45\relax a\mathchar 45\relax ba}}$.

Protocol $\Pi_{\mathsf{conc\mathchar 45\relax a\mathchar 45\relax
ba}}^{V,N,m,p,\mathsf{itr}}$ The protocol is parameterized by a set $V$ of
possible inputs (for each instance), positive integers $N$ and $m$
representing respectively the number of instances and the number of batched
executions to run per instance, a termination probability $p$, and the number
$\mathsf{itr}$ of iterations after which to truncate the executions. At the
first activation, verify that
$\mathsf{sid}=(\mathcal{P},\mathsf{sid}^{\prime})$ for a player set
$\mathcal{P}$ of size $n$. Let
$t\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\lceil\frac{n}{3}\rceil-1$.
Party $P_{i}\in\mathcal{P}$ proceeds as follows. Initialize sets $Q_{i,1}$,
$Q_{i,2}$, and $W_{i}$ to $\emptyset$, flag $\mathsf{finished}$ to 0, and
counter $\varphi$ to $1$. Also initialize
$S_{i,j}^{r}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\emptyset$,
$b_{j,k}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=0$,
$\vec{C}_{h}^{\prime}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bot$,
and $y_{i,j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bot$ for
all $h\in[n]$, $j\in[N]$, $k\in[m]$, and $\mathsf{itr}\leq
r\leq\mathsf{itr}+3$. Upon receiving input
$(\texttt{input},\mathsf{sid},(v_{i,1},\ldots,v_{i,N}))$ from the environment
where $v_{i,1},\ldots,v_{i,N}\in V$, do the following. For each $j\in[N]$ and
$k\in[m]$, send $(\texttt{input},\mathsf{sid}_{\varphi}^{j,k},v_{i,j})$ to an
instance of $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax
ba}}^{V,p,\mathsf{itr}+3}$ with SID
$\mathsf{sid}_{\varphi}^{j,k}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\mathsf{sid},\varphi,j,k)$.
Upon receiving input $(\texttt{fetch},\mathsf{sid})$ from the environment, if
$\mathsf{finished}=1$ then output
$(\texttt{output},\mathsf{sid},(y_{i,1},\ldots,y_{i,N}))$ to the environment;
else do: 1. For each $j\in[N]$ and $k\in[m]$, fetch the output from the
instance of $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax
ba}}^{V,p,\mathsf{itr}+3}$ with SID $\mathsf{sid}_{\varphi}^{j,k}$. Upon
receiving back
$(\texttt{output},\mathsf{sid}_{\varphi}^{j,k},(z_{i,1},\ldots,z_{i,\mathsf{itr}+3}))$,
update
$S_{i,j}^{r}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=S_{i,j}^{r}\cup\\{z_{i,r}\\}\setminus\\{\lambda\\}$
for $\mathsf{itr}\leq r\leq\mathsf{itr}+3$, and also set
$b_{j,k}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$. 2. Wait
until $b_{j,k}=1$ for all $j\in[N]$ and $k\in[m]$. Then, let
$\mathsf{continue}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$
if for all $j\in[N]$ it holds that $S_{i,j}^{\mathsf{itr}}\not=\emptyset$, and
$\mathsf{continue}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=0$
otherwise; send
$(\texttt{input},\mathsf{sid}_{\varphi}^{\mathrm{cont}},\mathsf{continue}_{i})$
to an instance of $\mathcal{F}_{\mathsf{a\mathchar 45\relax ba}}^{\\{0,1\\}}$
with SID
$\mathsf{sid}_{\varphi}^{\mathrm{cont}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\mathsf{sid},\varphi,\texttt{cont})$.
3. Fetch the output from the instance of $\mathcal{F}_{\mathsf{a\mathchar
45\relax ba}}^{\\{0,1\\}}$ with SID $\mathsf{sid}_{\varphi}^{\mathrm{cont}}$.
Upon receiving back
$(\texttt{output},\mathsf{sid}_{\varphi}^{\mathrm{cont}},\mathsf{continue})$,
do the following. If $\mathsf{continue}=1$, wait until for all $j\in[N]$ it
holds that $S_{i,j}^{\mathsf{itr}+1}\not=\emptyset$; then for each $j\in[N]$
choose $c_{i,j}\in S_{i,j}^{\mathsf{itr}+1}$, and send
$(\texttt{send},\mathsf{sid}_{i,\varphi}^{\mathrm{vector}},(c_{i,1},\ldots,c_{i,N}))$
to an instance of $\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ with SID
$\mathsf{sid}_{i,\varphi}^{\mathrm{vector}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\mathcal{P},P_{i},\mathsf{sid}^{\prime},\varphi,\texttt{vector})$.
Otherwise, start over (i.e., increment $\varphi$, re-initialize all other
local variables, and run truncated A-BA $mN$ times again). 4. For each
$h\in[n]$, fetch the output from the instance of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ with SID
$\mathsf{sid}_{h,\varphi}^{\mathrm{vector}}$. Upon receiving back
$(\texttt{output},\mathsf{sid}_{h,\varphi}^{\mathrm{vector}},(c^{\prime}_{h,1},\ldots,c^{\prime}_{h,N}))$,
record
$\vec{C}_{h}^{\prime}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(c^{\prime}_{h,1},\ldots,c^{\prime}_{h,N})$
and for each $b\in\\{1,2\\}$ wait until it holds that $c^{\prime}_{h,j}\in
S_{i,j}^{\mathsf{itr}+1+b}$ for all $j\in[N]$; then update
$Q_{i,b}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=Q_{i,b}\cup\\{P_{h}\\}$.
5. Wait until $|Q_{i,1}|\geq n-t$. Then, send
$(\texttt{send},\mathsf{sid}_{i,\varphi}^{\mathrm{set}},Q_{i,1}^{(n-t)})$ to
an instance of $\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ with SID
$\mathsf{sid}_{i,\varphi}^{\mathrm{set}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\mathcal{P},P_{i},\mathsf{sid}^{\prime},\varphi,\texttt{set})$.
6. For each $h\in[n]$, fetch the output from the instance of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ with SID
$\mathsf{sid}_{h,\varphi}^{\mathrm{set}}$. Upon receiving back
$(\texttt{output},\mathsf{sid}_{h,\varphi}^{\mathrm{set}},Q_{h,1}^{\prime})$
where $|Q_{h,1}^{\prime}|=n-t$, wait until $Q_{h,1}^{\prime}\subseteq
Q_{i,2}$; then update
$W_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=W_{i}\cup\\{h\\}$.
7. Wait until $|W_{i}|\geq n-t$. Then, send
$(\texttt{input},\mathsf{sid}_{\varphi}^{\mathrm{elect}})$ to an instance of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax ole}}$ with SID
$\mathsf{sid}_{\varphi}^{\mathrm{elect}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\mathsf{sid},\varphi,\texttt{elect})$.
8. Fetch the output from the instance of $\mathcal{F}_{\mathsf{a\mathchar
45\relax ole}}$ with SID $\mathsf{sid}_{\varphi}^{\mathrm{elect}}$. Upon
receiving back
$(\texttt{output},\mathsf{sid}_{\varphi}^{\mathrm{elect}},l_{i})$, wait until
$|W_{i}|\geq n-t$; then send
$(\texttt{input},\mathsf{sid}_{\varphi}^{\mathrm{vector}},\vec{C}^{\prime}_{l_{i}})$
to an instance of $\mathcal{F}_{\mathsf{a\mathchar 45\relax
ba}}^{V^{N}\cup\\{\bot\\}}$ with SID
$\mathsf{sid}_{\varphi}^{\mathrm{vector}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\mathsf{sid},\varphi,\texttt{vector})$
if it holds that $P_{l_{i}}\in Q_{i,2}$, and send
$(\texttt{input},\mathsf{sid}_{\varphi}^{\mathrm{vector}},\bot)$ otherwise. 9.
Fetch the output from the instance of $\mathcal{F}_{\mathsf{a\mathchar
45\relax ba}}^{V^{N}\cup\\{\bot\\}}$ with SID
$\mathsf{sid}_{\varphi}^{\mathrm{vector}}$. Upon receiving back
$(\texttt{output},\mathsf{sid}_{\varphi}^{\mathrm{vector}},\vec{Y})$, if
$\vec{Y}\not=\bot$ then record
$(y_{i,1},\ldots,y_{i,N})\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\vec{Y}$
and set
$\mathsf{finished}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$;
else start over.

Figure 10: The concurrent A-BA protocol.

###  5.3 Security Proof

We now consider the security of our concurrent A-BA protocol. Before stating
the theorem, it is worth noting that the specific parameters of the hybrid
model, which combine the different ideal functionalities, are not explicitly
specified in the theorem statement. However, they can be determined from the
protocol’s parameters and are integral to the overall security guarantees of
the protocol. Now, let us state the theorem formally:

######  Theorem 2.

For any domain $V$, integer $N$, constant $0<p<1$, and constant integer
$\mathsf{itr}>1$, setting
$m\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\log_{\frac{1}{1-p}}N$,
the protocol $\Pi_{\mathsf{conc\mathchar 45\relax a\mathchar 45\relax
ba}}^{V,N,m,p,\mathsf{itr}}$ UC-realizes $\mathcal{F}_{\mathsf{conc\mathchar
45\relax a\mathchar 45\relax ba}}^{V,N}$ with statistical security in the
$(\mathcal{F}_{\mathsf{a\mathchar 45\relax
cast}},\mathcal{F}_{\mathsf{a\mathchar 45\relax
ba}},\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax
ba}},\mathcal{F}_{\mathsf{a\mathchar 45\relax ole}})$-hybrid model, in
expected-constant rounds and in the presence of an adaptive and malicious
$t$-adversary, provided $t<n/3$.

###### Proof.

Let $\mathcal{A}$ be an adversary in the real world. We construct a simulator
$\mathcal{S}$ in the ideal world, such that no environment $\mathcal{Z}$ can
distinguish whether it is interacting with $\Pi_{\mathsf{conc\mathchar
45\relax a\mathchar 45\relax ba}}^{V,N,m,p,\mathsf{itr}}$ and $\mathcal{A}$,
or with $\mathcal{F}_{\mathsf{conc\mathchar 45\relax a\mathchar 45\relax
ba}}^{V,N}$ and $\mathcal{S}$. Here, $V$ and $N$ are given parameters of the
problem, and $p$ is the parameter for the $\mathcal{F}_{\mathsf{trunc\mathchar
45\relax a\mathchar 45\relax ba}}$ hybrid, which is determined based on the
specific protocol used to realize it. The parameters $m$ and $\mathsf{itr}$
need to be appropriately adjusted based on the other parameters to ensure an
expected-constant round complexity for $\Pi_{\mathsf{conc\mathchar 45\relax
a\mathchar 45\relax ba}}^{V,N,m,p,\mathsf{itr}}$. As discussed below, setting
$m\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\log_{\frac{1}{1-p}}N$
for any constant integer $\mathsf{itr}>1$ suffices.

The simulator internally runs a copy of $\mathcal{A}$, and plays the roles of
all the hybrids and the parties in a simulated execution of the protocol. All
inputs from $\mathcal{Z}$ are forwarded to $\mathcal{A}$, and all outputs from
$\mathcal{A}$ are forwarded to $\mathcal{Z}$. Moreover, whenever $\mathcal{A}$
corrupts a party in the simulation, $\mathcal{S}$ corrupts the same party in
the ideal world by interacting with $\mathcal{F}_{\mathsf{conc\mathchar
45\relax a\mathchar 45\relax ba}}^{V,N}$, and if the corruption was direct
(i.e., not via either of the aiding functionalities), then $\mathcal{S}$ sends
$\mathcal{A}$ the party’s state and thereafter follows $\mathcal{A}$’s
instructions for that party. Moreover, $\mathcal{S}$ manages delays in the
ideal functionality based on the delays that $\mathcal{A}$ sets on the
hybrids.

The simulated execution begins when $\mathcal{S}$ receives messages of the
form $(\texttt{leakage},\mathsf{sid},\cdot,\cdot)$ from
$\mathcal{F}_{\mathsf{conc\mathchar 45\relax a\mathchar 45\relax ba}}^{V,N}$.
These messages contain the values that party $P_{i}$ receives as input from
the environment. $\mathcal{S}$ can derive these input values from the leakage
message $(\texttt{leakage},\mathsf{sid},P_{i},(v_{1},\ldots,v_{N}))$ by
setting $v_{i,j}=v_{j}$ for all $j\in[N]$. The set
$\\{v_{1,j},v_{2,j},\ldots,v_{n,j}\\}$ represents the inputs for the $j$th
instance of the (concurrent) A-BA that the parties are supposed to solve.

Upon receiving these leakage messages, $\mathcal{S}$ can initiate sessions of
$\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax ba}}$ with
the actual inputs. For each instance $j\in[N]$, $\mathcal{S}$ invokes $m$
sessions of $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax
ba}}$ with the inputs $v_{1,j},v_{2,j},\ldots,v_{n,j}$. After this point,
$\mathcal{S}$ continues the simulation by honestly playing the roles of other
ideal functionalities and honest parties involved in the protocol. Since there
are no private states that $\mathcal{S}$ needs to guess or fake in order to
provide a consistent view, the rest of the simulation proceeds
straightforwardly.

Now, this internal execution generates a transcript that is perfectly
indistinguishable from a real-world execution. Therefore, it remains to show
that the protocol execution indeed results in the same output as
$\mathcal{F}_{\mathsf{conc\mathchar 45\relax a\mathchar 45\relax ba}}^{V,N}$.
To demonstrate this, we first establish that with probability $1$ the
execution will eventually terminate. Additionally, we show that if at least
$n-2t$ parties have the same input value for any instance (and there is only
one such value), then everyone will receive that value as the output;
otherwise, the output will be either one of the inputs provided by some honest
parties for that instance or a special value $\bot$.

#### Termination.

After initializing some variables, the parties collectively initiate $m$
sessions of $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax
ba}}$ for each of the $N$ instances. Since the maximum number of corrupted
parties is $t$ and $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar
45\relax ba}}$ only requires the participation of $n-t$ parties, all sessions
of $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax ba}}$
will eventually terminate upon receiving a sufficient number of activations
from the environment (i.e., every honest party $P_{i}$ will eventually set
$b_{j,k}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$ for all
$j\in[N]$ and $k\in[m]$).

If, for all $N$ instances, the integer $r$ sampled in any of the $m$ sessions
of $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax ba}}$ for
that instance is at most $\mathsf{itr}-1$ (so that an honest party $P_{i}$
must eventually receive $z_{i,\mathsf{itr}}\not=\lambda$ from that session),
then every honest party $P_{i}$ eventually sets
$\mathsf{continue}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$.
Here, $r$ is sampled from the geometric distribution $\mathrm{Geometric}(p)$
(that corresponds to expected-constant-round A-BA as in [41, 34]). We define
$E$ as the event where for all instances at least one of the $m$ sessions of
$\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax ba}}$ has
$r\leq\mathsf{itr}-1$. The probability of event $E$ occurring can be
calculated as follows, using similar logic as presented in [9].

Define $A_{r_{0}}$ as the event where $\mathcal{F}_{\mathsf{trunc\mathchar
45\relax a\mathchar 45\relax ba}}$ does not sample $r=r_{0}$ given $r\geq
r_{0}$. Then

${\mathrm{Pr}}[A_{r_{0}}]=1-p.$

Therefore, for the event $B_{r_{0}}$, in which at least one of the $m$
$\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax ba}}$’s for
an instance samples $r=r_{0}$ given $r\geq r_{0}$, we have

${\mathrm{Pr}}[B_{r_{0}}]=1-{\mathrm{Pr}}[A_{r_{0}}]^{m}=1-\left(1-p\right)^{m}.$

This implies that for the event $C_{r_{0}}$ in which for some of the $N$
instances, none of the $m$ $\mathcal{F}_{\mathsf{trunc\mathchar 45\relax
a\mathchar 45\relax ba}}$’s sample $r=r_{0}$ given $r\geq r_{0}$, the
following holds:

${\mathrm{Pr}}[C_{r_{0}}]=1-{\mathrm{Pr}}[B_{r_{0}}]^{N}=1-\left(1-\left(1-p\right)^{m}\right)^{N}$

Now we can calculate the probability of $E^{\mathrm{c}}$, which represents the
event where for some of the $N$ instances, none of the $m$
$\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax ba}}$’s
sample $r\leq\mathsf{itr}-1$:

${\mathrm{Pr}}[E^{\mathrm{c}}]=\prod_{r_{0}=1}^{\mathsf{itr}-1}{\mathrm{Pr}}[C_{r_{0}}]=\left(1-\left(1-\left(1-p\right)^{m}\right)^{N}\right)^{\mathsf{itr}-1}$

Therefore, the complementary probability is

${\mathrm{Pr}}[E]=1-{\mathrm{Pr}}[E^{\mathrm{c}}]=1-\left(1-\left(1-\left(1-p\right)^{m}\right)^{N}\right)^{\mathsf{itr}-1}.$

By setting
$m\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\log_{\frac{1}{1-p}}N$
it holds that

${\mathrm{Pr}}[E]=1-\left(1-\left(1-\frac{1}{N}\right)^{N}\right)^{\mathsf{itr}-1}.$

Then considering $\left(1-\frac{1}{N}\right)^{N}\approx\frac{1}{e}$ we have

${\mathrm{Pr}}[E]\approx 1-\left(1-\frac{1}{e}\right)^{\mathsf{itr}-1}.$

So, for a constant value of $\mathsf{itr}>1$, the probability
${\mathrm{Pr}}[E]$ is a non-zero constant. This implies that, with appropriate
parameter choices, every honest party $P_{i}$ sets
$\mathsf{continue}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$
with constant probability. In other words, the A-BA on continuation outputs
$\mathsf{continue}=1$ with constant probability.

In any case, since every honest party $P_{i}$ eventually sets
$\mathsf{continue}_{i}$ and $\mathcal{F}_{\mathsf{a\mathchar 45\relax ba}}$
only requires participation from $n-t$ parties, agreement on
$\mathsf{continue}$ will eventually be reached. When $\mathsf{continue}=0$,
all honest parties will eventually proceed to the next iteration.

On the other hand, when $\mathsf{continue}=1$, at least one honest party
$P_{g}$ must have provided $\mathsf{continue}_{g}=1$, meaning that it observed
$S_{g,j}^{\mathsf{itr}}\not=\emptyset$ for all $j\in[N]$. Note that whenever
an honest party $P_{g}$ adds $z_{g,r}\not=\lambda$ to $S_{g,j}^{r}$ for some
$j\in[N]$ and $\mathsf{itr}\leq r\leq\mathsf{itr}+2$, any honest party $P_{i}$
will eventually add $z_{i,r+1}=z_{g,r}$ to $S_{i,j}^{r+1}$, since
$\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax ba}}$ models
the 1-shift property. Thus, in case of continuation, every honest party
$P_{i}$ will eventually have $S_{i,j}^{\mathsf{itr}+1}\not=\emptyset$ for all
$j\in[N]$ and A-Cast $(c_{i,1},\ldots,c_{i,N})$.

Since every honest party $P_{g}$ eventually A-Casts a vector
$(c_{g,1},\ldots,c_{g,N})$ satisfying $c_{g,j}\in S_{g,j}^{\mathsf{itr}+1}$
for all $j\in[N]$, following the analysis above every honest party $P_{i}$
will eventually receive at least $n-t$ A-Casts
$\vec{C}_{h}^{\prime}=(c_{h,1}^{\prime},\ldots,c_{h,N}^{\prime})$ satisfying
$c_{h,j}^{\prime}\in S_{i,j}^{\mathsf{itr}+2}$ for all $j\in[N]$. Thus, every
honest party $P_{i}$ will eventually pass the threshold $|Q_{i,1}|\geq n-t$
and A-Cast $Q_{i,1}^{(n-t)}$.

Whenever an honest party $P_{g}$ adds $P_{h}$ to $Q_{g,1}$, any other honest
party $P_{i}$ will eventually add $P_{h}$ to $Q_{i,2}$. This is because
$P_{g}$ received some
$\vec{C}_{h}^{\prime}=(c_{h,1}^{\prime},\ldots,c_{h,N}^{\prime})$ from
$P_{h}$’s A-Cast, where $c_{h,j}^{\prime}\in S_{g,j}^{\mathsf{itr}+2}$ for all
$j\in[N]$, so eventually $P_{i}$ will receive the same $\vec{C}_{h}^{\prime}$,
and following the analysis above it will eventually hold that
$c_{h,j}^{\prime}\in S_{i,j}^{\mathsf{itr}+3}$ for all $j\in[N]$. Since every
honest party $P_{g}$ eventually A-Casts $Q_{g,1}^{(n-t)}$, every honest party
$P_{i}$ will eventually receive at least $n-t$ A-Casts $Q_{h,1}^{\prime}$
satisfying $|Q_{h,1}^{\prime}|=n-t$ and $Q_{h,1}^{\prime}\subseteq Q_{i,2}$.
Thus, every honest party $P_{i}$ will eventually pass the threshold
$|W_{i}|\geq n-t$ and participate in $\mathcal{F}_{\mathsf{a\mathchar 45\relax
ole}}$.

Before proceeding, it is important to note that by using a similar counting
argument as in [41, 34], we can guarantee that messages (suggestions) from at
least $n-2t$ parties will eventually be received by all honest parties (by the
time of participation in $\mathcal{F}_{\mathsf{a\mathchar 45\relax ole}}$). In
more detail, consider the first honest party $P_{i}$ who reaches the stage
where $s\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=|W_{i}|\geq
n-t$. We can construct an $s\times n$ table $T$, where $T_{h,l}=1$ if and only
if $P_{h}\in W_{i}$ and $P_{l}\in Q_{h,1}^{\prime}$ (where $Q_{h,1}^{\prime}$
was received from $P_{h}$’s A-Cast). Each row of the table contains (exactly)
$n-t$ entries equal to one, indicating that there are a total of $s(n-t)$ one-
entries in $T$. Let $q$ be the minimum number of columns in $T$ that contain
at least $t+1$ one-entries. By considering the worst-case distribution of
ones, we have the inequality

$qs+(n-q)t\geq s(n-t).$

Noting that it suffices to consider the case $s=n-t$ and rearranging terms, we
have

$\displaystyle q$ $\displaystyle\geq\frac{(n-t)^{2}-nt}{n-2t}$
$\displaystyle=\frac{(n-t)(n-2t)-t^{2}}{n-2t}$
$\displaystyle=n-t-\frac{t^{2}}{n-2t}$ $\displaystyle\geq n-2t.$
$\displaystyle(n-2t>t)$

Therefore, we can conclude that at least $q\geq n-2t$ columns in ($P_{i}$’s
local view of) the table contain at least $t+1$ one-entries. Fix such a column
$l$, and consider another honest party $P_{g}$ who reaches the stage
$|W_{g}|\geq n-t$. Since $(n-t)+(t+1)>n$, the $l$th column in $P_{g}$’s view
of the table must necessarily contain a one-entry. This means that $P_{g}$
received the A-Cast of $Q_{h,1}^{\prime}$ from some party $P_{h}$, where
$P_{l}\in Q_{h,1}^{\prime}\subseteq Q_{g,2}$. In other words, a set of at
least $n-2t$ parties will eventually be contained in the $Q_{g,2}$ set of
every honest party $P_{g}$ (by the time that $|W_{g}|\geq n-t$).

Since all honest parties eventually participate in
$\mathcal{F}_{\mathsf{a\mathchar 45\relax ole}}$, which only requires
participation from $n-t$ parties, every honest party $P_{i}$ will eventually
receive the index of a party $P_{l_{i}}$. With constant probability, there is
agreement on a random leader $P_{l}$. Conditioned on agreeing on a random
leader, with probability at least $\frac{n-2t}{n}>\frac{1}{3}$ the leader
$P_{l}$ is among the parties whose vectors will eventually be delivered to
(and validated by) all honest parties. We stress that it is crucial here that
a linear number of such parties are fixed _before_ any honest party
participates in $\mathcal{F}_{\mathsf{a\mathchar 45\relax ole}}$, and
consequently before the identity of the leader is leaked to the adversary.
Since every honest party $P_{i}$ waits until $|W_{i}|\geq n-t$, the condition
$P_{l}\in Q_{i,2}$ will hold, and hence all honest parties will input (the
same) $\vec{C}_{l}^{\prime}\not=\bot$ to the multi-valued A-BA on the leader’s
vector. In this case, every honest party $P_{i}$ will eventually receive
$\vec{Y}=\vec{C}_{l}^{\prime}$ from the A-BA and terminate.

In any case, every honest party $P_{i}$ eventually has $|W_{i}|\geq n-t$ and
participates in the multi-valued A-BA, so agreement on some $\vec{Y}$ will
eventually be reached. If $\vec{Y}=\bot$, all honest parties will eventually
proceed to the next iteration; otherwise, they will all output $\vec{Y}$.

Therefore, the execution of the protocol $\Pi_{\mathsf{conc\mathchar 45\relax
a\mathchar 45\relax ba}}$ does not encounter any deadlocks. Furthermore, by
choosing appropriate parameters, specifically
$m\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\log_{\frac{1}{1-p}}N$,
the protocol can achieve termination with a constant probability in each
iteration. This implies that $\Pi_{\mathsf{conc\mathchar 45\relax a\mathchar
45\relax ba}}$ will eventually terminate with probability $1$, and the
expected number of iterations is constant. Since the number of rounds in each
iteration is also constant, the overall round complexity of the protocol is
constant in expectation.

#### Correctness.

Now we demonstrate that once the protocol terminates, all honest parties
output the same value as the ideal functionality
$\mathcal{F}_{\mathsf{conc\mathchar 45\relax a\mathchar 45\relax ba}}^{V,N}$.
This part of the proof requires the intrusion-tolerance property of A-BA,
which guarantees that the output is either $\bot$ or a value provided by an
honest party.

Since we assumed termination, there was agreement on
$\vec{Y}=(y_{1},\ldots,y_{N})$. Since $\mathcal{F}_{\mathsf{a\mathchar
45\relax ba}}$ models the intrusion-tolerance property, this implies that at
least one honest party $P_{i}$ provided $\vec{C}_{l_{i}}^{\prime}=\vec{Y}$,
where $l_{i}$ was received from $\mathcal{F}_{\mathsf{a\mathchar 45\relax
ole}}$ and $P_{l_{i}}\in Q_{i,2}$, meaning that party $P_{l_{i}}$ A-Casted a
vector $\vec{C}_{l_{i}}^{\prime}=(y_{1},\ldots,y_{N})$ satisfying $y_{j}\in
S_{i,j}^{\mathsf{itr}+3}$ for all $j\in[N]$. This implies that $y_{j}$ is a
valid and non-empty (not $\lambda$) output from some session of
$\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax ba}}$ for
the $j$th instance, for each $j\in[N]$. According to the description of
$\mathcal{F}_{\mathsf{trunc\mathchar 45\relax a\mathchar 45\relax ba}}$, if
there is a unique input value that was provided by at least $n-2t$ parties for
an instance, everyone will receive that value as the output for the instance;
otherwise, the output will be either one of the inputs provided by some honest
parties for that instance or a special value $\bot$. It is clear from
inspection that $\mathcal{F}_{\mathsf{conc\mathchar 45\relax a\mathchar
45\relax ba}}^{V,N}$ generates its output in the same manner.

Therefore, with probability $1$, no environment can distinguish between the
execution of $\Pi_{\mathsf{conc\mathchar 45\relax a\mathchar 45\relax
ba}}^{V,N,m,p,\mathsf{itr}}$ with $\mathcal{A}$ and
$\mathcal{F}_{\mathsf{conc\mathchar 45\relax a\mathchar 45\relax ba}}^{V,N}$
with $\mathcal{S}$, assuming expected-PPT machines. However, in order to apply
UC composition guarantees, we need to introduce a stopping point (proportional
to the security parameter) for our expected-PPT machines and make them strict
PPT. In doing so, the distinguishing probability of the environment would
become a non-zero value which can be arbitrarily small, depending on the
duration for which we allow the machines to run. This ensures that the
_strict_ PPT protocol $\Pi_{\mathsf{conc\mathchar 45\relax a\mathchar 45\relax
ba}}^{V,N,m,p,\mathsf{itr}}$ UC-realizes $\mathcal{F}_{\mathsf{conc\mathchar
45\relax a\mathchar 45\relax ba}}^{V,N}$ with statistical security. ∎

## Acknowledgements

Our original motivation for this project was to provide a simulation-based
treatment of concurrent A-BA protocols, such as Ben-Or and El-Yaniv’s [9], but
the search for building blocks, in particular of an optimally resilient
asynchronous OCC protocol became a bit of a “detective story,” as many
references pointed to an unpublished manuscript by Feldman [41], which was
nowhere to be found. We thank Michael Ben-Or for providing it to us, which
corroborated its in-existence.

Ran Cohen’s research is supported in part by NSF grant no. 2055568. Juan
Garay’s research is supported in part by NSF grants no. 2001082 and 2055694.
Vassilis Zikas’s research is supported in part by NSF grant no. 2055599 and by
Sunday Group. The authors were also supported by the Algorand Centres of
Excellence programme managed by Algorand Foundation. Any opinions, findings,
and conclusions or recommendations expressed in this material are those of the
author(s) and do not necessarily reflect the views of Algorand Foundation.

## References

  * AAPS [23] Ittai Abraham, Gilad Asharov, Arpita Patra, and Gilad Stern.  Perfectly secure asynchronous agreement on a core set in constant expected time.  IACR Cryptology ePrint Archive, Report 2023/1130, 2023.  https://eprint.iacr.org/2023/1130.
  * AC [10] Hagit Attiya and Keren Censor-Hillel.  Lower bounds for randomized consensus under a weak adversary.  SIAM Journal on Computing, 39(8):3885–3904, 2010.
  * ADH [08] Ittai Abraham, Danny Dolev, and Joseph Y. Halpern.  An almost-surely terminating polynomial protocol for asynchronous byzantine agreement with optimal resilience.  In 27th ACM PODC, pages 405–414. ACM, 2008.
  * ADS [22] Ittai Abraham, Danny Dolev, and Gilad Stern.  Revisiting asynchronous fault tolerant computation with optimal resilience.  Distributed Comput., 35(4):333–355, 2022.
  * AJM+ [23] Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu.  Reaching consensus for asynchronous distributed key generation.  Distributed Comput., 36(3):219–252, 2023.
  * AMS [19] Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman.  Asymptotically optimal validated asynchronous byzantine agreement.  In 38th ACM PODC, pages 337–346. ACM, 2019.
  * BCG [93] Michael Ben-Or, Ran Canetti, and Oded Goldreich.  Asynchronous secure computation.  In 25th ACM STOC, pages 52–61. ACM Press, 1993.
  * BE [88] Michael Ben-Or and Ran El-Yaniv.  Interactive consistency in constant expected time.  Technical report, Inst. of Math. and Comp. Sci., Hebrew University, Jerusalem, 1988.
  * BE [03] Michael Ben-Or and Ran El-Yaniv.  Resilient-optimal interactive consistency in constant time.  Distributed Computing, 16(4):249–262, 2003.
  * Ben [83] Michael Ben-Or.  Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract).  In 2nd ACM PODC, pages 27–30. ACM, 1983.
  * BGP [89] Piotr Berman, Juan A. Garay, and Kenneth J. Perry.  Towards optimal distributed consensus (extended abstract).  In 30th FOCS, pages 410–415. IEEE Computer Society Press, 1989.
  * BGW [88] Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson.  Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract).  In 20th ACM STOC, pages 1–10. ACM Press, 1988.
  * BH [07] Zuzana Beerliová-Trubíniová and Martin Hirt.  Simple and efficient perfectly-secure asynchronous MPC.  In ASIACRYPT 2007, volume 4833 of LNCS, pages 376–392. Springer, Heidelberg, 2007.
  * BKR [94] Michael Ben-Or, Boaz Kelmer, and Tal Rabin.  Asynchronous secure computations with optimal resilience (extended abstract).  In 13th ACM PODC, pages 183–192. ACM, 1994.
  * Bor [96] Malte Borcherding.  Levels of authentication in distributed agreement.  In 10th International Workshop on Distributed Algorithms WDAG, pages 40–55. Springer, Berlin, Heidelberg, 1996.
  * Bra [87] Gabriel Bracha.  Asynchronous byzantine agreement protocols.  Inf. Comput., 75(2):130–143, 1987.
  * BS [93] Donald Beaver and Nicol So.  Global, unpredictable bit generation without broadcast.  In EUROCRYPT’93, volume 765 of LNCS, pages 424–434. Springer, Heidelberg, 1993.
  * BT [85] Gabriel Bracha and Sam Toueg.  Asynchronous consensus and broadcast protocols.  Journal of the ACM, 32(4):824–840, 1985.
  * BZL [20] Erica Blum, Chen-Da Liu Zhang, and Julian Loss.  Always have a backup plan: Fully secure synchronous MPC with asynchronous fallback.  In CRYPTO 2020, Part II, volume 12171 of LNCS, pages 707–731. Springer, Heidelberg, 2020.
  * Can [96] Ran Canetti.  Studies in secure multiparty computation and applications.  PhD thesis, Weizmann Institute of Science, 1996.
  * Can [20] Ran Canetti.  Universally composable security.  Journal of the ACM, 67(5):1–94, 2020.
  * CCD [88] David Chaum, Claude Crépeau, and Ivan Damgård.  Multiparty unconditionally secure protocols (extended abstract).  In 20th ACM STOC, pages 11–19. ACM Press, 1988.
  * CCGZ [19] Ran Cohen, Sandro Coretti, Juan Garay, and Vassilis Zikas.  Probabilistic termination and composability of cryptographic protocols.  Journal of Cryptology, 32(3):690–741, 2019.
  * CCGZ [21] Ran Cohen, Sandro Coretti, Juan A. Garay, and Vassilis Zikas.  Round-preserving parallel composition of probabilistic-termination cryptographic protocols.  Journal of Cryptology, 34(2):12, 2021.
  * CGHZ [16] Sandro Coretti, Juan Garay, Martin Hirt, and Vassilis Zikas.  Constant-round asynchronous multi-party computation based on one-way functions.  In ASIACRYPT 2016, Part II, volume 10032 of LNCS, pages 998–1021. Springer, Heidelberg, 2016.
  * CGZ [23] Ran Cohen, Juan A. Garay, and Vassilis Zikas.  Completeness theorems for adaptively secure broadcast.  In CRYPTO 2023, Part I, volume 14081 of LNCS, pages 3–38. Springer, Heidelberg, 2023.
  * CHM+ [22] Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, and Alex Samorodnitsky.  On the round complexity of randomized byzantine agreement.  Journal of Cryptology, 35(2):10, 2022.
  * CKPS [01] Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup.  Secure and efficient asynchronous broadcast protocols.  In CRYPTO 2001, volume 2139 of LNCS, pages 524–541. Springer, Heidelberg, 2001.
  * CKS [05] Christian Cachin, Klaus Kursawe, and Victor Shoup.  Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography.  Journal of Cryptology, 18(3):219–246, 2005.
  * CMS [89] Benny Chor, Michael Merritt, and David B. Shmoys.  Simple constant-time consensus protocols in realistic failure models.  Journal of the ACM, 36(3):591–614, 1989.
  * Coh [16] Ran Cohen.  Asynchronous secure multiparty computation in constant time.  In PKC 2016, Part II, volume 9615 of LNCS, pages 183–207. Springer, Heidelberg, 2016.
  * CPS [19] T.-H. Hubert Chan, Rafael Pass, and Elaine Shi.  Round complexity of Byzantine agreement, revisited.  IACR Cryptology ePrint Archive, Report 2019/886, 2019.  https://eprint.iacr.org/2019/886.
  * CPS [20] T.-H. Hubert Chan, Rafael Pass, and Elaine Shi.  Sublinear-round byzantine agreement under corrupt majority.  In PKC 2020, Part II, volume 12111 of LNCS, pages 246–265. Springer, Heidelberg, 2020.
  * CR [93] Ran Canetti and Tal Rabin.  Fast asynchronous byzantine agreement with optimal resilience.  In 25th ACM STOC, pages 42–51. ACM Press, 1993.
  * CR [98] Ran Canetti and Tal Rabin.  Fast asynchronous byzantine agreement with optimal resilience.  Full version of [34], 1998.  https://www.cs.tau.ac.il/~canetti/materials/cr93.ps.
  * DLS [88] Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer.  Consensus in the presence of partial synchrony.  Journal of the ACM, 35(2):288–323, 1988.
  * DS [83] Danny Dolev and H. Raymond Strong.  Authenticated algorithms for byzantine agreement.  SIAM Journal on Computing, 12(4):656–666, 1983.
  * dSKT [22] Luciano Freitas de Souza, Petr Kuznetsov, and Andrei Tonkikh.  Distributed randomness from approximate agreement.  In 36th DISC, volume 246 of LIPIcs, pages 24:1–24:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * DWZ [23] Sisi Duan, Xin Wang, and Haibin Zhang.  FIN: practical signature-free asynchronous common subset in constant time.  In ACM CCS 2023, pages 815–829. ACM, 2023.
  * Fel [88] Paul Neil Feldman.  Optimal Algorithms for Byzantine Agreement.  PhD thesis, Massachusetts Institute of Technology, 1988.
  * Fel [89] Paul Feldman.  Asynchronous byzantine agreement in constant expected time.  Unpublished manuscript, 1989.
  * FG [03] Matthias Fitzi and Juan A. Garay.  Efficient player-optimal protocols for strong and differential consensus.  In 22nd ACM PODC, pages 211–220. ACM, 2003.
  * FGL+ [91] Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy.  Approximating clique is almost NP-complete (preliminary version).  In 32nd FOCS, pages 2–12. IEEE Computer Society Press, 1991.
  * Fit [03] Matthias Fitzi.  Generalized communication and security models in Byzantine agreement.  PhD thesis, ETH Zurich, Zürich, Switzerland, 2003.
  * FL [82] Michael J. Fischer and Nancy A. Lynch.  A lower bound for the time to assure interactive consistency.  Information Processing Letters, 14(4):183–186, 1982.
  * FLM [86] Michael J. Fischer, Nancy A. Lynch, and Michael Merritt.  Easy impossibility proofs for distributed consensus problems.  Distributed Computing, 1(1):26–39, 1986.
  * FLP [85] Michael J. Fischer, Nancy A. Lynch, and Mike Paterson.  Impossibility of distributed consensus with one faulty process.  Journal of the ACM, 32(2):374–382, 1985.
  * FM [88] Paul Feldman and Silvio Micali.  Optimal algorithms for byzantine agreement.  In 20th ACM STOC, pages 148–161. ACM Press, 1988.
  * FM [89] Paul Feldman and Silvio Micali.  An optimal probabilistic algorithm for synchronous byzantine agreement.  In ICALP 89, volume 372 of LNCS, pages 341–378. Springer, Heidelberg, 1989.
  * FM [97] Pesech Feldman and Silvio Micali.  An optimal probabilistic protocol for synchronous byzantine agreement.  SIAM J. Comput., 26(4):873–933, 1997.
  * FN [09] Matthias Fitzi and Jesper Buus Nielsen.  On the number of synchronous rounds sufficient for authenticated byzantine agreement.  In 23rd DISC, volume 5805 of LNCS, pages 449–463. Springer, Heidelberg, 2009.
  * GGL [22] Diana Ghinea, Vipul Goyal, and Chen-Da Liu-Zhang.  Round-optimal byzantine agreement.  In EUROCRYPT 2022, Part I, volume 13275 of LNCS, pages 96–119. Springer, Heidelberg, 2022.
  * GKKO [07] Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo, and Rafail Ostrovsky.  Round complexity of authenticated broadcast with a dishonest majority.  In 48th FOCS, pages 658–668. IEEE Computer Society Press, 2007.
  * GLL+ [22] Yingzi Gao, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang.  Efficient asynchronous byzantine agreement without private setups.  In 42nd ICDCS, pages 246–257. IEEE, 2022.
  * GM [98] Juan A. Garay and Yoram Moses.  Fully polynomial byzantine agreement for _n_ > 3t processors in _t_ \+ 1 rounds.  SIAM J. Comput., 27(1):247–290, 1998.
  * GMW [87] Oded Goldreich, Silvio Micali, and Avi Wigderson.  How to play any mental game or A completeness theorem for protocols with honest majority.  In 19th ACM STOC, pages 218–229. ACM Press, 1987.
  * HNP [05] Martin Hirt, Jesper Buus Nielsen, and Bartosz Przydatek.  Cryptographic asynchronous multi-party computation with optimal resilience (extended abstract).  In EUROCRYPT 2005, volume 3494 of LNCS, pages 322–340. Springer, Heidelberg, 2005.
  * HNP [08] Martin Hirt, Jesper Buus Nielsen, and Bartosz Przydatek.  Asynchronous multi-party computation with quadratic communication.  In ICALP 2008, Part II, volume 5126 of LNCS, pages 473–485. Springer, Heidelberg, 2008.
  * HZ [10] Martin Hirt and Vassilis Zikas.  Adaptively secure broadcast.  In EUROCRYPT 2010, volume 6110 of LNCS, pages 466–485. Springer, Heidelberg, 2010.
  * KK [09] Jonathan Katz and Chiu-Yuen Koo.  On expected constant-round protocols for byzantine agreement.  Journal of Computer and System Sciences, 75(2):91–112, 2009.
  * KMTZ [13] Jonathan Katz, Ueli Maurer, Björn Tackmann, and Vassilis Zikas.  Universally composable synchronous computation.  In TCC 2013, volume 7785 of LNCS, pages 477–498. Springer, Heidelberg, 2013.
  * KY [86] Anna R. Karlin and Andrew Chi-Chih Yao.  Probabilistic lower bounds for Byzantine agreement and clock synchronization.  Unpublished manuscript, 1986.
  * LLM+ [20] Chen-Da Liu-Zhang, Julian Loss, Ueli Maurer, Tal Moran, and Daniel Tschudi.  MPC with synchronous security and asynchronous responsiveness.  In ASIACRYPT 2020, Part III, volume 12493 of LNCS, pages 92–119. Springer, Heidelberg, 2020.
  * LLR [02] Yehuda Lindell, Anna Lysyanskaya, and Tal Rabin.  Sequential composition of protocols without simultaneous termination.  In 21st ACM PODC, pages 203–212. ACM, 2002.
  * LLR [06] Yehuda Lindell, Anna Lysyanskaya, and Tal Rabin.  On the composition of authenticated byzantine agreement.  Journal of the ACM, 53(6):881–917, 2006.
  * LLTW [20] Yuan Lu, Zhenliang Lu, Qiang Tang, and Guiling Wang.  Dumbo-mvba: Optimal multi-valued validated asynchronous byzantine agreement, revisited.  In 39th ACM PODC, pages 129–138. ACM, 2020.
  * LSP [82] Leslie Lamport, Robert E. Shostak, and Marshall C. Pease.  The byzantine generals problem.  ACM Trans. Program. Lang. Syst., 4(3):382–401, 1982.
  * Mic [17] Silvio Micali.  Very simple and efficient byzantine agreement.  In ITCS 2017, volume 4266 of LIPIcs, pages 6:1–6:1. Schloss Dagstuhl, 2017.
  * MR [90] Silvio Micali and Tal Rabin.  Collective coin tossing without assumptions nor broadcasting.  In CRYPTO’90, volume 537 of LNCS, pages 253–266. Springer, Heidelberg, 1990.
  * MR [17] Achour Mostéfaoui and Michel Raynal.  Signature-free asynchronous byzantine systems: from multivalued to binary consensus with t< n/3, O(n${}^{\mbox{2}}$) messages, and constant time.  Acta Informatica, 54(5):501–520, 2017.
  * Nie [02] Jesper Buus Nielsen.  A threshold pseudorandom function construction and its applications.  In CRYPTO 2002, volume 2442 of LNCS, pages 401–416. Springer, Heidelberg, 2002.
  * Pat [11] Arpita Patra.  Error-free multi-valued broadcast and byzantine agreement with optimal communication complexity.  In 15th OPODIS, volume 7109 of LNCS, pages 34–49. Springer, 2011.
  * PCR [14] Arpita Patra, Ashish Choudhury, and C. Pandu Rangan.  Asynchronous byzantine agreement with optimal resilience.  Distributed Computing, 27(2):111–146, 2014.
  * PSL [80] Marshall C. Pease, Robert E. Shostak, and Leslie Lamport.  Reaching agreement in the presence of faults.  Journal of the ACM, 27(2):228–234, 1980.
  * PW [92] Birgit Pfitzmann and Michael Waidner.  Unconditional byzantine agreement for any number of faulty processors.  In 9th STACS, volume 577 of LNCS, pages 339–350. Springer, 1992.
  * Rab [83] Michael O. Rabin.  Randomized byzantine generals.  In 24th FOCS, pages 403–409. IEEE Computer Society Press, 1983.
  * SLM+ [23] Shravan Srinivasan, Julian Loss, Giulio Malavolta, Kartik Nayak, Charalampos Papamanthou, and Sri Aravinda Krishnan Thyagarajan.  Transparent batchable time-lock puzzles and applications to byzantine consensus.  In PKC 2023, Part I, LNCS, pages 554–584. Springer, Heidelberg, 2023.
  * TC [84] Russell Turpin and Brian A. Coan.  Extending binary byzantine agreement to multivalued byzantine agreement.  Information Processing Letters, 18(2):73–76, 1984.
  * WXDS [20] Jun Wan, Hanshen Xiao, Srinivas Devadas, and Elaine Shi.  Round-efficient byzantine broadcast under strongly adaptive and majority corruptions.  In TCC 2020, Part I, volume 12550 of LNCS, pages 412–456. Springer, Heidelberg, 2020.
  * WXSD [20] Jun Wan, Hanshen Xiao, Elaine Shi, and Srinivas Devadas.  Expected constant round byzantine broadcast under dishonest majority.  In TCC 2020, Part I, volume 12550 of LNCS, pages 381–411. Springer, Heidelberg, 2020.
  * Yao [82] Andrew Chi-Chih Yao.  Protocols for secure computations (extended abstract).  In 23rd FOCS, pages 160–164. IEEE Computer Society Press, 1982.
  * ZD [22] Haibin Zhang and Sisi Duan.  PACE: fully parallelizable BFT from reproposable byzantine agreement.  In ACM CCS 2022, pages 3151–3164. ACM, 2022.

##  Appendix A Attack on Ben-Or and El-Yaniv’s Select Protocol

In this section, we begin by presenting a static adversary that disproves an
important claim regarding the expected-constant round complexity for one of
the main subroutines in Ben-Or and El-Yaniv’s concurrent A-BA protocol [9].
Consequently, the assured expected-constant round complexity of their
concurrent A-BA protocol is no longer valid. Furthermore, we demonstrate that
when considering adaptive adversaries, attempting to argue even for weaker
claims becomes futile. The attacks we present here consider a simple case with
only four parties, one of which can be corrupted (respecting the bound
$t<n/3$). To provide essential context for our attacks, we present some of the
protocols nearly verbatim from [9] in Figures 11, 12, and 13.

Protocol $\Pi_{\mathsf{a\mathchar 45\relax cast\textsuperscript{+}}}$ Common
inputs: $n$, $t\leq(n-1)/3$; $k$ (the identity of the transmitter) Local input
for processor $p_{i}$: none Additional local input for processor $p_{k}$: $V$
Local output for processor $p_{i}$: $Value_{i}$, $Relay_{i}$ Epoch 1: ($p_{k}$
only) • A-Cast $V$. Epoch 2: (Every processor $p_{i}$) • Upon accepting a
value $v$ from a transmitter $p$, A-Cast $[``commit",p,v]$. Epoch 3: (Every
processor $p_{i}$) • Upon accepting $2t+1$ $[``commit",p^{\prime},v^{\prime}]$
A-Casts from a set $S$ of processors (transmitters), $Value_{i}\leftarrow
v^{\prime}$, $Relay_{i}\leftarrow S$, and return $Value_{i},Relay_{i}$.

Figure 11: The A-Cast+ protocol from [9, Fig. 3].

Protocol $\Pi_{\mathsf{spread}}$ Common inputs: $n$, $t\leq(n-1)/3$ Local
input for processor $p_{i}$: $V_{i}$ Local output for processor $p_{i}$:
$\langle X_{1},X_{2},\ldots,X_{n}\rangle$ Epoch 1: • A-Cast+ $V_{i}$. Epoch 2:
• Wait until $2t+1$ values $V_{i_{1}},\ldots,V_{i_{2t+1}}$ accepted (from
$p_{i_{1}},\ldots,p_{i_{2t+1}}$). • A-Cast
$\langle(p_{i_{1}},V_{i_{1}}),\ldots,(p_{i_{2t+1}},V_{i_{2t+1}})\rangle$.
Participate in the A-Cast of a vector
$u=\langle(p_{j_{1}},U_{j_{1}}),\ldots,(p_{j_{2t+1}},U_{j_{2t+1}})\rangle$
only if for every $1\leq k\leq 2t+1$, $U_{j_{k}}$ accepted from $p_{j_{k}}$.
Epoch 3: • Wait until $t+1$ vectors $u_{l_{1}},\ldots,u_{l_{2t+1}}$ [sic]
accepted (from $p_{l_{1}},\ldots,p_{l_{t+1}}$) such that for every $1\leq
k\leq t+1$ if
$u_{l_{k}}=\langle(p_{k_{1}},U_{k_{1}}),\ldots,(p_{k_{2t+1}},U_{k_{2t+1}})\rangle$,
and for every $1\leq r\leq 2t+1$, $U_{k_{r}}$ accepted from $p_{k_{r}}$’s
A-Cast+. • For every $1\leq l\leq n$: – If a value $V$ was accepted from
$p_{l}$ via A-Cast+ then $X_{l}\leftarrow(V,Relay_{i,l})$ (where
$(V,Relay_{i,l})$ is the output of A-Cast+). – Else
$X_{l}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\emptyset$. •
Return $\langle X_{1},X_{2},\ldots,X_{n}\rangle$.

Figure 12: The Spread protocol from [9, Fig. 4].

Protocol $\Pi_{\mathsf{select}}$ Common inputs: $n$, $t\leq(n-1)/3$ Local
input for processor $p_{i}$: $V_{i}$ \- an arbitrary value; $Pred_{i}(x)$ \- a
predicate Local output for processor $p_{i}$: $D_{i}$ Epoch 1: •
$U_{i}\leftarrow V_{i}$ and run Spread on input $U_{i}$ and let $View_{i}$
denote the local output. Epoch 2: • Run A-OLE. Let $k$ be the output denoting
the identity of the leader, $p_{k}$. Epoch 3: • $U\leftarrow View_{i}[k]$
(i.e., the value “related” to $p_{k}$ upon termination of Spread). • If $U$
was accepted during the run of Spread and $\models Pred_{i}(U)$, then
$R_{i}\leftarrow U$ and $U_{i}\leftarrow[``deflected",U,Relay_{i}]$, where
$Relay_{i}$ is obtained by Spread (via A-Cast+) for the accepted broadcast of
the leader $p_{k}$. • Else $R_{i}\leftarrow\emptyset$. • Run A-BA on input
$R_{i}$. Let $D_{i}$ denote the local output. • If $D_{i}\neq\emptyset$ then
return $D_{i}$. Epoch 4: • A-Cast $View_{i}$ ($View_{i}$ defined in Epoch 1).
Participate in admissible A-Casts only. Epoch 5: • Wait until $2t+1$ views,
$View_{i_{1}},\ldots,View_{i_{2t+1}}$ accepted. • A-Cast $U_{i}$. Epoch 6: •
Wait until $2t+1$ values accepted. • If a
$[``deflected",U^{\prime},Relay]$-message was accepted and $p_{k}\in Relay$
($p_{k}$ is the leader from Epoch 2) and there are $t+1$ processors in $Relay$
which have a non-null value related to $p_{k}$ in their accepted Views with
the same value $U^{\prime}$ (if several such messages were accepted with
different $U^{\prime}$ values take an arbitrary one), then $R_{i}\leftarrow
U^{\prime}$. • Else
$R_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\emptyset$.
Epoch 7: • Run A-BA on input $R_{i}$ and let $D_{i}$ denote the local output.
• If $D_{i}\neq\emptyset$ then return $D_{i}$. • Else $U_{i}\leftarrow V_{i}$
and go to Epoch 1.

Figure 13: The Select protocol from [9, Fig. 5].

Next, we highlight that certain aspects of the attacks do not necessitate any
corruption and can be executed solely by imposing appropriate delays. These
aspects are common to both the static and adaptive attacks; thus, they form
the initial focus of our analysis before we dive into the separate subsections
for the static and adaptive attacks. Claims 6 and 7 formulate capabilities of
adversaries only imposing delays maliciously.

######  Claim 6.

In any invocation of the $\Pi_{\mathsf{a\mathchar 45\relax
cast\textsuperscript{+}}}$ protocol, the adversary can arbitrarily assign
different sets of participants of size $n-t$ to the $Relay$ sets of honest
parties’ outputs by imposing appropriate delays. No corruption is necessary
for this manipulation.

###### Proof.

To assign a set $S$ of participants to the $Relay$ set of an honest party
$p_{i}$, the adversary can allow all the honest parties to accept the A-Cast
initiated in Epoch 1 of $\Pi_{\mathsf{a\mathchar 45\relax
cast\textsuperscript{+}}}$. However, the adversary selectively delivers
$[``commit",\cdot,\cdot]$ messages from parties in set $S$ to $p_{i}$ before
delivering any other $[``commit",\cdot,\cdot]$ messages. ∎

######  Claim 7.

Let $P=\\{p_{1},p_{2},p_{3},p_{4}\\}$ be the set of participants, $v_{i}$ for
$i\in[4]$ be the input of $p_{i}$, and $Relay_{i,j}$ for $i,j\in[4]$ be
arbitrary subsets of $P$ with size $3$. The adversary can manipulate the
output of the $\Pi_{\mathsf{spread}}$ protocol as follows solely through
message scheduling. No corruption is necessary.

$\displaystyle p_{1}\colon$
$\displaystyle\langle(v_{1},Relay_{1,1}),(v_{2},Relay_{1,2}),(v_{3},Relay_{1,3}),(v_{4},Relay_{1,4})\rangle$
$\displaystyle p_{2}\colon$
$\displaystyle\langle(v_{1},Relay_{2,1}),(v_{2},Relay_{2,2}),(v_{3},Relay_{2,3}),(v_{4},Relay_{2,4})\rangle$
$\displaystyle p_{3}\colon$
$\displaystyle\langle(v_{1},Relay_{3,1}),(v_{3},Relay_{3,3}),(v_{4},Relay_{3,4})\rangle$
$\displaystyle p_{4}\colon$
$\displaystyle\langle(v_{2},Relay_{4,2}),(v_{3},Relay_{4,3}),(v_{4},Relay_{4,4})\rangle$

###### Proof.

According to the description of $\Pi_{\mathsf{spread}}$, for any $i,j\in[4]$,
the $j$th component of the output of $p_{i}$ is either $\bot$ or is the output
of $\Pi_{\mathsf{a\mathchar 45\relax cast\textsuperscript{+}}}$ accepted from
$p_{j}$ (from Epoch 1). Since in each party’s output all the available values
corresponding to other parties are correct, the adversary does not need to
make any changes to them. Moreover, based on Claim 6, the adversary can set
the $Relay$ set in the output of $\Pi_{\mathsf{a\mathchar 45\relax
cast\textsuperscript{+}}}$ to any arbitrary subset of participants as long as
it has the correct size, which is 3. Since all the $Relay_{i,j}$ sets are of
size 3, the adversary will not face any challenges setting them. Now we only
need to demonstrate how the adversary can include and exclude inputs from
different parties in each party’s output to achieve the desired event. The
adversary can accomplish this by carefully designing the order in which the
parties accept the $\Pi_{\mathsf{a\mathchar 45\relax
cast\textsuperscript{+}}}$ messages from Epoch 1. The following steps outline
the message delivery order:

  * •

The adversary delivers the $\Pi_{\mathsf{a\mathchar 45\relax
cast\textsuperscript{+}}}$ messages to $p_{1}$ in the order:
$p_{1},p_{3},p_{4},p_{2}$.

  * •

The adversary delivers the $\Pi_{\mathsf{a\mathchar 45\relax
cast\textsuperscript{+}}}$ messages to $p_{2}$ in the order:
$p_{2},p_{3},p_{4},p_{1}$.

  * •

The adversary delivers the $\Pi_{\mathsf{a\mathchar 45\relax
cast\textsuperscript{+}}}$ messages to $p_{3}$ in the order:
$p_{1},p_{3},p_{4}$, and delays the $\Pi_{\mathsf{a\mathchar 45\relax
cast\textsuperscript{+}}}$ message from $p_{2}$ until $p_{3}$ terminates.

  * •

The adversary delivers the $\Pi_{\mathsf{a\mathchar 45\relax
cast\textsuperscript{+}}}$ messages to $p_{4}$ in the order:
$p_{2},p_{3},p_{4}$, and delays the $\Pi_{\mathsf{a\mathchar 45\relax
cast\textsuperscript{+}}}$ message from $p_{1}$ until $p_{4}$ terminates.

By using this scheduling and delivering all the A-Cast+ messages initiated in
Epoch 2, the following outcomes occur:

  * •

Parties $p_{1}$ and $p_{3}$ accept the vector
$\langle(p_{1},v_{1}),(p_{3},v_{3}),(p_{4},v_{4})\rangle$ twice (once from
$p_{1}$ and once from $p_{3}$ by the participation of $p_{1},p_{2},p_{3}$).

  * •

Parties $p_{2}$ and $p_{4}$ accept the vector
$\langle(p_{2},v_{2}),(p_{3},v_{3}),(p_{4},v_{4})\rangle$ twice (once from
$p_{2}$ and once from $p_{4}$ by the participation of $p_{1},p_{2},p_{4}$).

Therefore, all parties terminate with the given output as stated in the claim.
∎

###  A.1 Static Attack

$\Pi_{\mathsf{select}}$ may involve multiple iterations, where parties either
agree on a value and terminate, or restart the protocol. In the proof of the
$\Pi_{\mathsf{select}}$ protocol, an event $E$ is defined, which is claimed to
occur with a constant probability. It is argued that when $E$ happens in an
iteration, all parties terminate. However, we demonstrate that this claim is
not valid, resulting in uncertainty regarding the expected-constant round
complexity guarantee of the $\Pi_{\mathsf{select}}$ protocol.

Assuming the preconditions for the $\Pi_{\mathsf{select}}$ protocol hold
(i.e., for every non-faulty parties $p_{i}$ and $p_{j}$, $\models
Pred_{j}(V_{i})$ and $V_{i}\neq\emptyset$), we will demonstrate that the
argument regarding the round complexity is not valid. Let the static adversary
$\mathcal{A}$ corrupt $p_{1}$ before the protocol begins. According to Claim
7, $\mathcal{A}$ can make parties terminate $\Pi_{\mathsf{spread}}$ in Epoch 1
of $\Pi_{\mathsf{select}}$ with the following outputs where
$Relay_{1,2}=Relay_{4,2}=\\{p_{1},p_{2},p_{3}\\}$ (no corruption is required):

$\displaystyle p_{1}\colon$
$\displaystyle\langle(v_{1},Relay_{1,1}),(v_{2},Relay_{1,2}),(v_{3},Relay_{1,3}),(v_{4},Relay_{1,4})\rangle$
$\displaystyle p_{2}\colon$
$\displaystyle\langle(v_{1},Relay_{2,1}),(v_{2},Relay_{2,2}),(v_{3},Relay_{2,3}),(v_{4},Relay_{2,4})\rangle$
$\displaystyle p_{3}\colon$
$\displaystyle\langle(v_{1},Relay_{3,1}),(v_{3},Relay_{3,3}),(v_{4},Relay_{3,4})\rangle$
$\displaystyle p_{4}\colon$
$\displaystyle\langle(v_{2},Relay_{4,2}),(v_{3},Relay_{4,3}),(v_{4},Relay_{4,4})\rangle$

######  Remark 8.

Based on the properties of the $\Pi_{\mathsf{spread}}$ protocol, after the
termination of the first honest party, there exist two subsets of
participants, $P_{1}$ and $P_{2}$, satisfying the following conditions:
$P_{1}$ only contains honest parties, $|P_{1}|=t+1$, $|P_{2}|=2t+1$, and all
the values from parties in $P_{2}$ are included in the output vector of all
the parties in $P_{1}$.

Now let us assume that $\mathcal{A}$ allows $p_{4}$ to be the first to
terminate $\Pi_{\mathsf{spread}}$ in Epoch 1 of the $\Pi_{\mathsf{select}}$
protocol. In this case, $P_{1}$ and $P_{2}$ could be $\\{p_{2},p_{4}\\}$ and
$\\{p_{2},p_{3},p_{4}\\}$, respectively.

In Epoch 2 of the $\Pi_{\mathsf{select}}$ protocol, a leader $p_{k}$ is
randomly chosen. The event $E$ is defined as $p_{k}\in P_{2}\cap(P-T)$ and it
is claimed that if $E$ occurs, the protocol terminates with the correct
output. Since $p_{k}$ is chosen randomly and $|P_{2}\cap(P-T)|=t+1$, the
probability of the event $E$ is at least $\frac{1}{3}$. Therefore, this claim
suggests an expected-constant number of iterations (or asynchronous rounds).

However, we claim that when $p_{k}=p_{2}$, which satisfies $E$ (since $p_{2}$
is honest and is in $P_{2}$), the protocol will start over instead of
terminating. In the following, we explain the adversary’s behavior in Epoch 3
to Epoch 7 of the $\Pi_{\mathsf{select}}$ protocol and provide a proof for our
claim.

In Epoch 3 of $\Pi_{\mathsf{select}}$, $\mathcal{A}$ can delay $p_{2}$ and
assign a malicious value $v^{\prime}_{2}\neq v_{2}$ to $R_{1}$. However,
$\mathcal{A}$ allows $p_{1}$ to follow the protocol for the rest of its
actions. As a result, the following state is observed:

  * •

$p_{1}$: $R_{1}=v^{\prime}_{2}$ and $U_{1}=(v_{2},\\{p_{1},p_{2},p_{3}\\})$

  * •

$p_{2}$: Delayed

  * •

$p_{3}$: $R_{3}=\bot$ and $U_{3}=v_{3}$

  * •

$p_{4}$: $R_{4}=v_{2}$ and $U_{4}=(v_{2},\\{p_{1},p_{2},p_{3}\\})$

Consequently, the parties initiate the A-BA protocol with the inputs
$(v^{\prime}_{2},\text{delayed},\bot,v_{2})$. However, since there is no
majority in the input values, we have no guarantee on the output of this A-BA
protocol. In fact, as formulated in the A-BA ideal functionality, the
adversary $\mathcal{A}$ can manipulate the protocol execution to make it
output $\bot$ and prevent the termination of $\Pi_{\mathsf{select}}$.
Therefore, it is necessary to proceed to the next epoch, as the protocol
cannot terminate at this stage.

In Epoch 4 of $\Pi_{\mathsf{select}}$, $\mathcal{A}$ allows $p_{1}$ to follow
the protocol. It should be noted that all the views in this epoch are
admissible to everyone, as the components of all the views are either $\bot$
or the correct values. Therefore, all the views can be received by the honest
parties. The only control that $\mathcal{A}$ has is over the order in which
the views are received by the parties in the next epoch.

In Epoch 5 of $\Pi_{\mathsf{select}}$, $\mathcal{A}$ allows $p_{1}$ to follow
the protocol and strategically manages delays to achieve the following:

  * •

Delivers $view_{1},view_{3},view_{4}$ to $p_{1}$ as its first $2t+1$ views.

  * •

Delays the acceptance of any view for $p_{2}$ until the A-BA in Epoch 7 of
$\Pi_{\mathsf{select}}$ is terminated.

  * •

Delivers $view_{1},view_{3},view_{4}$ to $p_{3}$ as its first $2t+1$ views.

  * •

Delivers $view_{1},view_{3},view_{4}$ to $p_{4}$ as its first $2t+1$ views.

Then, parties A-Cast values as follows based on the output they received from
the $\Pi_{\mathsf{spread}}$ protocol in Epoch 1 of $\Pi_{\mathsf{select}}$:

  * •

$p_{1}$: $U_{1}=(v_{2},\\{p_{1},p_{2},p_{3}\\})$

  * •

$p_{2}$: Still waiting from the previous epoch

  * •

$p_{3}$: $U_{3}=v_{3}$

  * •

$p_{4}$: $U_{4}=(v_{2},\\{p_{1},p_{2},p_{3}\\})$

In Epoch 6 of $\Pi_{\mathsf{select}}$, $\mathcal{A}$ lets $p_{1}$ follow the
protocol, keeps $p_{2}$ waiting, and allows the remaining parties to receive
each other’s A-Cast messages. As a result, the following situation arises:

  * •

$p_{1},p_{3},p_{4}$: Receive $(v_{2},\\{p_{1},p_{2},p_{3}\\})$ from
$p_{1},p_{4}$, and $v_{3}$ from $p_{3}$.

  * •

$p_{2}$: Still waiting from previous epochs

However, the “if” condition in Epoch 6 is not satisfied because only $p_{1}$
among $\\{p_{1},p_{2},p_{3}\\}$ has an accepted view that includes a value
associated with $p_{2}$. Therefore, the following assignments are made:

  * •

$p_{1},p_{3},p_{4}$: Assign $R_{1}=R_{3}=R_{4}=\bot$.

  * •

$p_{2}$: Still waiting from previous epochs

In Epoch 7 of $\Pi_{\mathsf{select}}$, $\mathcal{A}$ allows $p_{1}$ to follow
the protocol. Consequently, parties initiate the A-BA protocol with the
following inputs:

  * •

$p_{1},p_{3},p_{4}$: $\bot$

  * •

$p_{2}$: Still waiting from previous epochs

As a result, parties complete the A-BA protocol and obtain the output $\bot$.
Since the output is $\bot$, they have to start over, completing our attack.

###  A.2 Adaptive Attack

In the static attack, we demonstrated that the claim “for all possibilities
for the set $P_{2}$, if the leader is an honest party in $P_{2}$, then the
protocol terminates with the correct value” is not valid. We provided specific
choices of the leader within certain possibilities for $P_{2}$ where the claim
does not hold. This shows that the claim is incorrect in those cases.

In the adaptive attack, we further illustrate the difficulty in finding an
argument for the weaker claim “there exists a possibility for $P_{2}$ such
that if the leader is an honest party in $P_{2}$, then the protocol terminates
with the correct values.” We use the same setup with four parties, namely
$p_{1}$, $p_{2}$, $p_{3}$, and $p_{4}$, and demonstrate that if either $p_{1}$
or $p_{2}$ is chosen as the leader, the adversary $\mathcal{A}$ can manipulate
the protocol to start over instead of terminating. Since any legitimate set
$P_{2}$ consists of three parties, it must include at least one of $p_{1}$ and
$p_{2}$. Therefore, in any possible set $P_{2}$, there is an honest party
whose selection as the leader does not guarantee termination. This shows the
hopelessness of finding a valid argument for the weaker claim.

Assuming the preconditions for the $\Pi_{\mathsf{select}}$ protocol hold, we
now consider adaptive corruption in this subsection. The adversary
$\mathcal{A}$ does not corrupt any party before the leader is selected. If the
chosen leader is $p_{2}$, then $\mathcal{A}$ follows the description of the
static attack by corrupting $p_{1}$ and executing the attack as previously
described.

However, if party $p_{1}$ is chosen as the leader, we can leverage symmetry
and modify the adversary’s description accordingly. We rename the parties as
follows:
$p^{\prime}_{1}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=p_{2}$,
$p^{\prime}_{2}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=p_{1}$,
$p^{\prime}_{3}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=p_{4}$,
and
$p^{\prime}_{4}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=p_{3}$.
The adversary $\mathcal{A}$ corrupts $p^{\prime}_{1}$ and runs the same static
adversary code on the participant set
$\\{p^{\prime}_{1},p^{\prime}_{2},p^{\prime}_{3},p^{\prime}_{4}\\}$.
Furthermore, it is important to note that in the static attack, we previously
specified that
$Relay_{1,2}=Relay_{4,2}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{p_{1},p_{2},p_{3}\\}$,
while allowing $Relay_{2,1}$ and $Relay_{3,1}$ to be arbitrary since they were
not essential to the attack and could take any value. However, in order to
achieve full symmetry in the static attack and apply the aforementioned
approach, $\mathcal{A}$ should now set
$Relay_{2,1}=Relay_{3,1}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{p_{1},p_{2},p_{4}\\}$
in the description of the static attack.

With these adjustments, our adaptive adversary is complete.

##  Appendix B The Asynchronous Turpin-Coan Extension

Here, we investigate when the generic extension of binary to multi-valued
synchronous BA (for $t<n/3$) given by Turpin and Coan [78] works in the
asynchronous setting with eventual delivery. It turns out that an asynchronous
version of the extension—with appropriate modifications—is secure when
$t<n/5$, but is provably insecure for any $t\geq n/5$ regardless of which
binary A-BA protocol is used. We remark that while our negative result is not
exactly a lower bound, as the attack that we present is on a specific
extension protocol, the fact that we lose two additive factors of $t$ in
resiliency (and even three, with a more naïve approach) gives some evidence
that more sophisticated techniques are needed to maintain optimal resiliency,
as in [70]. Since our primary goal is to show that the Turpin-Coan extension
cannot be used to get optimally resilient, multi-valued A-BA in expected-
constant rounds, we choose to work with simpler, property-based definitions in
this section.

We start by reviewing the original extension in [78], which requires just two
additional rounds. Parties first distribute their inputs amongst one another,
over P2P channels. An honest party, based on how many of the received values
disagree with his own, considers himself either “perplexed” or “content,” and
announces this information. If enough parties claim to be perplexed, the
honest party becomes “alert.” The parties now run a binary BA protocol to
agree on this last state (effectively, to determine if they all started with
the same input), and depending on the outcome they either output a default
value, or are able to recover a common value from their local transcripts of
the protocol.

Protocol $\Pi_{\mathsf{a\mathchar 45\relax tc}}^{V}$ Local input of party
$p_{i}$: $v_{i}\in V$, $|V|\geq 2$ Local output of party $p_{i}$: $v\in V$
Code for party $p_{i}$: 0. Initialize arrays $v[1..n]$ and $x[1..n]$ by
filling them with a default value $\bot$. 1. A-Cast $v_{i}$. 2. Whenever
$v^{\prime}_{j}$ is accepted from party $p_{j}$, record
$v[j]\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=v^{\prime}_{j}$.
3. Wait until $n-t$ values are accepted. Then, let
$x_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$ (“perplexed”)
if $v[j]\not=\bot$ and $v[j]\not=v_{i}$ for at least $t+1$ different indices
$j$, and otherwise let
$x_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=0$ (“content”).
A-Cast $(v_{i},x_{i})$. 4. Whenever $(v^{\prime}_{j},x^{\prime}_{j})$ is
accepted from party $p_{j}$, record
$x[j]\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=x^{\prime}_{j}$.
If $v[j]=\bot$, then additionally record
$v[j]\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=v^{\prime}_{j}$.
5. Wait until $n-t$ pairs are accepted. Then, let
$a_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$ (“alert”) if
$x[j]=1$ for at least $t+1$ different indices $j$, and otherwise let
$a_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=0$. Run binary
A-BA with input $a_{i}$. 6. If the binary computation agrees $1$, then set $v$
to be a predefined default value from $V$. Otherwise, if content set
$v\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=v_{i}$, and if
perplexed set $v$ to be the majority value from the non-bottom entries in
$v[]$ at indices $j$ for which $x[j]=0$. Output $v$.

Figure 14: The asynchronous Turpin-Coan extension.

Our asynchronous version of this extension, $\Pi_{\mathsf{a\mathchar 45\relax
tc}}$, is shown in Figure 14. We simply replace the basic message distribution
mechanism with A-Cast, and account for the fact that adversarial A-Cast’s may
never terminate (i.e., honest parties should only expect to receive $n-t$
values). To avoid a somewhat artificial attack wherein the adversary can
manipulate delays so that $t$ entries are missing in an honest party’s $v[]$
array and a _different_ set of $t$ entries are missing in the $x[]$ array, we
require parties to re-send their input value in the second A-Cast. Note that
this additional modification cannot _decrease_ security, since honest parties
will always use their actual input. In the following proposition, we prove the
security of $\Pi_{\mathsf{a\mathchar 45\relax tc}}$ for $t<n/5$. We emphasize
that in the asynchronous setting we must impose relaxed termination
requirements. However, since the modified extension is still deterministic and
constant-round, any termination guarantees provided by the underlying binary
A-BA protocol should be preserved; accordingly, we only prove the agreement
and validity properties.

######  Proposition 9.

For any input domain $V$, protocol $\Pi_{\mathsf{a\mathchar 45\relax tc}}^{V}$
securely implements multi-valued A-BA from A-Cast and binary A-BA, in constant
rounds and in the presence of an adaptive and malicious $t$-adversary,
provided $t<n/5$.

###### Proof.

The round complexity is easily established by inspection (considering A-Cast
and binary A-BA to be ideal primitives). We now prove correctness:

#### Validity.

If all honest parties begin with the same initial value $v$, then no honest
party is perplexed and all honest parties are not alert. The binary
computation agrees $0$ and all honest parties (which are content) output $v$.

#### Agreement.

There are two cases: the binary computation agrees either $1$ or $0$. In the
former case, all honest parties output a common default value. For the latter
case, we show that all content parties have the same initial value, and that
this value is correctly deduced by all the perplexed parties.

Note that each content party’s input appears in at least $n-t-t=n-2t$
positions in its $v[]$ array. Since at most $t$ of these positions correspond
to corrupted parties, we have that each content party has the same initial
value as at least $n-3t$ honest parties, which represent a majority of the
honest parties when $n>5t$. Of course there cannot be two distinct majorities,
so all content parties must have the same initial value.

Furthermore, since the binary computation agrees $0$, there must be at least
$2t+1$ honest content parties, for otherwise there would be at least $n-3t$
honest perplexed parties and all honest parties would be alert (at least
$n-4t\geq t+1$ of the corresponding entries in any honest party’s $x[]$ array
would not be $\bot$) and agreement would be on $1$. Each perplexed party has
$x[j]=0$ or $x[j]=\bot$ for all honest content parties and possibly for some
corrupted parties. Even in the worst case, when $x[j]=\bot$ for $t$ of the
honest content parties, there are still at least $2t+1-t=t+1$ honest content
parties left but at most $t$ corrupted parties, so the content parties are a
majority of those for which $x[j]=0$ and $v[j]\not=\bot$. ∎

It is not difficult to see that when the predefined default value comes from
outside of $V$, the resulting multi-valued A-BA protocol is actually
_intrusion-tolerant_ (see Section 1.2). We now show that
$\Pi_{\mathsf{a\mathchar 45\relax tc}}$ is insecure when $t\geq n/5$ (i.e.,
that the analysis above is tight). Our attack does not make any assumptions
regarding the underlying binary A-BA protocol, other than that it satisfies
the properties of A-BA. Moreover, we require only static corruptions, and
somewhat surprisingly the attack considers only binary inputs (i.e., using the
extension when $|V|=2$ actually breaks the security of the binary protocol for
$n/5\leq t<n/3$).

######  Proposition 10.

For all input domains $V$, protocol $\Pi_{\mathsf{a\mathchar 45\relax
tc}}^{V}$ does NOT securely implement multi-valued A-BA from A-Cast and binary
A-BA, in the presence of a static and malicious $t$-adversary, for any $t\geq
n/5$.

###### Proof.

It suffices to consider the case $n=5t$. We construct a distribution of
inputs, a static adversary $\mathcal{A}$, and a message scheduling such that
agreement is broken.

Let $\\{p_{1},\ldots,p_{5t}\\}$ be the set of parties. Define four sets
$A\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{p_{1},\ldots,p_{2t}\\}$,
$B\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{p_{2t+1},\ldots,p_{3t}\\}$,
$T\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{p_{3t+1},\ldots,p_{4t}\\}$,
and
$C\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{p_{4t+1},\ldots,p_{5t}\\}$.
The parties in $T$ are statically corrupted by $\mathcal{A}$ and instructed to
start the protocol with input $0$. Suppose the parties in $A$ and $B$ start
with input $1$, and parties in $C$ with input $0$. Now consider a message
scheduling in which: 1) both A-Casts from parties in $C$ get delayed for
parties in $A$, 2) the A-Casted input values from $p_{1},\ldots,p_{t}\in A$
get delayed for parties in $B$ and $C$, 3) the A-Casted pairs from parties in
$C$ get delayed for parties in $B$, and 4) the A-Casted pairs from
$p_{t+1},\ldots,p_{2t}\in A$ get delayed for parties in $C$.

Observe that all parties in $A$ will A-Cast that they are content.
$\mathcal{A}$ also instructs parties in $T$ to maliciously A-Cast that they
are content. On the other hand, the parties in both $B$ and $C$ will A-Cast
that they are perplexed. Then, no party in $A$ or $B$ will be alert, whereas
all parties in $C$ will be alert. We summarize all this information in Figure
15.

| $A_{1}$ | $A_{2}$ | $B$ | $\color[rgb]{1,0,0}T$ | $C$ |
---|---|---|---|---|---|---
$A$ | $1$ | $1$ | $1$ | $\color[rgb]{1,0,0}0$ |  |
$(1,\text{c})$ | $(1,\text{c})$ | $(1,\text{p})$ | $\color[rgb]{1,0,0}(0,\text{c})$ |  | not alert
$B$ |  | $1$ | $1$ | $\color[rgb]{1,0,0}0$ | $0$ |
$(1,\text{c})$ | $(1,\text{c})$ | $(1,\text{p})$ | $\color[rgb]{1,0,0}(0,\text{c})$ |  | not alert
$C$ |  | $1$ | $1$ | $\color[rgb]{1,0,0}0$ | $0$ |
$(1,\text{c})$ |  | $(1,\text{p})$ | $\color[rgb]{1,0,0}(0,\text{c})$ | $(0,\text{p})$ | alert
Figure 15: Summary of the A-Casts received by parties in $A$, $B$, and $C$,
and their resulting alert status. The content and perplexed values are denoted
by “c” and “p,” respectively. Note that each column corresponds to a set of
$t$ parties ($A_{1}$ and $A_{2}$ denote $\\{p_{1},\ldots,p_{t}\\}$ and
$\\{p_{t+1},\ldots,p_{2t}\\}$, respectively).

Consequently, if $\mathcal{A}$ instructs parties in $T$ to run the binary A-BA
protocol with input $0$ (not alert), and delays messages from parties in $C$
during the computation, then agreement will be on $0$. Therefore, parties in
$A$ will output their initial value $1$, while the parties in $B$ and $C$ will
try to deduce the correct output from their arrays. All parties in $B$ can do
this successfully ($2t$ of the $3t$ relevant entries in the $v[]$ array will
be $1$). However, for parties in $C$, $t$ of the $2t$ relevant entries will be
$1$ while the other $t$ will be $0$. ∎

It is possible to show that without the small modification in which parties
A-Cast their input twice, the protocol is secure if and only if $t<n/6$. We
have a method to extend binary to multi-valued A-BA in constant rounds for
$t<n/4$, which is not much more complicated than the synchronous extension in
[78] (although it requires _two_ invocations of the binary protocol). However,
as discussed in Section 3.2, to re-gain optimal resiliency $t<n/3$ we use the
asynchronous extension of Mostéfaoui and Raynal [70]. We leave open the
possibility of obtaining expected-constant-round multi-valued A-BA via other
approaches, such as substituting our multi-valued OCC in the binary A-BA
protocol from [34] (and making appropriate changes). In any case, we prefer
the solution in [70] as it is a _black-box_ reduction.