$P_j$ distributes an inconsistent verification point
to an honest verifier $P_i$ from the corresponding $\R$ set and still broadcasts an $\OK$ message during $\Auth$,
then $P_j$ will locally be discarded by the verifier $P_i$,  except with probability $\errorAICP$ (follows from the non-repudiation property of ICP).
From then onwards, in all the instances of $(\Auth, \Reveal)$,
involving $P_j$ as the signer,
if the verifier $P_i$ is added to the $\R$ set, then the “special"
verification information revealed by $P_i$ during $\Reveal$ will always be considered as accepted, irrespective of what
verification information
it actually receives from $P_j$ during $\Auth$.
Hence, $P_j$ will not have any chance of cheating the verifier $P_i$ in any $\Auth$ instance. By considering all possibilities
for a corrupt $\S$ and an honest verifier $P_i$, along with an honest $\INT$, it follows that
except with probability at most $\Order(n^3 \cdot \errorAICP)$,
the verification-points of all honest verifiers from corresponding $\R$,
will be accepted by every honest $\Receiver$,
during all the instances of $\Reveal$, in any instance of $\VSS$ or $\Rec$.
Consequently, except with probability at most $\Order(n^3 \cdot \errorAICP)$, the signatures revealed by all honest $\INT$ will be always accepted.

We stress that the above modification does not help a corrupt $\INT$ to break the
unforgeability property for an honest $\S$ and an honest $\Receiver$, with the help
of potentially corrupt verifiers.

Populating $\LD$ Sets During Instances of $\Reveal$.

Consider an instance of $\Reveal$ involving $P_i$ as $\Receiver$ and $P_j$ as $\INT$.
If $P_i$ finds that $P_j$ has tried to forge signature on an incorrect value, then $P_i$
adds $P_j$ to $\LD^{(i)}$. To achieve this goal, during $\Reveal$,
$P_i$ (as $\Receiver$) now additionally checks if there exists a subset of verifiers $\R'' \subseteq \R$, where $\R \setminus \R'' \in \Z_a$, such that
the verification-points of all the parties in $\R''$ are rejected. If such a subset $\R''$ exists, then clearly $P_j$ (as $\INT$) has cheated and tried to break the
unforgeability property, since
$\R''$ is bound to contain at least one honest verifier. If the verification point of an honest verifier is rejected, then clearly $P_j$ is corrupt.
Once $P_j \in \LD^{(i)}$, from then onwards,
in any instance of $\Reveal$ involving $P_j$ as $\INT$ and $P_i$ as $\Receiver$, party
$P_i$ always rejects any IC-signature revealed by $P_i$.

The above modification  ensures that if in any instance of $\Reveal$ involving an honest signer, a corrupt intermediary $P_j$ and an honest receiver $P_i$, $P_j$ tries to reveal an incorrect
signature during $\Reveal$,
then except with probability $\errorAICP$, the intermediary $P_j$ will be locally discarded by the receiver $P_i$ (follows from the unforgeability property of ICP).
From then onwards, in all the instances of $(\Auth, \Reveal)$,
involving $P_j$ as the intermediary and $P_i$ as the receiver, the signature revealed by $P_j$ during $\Reveal$ will always be rejected, irrespective of what
data is actually revealed by $P_j$.
Hence, by considering all possibilities for a corrupt $\INT$,
honest $\S$ and honest $\Receiver$,
it follows that except with probability at most $\Order(n^3 \cdot \errorAICP)$,
no corrupt $\INT$ will be able to forge an honest $\S$'s  signature to any honest $\Receiver$,
in any instance of $\Reveal$, during any instance of $\VSS$ or $\Rec$.

§.§ Network Agnostic Secure Multicast

Based on protocols $\VSS$ and $\Rec$, we design a secure verifiable multicast protocol $\SVM$. In the protocol, there exists a designed sender
$\Sender \in \PartySet$ with input $v \in \F$ and a designated set of
receivers $\ReceiverSet$. The goal is to let every party in $\ReceiverSet$ receive $v$, without revealing any additional information to the adversary.[Note that the requirements here are different
from broadcast since we need the privacy of $v$ if $\Sender$ is honest and if $\ReceiverSet$ consists of only honest parties.]
While in a synchronous network, the (honest) parties in $\ReceiverSet$ get $v$ after a “fixed" time, in an asynchronous network, they do so eventually.
Note that if $\Sender$ is corrupt, then the parties need not obtain any output, as $\Sender$ may not invoke the protocol.
However, if any honest party in $\ReceiverSet$ computes an output $v^{\star}$ (which could be different from $v$), then all honest parties in $\ReceiverSet$ will also output $v^{\star}$.
The “verifiability" here guarantees that in case the honest parties in $\ReceiverSet$ get any output, then all the (honest) parties in $\PartySet$ will be
“aware" of this; namely there will be a Boolean variable $\flag^{(\Sender, \ReceiverSet)}$, which all the honest parties will set to $1$.

The idea behind $\SVM$ is very simple. The parties participate in an instance of $\VSS$, where $\Sender$ plays the role of the dealer with input $v$.
Once any (honest) party computes an output during $\VSS$ (implying that $\Sender$ is committed to some value $v^{\star}$ which is the same as $v$ for an honest $\Sender$),
then it turns $\flag^{(\Sender, \ReceiverSet)}$ to $1$.
Once $\flag^{(\Sender, \ReceiverSet)}$ is turned to $1$, the parties invoke an instance of $\Rec$ to let only the parties in $\ReceiverSet$ reconstruct the committed value.
Protocol $\SVM$ and proof of its properties (stated in Lemma <ref>), are available in Appendix <ref>.

Protocol $\SVM$ achieves the following, where $\Sender$ participates with input $v$ and where each honest party initializes $\flag^{(\Sender, \ReceiverSet)}$ to $0$.

– Synchronous Network: If $\Sender$ is honest, then all honest parties set $\flag^{(\Sender, \ReceiverSet)}$ to $1$ at time $\TimeVSS$
and except with probability $\Order(n^3 \cdot \errorAICP)$, all honest parties in $\ReceiverSet$ output $v$, after time
$\TimeSVM = \TimeVSS + \TimeRec$. Moreover, if $\ReceiverSet$ consists of only honest parties, then the view of $\Adv$ remains independent of $v$.
If $\Sender$ is corrupt and some honest party sets $\flag^{(\Sender, \ReceiverSet)}$ to $1$, then there exists some $v^{\star}$ such that,
except with probability $\Order(n^3 \cdot \errorAICP)$, all honest parties in $\ReceiverSet$ output $v^{\star}$. Moreover, if any honest party sets
$\flag^{(\Sender, \ReceiverSet)}$ to $1$ at time $T$,
then all honest parties in $\ReceiverSet$ output $v^{\star}$ by time $T + 2\Delta$.

– Asynchronous Network: If $\Sender$ is honest, then all honest parties eventually set $\flag^{(\Sender, \ReceiverSet)}$ to $1$
and  except with probability $\Order(n^3 \cdot \errorAICP)$, all honest parties in $\ReceiverSet$ eventually output $v$.
Moreover, if $\ReceiverSet$ consists of only honest parties, then the view of the adversary remains independent of $v$.
If $\Sender$ is corrupt and some honest party sets $\flag^{(\Sender, \ReceiverSet)}$ to $1$, then there exists some $v^{\star}$ such that ,
except with probability $\Order(n^3 \cdot \errorAICP)$, all honest parties in $\ReceiverSet$ eventually output $v^{\star}$.

– Communication Complexity: $\Order(|\Z_s| \cdot n^8 \cdot \log{|\F|} \cdot |\sigma|)$ bits are communicated.

§ NETWORK AGNOSTIC PROTOCOL FOR GENERATING LINEARLY SECRET-SHARED RANDOM VALUES WITH IC-SIGNATURES

In this section, we present a network agnostic protocol $\Rand$, which allows the parties to jointly generate
linear secret-sharing of random values with IC-signatures.
To design the protocol $\Rand$, we first design a subprotocol $\MDVSS$.

§.§ Network Agnostic VSS for Multiple Dealers

Protocol $\MDVSS$ (Fig <ref>) is a multi-dealer VSS.
In the protocol, each party $P_{\ell} \in \PartySet$ participates as a dealer with some input $s^{(\ell)}$.
Then, irrespective of the network type, the protocol outputs a common subset of dealers $\Core \subseteq \PartySet$, which is guaranteed to have at least one honest dealer.
Moreover, corresponding to every dealer $P_{\ell} \in \Core$, there will be some value, say ${s^{\star}}^{(\ell)}$, which will be the same as $s^{(\ell)}$ for an honest $P_{\ell}$,
such that the values
$\{{s^{\star}}^{(\ell)} \}_{P_{\ell} \in \Core}$ are linearly secret-shared with IC-signatures. While in a synchronous network,  $\{[{s^{\star}}^{(\ell)}] \}_{P_{\ell} \in \Core}$
is generated after a “fixed" time, in an asynchronous network, $\{[{s^{\star}}^{(\ell)}] \}_{P_{\ell} \in \Core}$ is generated eventually.

The high level overview of $\MDVSS$ has been already discussed in detail in
Section <ref>.[Actually, the overview was for the protocol $\Rand$, but the same idea is also used in the protocol $\MDVSS$.]
The idea is to let every dealer $P_{\ell}$ to invoke an instance
of $\VSS$ to secret-share its input. However, we need to take special care to ensure that the inputs of all the dealers in $\Core$ are secret-shared with common
core-sets. For this, each individual dealer in its instance of $\VSS$ computes and publishes as many “legitimate" core-sets as possible and the parties run instances of
agreement on common subset
(ACS) to identify whether “sufficiently many" dealers have published the same legitimate core-sets in their respective instances of $\VSS$.
Moreover, to ensure that all the underlying IC-signatures satisfy the linearity property, we first need to identify the dealers who distribute shares as part of their respective
$\VSS$ instances. For this, we let each dealer distribute shares in its instance of $\VSS$ through instances of $\SVM$. This enables the parties to identify
a set of committed dealers $\CD$ who have indeed distributed shares as part of their $\VSS$ instances through instances of $\SVM$.

$\MDVSS(\PartySet, \Z_s, \Z_a, (s^{(1)}, \ldots, s^{(n)}), \SharingSpec_{\Z_s})$The statistically-secure VSS protocol for multiple dealers to generate linearly secret-shared values with

– Committing Shares: Each $P_{i} \in \PartySet$ executes the following steps.

– On having input $s^{(i)}$, randomly choose $s^{(i)}_1,\dots,s^{(i)}_{|\Z_s|}$,
such that $s^{(i)} = s^{(i)}_1 + \dots + s^{(i)}_{|\Z_s|}$.
Act as $\Sender$ and invoke instances $\SVM(P_{i}, s^{(i)}_1, S_1), \ldots, \SVM(P_{i}, s^{(i)}_{|\Z_s|}, S_{|\Z_s|})$ of $\SVM$.

– Corresponding to every dealer $P_{\ell} \in \PartySet$, participate in the instances
of $\SVM$, invoked by $P_{\ell}$ as a $\Sender$
and  wait till the local time becomes $\TimeSVM$. For $q = 1, \ldots, |\Z_s|$,
let $\flag^{(P_{\ell}, S_q)}$ be the Boolean flag, corresponding to the instance $\SVM(P_{\ell}, s^{(\ell)}_q, S_q)$, invoked by $P_{\ell}$.

– Identifying the Set of Committed Dealers Through ACS: Each $P_i \in \PartySet$ does the following.

– For $\ell = 1, \ldots, n$,
participate in an instance $\BA^{(\ell)}$ of $\BA$ with input $1$, provided $P_i$ has set
$\flag^{(P_{\ell}, S_q)} = 1$, for $q = 1, \ldots, |\Z_s|$.

– Once there exists a subset of dealers $\CD_i$ where $\PartySet \setminus \CD_i \in \Z_s$, such that
corresponding to every dealer $P_{\ell} \in \CD_i$, the instance
$\BA^{(\ell)}$ has produced output $1$, then participate with input $0$ in all the BA instances $\BA^{(\star)}$, for which no input is provided yet.

– Once all the $n$ instances of $\BA^{(\star)}$ have produced a binary output, set $\CD$ to be the set of dealers $P_{\ell}$,
such that
$\BA^{(\ell)}$ has produced output $1$.

– Exchanging IC-Signed Values: Each $P_i \in \PartySet$  waits till the local time becomes $\TimeSVM + 2\TimeBA$.
Then corresponding to each dealer $P_{\ell} \in \CD$, does the following.

– For each $S_q \in \ShareSpec_{\Z_s}$ such that $P_i \in S_q$,
upon computing an output $s^{(\ell)}_{qi}$ during $\SVM(P_{\ell}, s^{(\ell)}_q, S_q)$,
give $\ICSig(P_i, P_j, P_k, s^{(\ell)}_{qi})$ to every $P_j \in S_q$,  for every $P_k \in \PartySet$,
where the parties follow the linearity principle while generating IC-signatures.

– Announcing Results of Pairwise Consistency Tests:
Each $P_i \in \PartySet$  waits till the local time becomes $\TimeSVM + 2\TimeBA + \TimeAuth$
and then does the following, corresponding to each dealer $P_{\ell} \in \CD$.

– Upon receiving $\ICSig(P_j, P_i, P_k, s^{(\ell)}_{qj})$ from $P_j$ for each $S_q \in \ShareSpec$ such that $P_j, P_i \in S_q$, corresponding to every $P_k \in \PartySet$,
broadcast $\OK^{(\ell)}(i, j)$,  if
$s^{(\ell)}_{qi} = s^{(\ell)}_{qj}$ holds.

– Corresponding to every $P_j \in \PartySet$, participate in any instance of $\BC$ initiated by $P_j$ as a sender, to broadcast any $\OK^{(\ell)}(P_j, \star)$ message.

– Constructing Consistency Graphs: Each $P_i \in \PartySet$  waits till the local time becomes $\TimeSVM + 2\TimeBA + \TimeAuth + \TimeBC$
and then does the following, corresponding to each dealer $P_{\ell} \in \CD$.

– Construct an undirected consistency graph $G^{(\ell, i)}$ with $\PartySet$ as the vertex set, where
the edge $(P_j, P_k)$ is added to $G^{(\ell, i)}$, provided $\OK^{(\ell)}(j, k)$ and $\OK^{(\ell)}(k, j)$ is received from the broadcast of $P_j$ and $P_k$ respectively (through any mode).

– Public Announcement of Core Sets by the Committed Dealers: Each dealer $P_{\ell} \in \CD$
waits till its local time is $\TimeSVM + 2\TimeBA + \TimeAuth + \TimeBC$, and then
executes the following steps to compute core sets.

– $\forall S_p \in \ShareSpec_{\Z_s}$, once
$S_p$ forms a clique in $G^{(\ell, \ell)}$, then for $q = 1, \ldots, |\Z_s|$, compute core-set $\W^{(\ell)}_{p, q}$
and broadcast-set $\BroadcastSet^{(\ell)}_p$ with respect to $S_p$ as follows, followed by broadcasting
$(\CandidateCoreSets, P_{\ell}, S_p, \{ \W^{(\ell)}_{p, q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet^{(\ell)}_p, \{ s^{(\ell)}_q\}_{q \in \BroadcastSet^{(\ell)}_p})$.

– If $S_q$ constitutes a clique in the graph $G^{(\ell, \ell)}$, then set $\W^{(\ell)}_{p, q} = S_q$.

– Else if $(S_p \cap S_q)$ constitutes a clique in $G^{(\ell, \ell)}$ and
$\Z_s$ satisfies the $\Q^{(1)}(S_p \cap S_q, \Z_s)$ condition,
then set $\W^{(\ell)}_{p, q} = (S_p \cap S_q)$.

– Else set $\W^{(\ell)}_{p, q} = S_q$ and include $q$ to $\BroadcastSet^{(\ell)}_p$.

– Identifying Valid Core Sets: Each $P_i \in \PartySet$  waits for time $\TimeSVM + 2\TimeBA + \TimeAuth + 2\TimeBC$ and then initializes a set $\C_i = \emptyset$.
Corresponding to $P_{\ell} \in \CD$
and $p = 1, \ldots, |\Z_s|$, party $P_i$ includes $(P_{\ell}, S_p)$ to $\C_i$, provided all the following hold.

–  $(\CandidateCoreSets, P_{\ell}, S_p, \{ \W^{(\ell)}_{p, q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet^{(\ell)}_p, \{ s^{(\ell)}_q\}_{q \in \BroadcastSet^{(\ell)}_p})$
is received from the broadcast of $P_{\ell}$, such that  for $q = 1, \ldots, |\Z_s|$, the following hold.

– If $q \in \BroadcastSet^{(\ell)}_p$, then the set $\W^{(\ell)}_{p, q} = S_q$.

– If $(q \not \in \BroadcastSet^{(\ell)}_p)$, then $\W^{(\ell)}_{p, q}$ is either $S_q$ or  $(S_p \cap S_q)$, such that:

– If $\W^{(\ell)}_{p, q} = S_q$, then $S_q$ constitutes a clique in $G^{(\ell, i)}$.

– Else if $\W^{(\ell)}_{p, q} = (S_p \cap S_q)$, then
$(S_p \cap S_q)$ constitutes a clique in $G^{(\ell, i)}$ and
$\Z_s$ satisfies the $\Q^{(1)}(S_p \cap S_q, \Z_s)$ condition.

– Selecting the Common Committed Dealers and Core Sets through ACS:  Each party $P_i \in \PartySet$ does the following.

– For $p = 1, \ldots, |\Z_s|$, participate in an instance $\BA^{(1, p)}$ of $\BA$ with input $1$, provided there exists a set of dealers
${\cal A}_{p, i} \subseteq \CD$
where $\CD \setminus {\cal A}_{p, i} \in \Z_s$
and where $(P_{\ell}, S_p) \in \C_i$ for every $P_{\ell} \in {\cal A}_{p, i}$.

– Once any instance of $\BA^{(1, \star)}$ has produced an output $1$, participate with input $0$ in all the BA instances $\BA^{(1, \star)}$, for which no input is provided yet.

– Once all the $|\Z_s|$ instances of $\BA^{(1, \star)}$ have produced a binary output, set $\qcore$ to be the least index among $\{1, \ldots, |\Z_s| \}$, such that
$\BA^{(1, \qcore)}$ has produced output $1$.

– Once $\qcore$ is computed, then corresponding to each $P_j \in \CD$,
participate in an instance $\BA^{(2, j)}$ of $\BA$ with input $1$, provided $(P_j, S_{\qcore}) \in \C_i$.

– Once there exists a set of parties ${\cal B}_i \subseteq \CD$,
such that $\CD \setminus {\cal B}_i \in \Z_s$ and $\BA^{(2, j)}$ has produced output $1$, corresponding to each $P_j \in {\cal B}_i$,
participate with input $0$ in all the instances of $\BA^{(2, \star)}$, for which no input is provided yet.

– Once all the $|\CD|$
instances of $\BA^{(2, \star)}$ have produced a binary output, include all the parties $P_j$ from $\CD$ in $\Core$ (initialized to $\emptyset$), such that $\BA^{(2, j)}$ has produced output $1$.

– Computing Output: Each $P_i \in \PartySet$ does the following, after computing $\Core$ and $\qcore$.

– If $(\CandidateCoreSets, P_{\ell}, S_{\qcore}, \{ \W^{(\ell)}_{\qcore, q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet^{(\ell)}_{\qcore}, \{ s^{(\ell)}_{q}\}_{q \in \BroadcastSet^{(j)}_{\qcore}})$
is not yet received from the broadcast of $P_{\ell}$ for for any $P_{\ell} \in \Core$, then wait to receive it
from the broadcast of $P_{\ell}$ through fallback-mode.

– Once $(\CandidateCoreSets, P_{\ell}, S_{\qcore}, \{ \W^{(\ell)}_{\qcore, q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet^{(\ell)}_{\qcore}, \{ s^{(\ell)}_{q}\}_{q \in \BroadcastSet^{(j)}_{\qcore}})$
is available for every
$P_{\ell} \in \Core$, compute $\W_q$ for $q = 1, \ldots, |\Z_s|$ as follows.

– If $\W^{(\ell)}_{\qcore, q} = S_q$ for every $P_{\ell} \in \Core$, then set $\W_q = S_q$.

– Else set $\W_q = (S_{\qcore} \cap S_q)$.

– Corresponding to every $P_{\ell} \in \Core$ and every $S_q \in \ShareSpec_{\Z_s}$ such that $P_i \in S_q$, compute the output as follows.

– If $q \in \BroadcastSet^{(\ell)}_{\qcore}$, then set $[s^{(\ell)}]_q = s^{(\ell)}_q$, where $s^{(\ell)}_q$ was received from the broadcast of $P_{\ell}$,
as part of $(\CandidateCoreSets, P_{\ell}, S_{\qcore}, \allowbreak \{ \W^{(\ell)}_{\qcore, q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet^{(\ell)}_{\qcore}, \{ s^{(\ell)}_{q}\}_{q \in \BroadcastSet^{(j)}_{\qcore}})$.
Moreover, for every $P_j \in \W_q$ and every $P_k \in \PartySet$, set
$\ICSig(P_j, P_i, P_k, [s^{(\ell)}]_q)$ to the default value.

– Else, set $[s^{(\ell)}]_q$ to $s^{(\ell)}_{qi}$, where $s^{(\ell)}_{qi}$ was computed as output during $\SVM(P_{\ell}, s^{(\ell)}_q, S_q)$. Moreover,
if $P_i \in \W_q$, then
for every $P_j \in \W_q$ and every $P_k \in \PartySet$, set
$\ICSig(P_j, P_i, P_k, [s^{(\ell)}]_q)$ to  $\ICSig(P_j, P_i, P_k, s^{(\ell)}_{qj})$, received from $P_j$.

Output $\Core$, the core sets $\W_1, \ldots, \W_{|\Z_s|}$, shares
$\{[s^{(\ell)}]_q\}_{P_{\ell} \in \Core \; \wedge \; P_i \in S_q}$ and
the IC-signatures $\ICSig(P_j, P_i, P_k, [s^{(\ell)}]_q)_{P_{\ell} \in \Core \; \wedge \; P_j, P_i \in \W_q, P_k \in \PartySet}$.

The properties of $\MDVSS$, stated in Theorem <ref> are proved in Appendix <ref>.

Protocol $\MDVSS$ achieves the following where each $P_{\ell}$ participates with input $s^{(\ell)}$ and where  $\TimeMDVSS = \TimeSVM  + \TimeAuth + 2\TimeBC + 6\TimeBA$.

– $\Z_s$-Correctness&Commitment:   If the network is synchronous, then except with probability $\Order(n^3 \cdot \errorAICP)$,
at time $\TimeMDVSS$, all honest parties output a common set $\Core \subseteq \PartySet$
such that at least one honest party will be present in $\Core$.
Moreover, corresponding to every $P_{\ell} \in \Core$, there exists some ${s^{\star}}^{(\ell)}$, where ${s^{\star}}^{(\ell)} = s^{(\ell)}$ for an honest $P_{\ell}$,
such that the values $\{  {s^{\star}}^{(\ell)}  \}_{P_{\ell} \in \Core}$ are linearly secret-shared with IC-signatures.

– $\Z_a$-Correctness&Commitment:   If the network is asynchronous, then except with probability $\Order(n^3 \cdot \errorAICP)$, almost-surely
all honest parties output a common set $\Core \subseteq \PartySet$ eventually
such that at least one honest party will be present in $\Core$.
Moreover, corresponding to every $P_{\ell} \in \Core$, there exists some ${s^{\star}}^{(\ell)}$, where ${s^{\star}}^{(\ell)} = s^{(\ell)}$ for an honest $P_{\ell}$,
such that the values $\{  {s^{\star}}^{(\ell)}  \}_{P_{\ell} \in \Core}$ are eventually linearly secret-shared with IC-signatures.

– Privacy: Irrespective of the network type, the view of the adversary remains independent of $s^{(\ell)}$, corresponding to every honest $P_{\ell} \in \Core$.

– Communication Complexity: $\Order(|\Z_s|^2 \cdot n^9 \cdot \log{|\F|} \cdot |\sigma|)$ bits are communicated by
the honest parties. In addition,
$\Order(|\Z_s| + n)$ instances of $\BA$ are invoked.

Protocol $\MDVSS$ with $L$ Values for Each Dealer. In protocol $\MDVSS$, each dealer $P_{\ell} \in \PartySet$ participates with a single input.
Consider a scenario where each $P_{\ell}$ participates with $L$ inputs $\overrightarrow{S^{(\ell)}} = (s^{(\ell, 1)}, \ldots, s^{(\ell, L)})$, where $L \geq 1$.
The goal is to identify a common subset of dealers $\Core \subseteq \PartySet$ which is guaranteed to have at least one honest dealer, irrespective of the network type. Corresponding to every dealer $P_{\ell} \in \Core$, there exist $L$ values, say $\overrightarrow{{S^{\star}}^{(\ell)}} = ({s^{\star}}^{(\ell, 1)}, \ldots, {s^{\star}}^{(\ell, L)})$,
which will be the same as $\overrightarrow{S^{(\ell)}}$ for an honest $P_{\ell}$, where all the values in
$\{\overrightarrow{{S^{\star}}^{(\ell)}} \}_{P_{\ell} \in \Core}$ are linearly secret-shared with IC-signatures. To achieve this, we run the protocol $\MDVSS$ with the following modifications,
so that the number of instances of $\BA$ in the protocol still remains to be $\Order(|\Z_s| + n)$, which is independent of $L$.

Corresponding to each $s^{(\ell)} \in \overrightarrow{S^{(L)}}$, the dealer $P_{\ell}$ will pick $|\Z_s|$ random shares (which sum up to $s^{(\ell)}$) and the shares corresponding to the group
$S_q \in \ShareSpec_{|\Z_s|}$ are communicated through an instance of $\SVM$; hence $|\Z_s| \cdot L$ instances are invoked by $P_{\ell}$ as a $\Sender$.
Then, while identifying the set of committed dealers $\CD$, parties vote $1$ for $P_{\ell}$  in the instance $\BA^{(\ell)}$ provided the underlying $\flag$ variable is set to $1$ in all
the $|Z_s| \cdot L$ instances of $\SVM$ invoked by $P_{\ell}$. The rest of the steps for identifying $\CD$ remains the same. This way, by executing only $\Order(n)$ instances of $\BA$, we identify
the set $\CD$.

Next, the parties exchange IC-signatures on their supposedly common shares for each group, corresponding to all the $L$ values shared by each dealer from $\CD$.
However, each $P_i$ now broadcasts a single $\OK^{(\ell)}(i, j)$ message, corresponding to each $P_j \in S_q$, provided $P_i$ receives IC-signed common share from $P_j$
on the behalf of all the $L$ values, shared by $P_{\ell}$. This ensures that, for each $P_{\ell}$, every $P_i$ constructs a single consistency graph. Next, each dealer $P_{\ell}$
computes and broadcasts the candidate core-sets and broadcast-sets, as and when they are ready. The parties identify the $\Core$ set by running $\Order(|\Z_s| + n)$  instances of $\BA$.
To avoid repetition, we do not present the formal steps of the modified $\MDVSS$ protocol.
The protocol incurs a communication of $\Order(|\Z_s|^2 \cdot L \cdot n^9 \cdot \log{|\F|} \cdot |\sigma|)$ bits,
apart from $\Order(|\Z_s| + n)$ instances of $\BA$.

§.§ Protocol for Generating Secret-Shared Random Values

Protocol $\Rand$ (Fig <ref>) allows the parties to jointly generate linear secret-sharings of $L$ values with IC-signatures, where $L \geq 1$,
which are random for the adversary. For this, the parties invoke an instance of the (modified) $\MDVSS$ where each dealer $P_{\ell} \in \PartySet$ participates
with a random vector of $L$ values.
Let $\Core$ be the set of common dealers identified during the instance of $\MDVSS$. Then for $\mathfrak{l} = 1, \ldots, L$, the parties output the sum of ${\mathfrak{l}}^{th}$
value shared by all the dealers in $\Core$. Since there will be at least one honest dealer in $\Core$ whose shared values will be random for the adversary,
it follows that the resultant values also remain random for the adversary.

In the rest of the paper, we will refer to the core sets $\W_1, \ldots, \W_{|\Z_s|}$ obtained during $\Rand$ as global core-sets and denote them by $\GW_1, \ldots, \GW_{|\Z_s|}$.
From now onwards, all the secret-shared values will be generated with respect to these global core-sets.

$\Rand(\PartySet, \Z_s, \Z_a, \SharingSpec_{\Z_s}, L)$Protocol for generating linearly secret-shared random values with

– Secret-Sharing Random Values:
Each $P_{\ell} \in \PartySet$ picks $L$ random values $\overrightarrow{R^{(\ell)}} = (r^{(\ell, 1)}, \ldots, r^{(\ell, L)})$ and participates in an instance of $\MDVSS$ with input
$\overrightarrow{R^{(\ell)}}$ and  waits for time $\TimeMDVSS$.

– Computing Output: Let $(\Core, \W_1, \ldots, \W_{|\Z_s|}, \{ ([{r^{\star}}^{(\ell, 1)}], \ldots, [{r^{\star}}^{(\ell, L)}])    \}_{P_{\ell \in \Core}} )$
be the output from the instance of $\MDVSS$. For $\mathfrak{l} = 1, \ldots, L$, the parties locally compute
$[r^{(\mathfrak{l})}] = \displaystyle \sum_{P_{\ell} \in \Core} [{r^{\star}}^{(\ell, \mathfrak{l})}]$ from $\{[{r^{\star}}^{(\ell, \mathfrak{l})}] \}_{P_{\ell} \in \Core}$.
The parties then output $({\GW}_1, \ldots, {\GW}_{|\Z_s|}, \{[r^{(\mathfrak{l})}] \}_{\mathfrak{l} = 1, \ldots, L})$, where ${\GW}_q = \W_q$ for $q = 1, \ldots, |\Z_s|$.

Theorem <ref> follows easily from the above discussion.

Protocol $\Rand$ achieves the following where  $\TimeRand = \TimeMDVSS = \TimeSVM  + \TimeAuth + 2\TimeBC + 6\TimeBA$ and $L \geq 1$.

– $\Z_s$-correctness:  If the network is synchronous, then except with probability $\Order(n^3 \cdot \errorAICP)$,
at the time $\TimeRand$, there exist values $r^{(1)}, \ldots, r^{(L)}$, which are linearly secret-shared with IC-signatures, where the core-sets are
$\GW_1, \ldots, \GW_{|\Z_s|}$.

– $\Z_a$-correctness:  If the network is asynchronous, then except with probability $\Order(n^3 \cdot \errorAICP)$,
there exist values $r^{(1)}, \ldots, r^{(L)}$, which are almost-surely linearly secret-shared with IC-signatures, where the core-sets are
$\GW_1, \ldots, \GW_{|\Z_s|}$.

– Privacy: Irrespective of the network type, the view of the adversary remains independent of $r^{(1)}, \ldots, r^{(L)}$.

– Communication Complexity: The protocol incurs a communication of
$\Order(|\Z_s|^2 \cdot L \cdot n^9 \cdot \log{|\F|} \cdot |\sigma|)$ bits,
apart from $\Order(|\Z_s| + n)$ instances of $\BA$.

, satisfying the linearity property.
We first define the notion of linear secret-sharing with IC-signatures. Informally,  a vector of values $\vec{S} = (s^{(1)}, \ldots, s^{(L)})$ is said to be linearly secret-shared with IC-signatures,
provided each $s^{(\ell)}$ in $\vec{S}$ is secret-shared with IC-signatures (as per Definition <ref>). Additionally, we require that the core-sets
$\W_1, \ldots, \W_{|\Z_s|}$ are common across $[s^{(1}], \ldots, [s^{(L)}]$. Moreover, we require all (honest) parties in $S_q$ to have the share $[s^{(\ell)}]_q$.
Furthermore, we require the underlying IC-signatures to satisfy the linearity principle.

A vector of values $\vec{S} = (s^{(1)}, \ldots, s^{(L)})$ where $L \geq 1$ is said to be linearly secret-shared with IC-signatures, if there exist core sets $\W_1, \ldots, \W_{|\Z_s|}$
where $S_q \setminus \W_q \in \Z_s$, for each $S_q \in \ShareSpec_{|\Z_s|}$. Moreover, corresponding to each $s^{(\ell)} \in \vec{S}$, there exist shares $s^{(\ell)}_1, \ldots, s^{(\ell)}_{|\Z_s|}$,
such that
all the following hold.

– For each $S_q \in \ShareSpec_{\Z_s}$, all (honest) parties in $S_q$ have the share $s^{(\ell)}_q$.

– Every honest $P_i \in \W_q$ have the IC-signature
$\ICSig(P_j, P_i, P_k, s^{(\ell)}_q)$, corresponding to every $P_j \in \W_q$ and every $P_k \not \in \W_q$.
Moreover, if any corrupt $P_j \in \W_q$ has $\ICSig(P_j, P_i, P_k, s'^{(\ell)}_q)$, corresponding to any honest $P_i \in \W_q$ and any $P_k \not \in \W_q$, then
$s'^{(\ell)}_q = s^{(\ell)}_q$ holds.

– The IC-signatures
$\{ \ICSig(P_j, P_i, P_k, [s^{(\ell)}]_q) \}_{P_j, P_i \in \W_q, P_k \not \in \W_q}$ satisfy the linearity principle.

We abuse the notation and denote by $[s^{(\ell)}]$ the vector of information corresponding to a linear secret-sharing of $s^{(\ell)}$ with IC-signature. Moreover,
$[s^{(\ell)}]_q$ will denote the $q^{th}$ share of $s$, corresponding to $S_q$.

If $\vec{S} = (s^{(1)}, \ldots, s^{(L)})$ are linearly secret-shared with IC-signatures, then the parties can locally compute any publicly-known function of these values.
In more detail, let
$c_1, \ldots, c_{L} \in \F$ be publicly-known constants and let $s \defined c_1 \cdot s^{(1)} + \ldots + c_{L} \cdot s^{(L)}$.
the following holds:

\[ c_1 \cdot [s^{(1)}] + \ldots + c_{L} \cdot [s^{(L)}] = [s],    \]

where the core-sets corresponding to $[s]$ are
$\W_1, \ldots, \W_{|\Z_s|}$.
And corresponding to each $S_q \in \ShareSpec_{\Z_s}$, the share $[s]_q$
for each (honest) party in $S_q$ can be computed locally as $c_1 \cdot [s^{(1)}]_q + \ldots + c_{\ell} \cdot [s^{(\ell)}]_q$.
Moreover, every (honest) $P_i \in \W_q$ can compute $\ICSig(P_j, P_i, P_k, [s]_q)$
corresponding to every $P_j \in \W_q$ and every $P_k \not \in \W_q$, from $\ICSig(P_j, P_i, P_k, [s^{(1)}]_q), \ldots, \ICSig(P_j, P_i, P_k, [s^{(\ell)}]_q)$.
In the rest of the paper, we will say that the “parties in ${\cal P}$
locally compute $[c_1 \cdot s^{(1)} + \ldots + c_{\ell} \cdot s^{(\ell)}]$ from $[s^{(1)}], \ldots, [s^{(\ell)}]$" to mean the above.

§ NETWORK AGNOSTIC PROTOCOL FOR GENERATING RANDOM MULTIPLICATION TRIPLES

In this section, we present our network-agnostic triple-generation protocol, which generates random and private multiplication-triples which are linearly secret-shared with IC-signatures.
The protocol is based on several sub-protocols which we present next.
Throughout this section, we will assume the existence of global core-sets ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$, where $\Z_s$ satisfies the $\Q^{(1)}({\GW}_q, \Z_s)$ condition
for $q = 1, \ldots, |\Z_s|$.

Looking ahead, these core-sets will be generated by first running the protocol $\Rand$, using an appropriate value of $L$,
which will be determined across all the sub-protocols which we will be discussing next. All the secret-shared values in the various sub-protocols in the sequel will have ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$
as underlying core-sets.

§.§ Verifiably Generating Linear Secret Sharing of a Value with IC-signatures

In protocol $\LSh$ (Fig <ref>), there exists a designated dealer $\D \in \PartySet$ with private input $s$. In addition, there is
a random value $r \in \F$, which is linearly secret-shared with IC-signatures,
such that the underlying core-sets are $\GW_1, \ldots, \GW_{|\Z_s|}$ (the value $r$ will not be known to $\D$ at the beginning of the protocol).
The protocol allows the parties to let $\D$ verifiably generate a linear secret-sharing of $s$ with
IC-signatures, such that the underlying core-sets are  ${\GW}_1, \ldots, \GW_{|\Z_s|}$, where $s$ remains private for an honest $\D$.
The verifiability guarantees that even if $\D$ is corrupt, if any (honest) party computes an output, then there exists some value, say $s^{\star}$, which is linearly secret-shared with IC-signatures,
such that the underlying core-sets are ${\GW}_1, \ldots, \GW_{|\Z_s|}$.

The protocol idea is very simple and standard. We first let $\D$ reconstruct the value $r$, which is then used as a one-time pad (OTP) by $\D$ to make public an OTP-encryption of $s$.
Then, using the linearity property of secret-sharing, the parties locally remove the OTP from the OTP-encryption.

$\LSh(\D, s, \Z_s, \Z_a, \ShareSpec_{\Z_s}, [r], {\GW}_1, \ldots, {\GW}_{|\Z_s|})$VSS for verifiably generating a linear secret-sharing of a value with
IC-signatures with respect to given global core-setsfig:LSh

– Reconstructing the OTP Towards the Dealer: The parties in $\PartySet$ invoke an instance $\Rec([r], \{\D\})$ of $\Rec$ to let $\D$ reconstruct $r$
and  wait for time $\TimeRec$.

– Making the OTP-encryption Public: $\D$, upon computing the output $r$ from the instance of $\Rec$, broadcasts $\s = s + r$.

– Computing the Output: The parties in $\PartySet$  wait till the local time becomes
$\TimeRec + \TimeBC$. Then upon receiving $\s$ from the broadcast of $\D$, the parties in $\PartySet$
locally compute $[\s - r]$ from $[\s]$ and $[r]$. Here $[\s]$ denotes the default linear secret-sharing of $\s$ with IC-signatures and
core-sets ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$, where $[\s]_1 = \s$ and
$[\s]_2 = \ldots = [\s]_{|\Z_s|} = 0$, and where the parties set
$\ICSig(P_j, P_i, P_k, [\s]_q)_{P_j, P_i \in {\GW}_q, P_k \in \PartySet}$ to the default value.
The parties then output $({\GW}_1, \ldots, {\GW_{|\Z_s|}}, [\s - r])$.

The properties of the protocol $\LSh$ stated in Lemma <ref> are proved in Appendix <ref>.

Let $r$ be a random value which is linearly secret-shared with IC-signatures with ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets.
Then protocol $\LSh$ achieves the following where $\D$ participates with the input $s$.

– If $\D$ is honest, then the following hold, where $\TimeLSh = \TimeRec + \TimeBC$.

– $\Z_s$-Correctness: If the network is synchronous, then except with probability $\Order(n^3 \cdot \errorAICP)$, the honest parties output $[s]$ at the time $\TimeLSh$, with
${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets.

– $\Z_a$-Correctness: If the network is asynchronous, then except with probability $\Order(n^3 \cdot \errorAICP)$, the honest parties eventually
output $[s]$, with
${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets.

– Privacy: Irrespective of the network type, the view of the adversary remains independent of $s$.

– If $\D$ is corrupt then either no honest party computes any output or there exists some value, say $s^{\star}$, such that the following hold.

– $\Z_s$-Commitment: If the network is synchronous, then
except with probability $\Order(n^3 \cdot \errorAICP)$, the honest parties output $[s^{\star}]$, with
${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets. Moreover, if any honest party computes its output at the time $T$, then all honest parties will have their respective output by
the time $T + \Delta$.

– $\Z_a$-Commitment: If the network is asynchronous, then
except with probability $\Order(n^3 \cdot \errorAICP)$, the honest parties eventually output $[s^{\star}]$, with
${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets.

– Communication Complexity: $\Order(|\Z_s| \cdot n^3 \cdot \log{|\F|} + n^4 \cdot \log{|\F|} \cdot |\sigma|)$ bits are communicated by the honest parties.

We end this section with some notations which we use while invoking the protocol $\LSh$ in the rest of the paper.

[Notations for Using Protocol $\LSh$]

Let $P_i \in \PartySet$. In the rest of the paper we will say that “$P_i$ invokes an instance of $\LSh$ with input $s$" to mean that $P_i$ acts as $\D$ and invokes an instance
$\LSh(\D, s, \Z_s, \Z_a, \ShareSpec_{\Z_s}, [r], {\GW}_1, \ldots, {\GW}_{|\Z_s|})$ of $\LSh$. Here, $r$ will be the corresponding random “pad" for this instance of $\LSh$, which will already be linearly secret-shared
with IC-signatures, with ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets. If there are multiple instances of $\LSh$ invoked by $\D$, then corresponding to each instance, there will be a random secret-shared
pad available to the parties beforehand.  The parties will be knowing which secret-shared pad is associated with which instance of $\LSh$. This will be ensured by upper-bounding the maximum number of
$\LSh$ instances $\LMax$ invoked across all our protocols. The parties then generate $\LMax$ number of linearly secret-shared random values with IC-signatures,
with ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets, by running the protocol $\Rand$ beforehand with $L = \LMax$.

§.§ Non-Robust Multiplication Protocol

Protocol $\BasicMult$ (Fig <ref>) takes input $a$ and $b$, which are linearly secret-shared with IC-signatures, with ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets
and a publicly known subset $\Discarded \subset \PartySet$, consisting of only corrupt parties. The parties output a linear secret-sharing of $c$ with IC-signatures, with
${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets. If all the parties in
$\PartySet \setminus \Discarded$ behave honestly, then $c = a \cdot b$, else $c = a \cdot b + \delta$, where $\delta \neq 0$.
Moreover, the adversary does not learn anything additional about $a$ and $b$ in the protocol.
The protocol also takes input an iteration number $\iter$ and all the sets computed in the protocol are tagged with $\iter$.
Looking ahead, our robust triple-generation protocol will be executed iteratively, with each iteration invoking instances of $\BasicMult$.

A detailed overview of the protocol $\BasicMult$ has been already presented in Section <ref>. The idea is to let each summand $[a]_p \cdot [b]_q$ be linearly secret-shared
by exactly one summand-sharing party. A secret-sharing of $a \cdot b$ then follows from
the secret-sharing of each summand $[a]_p \cdot [b]_q$ owing to the linearity property of the secret-sharing.
To deal with the network agnostic condition, the summand-sharing parties are selected in two phases: first, we select them dynamically, without pre-assigning any summand to any
designated party. Once there exists a subset of parties from $\ShareSpec_{\Z_s}$ who have served the role of summand-sharing parties, we go to the second phase,
where each remaining summand is designated to the left-over parties through some publicly known assignment. Strict timeouts are maintained
to ensure that we don't stuck forever during the second phase.
Finally, if there are still any remaining summands which are not yet secret-shared, they are publicly reconstructed and the default sharing is taken on their behalf.
Throughout, the parties in $\Discarded$ are not let to secret-share any summand, since they are already known to be corrupt and at the same time, it is ensured that the shares
of the honest parties are never publicly reconstructed.

$\BasicMult(\Z_s, \Z_a, \ShareSpec_{\Z_s}, [a], [b], {\GW}_1, \ldots, {\GW}_{|\Z_s|}, \Discarded, \iter)$Network-agnostic non-robust multiplication protocolfig:BasicMult

– Initialization: The parties in $\PartySet$ do the following.

* Initialize the summand-index-set of indices of all summands:

\[\Products_\iter = \{(p, q)\}_{p, q = 1, \ldots, |\SharingSpec_{\Z_s}|}.\]

* Initialize the summand-index-set corresponding to each $P_j \in \PartySet \setminus \Discarded$:

\[\Products^{(j)}_\iter = \{(p, q)\}_{P_j \in S_p \cap S_q}. \]

* Initialize the summand-index-set corresponding to each $S_q \in \ShareSpec_{\Z_s}$:

\[\Products^{(S_q)}_\iter = \displaystyle \cup_{P_j \in S_q} \Products^{(j)}_\iter.\]

* Initialize the set of summands-sharing parties:

\[\Selected_\iter = \emptyset.\]

* Initialize the hop number:

\[\hop = 1.\]

Phase I: Sharing Summands Through Dynamic Assignment

– While there exists no $S_q \in \ShareSpec_{\Z_s}$, where $\Products^{(S_q)}_\iter  = \emptyset$, the parties do the following:

* Sharing Sum of Eligible Summands: Every $P_i \notin (\Selected_\iter \cup \Discarded)$ invokes an instance $\LSh^{(\phaseone, \hop, i)}$ of $\LSh$
with input $c^{(i)}_\iter$, where

\[ \displaystyle c^{(i)}_\iter = \sum_{(p, q) \in \Products^{(i)}_\iter} [a]_p[b]_q.\]

Corresponding to every $P_j \notin (\Selected_\iter \cup \Discarded)$, the parties in $\PartySet$ participate in the instance $\LSh^{(\phaseone, \hop, j)}$, if invoked by $P_j$.

* Selecting Summand-Sharing Party for the Hop Through ACS: The parties in $\PartySet$  wait for time $\TimeLSh$ and then do the following.

– For $j = 1, \ldots, n$, participate in an instance $\BA^{(\phaseone,\hop,j)}$ of $\BA$
corresponding to $P_j \in \PartySet$ with input $1$ if all the following hold:

– $P_j \notin (\Selected_\iter \cup \Discarded)$;

– An output $[c^{(j)}_\iter]$ is computed during the instance $\LSh^{(\phaseone,\hop,j)}$.

– Upon computing an output $1$ during the instance
$\BA^{(\phaseone,\hop,j)}$ corresponding to some $P_j \in \PartySet$, participate with input $0$
in the instances $\BA^{(\phaseone, \hop, k)}$ corresponding to parties $P_k \notin (\Selected_\iter \cup \Discarded)$, for which no input has been provided yet.

– Upon computing outputs during the instances  $\BA^{(\phaseone,\hop, i)}$ corresponding to each $P_i \notin (\Selected_\iter \cup \Discarded)$,
let $P_j$ be the least-indexed party, such that the output $1$ is computed during the instance $\BA^{(\phaseone, \hop, j)}$. Then update the following.

– $\Selected_\iter = \Selected_\iter \cup \{P_j\}$.

– $\Products_\iter = \Products_\iter \setminus \Products^{(j)}_\iter$.

– $\forall P_k \in \PartySet \setminus \{\Discarded \cup \Selected_\iter \}$:
$\Products^{(k)}_\iter = \Products^{(k)}_\iter \setminus \Products^{(j)}_\iter$.

– For each $S_q \in \ShareSpec_{\Z_s}$, $\Products^{(S_q)}_\iter = \Products^{(S_q)}_\iter \setminus \Products^{(j)}_\iter$.

– Set $\hop = \hop + 1$.

Phase II: Sharing Remaining Summands Through Static Assignment

* Re-assigning the Summand-Index-Set of Each Party: Corresponding to each $P_j \in \PartySet \setminus \Selected_\iter$,  the parties in $\PartySet$
set $\Products^{(j)}_\iter$ as

\[ \Products^{(j)}_\iter = \displaystyle \Products_\iter \cap \{(p, q)\}_{P_j = \min(S_p \cap S_q)}, \]

where $\min(S_p \cap S_q)$ denotes the minimum indexed party in $(S_p \cap S_q)$.

* Sharing Sum of Assigned Summands: Every party $P_i \notin (\Selected_\iter \cup \Discarded)$
invokes an instance $\LSh^{(\phasetwo, i)}$ of $\LSh$ with input $c^{(i)}_\iter$, where

\[ \displaystyle c^{(i)}_\iter = \sum_{(p, q) \in \Products^{(i)}_\iter} [a]_p[b]_q.\]

Corresponding to every $P_j \in \PartySet \setminus (\Selected_\iter \cup \Discarded)$,
the parties in $\PartySet$ participate in the instance $\LSh^{(\phasetwo, j)}$, if invoked by $P_j$.

* Agreeing on the Summand-Sharing parties of the Second Phase: The parties in $\PartySet$
wait for $\TimeLSh$ time after the beginning of the second phase.
Then for each $P_j \in \PartySet$, participate in an instance $\BA^{(\phasetwo, j)}$ of $\BA$ with input $1$, if all the following hold, otherwise
participate with input $0$.

– $P_j \notin (\Selected_\iter \cup \Discarded)$;

– An output $[c^{(j)}_\iter]$ is computed during the instance $\LSh^{(\phasetwo,j)}$.

* Updating the Sets for the Second Phase: Corresponding to each $P_j \notin (\Selected_\iter \cup \Discarded)$, such that $1$ is computed as the output during
$\BA^{(\phasetwo,j)}$, update

– $\Products_\iter = \Products_\iter \setminus \Products^{(j)}_\iter$;

– $\Selected_\iter = \Selected_\iter \cup \{P_j\}$.

Phase III: Reconstructing the Remaining Summands

* Reconstructing the Remaining Summands and Taking the Default Sharing: The parties in $\PartySet$ do the following.

– Corresponding to each $[a]_p$ such that $(p, \star) \in \Products_\iter$, participate in the instance
$\RecShare([a], S_p, \PartySet)$ of $\RecShare$ to publicly reconstruct $[a]_p$

– Corresponding to each $[b]_q$ such that $(\star, q) \in \Products_\iter$, participate in the instance
$\RecShare([b], S_q, \PartySet)$ of $\RecShare$ to publicly reconstruct $[b]_q$.

– Corresponding to every $P_j \in \PartySet \setminus \Selected_\iter$, take the default linear secret-sharing of
the public input $c^{(j)}_\iter$ with IC-signatures and core-sets ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$,
where[The default linear secret-sharing of $c^{(j)}_\iter$ is computed in a similar way as done in the protocol
$\Rand$ for $\s$ (see Fig <ref>).]

\[ \displaystyle c^{(j)}_\iter = \sum_{(p, q) \in \Products^{(j)}_\iter} [a]_p[b]_q.\]

* Output Computation:  The parties output
$({\GW}_1, \ldots, {\GW}_{|\Z_s|},  [c^{(1)}_\iter], \ldots, [c^{(n)}_\iter], \allowbreak [c_\iter])$, where $c_\iter \defined c^{(1)}_\iter + \ldots + c^{(n)}_\iter$.

The properties of the protocol $\BasicMult$ are claimed in the following lemmas, which are proved in Appendix <ref>.

During any instance $\BasicMult(\Z_s, \Z_a, \ShareSpec_{\Z_s}, [a], [b], {\GW}_1, \ldots, \allowbreak {\GW}_{|\Z_s|}, \Discarded, \iter)$ of $\BasicMult$,
if $P_j \in \Selected_{\iter}$ then $P_j \not \in \Discarded$, irrespective of the network type.

Suppose that no honest party is present in $\Discarded$. If the honest parties start participating during hop number $\hop$ of Phase I of $\BasicMult$ with iteration number $\iter$,
then except with probability $\Order(n^3 \cdot \errorAICP)$,
the hop takes $\TimeLSh + 2\TimeBA$ time to complete in a synchronous network, or almost-surely completes eventually in an asynchronous network.

If no honest party is present in $\Discarded$, then in protocol $\BasicMult$, except with probability $\Order(n^3 \cdot \errorAICP)$,
all honest parties compute some output by the time $\TimeBasicMult = (2n + 1) \cdot \TimeBA + (n + 1) \cdot \TimeLSh + \TimeRec$ in a synchronous network, or almost-surely,
eventually in an asynchronous network.

If no honest party is present in $\Discarded$, then the view of the adversary remains independent of $a$ and $b$ throughout the protocol, irrespective of the network type.

If no honest party is present in $\Discarded$ and if all parties in $\PartySet \setminus \Discarded$ behave honestly, then in protocol $\BasicMult$, the honest parties output
a linear secret-sharing of $a \cdot b$ with IC-signatures, with ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets, irrespective of the network type.

Protocol $\BasicMult$ incurs a communication of $\Order(|\Z_s| \cdot n^5 \cdot \log{|\F|} + n^6 \cdot \log{|\F|} \cdot |\sigma|)$
bits and makes $\Order(n^2)$ calls to $\BA$.

As a corollary of Lemma <ref>, we can derive the following corollary, which determines the maximum number of instances of $\LSh$ which are invoked during an instance
of $\BasicMult$. Looking ahead, this will be useful to later calculate the maximum number of instances of $\LSh$ which need to be invoked as part of our final multiplication protocol.
This will be further useful to determine the number of linearly secret-shared values with IC-signatures and core-sets ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$, which need to be generated through the
protocol $\Rand$ beforehand.

During any instance of $\BasicMult$, there can be at most $n^2 + n$ instances of $\LSh$ invoked.

Protocol $\BasicMult$ for $L$ Pairs of Inputs.

Protocol $\BasicMult$ can be easily generalized, if there are $L$ pairs of inputs $\{(a^{\ell}, b^{\ell}) \}_{\ell = 1, \ldots, L}$, all of which are linearly secret-shared with IC-signatures, with
${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets. However, with a slight modification during Phase I and Phase II, we can ensure that the number of instances of $\BA$ remain only
$\Order(n^2)$, which is independent of $L$. Consider Phase I. During hop number $\hop$, every party $P_i \not \in (\Selected_\iter \cup \Discarded)$ invokes $L$ instances of $\LSh$ to linearly secret-share
$L$ candidate summand-sums. Now while selecting the summand-sharing party through ACS for this hop, the parties vote for a candidate $P_j \not \in (\Selected_\iter \cup \Discarded)$, provided an output is computed in
all the $L$ instances of $\LSh$ invoked by $P_j$. Consequently, the number of instances of $\BA$ during Phase I will be $\Order(n^2)$.
Similarly during Phase II, each party outside $(\Selected_\iter \cup \Discarded)$ invokes $L$ instances of $\LSh$ to linearly secret-share $L$ candidate re-assigned summand-sums. And then the parties vote for a
candidate $P_j$ as a summand-sharing party, if an output is computed in all the $L$ instances of $\LSh$ invoked by $P_j$.
Finally, during Phase III, the default linear secret-sharing with IC-signatures is taken for the sum of all the summands, which are not yet secret-shared by any party, by making public all these summands.
The resultant protocol incurs a communication of $\Order(|\Z_s|^3 \cdot n^4 \cdot L \cdot \log{|\F|} + |\Z_s| \cdot n^5 \cdot L \cdot \log{|\F|} + n^6 \cdot L \cdot \log{|\F|} \cdot |\sigma|)$
bits and makes $\Order(n^2)$ calls to $\BA$. We also note that there will be at most $n^2 \cdot L + n \cdot L$ instances of $\LSh$ invoked in the generalized protocol.
To avoid repetition, we do not present the steps of the generalized protocol here.

§.§ Network Agnostic Random Triple Generation with Cheater Identification

The network-agnostic protocol $\RandMultCI$ (Fig <ref>) takes an iteration number $\iter$ and a publicly known subset of parties $\Discarded$, who
are guaranteed to be corrupt. If all the parties in $\PartySet \setminus \Discarded$
behave honestly, then the protocol outputs a random linearly secret-shared multiplication-triple with IC-signatures, with
${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core sets.
Otherwise, with a high probability, the honest parties identify a new corrupt party, which is added to $\Discarded$.

Protocol $\RandMultCI$ is based on [40] and
consists of two stages: during the first stage, the parties jointly generate a pair of random values, which are
linearly secret-shared with IC-signatures, with ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core sets.
During the second stage, the parties run an instance of $\BasicMult$ to compute the product of the pair of secret-shared random values from the first stage.
To check whether any cheating has occurred during the instance of $\BasicMult$, the parties then run a probabilistic test, namely
the “sacrificing trick" [27],
for which the parties need additional secret-shared random values, which
are generated during the first stage itself.

$\RandMultCI(\PartySet, \Z_s, \Z_a, \ShareSpec_{\Z_s}, {\GW}_1, \ldots, {\GW}_{|\Z_s|}, \Discarded, \iter)$ Network-agnostic protocol for generating secret-shared random multiplication-triple with cheater

– Generating Linear Secret Sharing of Random Values with IC-signatures: Each $P_i \in \PartySet$ does the following.

–  Invoke instances of $\LSh$ with randomly chosen inputs $a^{(i)}_\iter, b^{(i)}_\iter, b'^{(i)}_\iter, r^{(i)}_\iter \in \F$.

– Corresponding to every $P_j \in \PartySet$, participate in the instances of $\LSh$ invoked by $P_j$ (if any)
and  wait for time $\TimeLSh$.
Initialize a set $\CSet_i = \emptyset$  after local time $\TimeLSh$ and include $P_j$ in
$\CSet_i$, if any output is computed in all the instances of $\LSh$ invoked by $P_j$.

– Corresponding to every $P_j \in \PartySet$,
participate in an instance of $\BA^{(j)}$ of $\BA$ with input $1$, if $P_j \in \CSet_i$.

– Once $1$ has been computed as the output from instances of $\BA$ corresponding to a set of parties
in $\PartySet \setminus Z$ for some $Z \in \Z_s$, participate
with input $0$ in all the $\BA$ instances $\BA^{(j)}$, such that
$P_j \not \in \CSet_i$.

– Once a binary output is computed in all the instances of $\BA$ corresponding to the parties in $\PartySet$,
compute $\CoreSet$, which is the set of parties $P_j \in \PartySet$, such that
$1$ is computed as the output in the instance $\BA^{(j)}$.

Once $\CoreSet$ is computed, the parties in $\PartySet$ locally compute $[a_\iter], [b_\iter], [b'_\iter]$ and $[r_\iter]$ from
$\{[a^{(j)}_\iter] \}_{P_j \in \CoreSet}, \{[b^{(j)}_\iter] \}_{P_j \in \CoreSet}, \{[b'^{(j)}_\iter] \}_{P_j \in \CoreSet}$ and $\{[r^{(j)}_\iter] \}_{P_j \in \CoreSet}$ respectively as follows:

\[ [a_\iter] = \displaystyle \sum_{P_j \in \CoreSet} [a^{(j)}_\iter], \;  [b_\iter] = \displaystyle \sum_{P_j \in \CoreSet} [b^{(j)}_\iter],  \;
[b'_\iter] = \displaystyle \sum_{P_j \in \CoreSet} [b'^{(j)}_\iter], \;
[r_\iter] = \displaystyle \sum_{P_j \in \CoreSet} [r^{(j)}_\iter].\]

– Computing Secret-Shared Products: The parties in $\PartySet$ do the following.

– Participate in instances $\BasicMult(\Z_s, \Z_a, \ShareSpec_{\Z_s}, [a_\iter], [b_\iter], {\GW}_1, \ldots, {\GW}_{|\Z_s|}, \allowbreak \Discarded, \iter)$
and $\BasicMult(\Z_s, \Z_a, \ShareSpec_{\Z_s}, [a], [b'_\iter], {\GW}_1, \ldots, {\GW}_{|\Z_s|}, \Discarded, \iter)$ of $\BasicMult$
to compute the outputs $({\GW}_1, \ldots, {\GW}_{|\Z_s|}, [c^{(1)}_\iter] , \ldots, [c^{(n)}_\iter], [c_\iter])$ and
$({\GW}_1, \ldots, {\GW}_{|\Z_s|}, [c'^{(1)}_\iter] , \ldots, [c'^{(n)}_\iter], [c'_\iter])$ respectively.
Let $\Selected_{\iter, c}$ and $\Selected_{\iter, c'}$ be the summand-sharing parties for the two instances respectively.
Moreover, for each $P_j \in \Selected_{\iter, c}$, let $\Products^{(j)}_{\iter, c}$
be the set of ordered pairs of indices corresponding to the summands whose sum has been shared by $P_j$
during the instance $\BasicMult(\Z_s, \Z_a, \ShareSpec_{\Z_s}, [a_\iter], [b_\iter], {\GW}_1, \ldots, {\GW}_{|\Z_s|}, \Discarded, \iter)$.
And similarly,  for each $P_j \in \Selected_{\iter, c'}$, let $\Products^{(j)}_{\iter, c'}$
be the set of ordered pairs of indices corresponding to the summands whose sum has been shared by $P_j$
during the instance $\BasicMult(\Z_s, \Z_a, \ShareSpec_{\Z_s}, [a], [b'_\iter], {\GW}_1, \ldots, {\GW}_{|\Z_s|}, \Discarded, \iter)$.

– Error Detection in the Instances of $\BasicMult$: The parties in $\PartySet$ do the following.

– Upon computing outputs from the instances of $\BasicMult$, participate in an instance $\Rec([r_\iter], \PartySet)$ of $\Rec$ to publicly reconstruct $r_\iter$.

– Locally compute $[e_{\iter}] \defined r_\iter[b_\iter] + [b'_\iter]$ from $[b_\iter]$ and $[b'_\iter]$. Participate in an instance $\Rec([e_\iter], \PartySet)$ of $\Rec$
to publicly reconstruct $e_\iter$.

– Locally compute $[d_{\iter}] \defined e_\iter [a_\iter] - r_\iter [c_\iter] - [c'_\iter]$ from $[a_\iter], [c_\iter]$ and $[c'_\iter]$.
Participate in an instance $\Rec([d_\iter], \PartySet)$ of $\Rec$ to publicly reconstruct $d_\iter$.

– Output Computation in Case of Success:
If $d_\iter = 0$, then set the boolean variable $\flag_\iter=0$ and output ${({\GW}_1, \ldots, {\GW}_{|\Z_s|}, [a_\iter], [b_\iter], [c_\iter])}$.

– Cheater Identification in Case of Failure: If $d_\iter \neq 0$, then set the boolean variable
$\flag_\iter = 1$ and proceed as follows.

– For each $S_q \in \ShareSpec_{\Z_s}$, participate in instances $\RecShare([a_\iter], S_q, \allowbreak \PartySet), \RecShare([b_\iter], S_q, \PartySet)$ and
$\RecShare([b'_\iter], S_q, \PartySet)$
of $\RecShare$ to publicly reconstruct the shares $\{ [a_\iter]_q, [b_\iter]_q, [b'_\iter]_q\}_{S_q \in \ShareSpec_{\Z_s}}$.
In addition, for $i = 1, \ldots, n$, participate in instances $\Rec(c^{(i)}_\iter, \PartySet)$ and $\Rec(c'^{(i)}_\iter, \PartySet)$ to publicly reconstruct $c^{(i)}_\iter$ and $c'^{(i)}_\iter$.

* Set $\displaystyle \Discarded = \Discarded \cup \{P_j\}$, if $P_j \in \Selected_{\iter, c} \cup \Selected_{\iter, c'}$
and the following holds for $P_j$:

\[ \displaystyle r_{\iter} \cdot c^{(j)}_\iter + c'^{(j)}_\iter \neq r_{\iter} \cdot \sum_{(p, q) \in \Products^{(j)}_{\iter, c}} [a_\iter]_p[b_\iter]_q
+ \sum_{(p, q) \in \Products^{(j)}_{\iter, c'}}[a_\iter]_p [b'_\iter]_q.  \]

The properties of the protocol $\RandMultCI$ are claimed in the following lemmas, which are proved in Appendix <ref>.

In protocol $\RandMultCI$, the following hold.

– Synchronous Network: Except with probability $\Order(n^3 \cdot \errorAICP)$, honest parties will have linearly secret-shared $a_\iter, b_\iter, b'_\iter$
and $r_\iter$ with IC-signatures, with ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets, by the time $\TimeLSh + 2\TimeBA$. Moreover, adversary's view is independent of
$a_\iter, b_\iter, b'_\iter$ and $r_\iter$.

– Asynchronous Network: Except with probability $\Order(n^3 \cdot \errorAICP)$, almost-surely, honest parties will eventually have linearly secret-shared $a_\iter, b_\iter, b'_\iter$
and $r_\iter$ with IC-signatures, with ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets. Moreover, adversary's view is independent of
$a_\iter, b_\iter, b'_\iter$ and $r_\iter$.

Consider an arbitrary $\iter$,
such that all honest parties participate in the instance $\RandMultCI(\PartySet, \Z_s, \Z_a, \ShareSpec_{\Z_s}, {\GW}_1, \ldots, {\GW}_{|\Z_s|}, \Discarded, \iter)$,
no honest party is present in $\Discarded$.
Then except with probability $\Order(n^3 \cdot \errorAICP)$, all honest parties
reconstruct a (common) value $d_\iter$ and set $\flag_\iter$ to a common Boolean value,
at the time $\TimeLSh + 2\TimeBA + \TimeBasicMult + 3\TimeRec$ in a synchronous network, or eventually in an asynchronous network.

Consider an arbitrary $\iter$,
such that all honest parties participate in the instance $\RandMultCI(\PartySet, \Z_s, \Z_a, \ShareSpec_{\Z_s}, {\GW}_1, \ldots, {\GW}_{|\Z_s|}, \Discarded, \iter)$,
no honest party is present in $\Discarded$.
If no party in $\PartySet \setminus \Discarded$ behaves maliciously, then $d_\iter = 0$
the honest parties output $([a_\iter], [b_\iter], [c_\iter])$
at the time $ \TimeLSh + 2\TimeBA + \TimeBasicMult + 3\TimeRec$ in a synchronous network or eventually in an asynchronous network, where $c_\iter = a_\iter \cdot b_\iter$
and where ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ are
the underlying core-sets

Consider an arbitrary $\iter$,
such that all honest parties participate in the instance $\RandMultCI(\PartySet, \Z_s, \Z_a, \ShareSpec_{\Z_s}, {\GW}_1, \ldots, {\GW}_{|\Z_s|}, \Discarded, \iter)$,
no honest party is present in $\Discarded$.
If $d_\iter \neq 0$, then except with probability $\Order(n^3 \cdot \errorAICP)$,
the honest parties update $\Discarded$ by adding a new maliciously-corrupt
party in $\Discarded$, either at the time $\TimeRandMultCI = \TimeLSh + 2\TimeBA + \TimeBasicMult + 4\TimeRec$ in a synchronous network or eventually in an asynchronous network.

Consider an arbitrary $\iter$,
such that all honest parties participate in the instance $\RandMultCI(\PartySet, \Z_s, \Z_a, \ShareSpec_{\Z_s}, {\GW}_1, \ldots, {\GW}_{|\Z_s|}, \Discarded, \iter)$,
no honest party is present in $\Discarded$.
If $d_\iter = 0$, then the honest parties output linearly secret-shared
$(a_\iter, b_\iter, c_\iter)$ with IC-signatures with ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being
the underlying core-sets,
at the time $\TimeLSh + 2\TimeBA + \TimeBasicMult + 3\TimeRec$ in a synchronous network or eventually in an asynchronous network where,
except with probability  $\frac{1}{|\F|}$, the condition $c_\iter = a_\iter \cdot b_\iter$ holds.
Moreover, the view of $\Adv$ will be independent of $(a_\iter, b_\iter, c_\iter)$.

Protocol $\RandMultCI$ incurs a communication of $\Order(|\Z_s| \cdot n^5 \cdot \log{|\F|} + n^6 \cdot \log{|\F|} \cdot |\sigma|)$
bits and makes $\Order(n^2)$ calls to $\BA$.

Protocol $\RandMultCI$ for $L$ Triples.

Protocol $\RandMultCI$ can be easily generalized to generate $L$ triples with cheater identification, such that the number of instances of $\BA$ is independent of $L$.
To begin with, every party $P_i$ now picks $3L + 1$ random values $(r_\iter^{(i)}, \{a_\iter^{(\ell, i)}, b_\iter^{(\ell, i)}, {b'}_\iter^{(\ell, i)} \}_{\ell = 1, \ldots, L})$
and invokes $3L + 1$ instances of $\LSh$ to generate linear secret-sharing of these values with IC-signatures, with
${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets. Next, to determine $\CoreSet$, the parties invoke only $n$ instances of $\BA$, where the $j^{th}$ instance is used
to decide whether $P_j$ should be included in $\CoreSet$, the criteria being whether some output is computed in all the $3L + 1$ instances of $\LSh$ invoked by $P_j$.
Once $\CoreSet$ is decided, the parties locally compute $\{ [a_\iter^{(\ell)}] \}_{\ell = 1, \ldots, L}$, $\{ [b_\iter^{(\ell)}] \}_{\ell = 1, \ldots, L}$, $\{ [{b'}_\iter^{(\ell)}] \}_{\ell = 1, \ldots, L}$
and $[r_\iter]$ from $\{ [a_\iter^{(\ell, j)}] \}_{P_j \in \CoreSet, \ell = 1, \ldots, L}$, $\{ [b_\iter^{(\ell, j)}] \}_{P_j \in \CoreSet, \ell = 1, \ldots, L}$,
$\{ [{b'}_\iter^{(\ell, j)}] \}_{P_j \in \CoreSet, \ell = 1, \ldots, L}$ and $\{ [r_\iter^{(j)}] \}_{P_j \in \CoreSet}$ respectively.
The parties then invoke two instances of (generalized) $\BasicMult$ protocol with $L$ pairs of secret-shared inputs to compute
$\{ [c_\iter^{(\ell)}] \}_{\ell = 1, \ldots, L}$ and $\{ [{c'}_\iter^{(\ell)}] \}_{\ell = 1, \ldots, L}$ respectively. Note that this requires only $\Order(n^2)$ instances of $\BA$, apart from $n^2 \cdot L + n \cdot L$
instances of $\LSh$. The rest of the protocol steps are then generalized to deal with $L$ inputs.
The resultant protocol incurs a communication of
$\Order(|\Z_s| \cdot n^5 \cdot L \cdot \log{|\F|} + n^6 \cdot L \cdot \log{|\F|} \cdot |\sigma|)$
bits and makes $\Order(n^2)$ calls to $\BA$. We also note that there will be at most $n^2 \cdot L + 4n \cdot L + n$ instances of $\LSh$ invoked overall in the generalized protocol.
To avoid repetition, we do not present the steps of the generalized protocol here.

§.§ The Multiplication-Triple Generation Protocol

Protocol $\TripGen$ for generating a single secret-shared multiplication-triple is presented in Fig <ref>. The idea of the protocol is very simple and based on [40].
The parties iteratively run instances of $\RandMultCI$, till they hit upon an instance when no cheating is detected.
Corresponding to each “failed" instance of $\RandMultCI$, the parties keep updating the set $\Discarded$. Since after each failed instance the set $\Discarded$ is updated with
one new corrupt party, there will be at most $(t + 1)$ iterations, where $t$ is the cardinality of the largest-sized subset in $\Z_s$.

$\TripGen(\PartySet, \Z_s, \Z_a, \ShareSpec_{\Z_s}, {\GW}_1, \ldots, {\GW}_{|\Z_s|})$Network-agnostic protocol to generate a linear
secret sharing with IC-signature of a single random multiplication-triple.fig:TripGen

– Initialization: The parties in $\PartySet$ initialize $\Discarded = \emptyset$ and $\iter = 1$.

– Triple Generation with Cheater Identification: The parties in $\PartySet$ participate in an instance
$\RandMultCI(\PartySet, \Z_s, \Z_a, \ShareSpec_{\Z_s}, {\GW}_1, \ldots, {\GW}_{|\Z_s|}, \Discarded, \iter)$ of $\RandMultCI$ and wait for its completion.
Upon computing output from the instance, the parties proceed as follows.

* Positive Output: If the Boolean variable $\flag_\iter$ is set to $0$ during the instance of
$\RandMultCI$, then
output ${({\GW}_1, \allowbreak \ldots,  {\GW}_{|\Z_s|}, [a_\iter], [b_\iter], [c_\iter])}$, computed during the instance of $\RandMultCI$.

* Negative Output: Else set $\iter = \iter+1$ and go to the step labelled Triple Generation with Cheater Identification.

The properties of the protocol $\TripGen$ are claimed in the following lemmas, which are proved in Appendix <ref>.

Let $t$ be the size of the largest set in $\Z_s$. Then except with probability $\Order(n^3 \cdot \errorAICP)$, the honest parties compute an output during
$\TripGen$, by the time $\TimeTripGen = (t + 1) \cdot \TimeRandMultCI$ in a synchronous network, or almost-surely, eventually in an asynchronous network, where
$\TimeRandMultCI = \TimeLSh + 2\TimeBA + \TimeBasicMult + 4\TimeRec$.

If the honest parties output ${({\GW}_1,  \ldots,  {\GW}_{|\Z_s|}, [a_\iter], [b_\iter], [c_\iter])}$ during the protocol $\TripGen$,
then $a_\iter, b_\iter$ and $c_\iter$ are linearly secret-shared with IC-signatures, with
${\GW}_1,  \ldots,  {\GW}_{|\Z_s|}$ being the underlying core-sets. Moreover, $c_\iter = a_\iter b_\iter$ holds, except with probability $\frac{1}{|\F|}$.
Furthermore, the view of the adversary remains independent of $a_\iter, b_\iter$ and $c_\iter$.

Protocol $\TripGen$ incurs a communication of $\Order(|\Z_s| \cdot n^6 \cdot \log{|\F|} + n^7 \cdot \log{|\F|} \cdot |\sigma|)$
bits and makes $\Order(n^3)$ calls to $\BA$.

Protocol $\TripGen$ for Generating $L$ Multiplication-Triples.

To generate $L$ multiplication-triples, the parties now need to invoke an instance of the generalized (modified) $\RandMultCI$ protocol in each iteration,
which generates $L$ triples with cheater identification.
The rest of the protocol steps remain the same. To avoid repetition, we do not present the formal details here.
The protocol incurs a communication of $\Order(|\Z_s| \cdot n^6 \cdot L \cdot \log{|\F|} + n^7 \cdot L \cdot \log{|\F|} \cdot |\sigma|)$
bits and makes $\Order(n^3)$ calls to $\BA$.

On the Maximum Number of Calls of $\LSh$ in $\TripGen$.

As discussed in the previous section, each instance of $\RandMultCI$ for $L$ triples requires at most
$n^2 \cdot L + 4n \cdot L + n$ instances of $\LSh$. Now as there can be up to $t + 1 \approx n$ such instances of $\RandMultCI$ in the protocol $\TripGen$, it follows that
at most $n^3 \cdot L + 4n^2 \cdot L + n^2$ instances of $\LSh$ are invoked in the protocol $\TripGen$ for generating $L$ multiplication-triples.

§ NETWORK AGNOSTIC CIRCUIT-EVALUATIONPROTOCOL

The network-agnostic circuit-evaluation protocol $\PiMPC$ is presented in Fig <ref>.
The idea behind the protocol is to perform shared circuit-evaluation, where each value remains linearly secret-shared with IC-signatures and common core-sets
Once the function-output is secret-shared, it is publicly reconstructed. To achieve this goal, the parties first secret-share their respective inputs for the function $f$ through instances of $\LSh$.
The parties then agree on a common subset of parties $\CoreSet$, where $\PartySet \setminus \CoreSet \in \Z_s$, such that the inputs of the parties in $\CoreSet$ are linearly secret-shared
with IC-signatures. If the network is synchronous then it will be ensured that all honest parties are present in $\CoreSet$
and hence the inputs of all honest parties are considered for the circuit-evaluation.
The linearity of secret-sharing ensures that the linear gates in $\ckt$ are evaluated non-interactively, while Beaver's trick is deployed for evaluating multiplication gates in $\ckt$.
For the latter, the parties need to have $c_M$ number of random multiplication-triples apriori, which are linearly secret-shared with IC-signatures.
This is achieved by apriori calling the protocol $\TripGen$ with $L = c_M$, which in turn will require at most $n^3 \cdot c_M + 4n^2 \cdot c_M + n^2$ number of instances of $\LSh$.
As the total number of instances of $\LSh$ across $\TripGen$ and the input-phase is at most $n^3 \cdot c_M + 4n^2 \cdot c_M + n^2 + n$,
the parties first invoke an instance of $\Rand$
by setting $L = n^3 \cdot c_M + 4n^2 \cdot c_M + n^2 + n$, to generate
these many linearly secret-shared random values with IC-signatures, with ${\GW}_1,  \ldots,  {\GW}_{|\Z_s|}$ being the underlying core-sets.
This will ensure that all the values during the circuit-evaluation are linearly secret-shared with IC-signatures, with ${\GW}_1,  \ldots,  {\GW}_{|\Z_s|}$ being the underlying core-sets.

Notice that if the network is asynchronous then different parties may be in the different phases of the protocol. And consequently, a party upon reconstructing the function output cannot
afford to immediately terminate, as its presence may be required in the other parts of the protocol. Hence there is also a termination phase, which is executed concurrently, where the parties check if
it is “safe" to terminate the protocol.

$\PiMPC(\PartySet, \Z_s, \Z_a, \ShareSpec_{\Z_s}, \ckt, c_M)$Network agnostic secure circuit-evaluation protocol.fig:MPC

Pre-Processing Phase

– Generating Linearly Secret-Shared Random Values with IC-signatures: The parties invoke an instance $\Rand(\PartySet, \Z_s, \Z_a, \SharingSpec_{\Z_s}, L)$
where $L = n^3 \cdot c_M + 4n^2 \cdot c_M + n^2 + n$
and compute output
$({\GW}_1, \ldots, {\GW}_{|\Z_s|}, \{[r^{(\mathfrak{l})}] \}_{\mathfrak{l} = 1, \ldots, L})$

– Generating Linearly Secret-Shared Random Multiplication-Triples with IC-signatures:
Upon computing an output in the instance of $\Rand$,
the parties invoke an instance
$\TripGen(\PartySet, \Z_s, \Z_a, \ShareSpec_{\Z_s}, {\GW}_1, \ldots, {\GW}_{|\Z_s|})$ with $L = c_M$
and compute output ${({\GW}_1, \ldots,  {\GW}_{|\Z_s|}, \{[a^{(\ell)}], [b^{(\ell)}], [c^{(\ell)}]\}_{\ell = 1, \ldots, c_M})}$.
During the instance of $\TripGen$, the secret-shared values $\{[r^{(\mathfrak{l})}] \}_{\mathfrak{l} = 1, \ldots, n^3 \cdot c_M + 4n^2 \cdot c_M + n^2}$
are used as the corresponding pads in the underlying instances of $\LSh$, invoked as part of $\TripGen$.

Input Phase

Upon computing an output during the instance of $\TripGen$, each $P_i \in \PartySet$ does the following.

–  On having the input $x^{(i)}$, invoke an instance of $\LSh$ with input
$x^{(i)}$.[ The secret-shared random value
$r^{(n^3 \cdot c_M + 4n^2 \cdot c_M + n^2 + j)}$ serves as the pad for the instance of $\LSh$ invoked by $P_j$ in this phase.]

– Corresponding to every $P_j \in \PartySet$, participate in the instance of $\LSh$ invoked by $P_j$
and  wait for local time $\TimeLSh$ after starting the input phase. Then
initialize a set $\CSet_i = \emptyset$ and include $P_j$ in
$\CSet_i$, if any output is computed in the instance of $\LSh$ invoked by $P_j$.

– Corresponding to every $P_j \in \PartySet$,
participate in an instance of $\BA^{(j)}$ of $\BA$ with input $1$, if $P_j \in \CSet_i$.

– Once $1$ has been computed as the output from instances of $\BA$ corresponding to a set of parties
in $\PartySet \setminus Z$ for some $Z \in \Z_s$, participate
with input $0$ in all the $\BA$ instances $\BA^{(j)}$, such that
$P_j \not \in \CSet_i$.

– Once a binary output is computed in all the instances of $\BA$ corresponding to the parties in $\PartySet$,
compute $\CoreSet$, which is the set of parties $P_j \in \PartySet$, such that
$1$ is computed as the output in the instance $\BA^{(j)}$.

Once $\CoreSet$ is computed, corresponding to every $P_j \not \in \CoreSet$, the parties set $x^{(j)} = 0$ and  take the default
linear secret-sharing of $0$ with IC-signatures, with ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets.

Circuit-Evaluation Phase

– Evaluate each gate $g$ in the circuit
according to the topological ordering as follows, depending upon the type.

– Addition Gate: If $g$ is an addition gate with inputs $x, y$ and output $z$, then the parties in $\PartySet$ locally compute $[z] = [x + y]$ from $[x]$ and $[y]$.

– Multiplication Gate: If $g$ is the $\ell^{th}$ multiplication gate with inputs $x, y$ and output $z$, where $\ell \in \{1, \ldots, M \}$, then
the parties in $\PartySet$ do the following:

– Locally compute $[d^{(\ell)}] = [x - a^{(\ell)}]$ from $[x]$ and $[a^{(\ell)}]$ and
$[e^{(\ell)}] = [y - b^{(\ell)}]$ from $[y]$ and $[b^{(\ell)}]$.

– Participate in instances $\Rec([d^{(\ell)}], \PartySet)$ and $\Rec([e^{(\ell)}], \PartySet)$ of $\Rec$
to publicly reconstruct
$d^{(\ell)}$ and $e^{(\ell)}$, where $d^{(\ell)} \defined x - a^{(\ell)}$ and $e^{(\ell)} \defined y - b^{(\ell)}$.

– Upon reconstructing $d^{(\ell)}$ and $e^{(\ell)}$,  take the default linear secret-sharing of $d^{(\ell)} \cdot e^{(\ell)}$ with IC-signatures, with
${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ being the underlying core-sets. Then
locally compute
$[z] = [d^{(\ell)} \cdot e^{(\ell)}] + d^{(\ell)} \cdot [b^{(\ell)}] + e^{(\ell)} \cdot [a^{(\ell)}] + [c^{(\ell)}]$ from
$[d^{(\ell)} \cdot e^{(\ell)}], [a^{(\ell)}], [b^{(\ell)}]$ and $[c^{(\ell)}]$.

– Output Gate: If $g$ is the output gate with output $y$, then participate in an instance $\Rec([y], \PartySet)$ of $\Rec$ to publicly
reconstruct $y$.

Termination Phase

Every $P_i \in \PartySet$ concurrently executes the following steps during the protocol:

– Upon computing the circuit-output $y$, send the message $(\ready, P_i, y)$ to every party in $\PartySet$.

– Upon receiving the message $(\ready, P_j, y)$ from a set of parties ${\cal A}$ such that $\Z_s$ satisfies  $\Q^{(1)}({\cal A}, \Z_s)$ condition,
send $(\ready, P_i, y)$  to every party in $\PartySet$, provided no $(\ready, P_i, \star)$ message has been sent yet.

– Upon receiving the message $(\ready, P_j, y)$ from a set of parties $\W$ such that $\PartySet \setminus \W \in \Z_s$, output $y$ and terminate.

The properties of the protocol $\PiMPC$ stated in Theorem <ref>, are proved in Appendix <ref>.

Let $\Z_s$ and $\Z_a$ be monotone adversary structures where $\Z_a \subset \Z_s$,  the set
$\Z_s$ satisfy the condition $\Q^{(2)}(\PartySet, \Z_s)$, the set $\Z_a$ satisfy the condition $\Q^{(3)}(\PartySet, \Z_a)$ and $\Z_s, \Z_a$ together satisfy the
$\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition.
Let $\F$ be a finite field such that $|\F| \geq n^5 \cdot 2^{\ssec}$ where
$\ssec$ is the statistical security parameter. Moreover, let $y = f(x^{(1)}, \ldots, x^{(n)})$ be a publicly known function over $\F$ represented by an arithmetic circuit $\ckt$ over $\F$,
where each $P_i \in \PartySet$ has the input $x^{(i)}$. Furthermore, let $c_M$ and $D_M$ be the number of multiplication gates and the multiplicative depth of $\ckt$ respectively.
Then given an unconditionally-secure PKI,
protocol $\PiMPC$ achieves the following, where every honest $P_j$ participates with the input $x^{(j)}$ and where $t$ denotes the cardinality of the maximum sized subset in $\Z_s$.

– Synchronous Network: Except with probability $2^{-\ssec}$, all honest parties output $y = f(x^{(1)}, \ldots, x^{(n)})$ at the time
$[(3n + 5) t^2 + (74n + 140)t + 69n + D_M + 438] \cdot \Delta$, where $x^{(j)} = 0$, for every $P_j \not \in \CoreSet$ and where every honest party is present in $\CoreSet$, such that
$\PartySet \setminus \CoreSet \in \Z_s$.

– Asynchronous Network: Except with probability $2^{-\ssec}$, almost-surely, all honest parties eventually output $y = f(x^{(1)}, \ldots, x^{(n)})$
where $x^{(j)} = 0$, for every $P_j \not \in CoreSet$ and where $\PartySet \setminus \CoreSet \in \Z_s$.

The protocol incurs a communication of
$\Order(|\Z_s|^2 \cdot n^{12} \cdot \log{|\F|})$
bits and makes $\Order(n^3)$ calls to $\BA$.
Moreover, irrespective of the network type, the view of the adversary remains independent of the inputs of the honest parties in $\CoreSet$.

§ IMPOSSIBILITY RESULT

Here we show the necessity of the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition for network agnostic MPC. In fact we show that the condition is even necessary for network agnostic BA. For this, we generalize the
impossibility proof of [15] which shows the impossibility of network agnostic BA against threshold adversaries if $2t_s + t_a \geq n$.

Let $\Z_s$ and $\Z_a$ satisfy the
$\Q^{(2)}(\PartySet, \Z_s)$  and  $\Q^{(3)}(\PartySet, \Z_a)$ conditions respectively, where $\Z_a \subset \Z_s$.[The necessity of the
$\Q^{(2)}(\PartySet, \Z_s)$  and  $\Q^{(3)}(\PartySet, \Z_a)$ conditions follow from the existing results on the impossibility of unconditionally-secure SBA and ABA respectively, without
these conditions. The condition $\Z_a \subset \Z_s$ is also necessary since any potential corrupt subset which is tolerable in an asynchronous network should also be tolerable if
the network is synchronous.]
Moreover, let the parties have access to the setup of an unconditional PKI.
let $\Pi$ be an $n$-party protocol, which is a $\Z_s$-secure SBA protocol in the synchronous network and which is a $\Z_a$-secure ABA protocol in the asynchronous network (as per Definition <ref>).
Then $\Pi$ exists only if $\Z_s$ and $\Z_a$ satisfy the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition.

The proof is by contradiction. Let $\Pi$ exist, even if $\Z_s$ and $\Z_a$ do not satisfy the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition.
Then, there exist sets, say $Z_0, Z_1 \in \Z_s$ and $Z_2 \in \Z_a$ such that $Z_0 \cup Z_1 \cup Z_2  \supseteq \PartySet$ holds.
For simplicity and without loss of generality, assume that $Z_0, Z_1$ and $Z_2$ are disjoint.
Now consider the following executions of $\Pi$.
In all these executions, parties in $Z_0$ participate with input $0$, and parties in $Z_1$ participate with input $1$.

– Execution $E_1$: In this execution, the network is synchronous. All the parties in $Z_0$ are corrupted by the adversary and simply abort,
and all parties in $Z_2$ participate with input $1$. Since all the honest parties (namely the parties in $Z_1 \cup Z_2$) have input $1$, from the $\Z_s$-validity of $\Pi$ in the
synchronous network, the parties in $Z_1 \cup \Z_2$ should output $1$ after some fixed time, say $T_1$.

– Execution $E_2$: In this execution, the network is synchronous. All the parties in $Z_1$ are corrupted by the adversary and simply abort,
and all parties in $Z_2$ participate with input $0$. Since all the honest parties (namely the parties in $Z_0 \cup Z_2$) have input $0$, from the $\Z_s$-validity of $\Pi$ in the
synchronous network, the parties in $Z_0 \cup \Z_2$ should output $0$ after some fixed time, say $T_2$.

– Execution $E_3$: In this execution, the network is asynchronous, the adversary corrupts all the
parties in $Z_2$ and behave as follows:
the communication between the parties in $Z_0$ and $Z_1$ is delayed by at least time $\mbox{max}(T_1, T_2)$.
The adversary communicates with parties in $Z_0$ and $Z_1$, such that the views of the parties in $Z_0$ and $Z_1$ are identical to $E_1$ and $E_2$ respectively.
For this, the adversary runs $\Pi$ with input $0$ when interacting with the parties in $Z_0$ and runs
$\Pi$ with input $1$ when interacting with the parties in $Z_1$.
Hence, the parties in $Z_0$ output $0$, while the parties in $Z_1$ output $1$, which violates the $\Z_a$-consistency of $\Pi$ in the asynchronous network. This is a contradiction and hence, $\Pi$
does not exist.

§ ACKNOWLEDGEMENTS

We would like to thank Anirudh Chandramouli for several helpful discussions during the early stages of this research.

[1]
I. Abraham, D. Dolev, and J. Y. Halpern.
An Almost-surely Terminating Polynomial Protocol for Asynchronous
Byzantine Agreement with Optimal Resilience.
In PODC, pages 405–414. ACM, 2008.

[2]
I. Abraham, D. Dolev, and G. Stern.
Revisiting Asynchronous Fault Tolerant Computation with Optimal
In PODC, pages 139–148. ACM, 2020.

[3]
A. Appan, A. Chandramouli, and A. Choudhury.
Perfectly-Secure Synchronous MPC with Asynchronous Fallback
In PODC, pages 92–102. ACM, 2022.

[4]
A. Appan, A. Chandramouli, and A. Choudhury.
Perfectly Secure Synchronous MPC with Asynchronous Fallback
Guarantees Against General Adversaries.
IACR Cryptol. ePrint Arch., page 1047, 2022.

[5]
A. Appan, A. Chandramouli, and A. Choudhury.
Revisiting the Efficiency of Asynchronous MPC with Optimal
Resilience Against General Adversaries.
J. Cryptol., 36(3):16, 2023.

[6]
R. Bacho, D. Collins, C. Liu-Zhang, and J. Loss.
Network-Agnostic Security Comes for Free in DKG and MPC.
Cryptology ePrint Archive, Paper 2022/1369, 2022.

[7]
L. Bangalore, A. Choudhury, and A. Patra.
The Power of Shunning: Efficient Asynchronous Byzantine Agreement
J. ACM, 67(3):14:1–14:59, 2020.

[8]
D. Beaver.
Efficient Multiparty Protocols Using Circuit Randomization.
In J. Feigenbaum, editor, CRYPTO, volume 576 of Lecture
Notes in Computer Science, pages 420–432. Springer, 1991.

[9]
Z. Beerliová-Trubíniová and M. Hirt.
Efficient multi-party computation with dispute control.
In S. Halevi and T. Rabin, editors, Theory of Cryptography,
Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March
4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer
Science, pages 305–328. Springer Verlag, 2006.

[10]
Z. Beerliová-Trubíniová and M. Hirt.
Simple and Efficient Perfectly-Secure Asynchronous MPC.
In ASIACRYPT, volume 4833 of Lecture Notes in Computer
Science, pages 376–392. Springer Verlag, 2007.

[11]
M. Ben-Or.
Another Advantage of Free Choice (Extended Abstract): Completely
Asynchronous Agreement Protocols.
In PODC, pages 27–30. ACM, 1983.

[12]
M. Ben-Or, R. Canetti, and O. Goldreich.
Asynchronous Secure Computation.
In STOC, pages 52–61. ACM, 1993.

[13]
M. Ben-Or, S. Goldwasser, and A. Wigderson.
Completeness Theorems for Non-Cryptographic Fault-Tolerant
Distributed Computation (Extended Abstract).
In STOC, pages 1–10. ACM, 1988.

[14]
M. Ben-Or, B. Kelmer, and T. Rabin.
Asynchronous Secure Computations with Optimal Resilience (Extended
In PODC, pages 183–192. ACM, 1994.

[15]
E. Blum, J. Katz, and J. Loss.
Synchronous Consensus with Optimal Asynchronous Fallback
In TCC, volume 11891 of Lecture Notes in Computer
Science, pages 131–150. Springer, 2019.

[16]
E. Blum, J. Katz, and J. Loss.
Tardigrade: An Atomic Broadcast Protocol for Arbitrary Network
In ASIACRYPT, volume 13091 of Lecture Notes in Computer
Science, pages 547–572. Springer, 2021.

[17]
E. Blum, C. Liu Zhang, and J. Loss.
Always Have a Backup Plan: Fully Secure Synchronous MPC with
Asynchronous Fallback.
In CRYPTO, volume 12171 of Lecture Notes in Computer
Science, pages 707–731. Springer, 2020.

[18]
G. Bracha.
An Asynchronous [(n-1)/3]-Resilient Consensus Protocol.
In PODC, pages 154–162. ACM, 1984.

[19]
R. Canetti.
Studies in Secure Multiparty Computation and Applications.
PhD thesis, Weizmann Institute, Israel, 1995.

[20]
R. Canetti.
Universally Composable Security: A New Paradigm for Cryptographic
In FOCS, pages 136–145. IEEE Computer Society, 2001.

[21]
R. Canetti and T. Rabin.
Fast Asynchronous Byzantine Agreement with Optimal Resilience.
In STOC, pages 42–51, 1993.

[22]
B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch.
Verifiable Secret Sharing and Achieving Simultaneity in the Presence
of Faults (Extended Abstract).
In 26th Annual Symposium on Foundations of Computer Science,
Portland, Oregon, USA, 21-23 October 1985, pages 383–395. IEEE Computer
Society, 1985.

[23]
A. Choudhury.
Almost-Surely Terminating Asynchronous Byzantine Agreement Against
General Adversaries with Optimal Resilience.
In ICDCN, pages 167–176. ACM, 2023.

[24]
A. Choudhury and A. Patra.
An Efficient Framework for Unconditionally Secure Multiparty
IEEE Trans. Information Theory, 63(1):428–468, 2017.

[25]
A. Choudhury and A. Patra.
On the Communication Efficiency of Statistically Secure Asynchronous
MPC with Optimal Resilience.
J. Cryptol., 36(2):13, 2023.

[26]
R. Cramer, I. Damgård, S. Dziembowski, M. Hirt, and T. Rabin.
Efficient Multiparty Computations Secure Against an Adaptive
In EUROCRYPT, volume 1592 of Lecture Notes in Computer
Science, pages 311–326. Springer, 1999.

[27]
I. Damgård, V. Pastro, N. P. Smart, and S. Zakarias.
Multiparty Computation from Somewhat Homomorphic Encryption.
In R. Safavi-Naini and R. Canetti, editors, Advances in
Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara,
CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes
in Computer Science, pages 643–662. Springer, 2012.

[28]
G. Deligios and C. Liu-Zhang.
Synchronous Perfectly Secure Message Transmission with Optimal
Asynchronous Fallback Guarantees.
IACR Cryptol. ePrint Arch., page 1397, 2022.

[29]
D. Dolev, C. Dwork, O. Waarts, and M. Yung.
Perfectly Secure Message Transmission.
J. ACM, 40(1):17–47, 1993.

[30]
Danny Dolev and H. Raymond Strong.
Authenticated algorithms for byzantine agreement.
SIAM J. Comput., 12(4):656–666, 1983.

[31]
Pesech Feldman and Silvio Micali.
An optimal probabilistic protocol for synchronous byzantine
SIAM Journal on Computing, 26(4):873–933, 1997.

[32]
M. J. Fischer, N. A. Lynch, and M. Paterson.
Impossibility of Distributed Consensus with One Faulty Process.
J. ACM, 32(2):374–382, 1985.

[33]
M. Fitzi and U. M. Maurer.
Efficient Byzantine Agreement Secure Against General Adversaries.
In DISC, volume 1499 of Lecture Notes in Computer
Science, pages 134–148. Springer, 1998.

[34]
Matthias Fitzi.
Generalized Communication and Security Models in Byzantine
PhD thesis, 2002.

[35]
D. Ghinea, C. Liu-Zhang, and R. Wattenhofer.
Optimal Synchronous Approximate Agreement with Asynchronous
In PODC, pages 70–80. ACM, 2022.

[36]
O. Goldreich, S. Micali, and A. Wigderson.
How to Play any Mental Game or A Completeness Theorem for Protocols
with Honest Majority.
In A. V. Aho, editor, Proceedings of the 19th Annual ACM
Symposium on Theory of Computing, 1987, New York, New York, USA, pages
218–229. ACM, 1987.

[37]
V. Goyal, Y. Song, and C. Zhu.
Guaranteed Output Delivery Comes Free in Honest Majority MPC.
In CRYPTO, volume 12171 of Lecture Notes in Computer
Science, pages 618–646. Springer, 2020.

[38]
Martin Hirt and Ueli Maurer.
Complete characterization of adversaries tolerable in secure
multi-party computation (extended abstract).
In PODC, pages 25–34. ACM, 1997.

[39]
Martin Hirt and Ueli Maurer.
Player simulation and general adversary structures in perfect
multiparty computation.
Journal of Cryptology, 13(1):31–60, 2000.

[40]
Martin Hirt and Daniel Tschudi.
Efficient general-adversary multi-party computation.
In ASIACRYPT, volume 8270 of Lecture Notes in Computer
Science, pages 181–200. Springer, 2013.

[41]
M. Ito, A. Saito, and T. Nishizeki.
Secret Sharing Schemes Realizing General Access Structures).
In Global Telecommunication Conference, Globecom, pages
99–102. IEEE Computer Society, 1987.

[42]
M. V. N. Ashwin Kumar, K. Srinathan, and C. Pandu Rangan.
Asynchronous Perfectly Secure Computation Tolerating Generalized
In ACISP, volume 2384 of Lecture Notes in Computer
Science, pages 497–512. Springer, 2002.

[43]
K. Kursawe and F. C. Freiling.
Byzantine Fault Tolerance on General Hybrid Adversary Structures.
Technical Report, RWTH Aachen, 2005.

[44]
U. M. Maurer.
Secure Multi-party Computation Made Simple.
In SCN, volume 2576 of Lecture Notes in Computer Science,
pages 14–28. Springer, 2002.

[45]
A. Momose and L. Ren.
Multi-Threshold Byzantine Fault Tolerance.
In CCS, pages 1686–1699. ACM, 2021.

[46]
Atsuki Momose and Ling Ren.
Multi-threshold byzantine fault tolerance.
In Proceedings of the 2021 ACM SIGSAC Conference on Computer and
Communications Security, CCS '21, page 1686–1699, New York, NY, USA, 2021.
Association for Computing Machinery.

[47]
A. Mostéfaoui, H. Moumen, and M. Raynal.
Signature-Free Asynchronous Binary Byzantine Consensus with t
n/3, O(n2) Messages, and O(1) Expected Time.
J. ACM, 62(4):31:1–31:21, 2015.

[48]
A. Patra, A. Choudhury, and C. Pandu Rangan.
Efficient Asynchronous Verifiable Secret Sharing and Multiparty
J. Cryptology, 28(1):49–109, 2015.

[49]
Marshall Pease, Robert Shostak, and Leslie Lamport.
Reaching Agreement in the Presence of Faults.
Journal of the ACM (JACM), 27(2):228–234, 1980.

[50]
B. Pfitzmann and M.Waidner.
Information-theoretic Pseudosignatures and Byzantine Agreement for
$t \geq n/3$.
Technical Report RZ 2882 ($\#$90830), IBM Research, 1996.

[51]
Michael O. Rabin.
Randomized Byzantine Generals.
In 24th Annual Symposium on Foundations of Computer Science,
Tucson, Arizona, USA, 7-9 November 1983, pages 403–409, 1983.

[52]
T. Rabin and M. Ben-Or.
Verifiable Secret Sharing and Multiparty Protocols with Honest
Majority (Extended Abstract).
In STOC, pages 73–85. ACM, 1989.

[53]
A. C. Yao.
Protocols for Secure Computations (Extended Abstract).
In FOCS, pages 160–164. IEEE Computer Society, 1982.

§ PROPERTIES OF THE NETWORK AGNOSTIC BA PROTOCOL

In this section, we prove the properties of the network agnostic BA protocol (see Fig <ref> for the protocol).
We first formally present the sub-protocol $\PiPW$ and prove its properties.

§.§ Protocol $\PiPW$: Synchronous BA with Asynchronous Guaranteed Liveness

Protocol $\PiPW$ is presented in Fig <ref>, where for simplicity we assume that the input of each party is a bit.
The protocol is very simple.
Each party $P_i$ uses a Dolev-Strong (DS) style protocol [30]
to broadcast its input $b_i$. The protocol runs for $t+1$ “rounds", where $t$ is the size of the largest set in $\Z_s$.
Each party $P_i$ accumulates values on the behalf of every party $P_j$ in a set $\ACC_{ij}$. A bit $b$ is added to $\ACC_{ij}$ during round $r$ only if $P_i$ receives signatures on $b$ from $r$ distinct parties
including $P_j$. Party $P_i$ computes the final output by taking the “majority" among the accumulated values. This is done by computing a final set $\FIN_i$ of values based on each $\ACC_{ij}$ set.
Since the DS protocol is designed for the synchronous network, for convenience,
we present the protocol $\PiPW$ in a round-based fashion, where the parties set the duration of each round to $\Delta$ and will know the
beginning and end of each round.

$\PiPW(\PartySet, \Z_s, \Z_a)$ Synchronous BA with asynchronous guaranteed liveness. The above code is executed by every party $P_i$ with input $b_i$.fig:PW

– Initialization: Initialize the following sets.

– For $j = 1, \ldots, n$: the set of values accumulated on the behalf of $P_j$, $\ACC_{ij} = \emptyset$.

– $t$: size of the largest set in $\Z_s$.

– The final set of values to be considered while computing the output $\FIN_i = \emptyset$.

– Round 0: On having input bit $b_i$, sign $b_i$ to obtain the signature $\sigma_{ii}$. Set $\SET_i = \{\sigma_{ii}\}$ and send $(b_i, i, \SET_i)$ to every party $P_j \in \PartySet$.

– Round $r$ = $0$ to $t + 1$: On receiving $(b, j, \SET_j)$ in round $r$, check if all the following hold.

– $\SET_j$ contains valid signatures on $b$ from $r$ distinct parties, including $P_j$;

– $b \notin \ACC_{ij}$.

If all the above hold, then do the following.

– Add $b$ to $\ACC_{ij}$.

– If $r \neq (t + 1)$, then compute a signature $\sigma_{ij}$ on $b$ and send $(b,j, \SET_j \cup \{ \sigma_{ij} \})$ to every party $P_k \in \PartySet$.

– Output Computation: At time $(t+1) \cdot \Delta$, do the following.

– If $\ACC_{ij}$ contains exactly one value $b$, then add $(j,b)$ to $\FIN_i$.  Else, add $(j,\bot)$ to $\FIN_i$.

– If there exists a set $Z \in \Z_s$ and a value $b \neq \bot$ such that, for every $P_j \in \PartySet \setminus Z$, $(j,b)$ belongs to $\FIN_i$, then output $b$. Else, output $\bot$.

We next prove the properties of the protocol $\PiPW$, which are a straightforward generalization of the properties of the DS protocol.

Protocol $\PiPW$ achieves $\Z_s$-Consistency in a synchronous network.

We claim that each honest party $P_i$ computes the same set $\ACC_{ij}$ corresponding to every
party $P_j$, by time $(t + 1) \cdot \Delta$. Assuming the claim is true,
the proof then follows from the fact that $\FIN_i$ is computed deterministically at the time $(t + 1) \cdot \Delta$,
based on the sets $\ACC_{ij}$.
To prove the claim, consider an arbitrary honest party $P_i$ and an arbitrary $P_j$.
If $P_i$ includes $b$ to $\ACC_{ij}$, then we show that by the time $(t + 1) \cdot \Delta$, the value $b$ will be present in the set $\ACC_{kj}$ of every honest party $P_k$.
For this, we consider the following two cases.

– Case 1 - $P_i$ added $b$ to $\ACC_{ij}$ during round $r$ where  $r \leq t$:
In this case, $P_i$ must have received $(b, j, \SET_j)$ in round $r$, where $\SET_j$ contained valid signatures on $b$ from $r-1$ distinct parties apart from $P_j$. Party
$P_i$ then computes $\sigma_{ij}$, adds this to $\SET_j$, and sends $(b,j,\SET_j)$ to every party. When $P_k$ receives this during round $r+1$, it will find that $\SET_j$ contains $r$ valid signatures on $b$ apart from party $P_j$'s, including $\sigma_{ij}$. Hence, $P_k$ will add $b$ to $\ACC_{kj}$. Since $r+1 \leq t + 1$, this happens by time $(t + 1) \cdot \Delta$.

– Case 2 - $P_i$ added $b$ to $\ACC_{ij}$ during round $r = t + 1$:
In this case $P_i$ must have received $(b,j,\SET_j)$ in round $t + 1$, where $\SET_j$ contained valid signatures on $b$ from $t$ distinct parties apart from $P_j$.
This means that, in total, $P_i$ has received valid signatures on $b$ from $t+1$ distinct parties. Among these, at least one party, say $P_h$, must be honest, as there can be at most $t$ corrupt
parties. This means that $P_h$ must have added $b$ to $\ACC_{hj}$ during some round $r'$, where $r' \leq t$.
Thus, as argued in the previous case, each party $P_k$ also adds $b$ to $\ACC_{kj}$ by round $t + 1$ and hence time $(t + 1) \cdot \Delta$.

Protocol $\PiPW$ achieves $\Z_s$-Validity in a synchronous network.

Suppose that all honest parties have the same input $b$. Corresponding to each honest party $P_j$, every honest
$P_i$ sets $\ACC_{ij} = \{b\}$. This is because $P_i$ would receive a valid signature on $b$ from $P_j$ during round $0$, and adds $b$ to $\ACC_{ij}$. Further, $P_i$ will not add any $b' \neq b$ to $\ACC_{ij}$ during
any of the rounds, since the adversary cannot forge a signature on $b'$ on the behalf of $P_j$. Thus, for each honest $P_j$, party
$P_i$ adds $(j,b)$ to $\FIN_i$. Let $Z^{\star} \in \Z_s$ be the set of corrupt parties and let $\Hon = \PartySet \setminus Z^{\star}$ be the set of honest parties.
Hence corresponding to every $P_j \in \Hon$, then value $(j, b)$ is added to $\FIN_i$ of every $P_i \in \Hon$ by time $(t + 1) \cdot \Delta$.
Moreover, since $\Q^{(2)}(\PartySet, \Z_s)$
conditions holds, $\PartySet \setminus Z^{\star} \not \in \Z_s$. Consequently, as per the “majority" rule, every party in $\Hon$ outputs $b$.

In protocol $\PiPW$, irrespective of the network type, all honest parties obtain an output at the time $(t+1)\cdot \Delta$.

The proof follows from the fact that irrespective of the network type, the parties compute an output (which could be $\bot$) at the local time $(t + 1) \cdot \Delta$.

If the inputs of the parties are of size $\ell$ bits, then we invoke $\ell$ instances of $\PiPW$. The following lemma describes the communication cost incurred while doing this.

If the inputs of the parties are of size $\ell$ bits, then
protocol $\PiPW$ incurs a communication of $\Order(n^4 \cdot \ell \cdot |\sigma|)$ bits from the honest parties.

During round $0$, each party signs its input and sends this to every other party, incurring a total communication of
$\Order(\ell \cdot n^2 \cdot |\sigma|)$ bits. During the next $t$ rounds,
each party $P_i$ sends $(b, j,\SET_j)$ to every other party $P_k$ at most once. This is because $P_i$ sends this only if $b \notin \ACC_{ij}$ holds, and does not do this once it adds $b$ to $\ACC_{ij}$. Considering all possibilities for $b$, $i$, $j$ and $k$, and taking into account that $\SET_j$ will contain $\Order(n)$ signatures, the communication cost of this will be $\Order(\ell \cdot n^4 \cdot |\sigma|)$ bits.

The proof of Lemma <ref> now follows from Lemma <ref>-<ref>.

§.§ Protocool $\Acast$: Asynchronous Broadcast with Synchronous Guarantees

In this section, we prove the properties of the protocol $\Acast$ (see Fig <ref> for the protocol description).

Lemma <ref>.

Protocol $\Acast$ achieves the following properties.

– Asynchronous Network: The protocol is a $\Z_a$-secure broadcast protocol.

– Synchronous Network: (a) $\Z_s$-Liveness: If $\Sender$ is honest, then all honest parties obtain an output
within time $3\Delta$. (b) $\Z_s$-Validity: If $\Sender$ is honest, then every honest party with an output, outputs $m$.
(c) $\Z_s$-Consistency: If $\Sender$ is corrupt and some honest party outputs $m^{\star}$ at time $T$,
then every honest $P_i$ outputs $m^{\star}$ by the end of time $T+ \Delta$.

– Communication Complexity: $\Order(n^3 \cdot \ell \cdot |\sigma|)$ bits are communicated by the honest parties, where
$\ell$ is the size of $\Sender$'s input.

We first consider a synchronous network, followed by an asynchronous network.

Properties in the Synchronous Network.

Let $Z^{\star} \in \Z_s$ be the set of corrupt parties and let $\Hon = \PartySet \setminus Z^{\star}$ be the set of honest parties.
Suppose $\Sender$ is honest. Then by time $\Delta$, each party in $\Hon$ receives $\sign{(\propose, m)}_\Sender$ from $\Sender$
and no honest party ever receives $\sign{(\propose, m')}_\Sender$ from any party by time $2\Delta$, for any $m' \neq m$, since signature of an honest $\Sender$ cannot be forged.
Thus, every $P_j \in \Hon$
sends $\sign{(\vote, m)}_j$ by time $2\Delta$.
Consequently, by time $3\Delta$, every $P_i \in \Hon$ will have a quorum $\cert{m}$ of legitimately signed $\sign{(\vote, m)}_j$ messages corresponding to every $P_j \in \Hon$.
The parties $P_k \in Z^{\star}$ may send signed $\sign{(\vote, m')}_k$ messages where $m' \neq m$ and consequently
the parties in $\Hon$ may also have a quorum $\cert{m'}$ of legitimately signed $\sign{(\vote, m')}_k$ messages corresponding to every $P_k \in Z^{\star}$.
However, since $\Z_s$ satisfies the $\Q^{(2)}(\PartySet, \Z_s)$ condition, $\PartySet \setminus Z^{\star} = \Hon \not \in \Z_s$.
Consequently, the parties in $\Hon$ outputs $m$ by time $3\Delta$, as the condition for outputting an $m' \neq m$ will be never satisfied for the parties in $\Hon$.
This proves the $\Z_s$-liveness and $\Z_s$-validity.

We now consider $\Sender$ to be corrupt. We first show that no two parties in $\Hon$ can vote for different messages. On the contrary,
let $P_i \in \Hon$ sends $\sign{\vote, m')}_i$ at time $T_i$, and let $P_j \in \Hon$ sends $\sign{(\vote, m'')}_j$ at time $T_j$,
where $T_j \geq T_i$. This implies that $P_i$ must have received $\sign{(\propose, m')}_\Sender$ from $\Sender$ within time $T_i - \Delta$, and would have sent
$\sign{(\propose, m')}_\Sender$ to $P_j$. And $P_j$ would have received $\sign{(\propose, m')}_\Sender$ from $P_i$ within time $T_i$. Now since $T_i \leq T_j$,
it implies that $P_j$ would not have sent $\sign{(\vote, m'')}_j$ at time $T_j$, and this is a contradiction.

Now based on the above fact,  we proceed to prove that $\Z_s$-consistency holds.
Let $P_h \in \Hon$ outputs $m^\star$ at time $T$. This implies that at time $T$, there exists a subset $Z_{\alpha} \in \Z_s$, such that
$P_h$ has a quorum $\cert{m^{\star}}$ of legitimately signed $\sign{(\vote, m)}_{j}$ messages, corresponding to every $P_j \in \PartySet \setminus Z_{\alpha}$.
Now since $\Z_s$ satisfies the $\Q^{(2)}(\PartySet, \Z_s)$ condition, it follows that $\Hon \cap (\PartySet \setminus Z_{\alpha}) \neq \emptyset$. This implies that there exists at least
one party in $\Hon$, say $P_k$, who has voted for $m^{\star}$ by sending a $\sign{(\vote, m)}_{k}$ message. Consequently, no other party in $\Hon$ every votes for $m^{\star \star} \neq m^{\star}$.
The parties in $Z^{\star}$ may vote for $m^{\star \star} \neq m^{\star}$. But since $\PartySet \setminus Z^{\star} \not \in \Z_s$, it follows that no party in $\Hon$ will ever have a sufficiently large
quorum of legitimately signed vote messages for $m^{\star \star}$ to output $m^{\star \star}$.
Since $P_h$ sends $\cert{m^\star}$ to all parties at time $T$, every other party in $\Hon$ will receive $\cert{m^\star}$ by time $T + \Delta$.
Consequently, all the parties in $\Hon$ will output $m^{\star}$, latest by time $T + \Delta$.

Properties in the Asynchronous Network.

We now consider an asynchronous network. Let $Z^{\star} \in \Z_a$ be the set of corrupt parties and let
$\Hon = \PartySet \setminus Z^{\star}$ be the set of honest parties. We first consider an honest $\Sender$.
Each party in $\Hon$ eventually receives $\sign{(\propose, m)}_\Sender$ from $\Sender$. Furthermore, no party in $\Hon$ ever receives $\sign{(\propose, m')}_\Sender$ from any party,
for any $m' \neq m$,  since the signature of an honest $\Sender$ cannot be forged. Hence, each party in $\Hon$ eventually sends a signed $\vote$ message for $m$, which is eventually
delivered to every party in $\Hon$. The parties in $Z^{\star}$ may send signed $\vote$ messages for $m' \neq m$.
However, since $\Z_a$ satisfies the $\Q^{(3)}(\PartySet, \Z_a)$ condition, it follows that each party in $\Hon$ eventually outputs $m$ and the conditions for outputting $m' \neq m$ will be never satisfied
for any party in $\Hon$. This proves the $\Z_a$-liveness and $\Z_a$-consistency.

Next, consider a corrupt $\Sender$.
Let $P_h \in \Hon$  outputs $m^\star$. This implies there exists a subset $Z_{\alpha} \in \Z_s$, such that
$P_h$ has a quorum $\cert{m^{\star}}$ of legitimately signed $\vote$ messages for $m^{\star}$, corresponding to
every party in $\PartySet \setminus Z_{\alpha}$.
Now consider an arbitrary $P_i \in \Hon$, where $P_i \neq P_h$. We claim that for any $Z \in \Z_s$, party
$P_i$ will never have a
quorum $\cert{m^{\star \star}}$ of legitimately signed $\vote$ messages for $m^{\star \star}$, corresponding to
the parties in $\PartySet \setminus Z$.
On the contrary, let  $P_i$ eventually have a
quorum $\cert{m^{\star \star}}$ of legitimately signed $\vote$ messages for $m^{\star \star}$, corresponding to
every party in $\PartySet \setminus Z_{\beta}$, for some $Z_{\beta} \in \Z_s$.
Now since the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition is satisfied, it follows that $\Hon \cap (\PartySet \setminus Z_{\alpha}) \cap (\PartySet \setminus Z_{\beta}) \neq \emptyset$.
This implies that there exists at least one party from $\Hon$, say $P_k$, such that $P_k$ has voted both for $m^{\star}$, as well as $m^{\star \star}$, which is a
contradiction. Consequently, $P_i$ will never output $m^{\star \star}$.
Now, since $P_h$ sends $\cert{m^\star}$ to all the parties, party $P_i$ eventually receives  $\cert{m^\star}$ and outputs $m^\star$.
This proves $\Z_a$-consistency.

Finally, the communication complexity follows from the fact that irrespective of the type of network, every party may have to send a quorum of up to $\Order(n)$ signed $\vote$
messages, to every other party.

§.§ Properties of the Protocol $\BC$

In this section, we prove the properties of the protocol $\BC$ (see Fig <ref> for the formal description).

Theorem <ref>.

Protocol  $\BC$ achieves the following,
with a communication complexity of $\Order(n^4 \cdot \ell \cdot |\sigma|)$ bits,
where $\TimeBC =  3\Delta + \TimePW$.

– Synchronous network:

–(a) $\Z_s$-Liveness: At time $\TimeBC$, each honest party has an output.

– (b) $\Z_s$-Validity: If $\Sender$ is honest, then at time $\TimeBC$, each honest party
outputs $m$.

– (c) $\Z_s$-Consistency: If $\Sender$ is corrupt, then the output of every honest party is the same at
time $\TimeBC$.

–   (d) $\Z_s$-Fallback Consistency: If $\Sender$ is corrupt and some honest
party outputs $m^{\star} \neq \bot$ at time
$T$ through fallback-mode, then every honest party outputs $m^{\star}$ by
time $T + \Delta$.

– Asynchronous Network:

– (a) $\Z_a$-Liveness: At time $\TimeBC$, each honest party has an output.

– (b) $\Z_a$-Weak Validity: If $\Sender$ is honest, then at  time $\TimeBC$,
each honest party
outputs $m$ or $\bot$.

– (c) $\Z_a$-Fallback Validity: If $\Sender$ is honest, then each honest party
with output $\bot$ at time $\TimeBC$, eventually outputs
$m$ through fallback-mode.

– (d) $\Z_a$-Weak Consistency: If $\Sender$ is corrupt, then there exists some $m^{\star} \neq \bot$, such that
at time $\TimeBC$,
each honest party
outputs either
$m^{\star}$ or $\bot$.

– (e) $\Z_a$-Fallback Consistency: If $\Sender$ is corrupt, and some honest party
outputs $m^{\star} \neq \bot$ at  time
$T$ where $T \geq \TimeBC$, then
each honest party eventually outputs $m^{\star}$.

The $\Z_s$-liveness and $\Z_a$-liveness properties follow from the fact that
every honest party outputs something (including $\bot$) at (local)
time $\TimeBC$, irrespective of the type of the network.
We next prove the rest of the properties of the protocol in the synchronous network.

Properties in the Synchronous Network.

If $\Sender$ is honest, then due to the $\Z_s$-liveness and
$\Z_s$-validity properties of $\Acast$ in the synchronous network (see Lemma <ref>), all honest
parties receive $m$ from the Acast of $\Sender$
at time $3\Delta$. Consequently, all honest parties participate with input $m$ in the instance of $\PiPW$.
The $\Z_s$-guaranteed liveness and $\Z_s$-validity properties
of $\PiPW$ in the synchronous network (see Lemma <ref>) guarantees that at time $3\Delta + \TimePW$, all
honest parties will have
$m$ as the output from the instance
of $\PiPW$. As a result, all honest parties output $m$ at time $\TimeBC$, thus proving the $\Z_s$-validity property.

To prove the $\Z_s$-consistency property, we consider a corrupt $\Sender$.
From the $\Z_s$-consistency property of $\PiPW$ in the synchronous network (see Lemma <ref>),
all honest parties will have the same output from the instance of $\PiPW$ at time $\TimeBC$.
If all honest parties have the output $\bot$ for $\BC$ at time $\TimeBC$, then $\Z_s$-consistency
holds trivially. So, consider the case when
some honest party, say $P_i$, has the output $m^{\star} \neq \bot$ for $\BC$ at time $\TimeBC$.
This implies that all honest parties have the output $m^{\star}$ from the instance of $\PiPW$.
Moreover, at time $3\Delta$, at least one honest party, say $P_h$, has received $m^{\star}$ from the Acast of $\Sender$.
If the latter does not hold, then all honest parties would have participated
with input $\bot$ in the instance of $\PiPW$, and from the $\Z_s$-validity of $\PiPW$
in the synchronous
network (see Lemma <ref>), all honest  parties would compute $\bot$ as the output during the instance of $\PiPW$, which is a contradiction.
Since $P_h$ has received
$m^{\star}$ from $\Sender$'s Acast at time $3\Delta$, it follows from the $\Z_s$-consistency property of
$\Acast$ in the synchronous
network (see Lemma <ref>) that all honest parties will receive
$m^{\star}$ from $\Sender$'s Acast by time $4\Delta$. Moreover, $4\Delta < 3\Delta + \TimePW$ holds.
Consequently, at time $3 \Delta + \TimeBC$,
all honest parties will have $m^{\star}$ from $\Sender$'s Acast and as the output of
$\PiPW$, implying that all honest parties output $m^{\star}$ for $\BC$.

We next prove the  $\Z_s$-fallback consistency property for which
we again consider a corrupt $\Sender$.
Let $P_h$ be an honest party who outputs $m^{\star} \neq \bot$ at time $T$ through fallback-mode.
Note that $T > \TimeBC$, as the output during the fallback-mode is computed only after time $\TimeBC$.
We also note that each honest party has output $\bot$ at
time $\TimeBC$. This is because, from the proof of the $\Z_s$-consistency property of
$\BC$ (see above), if any honest party has an output
$m' \neq \bot$ at time $\TimeBC$, then all honest parties (including $P_h$) must have computed the output
$m'$ at time $\TimeBC$. Hence, $P_h$ will never change its output to
$m^{\star}$.[Recall that in the protocol $\BC$, the parties who obtain
an output different from $\bot$ at time $\TimeBC$, never change their output.]
Now since $P_h$ has obtained the output $m^{\star}$, it implies that at time $T$, it has received $m^{\star}$ from the Acast of
$\Sender$. It then follows from the $\Z_s$-consistency of
$\Acast$ in the synchronous network that every honest party will also receive
$m^{\star}$ from the Acast of $\Sender$, latest by time $T + \Delta$ and output $m^{\star}$.
This completes the proof of all the properties in the synchronous network.

Properties in the Asynchronous Network.

The $\Z_a$-weak validity property follows from the $\Z_a$-validity property of
$\Acast$ in the asynchronous network (see Lemma <ref>), which ensures that
no honest party ever receives an $m'$ from the Acast of $\Sender$, where $m' \neq m$.
So, if at all any honest party outputs a value different from $\bot$ at time $\TimeBC$, it has to be $m$.
The $\Z_a$-weak consistency property follows using similar arguments
as used to prove $\Z_s$-consistency in the synchronous network;
however we now rely on the $\Z_a$-validity and
properties of $\Acast$ in the asynchronous network (see Lemma <ref>).
The latter property ensures  that
for a corrupt $\Sender$, two different honest parties never end up receiving $m_1$ and $m_2$ from the Acast of $\Sender$, where $m_1\neq m_2$.

For the $\Z_s$-fallback validity property, consider an honest $\Sender$, and let
$P_i$ be an arbitrary honest party
who outputs $\bot$ at (local) time $\TimeBC$. Since the parties keep on participating in the protocol beyond time $\TimeBC$,
it follows from the $\Z_a$-liveness and
$\Z_a$-validity properties of $\Acast$ in the asynchronous network (see Lemma <ref>) that party $P_i$ will eventually
receive $m$ from the Acast of $\Sender$, by executing the steps of the fallback-mode of $\BC$.
Consequently, party $P_i$ eventually changes its output from
$\bot$ to $m$.

For the $\Z_a$-fallback consistency property, we consider a corrupt $\Sender$. Let
$P_j$ be an honest party who outputs some $m^{\star}$ different from $\bot$ at time $T$, where $T \geq \TimeBC$.
This implies that $P_j$ has
obtained $m^{\star}$ from the Acast of $\Sender$.
Now, consider an arbitrary honest $P_i$. From the
$\Z_a$-liveness and $\Z_a$-weak consistency properties of
$\BC$ in asynchronous network proved above,
it follows that $P_i$ outputs either $m^{\star}$ or $\bot$ at local time $\TimeBC$.
If $P_i$ has output $\bot$, then from the $\Z_a$-consistency
property of $\Acast$ in the asynchronous network (see Lemma <ref>), it follows that
$P_i$ will also eventually obtain $m^{\star}$ from the Acast of $\Sender$, by executing the steps of the fallback-mode of $\BC$.
Consequently, party $P_i$ eventually changes its output from
$\bot$ to $m^{\star}$.

The communication complexity (both in the synchronous as well as asynchronous network)
follows from the communication complexity of $\PiPW$ and $\Acast$.

§.§ Properties of the Protocol $\SBA$

In this section, we prove the properties of the protocol $\SBA$ (see Fig <ref> for the formal description).

Theorem <ref>.

Protocol $\SBA$ achieves the following where $\TimeSBA = \TimeBC$,
incurring a communication of
$\Order(n^5 \cdot |\sigma|)$ bits.

– Synchronous Network: the protocol is a $\Z_s$-secure SBA protocol where honest parties have an output, different from $\bot$, at time $\TimeSBA$.

– Asynchronous Network: the protocol achieves $\Z_a$-guaranteed liveness and $\Z_a$-weak validity, such that all honest parties have an output at (local) time $\TimeSBA$.

The communication complexity simply follows from the fact that $n$ instances of $\BC$ are invoked in the protocol.
The guaranteed liveness, both in the synchronous and asynchronous network trivially follows from
the $\Z_s$-liveness and $\Z_a$-liveness of $\BC$ (see Theorem <ref>), which ensures that all the $n$ instances of $\BC$ produce some output
within (local) time $\TimeBC$, both in a synchronous as well as an asynchronous network, through regular mode.
Hence, at local time $\TimeSBA = \TimeBC$, all honest parties will have some output.
We next prove the rest of the properties in a synchronous network.

Properties in the Synchronous Network.

Let $Z^{\star} \in \Z_s$ be the set of corrupt parties and let $\Hon = \PartySet \setminus Z^{\star}$ be the set of honest parties.
In a synchronous network, the instances of $\BC$ corresponding to the senders in $\Hon$,
result in an output different from $\bot$ for all honest parties (follows from the $\Z_s$-validity property of $\BC$ in the synchronous
network, Theorem <ref>). Hence $\Hon \subseteq \R$ will hold.
from the $\Z_s$-consistency property of $\BC$ in the synchronous network (Theorem <ref>),
all the parties in $\Hon$ obtain a common output from the $i^{th}$ instance of $\BC$, for $i = 1, \ldots, n$, at time $\TimeBC$.
Hence, all honest parties output the same value,
different from $\bot$, at time $\TimeBC$, proving the $\Z_s$-consistency of $\SBA$.
Finally, if all parties in $\Hon$ have the same input bit $b$, then only the instances of $\BC$ corresponding to the parties in $\R \setminus \Hon$ may output
$\bar{b} = 1 - b$. However, $\R \setminus \Hon \in \Z_s$. Moreover, $\R \setminus Z^{\star} \not \in \Z_s$ (since $\Z_s$ satisfies the $\Q^{(2)}(\PartySet, \Z_s)$ condition).
It then follows that all honest parties output $b$, proving $\Z_s$-validity of $\SBA$.

Properties in the Asynchronous Network.

Let $Z^{\star} \in \Z_a$ be the set of corrupt parties and let $\Hon = \PartySet \setminus Z^{\star}$ be the set of honest parties.
Suppose all the parties in $\Hon$ have the same input bit $b$. Let
$P_i \in \Hon$ be an arbitrary party, that obtains an output $c$, different from $\bot$, at time $\TimeBC$. This implies that there exists a subset of parties $\R$ for $P_i$, where $\PartySet \setminus \R \in \Z_s$, such that
$P_i$ has obtained a Boolean output $b_i^{(j)}$ from the $\BC$ instances, corresponding to every $P_j \in \R$. Moreover, there also exists a subset of parties
$\R_i \subseteq \R$, where $\R \setminus \R_i \in \Z_s$, such that
the output $b_i^{(j)} = c$, corresponding to every $P_j \in \R_i$. Now since the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$
condition is satisfied, it follows that $\Z_a$ satisfies the $\Q^{(1)}(\R_i, \Z_a)$ condition and hence
$\R_i \cap \Hon \neq \emptyset$. Consequently, $c = b$ holds.
This proves the $\Z_a$-weak validity in the asynchronous network.

§.§ Protocol $\Vote$: Asynchronous Graded Agreement with Synchronous Validity

To design protocol $\Vote$, we first design a sub-protocol $\Prop$ for proposing values.

§.§.§ $\Prop$: A Network Agnostic Protocol for Proposing Values

Protocol $\Prop$ takes an input value from each party from the set $\{0, 1, \lambda\}$
and outputs a set $\prop$ of proposed values for each party. Liveness is ensured in an asynchronous network as long as each honest party holds one of two inputs. In an asynchronous network, it will be ensured that each value in the output $\prop$ must be the input of some honest party. Moreover, if any two honest parties output a singleton set for $\prop$, then they must output the same set. In a synchronous network, validity and liveness are ensured as long as each honest party participates with the same input. Protocol $\Prop$ is presented in figure <ref>.

$\Prop(\PartySet, \Z_s, \Z_a)$Sub-protocol to propose values. The above code is executed by every party $P_i$ with input $v \in \{0, 1, \lambda\}$fig:Prop

* Set $\vals = \prop = \emptyset$.

* On having the input $v \in \{0, 1, \lambda\}$, send $(\prepare, v)$ to every party $P_j \in \PartySet$.

* On receiving $(\prepare,b)$ for some $b \in \{0,1,\lambda\}$ from a set of parties $S^{(b)}$ satisfying $\Q^1(S^{(b)}, \Z_s)$ condition,
send $(\prepare,b)$ to all $P_j \in \PartySet$, if not sent earlier.

* Upon receiving the message $(\prepare, b)$ for some $b \in \{0,1,\lambda\}$ from parties in set $\PrepSet^{(b)} = \PartySet \setminus Z$ for some $Z \in \Z_s$, set $\vals = \vals \cup \{b\}$.

* Upon adding the first value $b$ to $\vals$, send $(\propose,b)$ to every party $P_j \in \PartySet$.

* Upon receiving $(\propose, b)$ messages from a set of parties $\PropSet = \PartySet \setminus Z$ for some $Z \in \Z_s$ on values $b \in \vals$, let
$\prop \subseteq \vals$ be the set of values carried by those messages.
Output $\prop$.

The guarantees provided by $\Prop$ are proven in a series of lemmas below. In the below proofs, we assume that $Z^\star$ is the set of corrupt parties.

Suppose that the network is asynchronous. If two honest parties $P_i$ and $P_j$ output $\{b\}$ and $\{b'\}$ respectively, then $b = b'$.

Since $P_i$ outputs $\{b\}$, it must have received $(\propose, b)$ from a set of parties $\PropSet = \PartySet \setminus Z$ for some $Z \in \Z_s$.
Similarly, since $P_j$ outputs $\{b'\}, it$ must have received $(\propose, b')$ from a set of parties $\PropSet' = \PartySet \setminus Z'$ for some $Z' \in \Z_s$.
Let $\PropSet_\Hon$ and $\PropSet_\Hon$ be the set of honest parties in $\PropSet$ and $\PropSet'$ respectively. Since $\Z_s, \Z_a$ satisfy the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$
condition and $Z^{\star} \in \Z_a$, it follows
that  $\PropSet_\Hon \cap \PropSet'_\Hon \neq \emptyset$. Let $P_h \in \PropSet_\Hon \cap \PropSet'_\Hon$.
If $b \neq b'$, this would mean that $P_h$ has sent both $(\propose, b)$ and $(\propose, b')$, which is a contradiction, since an honest party sends
at most one $\propose$ message as per the protocol.

Suppose that the network is asynchronous. If no honest party has input $v$, then no honest party outputs $\prop$ containing $v$.

If $v$ was not input by any honest party, then no honest party sends $(\prepare,v)$ in step $2$. Hence, no honest party receives $(\prepare,v)$ from a set of parties $S^{(v)}$
which satisfies the $\Q^1(S^{(v)}, \Z_s)$ condition during step $3$, since such a set must contain at least one honest party. Consequently, no honest party sends $(\propose,v)$. Thus, no honest party adds $v$ to $\vals$ and no honest party outputs $\prop$ containing $v$.

Suppose that the network is asynchronous. If an honest party sends $(\propose,b)$, then all honest parties add $b$ to $\vals$.

Suppose that some honest party $P_i$ sends $(\propose,b)$. This means that $P_i$ received $(\prepare,b)$ from a set of parties $\PrepSet = \PartySet \setminus Z$ for some $Z \in \S_s$. Thus, from the conditions $\Con$, the set of honest parties $\PrepSet_\Hon$ in $\PrepSet$ satisfy the $\Q^1(\PrepSet_\Hon,\Z_s)$ condition. Thus, every honest party eventually receives $(\prepare,b)$ from a set of parties $S$ which satisfies the $\Q^1(S,\Z_s)$ condition, and sends $(\prepare,b)$. This further implies that every honest party receives $(\prepare,b)$ from the set of parties $\Hon$, which is $\PartySet \setminus Z^\star$ for $Z^\star \in \Z_a \subseteq \Z_s$. Consequently, every honest party adds $b$ to $\vals$.

The following lemmas help prove liveness.

Suppose that the network is asynchronous. If all honest parties hold one of two inputs, say $v_0$ and $v_1$, then all honest parties eventually compute
an output.

We first show that every honest party eventually sends a $\propose$ message.

Let $\Hon_0$ and $\Hon_1$ be the sets of honest parties holding inputs $v_0$ and $v_1$ respectively
and let $\Hon$ be the set of honest parties.
We know that due to the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition, $\Z_s$ satisfies the
$\Q^{(2)}(\Hon, \Z_s)$ condition. Now, consider the following cases.

– Case 1 - $\Hon_0$ satisfies the $\Q^1(\Hon_0,\Z_s)$ condition: In this case, $\Hon_0$ is a candidate for the set $S^{(v_0)}$, since all
the parties in $\Hon_0$ send $(\prepare,v_0)$ in step $2$.

– Case 2 - $\Hon_0$ does not satisfy the $\Q^1(\Hon_0,\Z_s)$ condition: In this case, $\Z_s$
must satisfy the $\Q^1(\Hon_1,\Z_s)$ condition, since $\Z_s$ satisfies the
$\Q^{(2)}(\Hon, \Z_s)$ condition. Then similar to what was argued in the previous case, $\Hon_1$ is a candidate for the set $S^{(v_1)}$.

Let $v_b$ be the input corresponding to the candidate set $S^{(v_b)}$. Every honest party will now eventually send $(\prepare, v_b)$ in step $3$.
This would mean that the set of honest parties $\Hon = \PartySet \setminus Z^\star$ is a candidate for the set $\PrepSet^{(v_b)}$.
Thus, every honest party eventually adds $v_b$ to $\vals$ and sends a $\propose$ message for some value $v_b$.
This way, every honest party eventually receives $\propose$ messages from every other honest party for $v_b$ and thus, the set $\Hon$ also forms a candidate for the set $\PropSet$. Thus, all
honest parties eventually compute an output.

If the network is synchronous and if all honest parties participate with input $v$, then all honest parties output $\prop = \{v\}$ at time $2\Delta$.

Let $\Hon = \PartySet \setminus Z^\star$ be the set of honest parties. Then
in step $2$, every party in $\Hon$ sends $(\prepare,v)$ to every party, which is delivered within $\Delta$ time.
Thus, at time $\Delta$, all the parties in $\Hon$ receive $(\prepare,v)$ from the parties in $\Hon$ and add $v$ to $\vals$. Further, no other value $v^{\star}$ will be
added to $\vals$, since only the parties in $Z^{\star}$ may send a $\prepare$ message for $v^{\star}$ and $\Z_s$
does not satisfy the $\Q^{(1)}(Z^\star, \Z_s)$ condition.
Thus, all the parties in $\Hon$ send $(\propose, v)$ in step $5$, which gets delivered to all the parties in $\Hon$ at time $2\Delta$.
Consequently, all the parties in $\Hon$ output $\prop = \{v\}$.

Protocol $\Prop$ incurs a communication of $\Order(n^2)$ bits.

The proof follows from the fact that each party sends $(\prepare,b)$ to every other party at most once for any value of $b \in \{0,1,\lambda\}$.

§.§.§ The Graded Agreement Protocol

We now present protocol $\Vote$ (Figure <ref>) based on protocol $\Prop$. The protocol cleverly “stitches" together two instances of $\Prop$, by defining the input for the second instance based on the output from the first instance. Each party, with input either $0$ or $1$, participates in the first instance of $\Prop$ with their input. Since the parties participate with one of two inputs, this instance will
eventually complete (in an asynchronous network),
and the parties obtain an output, say $\prop_1$. Only if $\prop_1$ is a singleton set, say $\{b\}$, for some party, then that party participates in the second instance of $\Prop$ with the input $b$. Otherwise, it participates in the second instance with a default input of $\lambda$. Since no two honest parties can output different singleton sets for $\prop_1$, this ensures that each honest party participates with an input of either $b$ or
$\lambda$ (in an asynchronous network).
Thus, the second instance of $\Prop$ also eventually completed with an output, say $\prop_2$. This also ensures that $\prop_2$ can contain only values $b$ and $\lambda$. If $\prop_2$ contains only $b$ for some honest party, then that party outputs $b$ with a grade of $2$. If $\prop_2$ contains $b$ along with $\lambda$, then the party outputs $b$ with a grade of $1$.
Else, if $\prop_2$ contains only $\lambda$, then the party outputs $\bot$ with a grade of $0$.  If the network is synchronous and all honest parties start the protocol with the same input, then
both $\prop_1$
as well as $\prop_2$ will be a singleton set containing that value and hence all honest parties will output that value with the highest grade.

$\Vote(\PartySet, \Z_s, \Z_a)$Asynchronous graded agreement with synchronous validity. The above code is executed by every party $P_i$ with input $v \in \{0,1\}$.fig:GA

* On having the input $v \in \{0, 1 \}$, set $b_1 = v$. Participate in an instance of the protocol $\Prop$ with input $b_1$ and wait for its completion. Let
$\prop_1$ be the output computed during the instance of $\prop$.

* If $\prop_1 = \{b\}$ for some $b \in \{0, 1 \}$, then set $b_2 = b$. Else, set $b_2 = \lambda$. Then
participate in an instance of the protocol $\Prop$ with input $b_2$ and wait for its completion. Let $\prop_2$ be the output computed from this instance of $\prop$.

* If $\prop_2 = \{b'\}$ and $b' \neq \lambda$, then output $(b', 2)$. If $\prop_2 = \{b', \lambda\}$ where $b' \in \{0, 1 \}$, then output $(b', 1)$. Else, if $\prop_2 = \{\lambda\}$, then
output $(\bot, 0)$.

We now proceed to prove the properties of the protocol $\Vote$.

Protocol $\Vote$ achieves the following in a synchronous network, where $\TimeVote = 4\Delta$.

– (a) $\Z_s$-Liveness:
If all honest parties participate in the protocol with the same input, then at time $\TimeVote$,
all honest parties obtain an output.

– (b) $\Z_s$-Graded Validity: If every honest party's input is $b$, then all honest parties with an output, output $(b, 2)$.

If all honest parties participate in the protocol $\Vote$ with the same input $b$, then
from Lemma <ref>, all honest parties output $\prop_1 = \{b\}$ at time $2\Delta$.
Thus, all honest parties participate with input $b_2 = b$ in the second instance of $\Vote$ and,
once again from Lemma <ref>, output $\prop_2 = \{b\}$ at time $4 \Delta$. Thus, all honest parties output $(b, 2)$.

Protocol $\Vote$ achieves the following in an asynchronous network.

– (a) $\Z_a$-Liveness:  If all honest parties participate in the protocol with a binary input, then each honest party eventually obtains an output.

– (b) $\Z_a$-Graded Validity:  If every honest party's input is $b$, then all honest parties with an output, output $(b, 2)$.

– (c) $\Z_a$-Graded Consistency:  If two honest parties output grades $g, g'$, then $|g - g'| \leq 1$ holds; moreover,
if two honest parties output $(v, g)$ and $(v', g')$ with $g, g' \geq 1$, then $v = v'$.

Since each honest party participates with a binary input,
from Lemma <ref>, each party eventually outputs some value for $\prop_1$ during the first instance of $\prop$. Now there are two possible cases.

– Case 1 - Some honest party outputs $\{b\}$ as its value for $\prop_1$ where $b \in \{0, 1 \}$:
From Lemma <ref>, no honest party can output $\{b'\}$, where $b \neq b'$, as $\prop_1$.
Thus, each honest party participates with input either $b$ or $\lambda$ for the second instance of $\prop$.

– Case 2 - No honest party outputs $\{b\}$ as its value for $\prop_1$ for any $b \in \{ 0, 1\}$: In this case, all honest parties participate with input $\lambda$ in the second instance of $\prop$.

In either case, the honest parties participate in the second instance of $\Prop$ with no more than two different inputs.
Thus, from Lemma <ref>, all parties eventually compute some value for $\prop_2$ during the second instance of $\prop$ and hence compute some
output for protocol $\Vote$. This proves the $\Z_a$-Liveness.

We next prove the $\Z_a$-Graded Consistency. We first show that the grades output by any two parties differ by at most $1$. For this,
suppose that some honest party $P_i$ outputs $(b, 2)$. We show that no other honest party $P_j$ can output $(\bot, 0)$.
Since $P_i$ output $(b, 2)$, from Lemma <ref>, $P_j$ cannot output $\prop_2 = \{\lambda\}$. Thus, $P_j$ cannot output $(\bot, 0)$.
Next, we show that any two honest parties which output non-zero grades must output the same value. Similar to what was argued for the proof of $\Z_a$-Liveness,
there exists a bit $b$ such that each honest party participates in $\Prop$ with input $b$ or $\lambda$ during step $2$.
Thus, $\prop_2 \subseteq \{b,\lambda\}$ for every honest party. This means that any honest party which outputs a non-zero grade must output it along with the bit $b$.

We finally prove the $\Z_a$-Graded Validity. Suppose that each honest party participates with the same input bit $b$.
From Lemma <ref>, we know that all honest parties output some value for $\prop_1$. From Lemma <ref>, all honest parties must output $\prop_1 = \{b\}$.
Hence, all honest parties participate in $\Prop$ in step $2$ with input $b$. By the same argument, all honest parties output $\prop_2 = \{b\}$. Hence, all honest parties output $(b,2)$.

Protocol $\Vote$ incurs a communication of $\Order(n^2)$ bits.

The proof follows from Lemma <ref>, since $\Prop$ is invoked twice in the protocol.

§.§ Properties of the Protocol $\ABA$

In this section, we prove the properties of the protocol $\ABA$ (see Fig <ref> for the protocol steps). We start with the properties in the asynchronous network first, which mostly follows from [23]
and are recalled from [23].
We start with the validity property.

In protocol $\ABA$, if the network is asynchronous and all honest parties have the same input bit $b$, then
all honest parties eventually output $b$.

Let $Z^{\star} \in \Z_a$ be the set of corrupt parties.
If every honest party has the same input bit $b$,
then from the $\Z_a$-Graded Validity of $\Vote$ in the asynchronous network (Lemma <ref>),
all honest parties eventually output $(b, 2)$ at the end of the first as well as the second instance of the $\Vote$ protocol
during the first iteration. Consequently, every honest party eventually sends a signed $(\ready, b)$ message to all the parties and only the parties
in $Z^{\star}$ may send a signed $(\ready, \overline{b})$ message. It now follows easily from the steps of the output computation stage that no honest party ever
sends a signed $(\ready, \overline{b})$ message and all hence honest parties eventually output $b$.

We next prove the consistency property.

In protocol $\ABA$, if the network is asynchronous and if any honest party outputs $b$, then
every other honest party eventually outputs $b$.

Let $P_i$ be the first honest party who sends a signed $\ready$ message for some bit $b \in \{0, 1 \}$, during some iteration, say iteration $r$.
We show that no honest party ever sends a signed $(\ready, \overline{b})$ message during iteration $r$ or in the subsequent iterations.