Since $P_i$ has sent a signed $\ready$ message for $b$, it implies that $P_i$ outputs $(b, 2)$ in the second instance of the $\Vote$ protocol during iteration $r$ and sets $\committed$ to $\true$.
Then, from the $\Z_a$-Graded Consistency of
$\Vote$ in the asynchronous network (Lemma <ref>),
every other honest party
outputs either $(b, 2)$ or $(b, 1)$ in the second instance of the $\Vote$ protocol during iteration $r$. Consequently, no other
honest party sends the signed $(\ready, \overline{b})$ message during iteration $r$. Also, from the protocol steps, all honest parties
update their input
to $b$ for the next iteration. This further implies that all honest parties will continue to input $b$
to each subsequent invocation of $\Vote$, ignoring the output of $\CoinFlip$, for as long as they continue running.
Consequently, no honest party ever sends a signed $(\ready, \overline{b})$ message.

Now let some honest party, say $P_h$, computes the output $b$ during iteration $k$. This
implies that $P_h$ receives the signed $(\ready, b)$ message from a set of parties, say ${\cal T}$, such that
$\PartySet \setminus {\cal T} \in \Z_s$. The set ${\cal T}$ is bound to have at least one honest party, due to the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition, implying that
at least one honest party has sent a signed $(\ready, b)$ message, either during the iteration $k$ or some previous iteration.
From the protocol steps, $P_h$ sends $\C(b)$, the set of signed $(\ready, b)$ messages of the parties in ${\cal T}$ to all other parties, which get eventually delivered.
Moreover, as shown above,
no honest party will ever send a signed $(\ready, \overline{b})$ message.
Consequently, every honest party
eventually receives sufficiently many numbers of signed $(\ready, b)$ messages
and outputs $b$.

We next prove that at the end of each iteration, the updated value of all honest parties will be the same with the probability
at least $\frac{1}{2n}$.

In protocol $\ABA$, if the network is asynchronous and if
all honest parties participate during iteration $k$, then with probability at least $\frac{1}{2n}$, all honest parties have the same updated bit
$b$ at the end of iteration $k$.

To prove the lemma statement, we consider an event $\Agree$, which denotes that all honest parties have the same input for the second instance
of $\Vote$ during iteration $k$. If the event $\Agree$ occurs, then from the $\Z_a$-Graded Validity of $\Vote$ in the asynchronous
network (Lemma <ref>),
all honest parties will have the same
updated bit at the end of iteration $k$. We show that the event $\Agree$ occurs during iteration $k$ with a probability of at least $\frac{1}{2n}$.
For this, we consider two different possible cases with respect to the output from the first instance of $\Vote$ during iteration $k$.

– Case I: No honest party obtains an output $(b, 2)$ for any $b \in \{0, 1 \}$ during the first instance of $\Vote$.
In this case, all honest parties set the output from the instance of $\CoinFlip$ during iteration $k$ as the input for the second instance of $\Vote$.
From the $(\Z_a, p)$-commonness of $\CoinFlip$ in asynchronous network [23],
all honest parties will have the same output bit $\Coin_k$ from the instance of $\CoinFlip$ with a probability of at least
$p = \frac{1}{n} > \frac{1}{2n}$.

– Case II: Some honest party obtains an output $(b, 2)$ during the first instance of $\Vote$.
In this case, the $\Z_a$-Graded Consistency of $\Vote$ in the asynchronous
network (Lemma <ref>)
ensure that all honest parties obtain the output
$(b, 2)$ or $(b, 1)$ from the first instance of $\Vote$. Moreover, from the protocol steps, the output of the
instance of $\CoinFlip$ during iteration $k$ is not revealed, until the first honest party generates an output from the first instance of $\Vote$ during iteration
$k$. Consequently, the output bit $b$ from the first instance of $\Vote$ is independent of the output of $\CoinFlip$.
From the $(\Z_a, p)$-commonness of $\CoinFlip$ in asynchronous network [23],
all honest parties will have the same output bit $\Coin_k$ from the instance of $\CoinFlip$ with a probability of at least
$p = \frac{1}{n}$.  Then the probability that $\Coin_k = b$ holds is at least $\frac{1}{2} \cdot \frac{1}{n} = \frac{1}{2n}$ and with this probability,
all honest
parties will have the same input for the second instance of $\Vote$.

We next derive the expected number of iterations required in the protocol $\ABA$ for the honest parties to produce an output.
This automatically gives the expected running time in an asynchronous network, since each iteration takes a constant time.

If the network is asynchronous, then
in protocol $\ABA$, it requires expected $\Order(n^2)$
iterations for the honest parties to compute an output.

To prove the lemma, we need to derive the expected number of iterations, until all the honest parties have the same input during the second instance
of $\Vote$ of an iteration. This is because once all the honest parties have the same input during the second instance
of $\Vote$ of an iteration, then all honest parties will set $\committed$ to $\true$ at the end of that iteration and start sending signed $\ready$ messages, followed
by computing an output.
Let $\tau$ be the random variable
which counts the number of iterations until all honest parties
have the same input during the second instance
of $\Vote$ in an iteration.
Then the probability that $\tau = k$ is given as:

\begin{align*}
\Pr(\tau = k) &= \Pr(\tau \neq 1)\cdot\Pr (\tau \neq 2 \mid \tau \neq 1)\cdot \ldots
\cdot Pr(\tau \neq (k-1) \mid \tau \neq 1 \cap \ldots \cap  \\
& \tau \neq (k-2))  \cdot  \Pr(\tau = k \mid \tau \neq 1 \cap \ldots \cap \tau \neq    (k-1)).
\end{align*}

From Lemma <ref>,
every multiplicand on the right-hand side in
the above equation, except the last one, is upper bounded by $(1 - \frac{1}{2n})$
and the last multiplicand is upper bounded by $\frac{1}{2n}$. Hence, we get

\[ \Pr(\tau = k) \leq (1 - \frac{1}{2n})^{k-1}(\frac{1}{2n}).\]

Now the expected
value $E(\tau)$ of $\tau$ is computed as follows:

\begin{align*}
E(\tau) &=  \sum_{k=0}^{\infty} \tau \cdot \Pr(\tau = k) \\
&\leq \sum_{k=0}^{\infty}k(1 - \frac{1}{2n})^{k-1}(\frac{1}{2n})\\
&= \frac{1}{2n}\sum_{k=0}^{\infty}k(1 - \frac{1}{2n})^{k-1}\\
&= \frac{1}{1 - (1 - \frac{1}{2n})} + \frac{1 - \frac{1}{2n}}{\Big(1 - (1 -
\frac{1}{2n})\Big)^2}\\
&= 2n + 4n^2 - 2n = 4n^2
\end{align*}

The expression for $E(\tau)$ is a sum of $AGP$ up to infinite terms, which is
given by $\frac{a}{1 - r} + \frac{dr}{(1-r)^2}$, where $a=1$, $r= 1 -
\frac{1}{2n}$ and $d = 1$. Hence, we have $E(\tau) \leq 4n^2$.

We finally prove the properties of the protocol $\ABA$ in a synchronous network.

If the network is synchronous and if all honest parties have the same input $b \in \{ 0, 1\}$ during $\ABA$, then all honest parties output $b$,
at time $\TimeABA = \TimeCoinFlip + 2\TimeVote + \Delta$.

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.
If all the parties in $\Hon$ participate with input $b$, then from the $\Z_s$-liveness
and $\Z_s$-Graded Validity of $\Vote$ in the synchronous network (Lemma <ref>), all the parties in $\Hon$ output
$(b, 2)$ during the first instance of $\Vote$ at time $\TimeVote$ in the first iteration. The $\Z_s$-Guaranteed Liveness of $\Vote$ in the synchronous network [23]
ensures that all honest parties compute some output from the instance of $\CoinFlip$ during the first iteration at the time $\TimeVote + \TimeCoinFlip$.
Since the parties in $\Hon$ output $(b, 2)$ during the first instance of $\Vote$, they participate with input $b$ during the second instance of $\Vote$.
Consequently,  from the $\Z_s$-liveness
and $\Z_s$-Graded Validity of $\Vote$ in the synchronous network,
all the parties in $\Hon$ compute the output $(b, 2)$ during the second instance of $\Vote$ in the first iteration at the time $2\TimeVote + \TimeCoinFlip$.
Hence every party in $\Hon$ sends a signed $\ready$ message for $b$ at the time $2\TimeVote + \TimeCoinFlip$, which gets delivered at the time $\TimeABA$.
Moreover, only the parties in $Z^{\star}$ may send a signed $\ready$ message for $\overline{b}$.
Since $\PartySet \setminus \Hon = Z^{\star} \in \Z_s$ and since $\Hon \not \in \Z_s$ (due to the $\Q^{(2)}(\PartySet, \Z_s)$ condition),
it follows that all the parties in $\Hon$ will have sufficiently many signed $\ready$ messages for $b$ at the time $\TimeABA$ to output $b$.

The proof of Theorem <ref> now follows from Lemma <ref>-<ref>.
The communication complexity follows from the communication complexity of $\CoinFlip$ [23] and the communication complexity of $\Vote$ (Lemma <ref>)
and the fact that in a synchronous network, only a constant number of invocations of $\Vote$ and $\CoinFlip$ are involved, while in an asynchronous network,
there are $\mbox{poly}(n)$ invocations of $\Vote$ and $\CoinFlip$ in expectation.

Suppose that the network is synchronous. $\Vote$ achieves $\Z_s$-Liveness and $\Z_s$-Graded Validity.

From Lemma <ref> all honest parties output $\prop_1 = \{v\}$ at time $2 \cdot \Delta$. Thus, all honest parties participate with input $b_2 = v$ and, once again from Lemma <ref>, output $\prop_2 = \{v\}$ at time $4 \cdot \Delta$. Thus, all honest parties output $(v,2)$.

§ PROPERTIES OF OUR NETWORK AGNOSTIC ICP

In this section, we prove the properties of our network-agnostic ICP (see Fig <ref> for the formal details). Throughout this section, we assume that $\Z_s$ and $\Z_a$ satisfy the conditions
$\Z_a \subset \Z_s$, $\Q^{(2)}(\PartySet, \Z_s)$, $\Q^{(3)}(\PartySet, \Z_a)$ and $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$.

If $\mathsf{S}, \mathsf{I}$ and $\mathsf{R}$ are honest, then the following hold during protocol $\Auth$ and $\Reveal$.

– $\AdvStruct_s$-Correctness: In a synchronous network, each honest party sets $\authCompleted_{(\S, \INT, \Receiver)}$
to $1$ during $\Auth$ at time $\TimeAuth = \Delta + 4\TimeBC$. Moreover $\mathsf{R}$ outputs $s$ during $\Reveal$ which takes $\TimeReveal = \Delta$ time.

– $\AdvStruct_a$-Correctness:  In an asynchronous network, each honest
party eventually sets $\authCompleted_{(\S, \INT, \Receiver)}$
to $1$ during $\Auth$ and $\mathsf{R}$ eventually outputs $s$ during $\Reveal$.

We first start with the synchronous network. Let $Z^{\star} \in \Z_s$ be set of corrupt parties and let
$\Hon = \PartySet \setminus Z^{\star}$ be the set of honest parties.
During $\Auth$, $\mathsf{S}$ chooses a random $t$-degree signing-polynomial $F(x)$ such that $s = F(0)$ holds,
a random $t$-degree masking-polynomial $M(x)$, and computes
verification points $(\alpha_i, v_i, m_i)$ such that $v_i = F(\alpha_i)$ and $m_i = M(\alpha_i)$ hold. $\mathsf{S}$ then
sends the signing-polynomial $F(x)$ and masking-polynomial $M(x)$  to $\mathsf{I}$, and the
corresponding verification-point $(\alpha_i, v_i, m_i)$ to each verifier $P_i$.
Consequently, each verifier in $\Hon$
receives its verification-point by time $\Delta$, and indicates this by broadcasting $(\Received,i)$. Since $\PartySet \setminus \Hon = Z^{\star} \in \AdvStructure_s$,
from the $\Z_s$-validity of $\BC$ in the synchronous network (see Theorem <ref>),
it follows that at time $\Delta + \TimeBC$, $\mathsf{S}$ will find a set $\R$, such that $\PartySet \setminus \R \in \AdvStructure_s$, where
each verifier in $\R$ has indicated that it has received its verification-point. Consequently, $\mathsf{S}$ will broadcast $\R$ at time $\Delta + \TimeBC$.
From the $\Z_s$-validity of $\BC$ in the synchronous network, $\mathsf{I}$ will receive $\R$ at time $\Delta + 2\TimeBC$.
Moreover, due to the $\Z_s$-Consistency and $\Z_s$-Validity of $\BC$ in the synchronous network,
party $\mathsf{I}$ would have gotten $(\Received,i)$, corresponding to every verifier $P_i \in \R$, by time $\Delta + 2\TimeBC$. Furthermore, $\PartySet \setminus \R \in \Z_s$ will hold.
Hence, $\mathsf{I}$ will randomly select $d \in \F$, compute $B(x) = dF(x) + M(x)$, and broadcast $(d, B(x))$. From the $\Z_s$-validity of $\BC$ in the synchronous network,
this will be delivered to every honest party, including
$\mathsf{S}$, by time $\Delta + 3\TimeBC$.
Moreover,  $\mathsf{S}$ will find that $B(\alpha_j) = dv_j + m_j$ holds
for all the verifiers $P_j \in \R$. Consequently, $\mathsf{S}$ will broadcast an $\OK$ message, which is received by every $P_i \in \Hon$ at time $\Delta + 4\TimeBC$, due to the
$\Z_s$-validity of $\BC$ in the synchronous network.
Thus, each $P_i \in \Hon$ sets $\authCompleted_{(\S, \INT, \Receiver)}$
to $1$, while $\mathsf{I}$ additionally sets $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$ to $F(x)$ at time $\Delta + 4 \TimeBC$.

During $\Reveal$, $\mathsf{I}$ will send $F(x)$ to $\mathsf{R}$, and each verifier $P_i \in \Hon \cap \R$ will send its
verification point $(\alpha_i,v_i,m_i)$ to $\mathsf{R}$. These points and the polynomial $F(x)$ are received by
$\mathsf{R}$ within $\Delta$ time. Moreover, the condition $v_i = F(\alpha_i)$ will hold true for these points, and consequently, these points
will be accepted.
Since $\R \setminus (\Hon \cap \R) \subseteq Z^{\star} \in \AdvStructure_s$, it follows that at time $\Delta$, receiver
$\mathsf{R}$ will find a subset $\R' \subseteq \R$ where $\R \setminus \R' \in \AdvStructure_s$, such that the points corresponding to
all the parties in $\R'$ are accepted.
This implies that $\mathsf{R}$ will output $s = F(0)$ within time $\Delta$.

The proof for the asynchronous case is similar as above, except that each “favourable" event occurs eventually, and follows from the fact that every set in $\Z_a$ is a subset of some set in $\Z_s$. Moreover, we rely on the
properties of $\BC$ in the asynchronous network.

We next prove the privacy property, for which we again need to consider an honest $\S, \INT$ and $\Receiver$.

If $\S, \INT$ and $\Receiver$ are honest, then the view of $\Adv$ remains independent of $s$ during $\Auth$ and $\Reveal$, irrespective of the network

We prove privacy in a synchronous network. The privacy in an asynchronous network automatically follows, since $\Z_a$ is a subset of $\Z_s$. Let $t = \max\{ |Z| :  Z \in \AdvStruct_s 	\}$ and let $Z^\star \in \AdvStructure_s$ be the set of corrupt parties.
For simplicity and without loss of generality, let
$|Z^\star| = t$.
During $\Auth$, the adversary $\Adv$ learns  $t$ verification-points $\{(\alpha_i, v_i, m_i) \}_{P_i \in Z^\star}$.
However, since $F(x)$ is a random $t$-degree polynomial with $F(0) = s$,
the points $\{(\alpha_i, v_i) \}_{P_i \in Z^{\star}}$ are distributed independently of $s$.
That is, for every candidate $s \in \F$ from the point of view of $\Adv$, there is a corresponding unique
$t$-degree polynomial $F(x)$, such that $F(\alpha_i) = v_i$ holds corresponding to every $P_i \in Z^{\star}$.

During $\Auth$, the adversary $\Adv$ also learns $d$ and the blinded-polynomial $B(x) = dF(x) + M(x)$.
However, this does not add any new information about $s$ to the view of the adversary. This is because
$M(x)$ is a random $t$-degree polynomial and $\Adv$ learns $t$ points on $M(x)$, corresponding to the parties in $Z^{\star}$.
Hence, for every candidate $M(x)$ polynomial from the point of view of
$\Adv$ where $M(\alpha_i) = m_i$ holds for every $P_i \in Z^{\star}$, there is a corresponding unique
$t$-degree polynomial $F(x)$, such that $F(\alpha_i) = v_i$ holds corresponding to every $P_i \in Z^{\star}$, and where
$dF(x) + M(x) = B(x)$.
Finally, $\Adv$ does not learn anything new about $s$ during $\Reveal$, since the verification-points and the signing-polynomial are sent only to $\mathsf{R}$, who is honest
as per the lemma conditions.

We next prove the unforgeability property, for which we have to consider a corrupt $\INT$.

If $\mathsf{S}, \mathsf{R}$ are honest, $\mathsf{I}$ is corrupt
and if $\mathsf{R}$ outputs $s' \in \F$ during $\Reveal$, then $s' = s$ holds except with
probability at most $\errorAICP \defined \frac{nt}{|\F| - 1}$, where $t = \max\{ |Z| :  Z \in \AdvStruct_s \}$, irrespective of the network type.

Let $\Hon$ be the set of honest parties in $\PartySet$ and let $Z^{\star} = \PartySet \setminus \Hon$ be the set of corrupt parties.
Since $\mathsf{R}$ outputs $s'$ during $\Reveal$, it implies that during $\Auth$, the variable
$\authCompleted_{(\S, \INT, \Receiver)}$ is set to $1$ by $\mathsf{R}$. This further implies that
$\mathsf{S}$ has broadcasted an $\OK$ message during $\Auth$, which also
implies that during $\Auth$,
$\mathsf{I}$ had broadcasted a $t$-degree blinded-polynomial $B(x)$, and $\mathsf{S}$ broadcasted the set $\R$. Furthermore,
$\mathsf{S}$ has verified that
$B(\alpha_i) = dv_i + m_i$ holds for every verifier $P_i \in \R$.
Now during $\Reveal$, if $\mathsf{I}$ sends $F(x)$ as $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$ to $\mathsf{R}$, then
$s' = s$ holds with probability $1$.
So, consider the case when $\mathsf{I}$ sends $F'(x)$ as $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$ to $\mathsf{R}$, where
$F'(x)$ is a $t$-degree polynomial such that $F'(x) \neq F(x)$ and where $F'(0) = s'$. In this case, we claim that except with probability at most $\frac{nt}{|\F| - 1}$,
the verification-point of no honest verifier from $\R$ will get accepted by $\mathsf{R}$ during $\Reveal$, with respect to $F'(x)$. Now, assuming that the claim is true, the
proof follows using the following arguments, depending upon the network type.

– Synchronous Network:

In this case, all the verifiers in $\Hon$ will be present in $\R$. This is because, each verifier $P_i \in \Hon$ would have received its verification-point from $\S$ during $\Auth$, within time $\Delta$ and
indicates this by broadcasting $(\Received, i)$, which is received by $\S$ at time $\Delta + \TimeBC$. Let $\R'$ be the set of verifiers from which $\mathsf{R}$ receives verification points which it accepts. Since the
verification point of none of the honest verifier will be accepted.
Hence $(\Hon \cap \R') = \emptyset$ and so
$\Hon \subseteq \R \setminus \R'$ must hold. Since $\Hon$ satisfies the $\Q^1(\PartySet,\Z_s)$ condition, $\R \setminus \R' \in \Z_s$ will never hold true. Hence, $\mathsf{R}$ will not output $s' \neq s$.

– Asynchronous Network: In this case, we first note that $\Z_s$ and $\Z_a$ satisfy the $\Q^{(1, 1)}(\R, \Z_s, \Z_a)$ condition. This is because
$\PartySet \setminus \R \in \Z_s$ and $\Z_s$ and $\Z_a$ satisfy the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition. From the steps of $\Reveal$, it follow that for
$\Receiver$ to output $F'(0)$, $\Receiver$ should find a subset of verifiers $\R' \subseteq \R$, where $\R \setminus \R' \in \Z_s$, such that the verification-points of all the verifiers in
$\R'$ are accepted by $\Receiver$. This further implies that $\R' \cap \Hon \neq \emptyset$, as  $\Z_a$ satisfies the $\Q^{(1)}(\R', \Z_a)$ condition.
And hence $\R'$ has at least one honest verifier, whose verification-point is accepted with respect to $F'(x)$. However, from the above claim, it is not possible and hence
$\mathsf{R}$ will not output $s' \neq s$.

We now prove the claimed statement. So consider an arbitrary verifier $P_i \in \Hon \cap \R$ from whom $\mathsf{R}$ receives the verification-point $(\alpha_i,v_i,m_i)$ during $\Reveal$.
This point can be accepted with respect to $F'(x)$, only if either of the following holds.

* $v_i = F'(\alpha_i)$:
This is possible with probability at most $\frac{t}{|\F| - 1}$.
This is because $F'(x)$ and $F(x)$, being distinct $t$-degree polynomials, can have  at most $t$ points in common.
And the evaluation-point $\alpha_i$ corresponding to $P_i$, being randomly selected from $\F - \{0\}$, will not be known to

* $dv_i + m_i \neq B(\alpha_i)$: This is impossible, as otherwise $\mathsf{S}$ would have not broadcasted $\OK$ during
$\Auth$, which is a contradiction.

As there could be up to $n - 1$ honest verifiers in $\R$, it follows from the union bound that except with probability at most $\frac{nt}{|\F| - 1}$,
the verification-point of no honest verifier from $\R$ will get accepted by $\mathsf{R}$ during $\Reveal$, with respect to $F'(x)$.

We next prove the non-repudiation property, for which we have to consider a corrupt $\S$.

If $\mathsf{S}$ is corrupt, $\mathsf{I}, \mathsf{R}$ are honest
and if $\mathsf{I}$ sets $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$ during $\Auth$, then the following hold, except with probability at most $\frac{n}{|\F| - 1}$.

– $\AdvStruct_s$-Non-Repudiation:  In a synchronous network, $\mathsf{R}$ outputs $s$ during $\Reveal$, which takes $\TimeReveal = \Delta$ time.

– $\AdvStruct_a$-Non-Repudiation: In an asynchronous network, $\mathsf{R}$ eventually outputs $s$ during during $\Reveal$.

Let $\Hon$ be the set of honest parties in $\PartySet$ and $Z^{\star}$ be the set of corrupt parties, where $\Hon = \PartySet \setminus Z^{\star}$.
Since  $\mathsf{I}$ has set $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$ during $\Auth$, it implies that $\mathsf{I}$ has set the variable
$\authCompleted_{(\S, \INT, \Receiver)}$ to $1$. This further implies that $\mathsf{I}$ has broadcasted
$(d, B(x))$, where $B(x) = dF(x) + M(x)$, and where $F(x)$ and $M(x)$ are the $t$-degree
signing and masking-polynomials received by $\mathsf{I}$ from $\mathsf{S}$.
Moreover, $\mathsf{I}$ also received the set of supporting verifiers $\R$ from the broadcast of $\mathsf{S}$, and verified that $\PartySet \setminus \R \in \Z_s$ holds.
Furthermore, $\mathsf{S}$ has broadcasted an $\OK$ message.
Consequently, from the consistency properties of $\BC$ (see Theorem <ref>),
irrespective of the network type, all honest parties including $\mathsf{R}$ eventually set $\authCompleted_{(\S, \INT, \Receiver)}$ to $1$.
$\mathsf{I}$ sets $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$ to $F(x)$, where
$s = F(0)$.
During $\Reveal$, $\mathsf{I}$ sends
$F(x)$ to $\mathsf{R}$. Moreover, every verifier $P_i \in \Hon \cap \R$ sends its verification-point
$(\alpha_i,v_i,m_i)$ to $\mathsf{R}$.
In a synchronous network, these will be received by $\mathsf{R}$ within time $\Delta$,
while in an asynchronous network, these will be eventually received by $\mathsf{R}$.
We claim that except with probability at most $\frac{n}{|\F|-1}$,
all these verification-points are  accepted by $\mathsf{R}$.
Now, assuming that the claim is true, the proof follows from the fact that
$\Hon \cap \R = \R \setminus Z^{\star}$, and $Z^{\star} \in \Z_s$ holds, irrespective of the network type (since $\Z_a \subset \Z_s$).
Consequently, $\mathsf{R}$ accepts the verification-points from a subset of the verifiers
$\R' \subseteq \R$ where $\R \setminus \R' \in \AdvStructure_s$. And hence it outputs $s$, either within
time $\Delta$ in a synchronous network, or eventually, in an asynchronous network.

We now proceed to prove the claim. So consider an arbitrary verifier $P_i \in \Hon \cap \R$ whose verification-point $(\alpha_i, v_i, m_i)$ is received by $\mathsf{R}$
during $\Reveal$. Now, there are two possible cases, depending upon the relationship that holds between $F(\alpha_i)$ and $v_i$
during $\Auth$.

– $v_i = F(\alpha_i)$ holds: In this case, according to the protocol steps of $\Reveal$, the point $(\alpha_i, v_i, m_i)$ is accepted by $\mathsf{R}$.

– $v_i \neq F(\alpha_i)$ holds: In this case, we claim that except with probability at most $\frac{1}{|\F| - 1}$, the condition
$dv_i + m_i \neq B(\alpha_i)$ will hold, implying that the point $(\alpha_i, v_i, m_i)$ is accepted by $\mathsf{R}$.
This is because the only way $dv_i + m_i = B(\alpha_i)$ holds is when $\mathsf{S}$ distributes $(\alpha_i, v_i, m_i)$ to $P_i$
where $v_i \neq F(\alpha_i)$ and $m_i \neq M(\alpha_i)$ holds, and $\mathsf{I}$ selects $d = (M(\alpha_i) - m_i)\cdot(v_i - F(\alpha_i))^{-1}$.
However, $\mathsf{S}$ will not be knowing the random $d$ from $\F \setminus \{ 0\}$ which $\mathsf{I}$ is going to pick, while distributing
$F(x), M(x)$ to $\mathsf{I}$, and $(\alpha_i, v_i, m_i)$ to $P_i$. Hence, the probability that $\INT$ indeed selects $d = (M(\alpha_i) - m_i)\cdot(v_i - F(\alpha_i))^{-1}$
is $\frac{1}{|\F| - 1}$.

As there can be up to $n - 1$ honest verifiers in $\R$, from the union bound, it follows that except with probability at most
$\frac{n}{|\F| - 1}$, the verification-point of all honest verifiers in $\R$ are accepted by $\mathsf{R}$.

We finally derive the communication complexity.

Protocol $\Auth$ incurs a communication of $\Order(n^5 \cdot \log{|\F|} \cdot |\sigma|)$ bits. Protocol
$\Reveal$ incurs a communication of $\Order(n \cdot \log{|\F|})$ bits.

During $\Auth$, signer $\mathsf{S}$ sends $t$-degree polynomials
$F(x)$ and $M(x)$ to $\mathsf{I}$, and verification-points to each verifier. This requires a communication of $\Order(n \cdot \log{|\F|})$ bits.
Intermediary $\mathsf{I}$ needs to broadcast $B(x)$ and $d$ using protocol $\BC$,
while $\S$ needs to broadcast
the set $\R$ using $\BC$. Moreover, $\mathsf{S}$ may need to broadcast $s$ using $\BC$.
By substituting the communication cost of $\BC$ (see Theorem <ref>), the overall communication cost of $\Auth$ turns out to be
$\Order(n^5 \cdot \log{|\F|} \cdot |\sigma|)$ bits.
During $\Reveal$, $\mathsf{I}$ may send $F(x)$ to $\mathsf{R}$, and each verifier may send its verification-point to $\mathsf{R}$.
This incurs a communication of $\Order(n \cdot \log{|\F|})$ bits.

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

§ PROPERTIES OF NETWORK AGNOSTIC VSS

In this section, we prove the properties of the protocol $\VSS$ (see Fig <ref>).  Throughout this section, we assume that $\Z_s$ and $\Z_a$ satisfy the conditions
$\Z_a \subset \Z_s$, $\Q^{(2)}(\PartySet, \Z_s)$, $\Q^{(3)}(\PartySet, \Z_a)$ and $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$.
We start with the properties in a synchronous network and first consider an honest
$\D$. We first show that an honest $\D$ will broadcast some candidate core-sets, which will be accepted by all honest parties. Moreover, adversary will not learn
any additional information about $s$.

If the network is synchronous and $\D$ is honest,
participating  in $\VSS$ with input $s$, then all the following hold, where $\Hon$ is the set of honest parties.

– There exists some $S_p \in \ShareSpec_{\Z_s}$, such that $\D$ broadcasts a message
$(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$ at time $\Delta + \TimeAuth + \TimeBC$,
and every $P_i \in \Hon$ includes $(\D, S_p)$ to the set $\C_i$ at time $\Delta + \TimeAuth + 2\TimeBC$.
Moreover, all the following hold for $q = 1, \ldots, |\Z_s|$.

– If $S_q = \Hon$, then $q \not \in \BroadcastSet$.

– $\W_{q}$ will be either $S_q$ or $(S_p \cap S_q)$. Moreover,
$\Z_s$ will satisfy the $\Q^{(1)}(\W_q, \Z_s)$ condition.

– Corresponding to every $S_q \in \ShareSpec_{\Z_s}$, every honest $P_i \in \W_{q}$ will have the IC-signature
$\ICSig(P_j, P_i, P_k, s_q)$ of every $P_j \in \W_{q}$ for every $P_k \not \in S_q$, such that
the underlying signatures will satisfy the linearity principle.
Furthermore, if any corrupt $P_j \in \W_{q}$ has the IC-signature $\ICSig(P_i, P_j, P_k, s'_q)$ of any honest $P_i \in \W_{q}$ for any $P_k \in \PartySet$, then
$s'_q = s_q$ holds and the underlying signatures will satisfy the linearity principle.

– Corresponding to every $S_q \in \ShareSpec_{\Z_s}$,
every honest $P_i \in S_q$ will have the share $s_q$, except with a probability $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$, at time $\Delta + \TimeAuth + 2\TimeBC + \TimeReveal$, where
$s = s_1 + \ldots + s_{|\Z_s|}$.

– The view of the adversary will be independent of $s$.

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.
We note that $\Hon \in \ShareSpec_{\Z_s}$.
Since $\D$ is honest, it picks the shares $s_1,\dots, s_{|\Z_s|}$ such that $s = s_1 + \dots + s_{|\Z_s|}$ and sends $s_q$ to each party $P_i \in S_q$, corresponding to
every $S_q \in \ShareSpec_{\Z_s}$. These shares are delivered within time $\Delta$. Now consider an arbitrary $S_q \in \ShareSpec_{\Z_s}$.
At time $\Delta$, each party $P_i \in (S_q \cap \Hon)$ starts giving
$\ICSig(P_i, P_j, P_k, s_{qi})$ to every $P_j \in S_q$, for every $P_k \in \PartySet$, where $s_{qi} = s_q$ holds.
Moreover, the linearity principle is followed while generating these IC-signatures.
Then from the $\Z_s$-correctness of $\Auth$ in the synchronous network (Theorem <ref>),
it follows that at time $\Delta + \TimeAuth$, each party $P_i \in (S_q \cap \Hon)$ will receive
$\ICSig(P_j, P_i, P_k, s_{qj})$ from every $P_j \in (S_q \cap \Hon)$, for every $P_k \in \PartySet$, such that $s_{qj} = s_{qi} = s_q$ holds.
Since $S_q$ is arbitrary, it follows that at time $\Delta + \TimeAuth$, every party $P_i \in \Hon$ broadcasts an $\OK(i, j)$ message, corresponding to every
$P_j \in \Hon$. From the $\Z_s$-validity of $\BC$ in the synchronous network (Theorem <ref>), it follows that
these $\OK(i, j)$ messages are received by every party in $\Hon$ through regular-mode at time $\Delta + \TimeAuth + \TimeBC$.
Consequently, the set $\Hon$ constitutes a clique in the consistency graph of every party in $\Hon$ at time $\Delta + \TimeAuth + \TimeBC$.
Now since the set $\Hon \in \ShareSpec_{\Z_s}$, it follows that at time $\Delta + \TimeAuth + \TimeBC$, there exists some
$S_p \in \ShareSpec_{\Z_s}$, such that $\D$ computes the core-sets $\{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}$ and broadcast-set $\BroadcastSet$, followed by
broadcasting  $(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$ at time $\Delta + \TimeAuth + \TimeBC$.
Moreover, since $\D$ is honest, it computes the sets $\{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}$ and $\BroadcastSet$ honestly, satisfying the following conditions, for
$q = 1, \ldots, |\Z_s|$.

– If $S_q$ constitutes a clique in the graph $G^{(\D)}$, then $\W_{q} = S_q$.

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

– Else $\W_{q} = S_q$ and $q \in \BroadcastSet$.

Note that for each $\W_q$, the condition $\Q^{(1)}(\W_q, \Z_s)$  holds. This is obviously true if $\W_{q} = (S_p \cap S_q)$, since in this case $\D$ also checks that
$\Q^{(1)}(S_p \cap S_q, \Z_s)$ condition holds. On the other hand, even if $\W_q = S_q$, the condition $\Q^{(1)}(\W_q, \Z_s)$  holds, as
$\Q^{(1)}(S_q, \Z_s)$  holds due to the $\Q^{(2)}(\PartySet, \Z_s)$ condition.
We also note that if $S_q = \Hon$, then $q \notin \BroadcastSet$ and consequently, $\D$ does not make public the share $s_q$. This is because
as shown above, at time $\Delta + \TimeAuth + \TimeBC$, the parties in $S_q$ constitute a clique in the graph $G^{(\D)}$.

Since $\D$ broadcasts $(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$ at time $\Delta + \TimeAuth + \TimeBC$,
from the $\Z_s$-validity of $\BC$ in the synchronous network, it follows that all the parties in $\Hon$ will receive
$(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$ from the broadcast of
$\D$, at time $\Delta + \TimeAuth + 2\TimeBC$. To show that every $P_i \in \Hon$ will include $(\D, S_p)$ to the set $\C_i$, we need to show that all the conditions which hold
for $\D$ in its graph $G^{(\D)}$ at time $\Delta + \TimeAuth + \TimeBC$, are bound to hold for every $P_i \in \Hon$, at the time $\Delta + \TimeAuth + 2\TimeBC$.
Namely, all the edges which are present in $G^{(\D)}$ at time $\Delta + \TimeAuth + \TimeBC$, are bound to be present in the
graph $G^{(i)}$ every $P_i \in \Hon$, at the time $\Delta + \TimeAuth + 2\TimeBC$.
However, this simply follows from the $\Z_s$-validity, $\Z_s$-consistency and $\Z_s$-fallback consistency of $\BC$ in the synchronous network (see Theorem <ref>)
and the fact that edges are added to consistency graphs, based on the receipt of $\OK(\star, \star)$ messages, which are broadcasted through various $\BC$ instances.
Consequently, any edge $(i, j)$ which is included in $G^{(\D)}$ at the time $\Delta + \TimeAuth + \TimeBC$, is bound to be included in the graph $G^{(i)}$ of every
$P_i \in \Hon$, latest by time $\Delta + \TimeAuth + 2\TimeBC$.

We next note that corresponding to every $S_q \in \ShareSpec_{\Z_s}$, every honest $P_i \in \W_{q}$ will have the share $s_q$, which is either made public by $\D$
as part of the $\CandidateCoreSets$ message
or received from $\D$. Each honest $P_i \in W_q$ will thus set $[s]_q$ to $s_q$ at time $\Delta + \TimeAuth + 2\TimeBC$.
We next show that each $P_i \in \Hon$ will have $\ICSig(P_j, P_i, P_k, s_q)$ corresponding to
every $S_q \in \ShareSpec_{\Z_s}$, where $P_i \in \W_q$, for every $P_j \in \W_q$ and every $P_k \not \in S_q$.
This also is set at time $\Delta + \TimeAuth + 2\TimeBC$. This is because there are two possible cases with respect to $q$.
If $q \in \BroadcastSet$, then from the protocol steps, $\W_q$ is publicly set to $S_q$ and $\ICSig(P_j, P_i, P_k, s_q)$ is set to the default value.
On the other hand, if $q \not \in \BroadcastSet$, then also $P_i$ will possess $\ICSig(P_j, P_i, P_k, s_q)$. This is because as per the protocol steps,
since $P_i, P_j \in \W_q$, it follows that
$P_i$ must have verified that the edge $(P_i, P_j) \in G^{(i)}$, which further implies that $P_i$ has received $\ICSig(P_j, P_i, P_k, s_{qj})$ from $P_j$, where $s_{qj} = s_{qi}$ holds.
And since $\D$ is honest, $s_{qi} = s_q$ holds, implying that $\ICSig(P_j, P_i, P_k, s_{qj})$ is the same as $\ICSig(P_j, P_i, P_k, s_q)$.
On the other hand, in the protocol, $P_i$ gives $\ICSig(P_i, P_j, P_k, s_{qi})$ to every $P_j \in S_q$ for every $P_k \in \PartySet$, where $s_{qi} = s_q$ holds.
Hence if any corrupt $P_j \in \W_{q}$ has $\ICSig(P_i, P_j, P_k, s'_q)$ of any honest $P_i \in \W_{q}$
for any $P_k  \in \PartySet$, then
$s'_q = s_q$ holds.

We now show that, corresponding to each $S_q \in \ShareSpec_{\Z_s}$, every honest party $P_i \in S_q \setminus W_q$ sets $[s]_q$ to $s_q$, except with a probability of $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$, at time $\Delta + \TimeAuth + 2\TimeBC + \TimeReveal$. For this, we first show that $P_i$ sets $[s]_q$ to some value.
Since $\Z_s$ satisfies the $\Q^{(1)}(\W_q, \Z_s)$ condition, the set
$\W_q$ contains at least one honest party, say $P_j$. Since $P_j$ follows the protocol steps honestly, it reveals
$\ICSig(P_k, P_j, P_i, [s]_q)$ of every $P_k \in \W_q$ to $P_i$, at time $\Delta + \TimeAuth + 2\TimeBC$. From the $\Z_s$-correctness  of ICP in the synchronous network
(see Theorem <ref>), it follows that $P_i$ will accept  these signatures
after time $\TimeReveal$. On the other hand, even if $P_k \in \W_q$ is corrupt, then also from the $\Z_s$-non-repudiation property of ICP in the synchronous network
(see Theorem <ref>), it follows that $P_i$ accepts $\ICSig(P_k, P_j, P_i, [s]_q)$, except with a probability $\errorAICP$, after time $\TimeReveal$. As there can be $\Order(n)$ corrupt parties in $\W_q$, from the union bound, it follows that
except with a probability $\Order(n \cdot \errorAICP)$, party $P_i$ will find a candidate party from $\W_q$, who reveals $[s]_q$, along with the IC-signature of all the parties in $\W_q$, after time $\TimeReveal$. Now as there can be $\Order(n)$ parties in $S_q \setminus \W_q$, it follows that except with probability $\Order(n^2 \cdot \errorAICP)$, every honest party $P_i \in S_q \setminus \W_q$ will find a candidate party from $\W_q$, who reveals $[s]_q$ along with the IC-signature of all the parties in $\W_q$ at time $\Delta + \TimeAuth + 2\TimeBC + \TimeReveal$.

We next show that $P_i \in S_q \setminus W_q$ indeed sets $[s]_q$ to $s_q$. Suppose that $P_i$ sets $[s]_q$ to some value $s'$. From the protocols steps, this implies that there exists some $P_j \in \W_q$, such that $P_i$ has accepted
$\ICSig(P_k, P_j, P_i, s')$ of every $P_k \in \W_q$, revealed by $P_j$.  If $P_j$ is honest, then indeed $s' = [s]_q$, as one of the IC-signatures
$\ICSig(P_k, P_j, P_i, s')$ is the same as $\ICSig(P_k, P_j, P_i, [s]_q)$, corresponding to the honest $P_k \in \W_q$, which is guaranteed to exist.
So consider the case when $P_j$ is corrupt.
Moreover, let $P_k \in \W_q$ be an honest party (which is guaranteed to exist).
In order that $s' \neq [s]_q$, it must be the case that $P_i$ accepts  $\ICSig(P_k, P_j, P_i, s')$, revealed by $P_j$.  However, from
the unforgeability property of ICP (see Theorem <ref>), this can happen only with probability $\errorAICP$. Now as there can be up to $\Order(n)$ corrupt parties in $\W_q$, from the union bound, it follows that the probability that $P_i$ outputs $s' \neq [s]_q$ is at most $\Order(n \cdot \errorAICP)$. Since there can be up to $\Order(n)$ parties in $S_q \setminus \W_q$, it follows that except with probability at most
$\Order(n^2 \cdot \errorAICP)$, the output of every honest party in $S_q$ is indeed $s_q$. Now, there can be $|\ShareSpec_{\Z_s}|$ possibilities for $S_q$. From the union bound, it follows that corresponding to each $S_q \in \ShareSpec_{\Z_s}$, every honest party $P_i \in S_q \setminus W_q$ sets $[s]_q$ to $s_q$, except with a probability of $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$.

Finally, the privacy for $s$ follows from the fact that throughout the protocol, the view of the adversary remains independent of the share $s_q$, corresponding to the group $S_q$, where
$S_q = \Hon$. This is because as shown above, $q \notin \BroadcastSet$ and consequently, $\D$ does not make public the share $s_q$.
Moreover, during the pairwise consistency tests, the view of the adversary remains independent of $s_q$, when the parties in $\Hon$ exchange IC-signed $s_q$, which
follows from the privacy property of ICP (see Theorem <ref>). Further, while computing the output, $\ICSig(P_k, P_j, P_i, s_q)$ is revealed by party $P_j \in W_q$ only to each party $P_i \in S_q \setminus W_q$. Hence, the adversary does not learn $s_q$.

An immediate corollary of Lemma <ref> is that if $\D$ is honest, then the parties output $[s]$ at time $\Delta + \TimeAuth + 2\TimeBC + \TimeReveal$, which follows
from the definition of $[\cdot]$-sharing.

If the network is synchronous and $\D$ is honest and
participates in $\VSS$ with input $s$, then the parties output $[s]$ at time $\Delta + \TimeAuth + 2\TimeBC + \TimeReveal$, except with a probability of $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$.

We next consider a corrupt $\D$ in the synchronous network and show that if any honest party computes an output at time $T$, then there exists some $s^{\star} \in \F$ such that the (honest)
parties output $[s^{\star}]$ by time $T + \Delta$, except with probability $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$.

If the network is synchronous and $\D$ is corrupt and if any honest party computes an output at time $T$, then there exists some $s^{\star} \in \F$, such that the honest parties output
$[s^{\star}]$ by time $T + \Delta$, except with a probability of $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$.

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. Let $P_\ell \in \Hon$ be the first honest party
which computes an output at time $T$. The way in which the core sets are defined ensures that each set in $\{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}$ must contain at least one honest party. Since $\Reveal$ takes at least $\TimeReveal$ time to complete, this means that there exists $S_p \in \ShareSpec_{\Z_s}$ such that some honest party $P_m$ receives a message
$(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$ from the broadcast
of $\D$ by the time $T - \TimeReveal$ and includes $(\D, S_p)$ to $\C_m$.
This further implies that $P_m$ has verified that the following hold, for
$q = 1, \ldots, |\Z_s|$, by time $T - \TimeReveal$.

– If $q \not \in \BroadcastSet$, then $\W_{q}$ is either $S_q$ or $(S_p \cap S_q)$. Moreover,
$\Z_s$ satisfies the $\Q^{(1)}(\W_q, \Z_s)$ condition
and the parties in
$\W_q$ constitute a clique in the graph $G^{(m)}$.

– If  $q  \in \BroadcastSet$, then $\D$ has made public $s_q$, as part of the $\CandidateCoreSets$ message. Moreover, $\W_q$ is set to $S_q$.

From the $\Z_s$-consistency and $\Z_s$-fallback consistency of $\BC$ in the synchronous network (see Theorem <ref>), it follows that every party in $\Hon$ will receive
$(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$ from the broadcast
of $\D$, latest by time $T - \TimeReveal + \Delta$. We next show that each $P_i \in \Hon$ will include $(\D, S_p)$ to $\C_i$, latest by time $T - \TimeReveal + \Delta$.
For this, it is enough to show that all the edges which are present in $G^{(m)}$ at time $T- \TimeReveal$, are bound to be present in the
graph $G^{(i)}$ every $P_i \in \Hon$, by the time $T - \TimeReveal + \Delta$.
However, this simply follows from the $\Z_s$-validity, $\Z_s$-consistency and $\Z_s$-fallback consistency of $\BC$ in the synchronous network (see Theorem <ref>)
and the fact that edges are added to consistency graphs, based on the receipt of $\OK(\star, \star)$ messages, which are broadcasted through various $\BC$ instances.
Consequently, any edge $(i, j)$ which is included in $G^{(m)}$ at the time $T$, is bound to be included in the graph $G^{(i)}$ of every
$P_i \in \Hon$, latest by time $T - \TimeReveal + \Delta$.

We next show that by time $T - \TimeReveal + \Delta$, corresponding to every $S_q \in \ShareSpec_{\Z_s}$, every $P_i \in \W_q$ will have a common share, say $s^{\star}_q$.
If $q \in \BroadcastSet$, this is trivially true, since in this case, $\D$ makes public the share $s_q$ and hence  $s^{\star}_q = s_q$.
On the other hand, consider the case when $q \not \in \BroadcastSet$ and consider arbitrary $P_i, P_j \in (\W_q \cap \Hon)$. Since $P_i$ and $P_j$ are part of a clique,
it follows that $P_i$ and $P_j$ have broadcasted the messages $\OK(i, j)$ and $\OK(j, i)$ respectively. Moreover, these messages were broadcasted, latest by time $T - \TimeReveal - \TimeBC$, since
it takes at least $\TimeBC$ time to compute any output in an instance of $\BC$ in the synchronous network (see Theorem <ref>).
Now since $P_i$ and $P_j$ have broadcasted $\OK(i, j)$ and $\OK(j, i)$ messages, it implies that they have verified that $s_{qi} = s_{qj}$ holds, where
$s_{qi}$ and $s_{qj}$ are the shares, received by $P_i$ and $P_j$ respectively, from $\D$. Let $s_{qi} = s_{qj} = s^{\star}_q$.
We define

\[ s^{\star} \defined \displaystyle \sum_{q = 1, \ldots, |\Z_s|} s^{\star}_q.    \]

Till now we have shown that there exists some $s^{\star} \in \F$, such that by time $T - \TimeReveal + \Delta$, all the parties in $\Hon$ will have the core-sets $\W_1, \ldots, \W_{|\Z_s|}$, where
$S_q \setminus \W_q \in \Z_a$, for $q = 1, \ldots, |\Z_s|$ and where each $P_i \in (\W_q \cap \Hon)$ will have a common share $[s^{\star}]_q$.
We need to show that by the time $T - \TimeReveal + \Delta$, the parties in $\Hon$ will have the required IC-signatures, as part of $[s^{\star}]$, satisfying the linearity property.
Namely, each $P_i \in \Hon$ will have $\ICSig(P_j, P_i, P_k, [s^{\star}]_q)$, corresponding to
every $S_q \in \ShareSpec_{\Z_s}$ where $P_i \in \W_q$, of every $P_j \in \W_q$ and for every $P_k \in \PartySet$. There are two possible cases with respect to $q$.
If $q \in \BroadcastSet$, then from the protocol steps, $\W_q$ is publicly set to $S_q$ and $\ICSig(P_j, P_i, P_k, [s^{\star}]_q)$ is set to the default value of
$\ICSig(P_j, P_i, P_k, s_q)$, where $s_q$ is made public by $\D$. As per our notations, $s_q = s^{\star}_q$ for every
$q \in \BroadcastSet$.
On the other hand, if $q \not \in \BroadcastSet$, then also $P_i$ will possess $\ICSig(P_j, P_i, P_k, [s^{\star}]_q)$. This is because as per the protocol steps,
since $P_i, P_j \in \W_q$, it follows that
$P_i$ must have verified that the edge $(P_i, P_j) \in G^{(i)}$, which further implies that $P_i$ has received $\ICSig(P_j, P_i, P_k, s_{qj})$ from $P_j$, where $s_{qj} = s_{qi}$ holds.
Here $s_{qi}$ is the share received by $P_i$ from $\D$ and as per our notation, $s_{qi} = s^{\star}_q$.
Hence $\ICSig(P_j, P_i, P_k, s_{qj})$ is the same as $\ICSig(P_j, P_i, P_k, [s^{\star}]_q)$.
On the other hand, in the protocol, $P_i$ gives $\ICSig(P_i, P_j, P_k, s_{qi})$ to every $P_j \in S_q$ for every $P_k \in \PartySet$, where $s_{qi} = [s^{\star}]_q$ holds.
Hence if any corrupt $P_j \in \W_{q}$ has $\ICSig(P_i, P_j, P_k, s'_q)$, of any honest $P_i \in \W_{q}$
for any $P_k \in \PartySet$, then
$s'_q = [s^{\star}]_q$ holds. It is easy to see that all the underlying IC-signatures will be linear since the parties follow the linearity principle while generating IC-signatures.

Finally, we now show that every honest party $P_i \in S_q \setminus W_q$ gets $[s^\star]_q$, except with a probability of $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$, at time $T + \Delta$. For this, we first show that $P_i$ computes some share on the behalf of $S_q$. Since  $\Z_s$ satisfies the $\Q^{(1)}(\W_q, \Z_s)$ condition, the set
$\W_q$ contains at least one honest party, say $P_j$. Since $P_j$ follows the protocol steps honestly, it reveals $\ICSig(P_k, P_j, P_i, [s^\star]_q)$ of every $P_k \in \W_q$ to $P_i$,
at time $T - \TimeReveal + \Delta$. From
the $\Z_s$-correctness of ICP in the synchronous network
(see Theorem <ref>), it follows that $P_i$ will accept the IC-signatures $\ICSig(P_k, P_j, P_i, [s^\star]_q)$, revealed by $P_j$,
after time $\TimeReveal$. On the other hand, even if $P_k \in \W_q$ is corrupt, then also from the $\Z_s$-non-repudiation property of ICP in the synchronous network (see Theorem <ref>), it follows that $P_i$ accepts $\ICSig(P_k, P_j, P_i, [s^\star]_q)$, except with a probability $\errorAICP$, after time $\TimeReveal$. As there can be $\Order(n)$ corrupt parties in $\W_q$, from the union bound, it follows that
except with a probability $\Order(n \cdot \errorAICP)$, party $P_i$ will find a candidate party from $\W_q$, who reveals $[s^\star]_q$, along with the IC-signature of all the parties in $\W_q$, after time $\TimeReveal$. Now as there can be $\Order(n)$ parties in $S_q \setminus \W_q$, it follows that except with probability $\Order(n^2 \cdot \errorAICP)$, every honest party $P_i \in S_q \setminus \W_q$ will find a candidate party from $\W_q$, who reveals $[s^\star]_q$ along with the IC-signature of all the parties in $\W_q$ at time $T + \Delta$.

We next show that $P_i \in S_q \setminus W_q$ indeed sets $[s^\star]_q$ as the share corresponding to $S_q$.
Suppose that $P_i$ sets the share to some value $s'$. From the protocol steps, this implies that there exists some $P_j \in \W_q$, such that $P_i$ has accepted
the IC-signatures $\ICSig(P_k, P_j, P_i, s')$ of every $P_k \in \W_q$, revealed by $P_j$.  If $P_j$ is honest, then indeed $s' = [s^\star]_q$, as one of the IC-signatures
$\ICSig(P_k, P_j, P_i, s')$ is the same as $\ICSig(P_k, P_j, P_i, [s^\star]_q)$, corresponding to the honest $P_k \in \W_q$, which is guaranteed to exist.
So consider the case when $P_j$ is corrupt.
Moreover, let $P_k \in \W_q$ be an honest party (which is guaranteed to exist).
In order that $s' \neq [s^\star]_q$, it must be the case that $P_i$ accepts  $\ICSig(P_k, P_j, P_i, s')$, revealed by $P_j$.  However, from
the unforgeability property of ICP (see Theorem <ref>), this can happen only with probability $\errorAICP$. Now as there can be up to $\Order(n)$ corrupt parties in $\W_q$, from the union bound, it follows that the probability that $P_i$ outputs $s' \neq [s^\star]_q$ is at most $\Order(n \cdot \errorAICP)$. Since there can be up to $\Order(n)$ parties in $S_q \setminus \W_q$, it follows that except with probability at most
$\Order(n^2 \cdot \errorAICP)$, the output of every honest party in $S_q$ is indeed $[s^\star]_q$. Now, there can be $|\ShareSpec_{\Z_s}|$ possibilities for $S_q$. From the union bound, it follows that corresponding to each $S_q \in \ShareSpec_{\Z_s}$, every honest party in $S_q$ outputs $[s^\star]_q$, except with a probability of $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$.

We next consider an asynchronous network and prove the analogue of Lemma <ref> by showing that if $\D$ is honest, then the parties eventually output $[s]$
except with a probability of $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$. Further, the adversary learns no additional information about $s$. The proof of the lemma follows closely the proof of Lemma <ref>,
except that we now rely on the properties of $\BC$, and ICP in the asynchronous network.

If the network is asynchronous and $\D$ is honest,
participating  in $\VSS$ with input $s$, then the honest parties eventually output $[s]$ except with a probability of $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$, with the view of the adversary remaining independent of $s$.

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 note that $\Hon \in \ShareSpec_{\Z_s}$, since $Z^{\star} \in \Z_s$ as $\Z_a \subset \Z_s$.
Since $\D$ is honest, it picks the shares $s_1,\dots, s_{|\Z_s|}$ such that $s = s_1 + \dots + s_{|\Z_s|}$ and sends $s_q$ to each party $P_i \in S_q$, corresponding to
every $S_q \in \ShareSpec_{\Z_s}$. These shares are eventually delivered. Now consider an arbitrary $S_q \in \ShareSpec_{\Z_s}$.
After receiving the share $s_{qi}$ from $\D$, each party $P_i \in (S_q \cap \Hon)$ starts giving
$\ICSig(P_i, P_j, P_k, s_{qi})$ to every $P_j \in S_q$, for every $P_k \in \PartySet$, where $s_{qi} = s_q$ holds,
such that the linearity principle is followed while generating these IC-signatures.
Then from the $\Z_a$-correctness of $\Auth$ in the asynchronous network (Theorem <ref>),
it follows that each party $P_i \in (S_q \cap \Hon)$ will eventually receive
$\ICSig(P_j, P_i, P_k, s_{qj})$ from every $P_j \in (S_q \cap \Hon)$, for every $P_k \in \PartySet$, such that $s_{qj} = s_{qi} = s_q$ holds.
Since $S_q$ is arbitrary, it follows that eventually, every party $P_i \in \Hon$ broadcasts an $\OK(i, j)$ message, corresponding to every
$P_j \in \Hon$. From the $\Z_a$-weak validity and $\Z_a$-fallback validity  of $\BC$ in the asynchronous network (Theorem <ref>), it follows that
these $\OK(i, j)$ messages are eventually received by every party in $\Hon$.
Consequently, the set $\Hon$ eventually constitutes a clique in the consistency graph of every party in $\Hon$.
Now since the set $\Hon \in \ShareSpec_{\Z_s}$, it follows that eventually, there exists some
$S_p \in \ShareSpec_{\Z_s}$, such that $\D$ computes the core-sets $\{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}$ and broadcast-set $\BroadcastSet$, followed by
broadcasting  $(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$.
Moreover, since $\D$ is honest, it computes the sets $\{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}$ and $\BroadcastSet$ honestly, satisfying the following conditions, for
$q = 1, \ldots, |\Z_s|$.

– If $S_q$ constitutes a clique in the graph $G^{(\D)}$, then $\W_{q} = S_q$.

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

– Else $\W_{q} = S_q$ and $q \in \BroadcastSet$.

Note that for each $\W_q$, the condition $\Q^{(1)}(\W_q, \Z_s)$  holds. This is obviously true if $\W_{q} = (S_p \cap S_q)$, since in this case $\D$ also checks that
$\Q^{(1)}(S_p \cap S_q, \Z_s)$ holds. On the other hand, even if $\W_q = S_q$,
the condition $\Q^{(1)}(\W_q, \Z_s)$ holds, since $\Q^{(1)}(S_q, \Z_s)$ holds.
We also note that if $S_q = \Hon$, then $q \notin \BroadcastSet$ and consequently, $\D$ does not make public the share $s_q$. This is because
the parties in $S_p \cap S_q$ will constitute a clique and the $\Q^{(1)}(S_p \cap S_q, \Z_s)$ condition will be satisfied due to the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$
condition. Hence $\W_q$ will be set to $S_p \cap S_q$.

Since $\D$ eventually broadcasts $(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$,
from the $\Z_a$-weak validity and $\Z_a$-fallback validity of $\BC$ in the asynchronous network, it follows that all the parties in $\Hon$ will eventually receive
$(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$ from the broadcast of
$\D$. We next show that every $P_i \in \Hon$ will eventually include $(\D, S_p)$ to the set $\C_i$. For this, we need to show that all the conditions which hold
for $\D$ in its graph $G^{(\D)}$ when it broadcasts the $\CandidateCoreSets$ message,
are bound to eventually hold for every $P_i \in \Hon$.
However, this simply follows from the $\Z_a$-weak validity, $\Z_a$-fallback validity, $\Z_a$-weak consistency and $\Z_a$-fallback consistency of
$\BC$ in the asynchronous network (see Theorem <ref>)
and the fact that edges are added to consistency graphs, based on the receipt of $\OK(\star, \star)$ messages, which are broadcasted through various $\BC$ instances.
Consequently, any edge $(i, j)$ which is included in $G^{(\D)}$, is bound to be eventually included in the graph $G^{(i)}$ of every
$P_i \in \Hon$.

Note that corresponding to every $S_q \in \ShareSpec_{\Z_s}$, every honest $P_i \in \W_{q}$ will have the share $s_q$, which is either made public by $\D$
as part of the $\CandidateCoreSets$ message
or received from $\D$.
Next, we note that each $P_i \in \Hon$ will have $\ICSig(P_j, P_i, P_k, s_q)$, corresponding to
every $S_q \in \ShareSpec_{\Z_s}$ where $P_i \in \W_q$, from every $P_j \in \W_q$ and for every $P_k \in \PartySet$.
On the other hand, if any corrupt $P_j \in \W_{q}$ has $\ICSig(P_i, P_j, P_k, s'_q)$ of any honest $P_i \in \W_{q}$ for
any $P_k  \in \PartySet$, then
$s'_q = s_q$ holds.
The proof for this is exactly the same as that of Lemma <ref>.

We now show that every honest party $P_i \in S_q \setminus W_q$ eventually sets $[s]_q$ to $s_q$, except with a probability of $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$. We first show that $P_i$ sets $[s]_q$ to some value. Since
$\Z_s$ satisfies the $\Q^{(1)}(\W_q, \Z_s)$ condition,
this means that $\W_q$ contains at least one honest party, say $P_j$. Since $P_j$ follows the protocol steps honestly, it reveals
$\ICSig(P_k, P_j, P_i, [s]_q)$ of every $P_k \in \W_q$ to $P_i$. From the
$\Z_a$-correctness property of ICP in the asynchronous network
(see Theorem <ref>), it follows that $P_i$ will eventually accept these signatures.
On the other hand, even if
$P_k \in \W_q$ is corrupt, then from the $\Z_a$-non-repudiation property of ICP in the asynchronous network
(see Theorem <ref>), it follows that $P_i$ eventually accepts $\ICSig(P_k, P_j, P_i, [s]_q)$, except with a probability $\errorAICP$. From the union bound, it follows that except with probability $\Order(n^2 \cdot \errorAICP)$, each party $P_i \in S_q$ outputs some value for $[s]_q$. Further, this value must be $s_q$. The proof of this follows from what was shown in <ref>. Now, there can be $|\ShareSpec_{\Z_s}|$ possibilities for $S_q$. From the union bound, it follows that corresponding to each $S_q \in \ShareSpec_{\Z_s}$, every honest party in $S_q$ eventually outputs $[s]_q$, except with a probability of $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$.

Finally, the privacy for $s$ follows from the fact that throughout the protocol, the view of the adversary remains independent of the share $s_q$, corresponding to the group $S_q$, where
$S_q = \Hon$. This is because as shown above, $q \notin \BroadcastSet$ and consequently, $\D$ does not make public the share $s_q$.
Moreover, during the pairwise consistency tests, the view of the adversary remains independent of $s_q$, when the parties in $\Hon$ exchange IC-signed $s_q$, which
follows from the privacy property of ICP (see Theorem <ref>). Further, while computing the output, $\ICSig(P_k, P_j, P_i, s_q)$ is revealed by party $P_j \in W_q$ only to each party $P_i \in S_q \setminus W_q$. Hence, the adversary does not learn $s_q$.

Finally, we consider a corrupt $\D$ in the asynchronous network and prove the analogue of Lemma <ref>, whose proof is very similar to that
of Lemma <ref>.

If the network is asynchronous and $\D$ is corrupt and if any honest party computes an output, then there exists some $s^{\star} \in \F$, such that the honest parties eventually output
$[s^{\star}]$, except with a probability of $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$.

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. Let $P_m \in \Hon$ be the first honest party,
who computes an output in the protocol $\VSS$. This implies that there exists some  $S_p \in \ShareSpec_{\Z_s}$, such that $P_m$ receives a message
$(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$ from the broadcast
of $\D$, and includes $(\D, S_p)$ to $\C_m$.
This further implies that $P_m$ has verified that the following hold, for
$q = 1, \ldots, |\Z_s|$.

– If $q \not \in \BroadcastSet$, then $\W_{q}$ is either $S_q$ or $(S_p \cap S_q)$. Moreover,
$\Z_s$ satisfies the $\Q^{(1)}(\W_q, \Z_s)$ condition
and the parties in
$\W_q$ constitute a clique in the graph $G^{(m)}$.

– If  $q  \in \BroadcastSet$, then $\D$ has made public $s_q$, as part of the $\CandidateCoreSets$ message. Moreover, $\W_q$ is set to $S_q$.

From the $\Z_a$-weak consistency and $\Z_a$-fallback consistency of $\BC$ in the asynchronous network (see Theorem <ref>),
it follows that every party in $\Hon$ will eventually receive
$(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$ from the broadcast
of $\D$. We next show that each $P_i \in \Hon$ will eventually include $(\D, S_p)$ to $\C_i$.
For this, it is enough to show that all the edges which are present in $G^{(m)}$ when $(\D, S_p)$ is included in $\C_i$,
are bound to be eventually present in the
graph $G^{(i)}$ of every $P_i \in \Hon$.
However, this simply follows from the $\Z_a$-weak validity, $\Z_a$-fallback validity, $\Z_a$-weak consistency and $\Z_a$-fallback consistency of $\BC$ in the
asynchronous network (see Theorem <ref>)
and the fact that edges are added to consistency graphs, based on the receipt of $\OK(\star, \star)$ messages, which are broadcasted through various $\BC$ instances.

Next, it can be shown that corresponding to every $S_q \in \ShareSpec_{\Z_s}$, every $P_i \in \W_q$ will have a common share, say $s^{\star}_q$.
The proof for this is the same as Lemma <ref>.
We define

\[ s^{\star} \defined \displaystyle \sum_{q = 1, \ldots, |\Z_s|} s^{\star}_q.    \]

Now similar to the proof of Lemma <ref>, it can be shown that each party $P_i$ in $(\Hon \cap \W_q)$ will eventually have the required IC-signatures
on $[s^{\star}]_q$ as part of $[s^{\star}]$ and
will reveal these to parties in $S_q \setminus W_q$. Consequently, each party in $\Hon$ will eventually set $[s^\star]_q$ as the share corresponding to $S_q$
and hence, $s^{\star}$ will eventually be secret-shared, except with a probability of $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$.

We next derive the communication complexity of the protocol $\VSS$.

Protocol $\VSS$ incurs a communication of $\Order(|\Z_s| \cdot n^8 \cdot \log{|\F|} \cdot |\sigma|)$ bits.

In the protocol, $\D$ needs to send the share $s_q$ to all the parties in $S_q$. This incurs a total communication of $\Order(|\Z_s| \cdot n \cdot \log{|\F|})$ bits. There are
$\Order(|\Z_s| \cdot n^3)$ instances of $\Auth$ invoked, to exchange IC-signed values, during the pairwise consistency tests. From Theorem <ref>,
this incurs a total communication of
$\Order(|\Z_s| \cdot n^8 \cdot \log{|\F|} \cdot |\sigma|)$ bits. There are $\Order(n^2)$ $\OK$ messages which need to be broadcasted, which from Theorem <ref>,
incurs a total communication of
$\Order(n^6 \cdot \log{n} \cdot |\sigma|)$ bits, since each $\OK$ message encodes the identity of two parties, requiring $\log{n}$ bits.
Finally, $\D$ needs to broadcast a candidate $(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$ message, where
$S_p, \BroadcastSet$ and each $\W_q$ can be represented by $\Order(n)$ bits. And corresponding to the indices in $\BroadcastSet$, the dealer $\D$ may end up broadcasting
$\Order(|\Z_s|)$ shares. From Theorem <ref>, this incurs a total communication of $\Order(|\Z_s| \cdot (n^5 \cdot |\sigma| + n^4 \cdot \log{|\F|} \cdot |\sigma|))$ bits. While computing the output, $\Order(n^3 \cdot |\Z_s|)$ instances of $\Reveal$ are involved, which incur a communication of $\Order(|\Z_s| \cdot n^4 \cdot \log{|\F|})$ bits.

Theorem <ref> now follows from Lemma <ref>-<ref>.

Theorem <ref>.
Protocol $\VSS$ achieves the following, except with a probability of $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$, where $\D$ has input $s \in \F$ for $\VSS$ and where
$\TimeVSS = \Delta + \TimeAuth + 2\TimeBC + \TimeReveal$.

– If $\D$ is honest, then the following hold.

– $\Z_s$-correctness: In a synchronous network, the honest parties output $[s]$ at time $\TimeVSS$.

– $\Z_a$-correctness: In an asynchronous network, the honest parties eventually output  $[s]$.

– Privacy: Adversary's view remains independent of $s$ in any network.

– If $\D$ is corrupt, then the following hold.

–  $\Z_s$-commitment: In a synchronous network, either no honest party obtains any output or there exists some
$s^{\star} \in \F$, such that the parties output $[s^{\star}]$.
Moreover, if any honest party computes its output corresponding to $[s^{\star}]$ at time $T$, then all honest parties
compute their output corresponding to $[s^{\star}]$ by time $T + \Delta$.

–  $\Z_a$-commitment: In an asynchronous network, either no honest party obtains any output or there exists some
$s^{\star} \in \F$, such that the honest parties eventually output $[s^{\star}]$.

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

If $\D$ is honest, then except with probability at most $|\Z_s| \cdot n^2 \cdot \errorAICP$, protocol $\VSS$ achieves the following,
where $\D$ has input $s \in \F$ for $\VSS$ and where
$\TimeVSS = 2\Delta + \TimeAuth + 2\TimeBC + \TimeBA$.

– $\Z_s$-correctness: In a synchronous network, the honest parties output $[s]$ at time $\TimeVSS$.

– $\Z_a$-correctness: In an asynchronous network, almost-surely, the honest parties eventually output  $[s]$.

We first consider a 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.
We begin by showing that all the parties in $\Hon$ participate with input $0$ in the instance of $\BA$ at time $\Delta + \TimeAuth + 2\TimeBC$.

every honest party (including $\D$) adds the edge $(P_i,P_j)$ in its consistency graph at time $\Delta + \TimeAuth + \TimeBC$. Consequently, the set of honest parties $\Hon$, which is also a set in $\ShareSpec$, forms a clique in $G^\D$. Hence, $\D$ will assign the core set $\C$ to some set $S_q \in \ShareSpec$ at time $\Delta + \TimeAuth + \TimeBC$, and broadcast this. For every set $S_q \in \ShareSpec$ for which there does not exist $\W_q$ such that $S_q \setminus \W_q \in \Z_a$ and $\W_q$ forms a clique in $G^{\D}$, $\D$ broadcasts $s_q$ and adds $q$ to the set $\BroadcastSet$. $\D$ then broadcasts $\BroadcastSet$. From the $\Z_s$-validity of $\BC$, every honest party $P_i$ receives $\C$ and $\BroadcastSet$ at time $\Delta + \TimeAuth + 2\TimeBC$. Furthermore, from the $\Z_s$-consistency of $\BC$, $G^{(i)}$ and $G^\D$ will be the same at time $\Delta + \TimeAuth + \TimeBC$. This is because parties participate in broadcast for announcing the results of pairwise consistency tests only at time $\Delta + \TimeAuth$. Since $\BC$ takes at least $\TimeBC$ time in a synchronous network, any $\OK(j,k)$ message received by $\D$ at time $\Delta + \TimeAuth + \TimeBC$ must have been sent at time $\Delta + \TimeAuth$. From the $\Z_s$-consistency of $\BC$, every honest party $P_i$ also receives this at time $\Delta + \TimeAuth + \TimeBC$. Thus, for every $q \notin \BroadcastSet$, a set $\W_q$ such that $S_q \setminus \W_q \in \Z_a$ and $\W_q$ forms a clique in $G^{(i)}$ will be found.

We next consider an asynchronous network. Similar to what was argued for the case of a synchronous network, $\D$ randomly picks shares $s_1,\dots,s_h$ such that $s = s_1 + \dots + s_h$, and sends $s_q$ to each party $P_i \in S_q$, for all the sets $S_q \in \ShareSpec$. Each party $P_i \in S_q$ eventually receives $s_{qi}$ from $\D$, and gives $\ICSig(P_i, P_j, P_k, s_{qi})$ to every $P_j \in S_q$, corresponding to every $P_k \in \PartySet$. From the $\Z_a$-correctness of $\Auth$ (Claim <ref>), each honest party $P_i$ will eventually receive $\ICSig(P_j, P_i, P_k, s_{qj})$ such that $s_{qj} = s_{qi}$ holds from every honest party $P_j$, for every $P_k \in \PartySet$. This, it receives for every set $S_q \in \ShareSpec$ such that $P_i, P_j \in S_q$. Thus, every honest party $P_i$ eventually broadcasts $\OK(i,j)$ for every other honest party $P_j$. From the $\Z_a$-validity of $\BC$, every honest party (including $\D$) eventually adds the edge $(P_i,P_j)$ in its consistency graph at time. Consequently, the set of honest parties $\Hon$, which is also a set in $\ShareSpec$, will eventually form a clique in $G^\D$. Hence, $\D$ will assign the core set $\C$ to some set $S_q \in \ShareSpec$, and broadcast this. For every set $S_q \in \ShareSpec$ for which there does not exist $\W_q$ such that $S_q \setminus \W_q \in \Z_a$ and $\W_q$ forms a clique in $G^{\D}$, $\D$ broadcasts $s_q$ and adds $q$ to the set $\BroadcastSet$. $\D$ then broadcasts $\BroadcastSet$. From the $\Z_a$-validity of $\BC$, every honest party $P_i$  eventually receives $\C$ and $\BroadcastSet$. Furthermore, from the $\Z_a$-consistency of $\BC$, each honest party $P_i$ will eventually add all edges which were present in $G^\D$ when $\D$ found $\C$ to $G^{(i)}$. Thus, for every $q \notin \BroadcastSet$, a set $\W_q$ which forms a clique in $G^{(i)}$ such that $S_q \setminus \W_q \in \Z_a$ will be found.

Let $\Z_s$ and $\Z_a$ be adversary structures satisfying conditions $\Con$. Then, privacy holds during protocol $\VSS$.

Suppose that $\D$ is honest. Let $\Hon$ and $Z^\star$ be the set of honest and corrupt parties among $\PartySet$ respectively. Irrespective of the network type, there will be some set of parties $S_q \in \ShareSpec$, where $S_q \coloneqq \PartySet \setminus Z$ for some $Z \in \Z_s$ such that $Z^\star \subseteq Z$, which contains only honest parties. We claim that throughout the protocol, the adversary's view remains independent of $s_q$. Since $s = s_1 + \dots + s_q + \dots + s_h$, this implies that the adversary's view remains independent of $s$.

We now proceed to prove our claim. While distributing shares, $\D$ gives $s_q$ only to the honest parties in $S_q$. While performing pairwise consistency tests, from the privacy of $\Auth$ (Lemma <ref>), the adversary's view continues to remain independent of $s_q$. We next state that irrespective of the network type, $\D$ will never add $q$ to $\BroadcastSet$. Assuming that this is true, then from the privacy of $\Reveal$ (Lemma <ref>), $\Adv$ doesn't learn the value of $s_q$ while the parties compute the share.

To prove our statement, first consider a synchronous network. From the proof of Claim <ref>, at time $\Delta + \TimeAuth + \TimeBC$, the set of honest parties $\Hon$ form a clique in $G^\D$. Hence, $\D$ will be able to find a $\W_q = S_q \setminus \emptyset$, where $\emptyset \in \Z_a$, such that $\W_q$ is a clique in $G^\D$. Hence, $\D$ will not add $q$ to $\BroadcastSet$. Now, consider an asynchronous network. From the proof of Claim <ref>, $\D$ will eventually find some core set $\C \in \ShareSpec$ such that the set of parties in $\C$ form a clique in $G^\D$. Since $Z^\star \in \Z_a$, the set $\C \setminus Z^\star$ consists of only honest parties and hence, is a subset of $S_q$. This means that $\D$ will be able to find $\W_q \subseteq S_q$ such that the parties in $\W_q$ form a clique in $G^\D$, and $\W_q = S_q \setminus Z$ for some $Z \in \Z_a$. Hence, $\D$ does not add $q$ to $\BroadcastSet$. This proves our statement, and hence, our claim.

Let $\Z_s$ and $\Z_a$ be adversary structures satisfying conditions $\Con$. Then, protocol $\VSS$ satisfies $\Z_s$-commitment and $\Z_a$-commitment in a synchronous and an asynchronous network respectively.

If no honest party obtains an output, then the claim holds trivially. So, assume that at least one honest party, say $P_h$, obtained an output. We first show that every honest party must have accepted the sets $\C$ and $\BroadcastSet$ broadcasted by $\D$.

Suppose that the network is synchronous, and that $P_h$ obtained an output at time $\TimeVSS$. Since $P_h$ has obtained an output at time $\TimeVSS = 2\Delta + \TimeAuth + 2\TimeBC$, and since $\Reveal$ takes at least $\Delta$ time, $P_h$ must have accepted $\C$ and $\BroadcastSet$ at time  $\Delta + \TimeAuth + 2\TimeBC$. Since it takes at least $\TimeBC$ time for $\BC$ to generate an output, and since parties participate in the broadcast for announcing sets $\C$ and $\BroadcastSet$ at time $\Delta + \TimeAuth + \TimeBC$, $\D$ must have broadcasted $\C$ and $\BroadcastSet$ at time $\Delta + \TimeAuth + \TimeBC$. Hence, from the $\Z_s$-consistency of $\BC$, every honest party $P_i$ also receives $\C$ and $\BroadcastSet$ at time $\Delta + \TimeAuth + 2\TimeBC$. We next claim that, at time $\Delta + \TimeAuth + \TimeBC$, the consistency graphs $G^{(h)}$ and $G^{(i)}$ are the same. Consider an edge $(P_j,P_k)$ in $G^{(h)}$. For this, $P_j$ and $P_k$ must have broadcasted $\OK(j,k)$ and $\OK(k,j)$ respectively at time $\Delta + \TimeAuth$. This is because $\BC$ takes at least $\TimeBC$ time to generate an output in a synchronous network, and because parties start participating in broadcasts corresponding to the results of pairwise consistency tests at time $\Delta + \TimeAuth$. Hence, by the $\Z_s$-validity of $\BC$, $P_i$ will also receive $\OK(j,k)$ and $\OK(k,j)$ from the broadcast of $P_j$ and $P_k$ at time $\Delta + \TimeAuth + \TimeBC$, and add this edge to $G^{(i)}$. Hence the consistency graphs $G^{(h)}$ and $G^{(i)}$ are the same at time $\Delta + \TimeAuth + \TimeBC$. Now, consider the conditions required for $P_i$ to accept $\C$ and $\BroadcastSet$ at time $\Delta + \TimeAuth + 2\TimeBC$.

* The parties in $\C$ formed a clique in $G^{(i)}$ at time $\Delta + \TimeAuth + \TimeBC$ : Since this was true for $P_h$, and since $G^{(h)}$ and $G^{(i)}$ are the same at time $\Delta + \TimeAuth + \TimeBC$, this holds true for $P_i$ as well.

* For each $q \in \BroadcastSet$, $s_q$ is received from the broadcast of $\D$ : Since this holds true for $P_h$ at time $\Delta + \TimeAuth + 2\TimeBC$, $\D$ must have broadcasted $s_q$ at time $\Delta + \TimeAuth + \TimeBC$. This is because it takes at least $\TimeBC$ time for $\BC$ to generate an output, and since parties participate in the broadcast initiated by $\D$ at time $\Delta + \TimeAuth + \TimeBC$. Hence, from the $\Z_s$-consistency of $\BC$, $P_i$ receives $s_q$ for each $q \in \BroadcastSet$ at time $\Delta + \TimeAuth + 2\TimeBC$.

* For each $S_q \in \ShareSpec$ such that $q \notin \BroadcastSet$, a set $\W_q$ such that $S_q \setminus \W_q \in \Z_a$ and $\W_q$ forms a clique in $G^{(i)}$ was found at time $\Delta + \TimeAuth + \TimeBC$ : Same argument as point 1.

Hence, every honest party $P_i$ accepts $\C$ and $\BroadcastSet$ in a synchronous network at time $\Delta + \TimeAuth + 2\TimeBC$.  We now consider an asynchonous network, and argue the same. Since $P_h$ has obtained an output, $P_h$ must have accepted $\C$ and $\BroadcastSet$. Since $P_h$ received $\C$ and $\BroadcastSet$ from the broadcast of $\D$, from the $\Z_a$-consistency of $\BC$, each honest party $P_i$ eventually receives $\C$ and $\BroadcastSet$ from the broadcast of $\D$. We next claim that each edge in $G^{(h)}$ will eventually be present in $G^{(i)}$. This follows form the $\Z_a$-consistency of $\BC$. Furthermore, for the same reasons, each value $s_q$ obtained by $P_h$ from the broadcast of $\D$ corresponding to the set $S_q \in \ShareSpec$ such that $q \notin \BroadcastSet$ will eventually be received by $P_i$. Thus, every honest party $P_i$ will also accept $\C$ and $\BroadcastSet$.

We now show that, except with probability $|\Z_s| \cdot n^2 \cdot \errorAICP$, in either network, the share computed by every honest party $P_i$, for each $S_q \in \ShareSpec$ such that $P_i \in S_q$, is correct. In a synchronous network, while the parties compute this output at time $2\Delta + \TimeAuth + 2\TimeBC$, in an asynchronous network, the parties eventually compute an output. The proof for this is the same as that for Claim <ref>, except that for $S_q$ such that $q \notin \BroadcastSet$, the parties output the value held by honest parties in $\W_q$. Hence, we skip the formal proof.

Since we haven't finalized $\BC$, proof for case when output is computed after time $\TimeVSS$ in a synchronous network hasn't been written.

§ NETWORK AGNOSTIC RECONSTRUCTION PROTOCOLS AND SECURE MULTICAST

This section presents our network-agnostic reconstruction protocols and secure multicast protocol, along with their
properties. We start with the protocol $\RecShare$
for reconstructing a designated share,
presented in Fig <ref>.

$\RecShare([s], S_q, \ReceiverSet)$Network agnostic
reconstruction protocol to reconstruct a designated share $[s]_q$. The above code is executed by each $P_i \in \PartySet$.fig:RecShare

– Sending IC-signed Share to the Parties: If $P_i \in \W_q$, then
reveal $\ICSig(P_j, P_i, P_k, [s]_q)$ of every
$P_j \in \W_q$ to every $P_k \in \ReceiverSet \setminus \W_q$. Here $\W_q$ denotes the publicly known core-set corresponding to $S_q \in \ShareSpec_{\Z_s}$, as part of

– Computing Output: If $P_i \in (\ReceiverSet \cap \W_q)$, then output $[s]_q$.
Else if $P_i \in \ReceiverSet \setminus \W_q$, then
if there exists any $P_j \in \W_q$ and a value $s_{qj}$, such that $P_i$ has accepted
$\ICSig(P_k, P_j, P_i, s_{qj})$ of every $P_k \in \W_q$. Upon finding such a $P_j$,
output $[s]_q = s_{qj}$.[If there are multiple such parties $P_j$, then consider the one with the smallest index.]

We next prove the properties of the protocol $\RecShare$.

Lemma <ref>.
Let $s$ be a value which is linearly secret-shared with IC signatures, let $S_q \in \ShareSpec_{\Z_s}$ be a designated set and let $\ReceiverSet \subseteq \PartySet$ be a designated
set of receivers. Then protocol $\RecShare$ achieves the following.

– $\Z_s$-correctness: In a synchronous network, all honest parties in $\ReceiverSet$ output $[s]_q$ at time $\TimeRecShare = \TimeReveal$,
except with a probability of $\Order(n^2 \cdot \errorAICP)$.

–  $\Z_a$-correctness: In an asynchronous network, all honest parties in $\ReceiverSet$ eventually output $[s]_q$,
except with a probability of $\Order(n^2 \cdot \errorAICP)$.

– Privacy: If $\ReceiverSet$ consists of only honest parties, then the view of the adversary remains independent of $[s]_q$.

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

We first note that all honest parties in $(\ReceiverSet \cap \W_q)$ output $[s]_q$ correctly. So consider an arbitrary honest $P_i \in \ReceiverSet \setminus \W_q$.
We first show that $P_i$ indeed computes an output in the protocol, irrespective of the network type.

Since $\Z_s$ satisfies
the $\Q^{(1)}(\W_q, \Z_s)$ condition, it contains at least one honest party, say
$P_j$. Since $P_j$ follows the protocol steps honestly, it reveals $\ICSig(P_k, P_j, P_i, [s]_q)$ of
every $P_k \in \W_q$  to $P_i$.
From the correctness properties of ICP (see Theorem <ref>),
it follows that $P_i$ will accept the IC-signatures
$\ICSig(P_k, P_j, P_i, [s]_q)$, revealed by $P_j$, after time
$\TimeReveal$ in a synchronous network, or eventually in an asynchronous network.
On the other hand, even if $P_k \in \W_q$ is corrupt, then also
from the non-repudiation properties of ICP, it follows
that $P_i$
accepts $\ICSig(P_k, P_j, P_i, [s]_q)$, except with a probability $\errorAICP$,
after time
$\TimeReveal$ in a synchronous network, or eventually in an asynchronous network.
As there can be $\Order(n)$ corrupt parties in $\W_q$, from the union bound, it follows that
except with a probability $\Order(n \cdot \errorAICP)$, party $P_i$ will find a candidate party from $\W_q$, who reveals $[s]_q$, along with the IC-signature of all the parties in $\W_q$,
after time
$\TimeReveal$ in a synchronous network, or eventually in an asynchronous network.
This is because the honest party in $\W_q$ always constitutes a candidate party.
Now as there can be $\Order(n)$ parties in $\ReceiverSet \setminus \W_q$, it follows that
except with probability $\Order(n^2 \cdot \errorAICP)$, every honest party in $\ReceiverSet \setminus \W_q$ will
find a candidate party from $\W_q$, who reveals $[s]_q$, along with the IC-signature of all the parties in $\W_q$,
after time
$\TimeReveal$ in a synchronous network, or eventually in an asynchronous network.
Hence all honest parties in $\ReceiverSet$ compute an output,  after time
$\TimeReveal$ in a synchronous network, or eventually in an asynchronous network, except
with a probability $\Order(n^2 \cdot \errorAICP)$.

We next show that the output computed by all the honest parties is indeed correct. While this is trivially true for the parties in $(\ReceiverSet \cap \W_q)$,
consider an arbitrary honest party $P_i \in \ReceiverSet \setminus \W_q$.
The above argument shows that $P_i$ computes an output in the protocol, irrespective of the network type. So let $P_i$ output $s'$.
We wish to show that $s' =  [s]_q$. From the protocol steps, since $P_i$ outputs $s'$, it implies that there exists some $P_j \in \W_q$, such that $P_i$ has accepted
$\ICSig(P_k, P_j, P_i, s')$ of every $P_k \in \W_q$, revealed by $P_j$.  If $P_j$ is honest, then indeed $s' = [s]_q$, as one of the IC-signatures
$\ICSig(P_k, P_j, P_i, s')$ is the same as $\ICSig(P_k, P_j, P_i, [s]_q)$, corresponding to the honest $P_k \in \W_q$, which is guaranteed to exist.
So consider the case when $P_j$ is corrupt.
Moreover, let $P_k \in \W_q$ be an honest party (which is guaranteed to exist).
In order that $s' \neq [s]_q$, it must be the case that $P_i$ accepts  $\ICSig(P_k, P_j, P_i, s')$, revealed by $P_j$.  However, from
the unforgeability property of ICP (see Theorem <ref>), this can happen only with probability $\errorAICP$.
Now as there can be up to $\Order(n)$ corrupt parties in $\W_q$, from the union bound, it follows that the probability that $P_i$ outputs
$s' \neq [s]_q$ is at most $\Order(n \cdot \errorAICP)$.
And since there can be up to $\Order(n)$ parties in $\ReceiverSet \setminus \W_q$, it follows that except with probability at most
$\Order(n^2 \cdot \errorAICP)$, the output of every honest party in $\ReceiverSet$ is indeed $[s]_q$.

Communication complexity follows from the communication complexity of $\Reveal$ (Theorem <ref>) and the fact that $\Order(|\ReceiverSet| \cdot n^2)$ instances of $\Reveal$ are involved.
And privacy follows from the privacy of ICP.

Protocol $\Rec$ for reconstructing $s$ by a designated set of receivers is presented in Fig <ref>.

$\Rec([s], \ReceiverSet)$ Network agnostic reconstruction protocol to
reconstruct a secret-shared value with IC signatures. The above code is executed by each party $P_i \in \PartySet$.fig:Rec

– Reconstructing Individual Shares: Corresponding to each $S_q \in \ShareSpec_{\Z_s}$, participate in an instance $\RecShare([s], S_q, \ReceiverSet)$
of $\RecShare$, to let the parties in $\ReceiverSet$ reconstruct $[s]_q$.

– Computing Output: If $P_i \in \ReceiverSet$, then output $\displaystyle s = \sum_{S_q \in \ShareSpec} [s]_q$.

The properties of the protocol $\Rec$ are stated in Lemma <ref>.

Lemma <ref>.

Let $s$ be a value which is linearly secret-shared with IC signatures and let $\ReceiverSet \subseteq \PartySet$ be a set of designated receivers.
Then protocol $\Rec$ achieves the following.

– $\Z_s$-correctness: In a synchronous network, all honest parties in $\ReceiverSet$ output $s$ at time $\TimeRec = \TimeRecShare$,
except with probability $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$.

–  $\Z_a$-correctness: In an asynchronous network, all honest parties in $\ReceiverSet$ eventually output $s$,
except with probability $\Order(|\ShareSpec_{\Z_s}| \cdot n^2 \cdot \errorAICP)$.

– Privacy: If $\ReceiverSet$ consists of only honest parties, then the view of the adversary remains independent of $s$.

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

The proof follows from Lemma <ref>, and the fact that $|\ShareSpec_{\Z_s}|$ instances of $\RecShare$ are invoked.

§.§ Network Agnostic Secure Multicast

Protocol $\SVM$ is presented in Fig <ref>.

$\SVM(\Sender, v, \ReceiverSet)$The network agnostic SVM protocolfig:SVM

– Sending the Value to the Parties: $\Sender$ on having the input $v$, invokes an instance of $\VSS$ with input $v$ and the parties in $\PartySet$ participates in this instance.

– Verifying if Sender has Committed Any Value: Each $P_i \in \PartySet$  waits till its local time becomes $\TimeVSS$, initializes a Boolean variable $\flag^{(\Sender, \ReceiverSet)}$ to $0$ and
then do the following.

– Upon computing an output in the $\VSS$ instance, set $\flag^{(\Sender, \ReceiverSet)}$ to $1$.

– Upon setting $\flag^{(\Sender, \ReceiverSet)}$ to $1$, participate in an instance $\Rec([v], \ReceiverSet)$ of $\Rec$ to let the parties in $\ReceiverSet$ reconstruct $v$

– Computing Output: Each $P_i \in \ReceiverSet$ upon computing an output $v$ during the instance $\Rec([v], \ReceiverSet)$, outputs $v$.

We next prove the properties of the protocol $\SVM$.

Lemma <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 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.

Let us first consider an honest $\Sender$. If the network is synchronous, then from the $\Z_s$-correctness of $\VSS$ in the synchronous network (Theorem <ref>),
at time $\TimeVSS$, all honest parties will output $[v]$. Consequently, each honest party will set $\flag^{(\Sender, \ReceiverSet)}$ to $1$ and start participating in the instance of $\Rec$.
Hence, from the $\Z_s$-correctness of $\Rec$ in the synchronous network
(Lemma <ref>), coupled with the modifications presented in Section <ref>, it follows that all honest
parties  in $\ReceiverSet$ output $v$, except with probability $\Order(n^3 \cdot \errorAICP)$, after time $\TimeSVM = \TimeVSS + \TimeRec$.
The privacy of $v$ follows from the privacy of $\VSS$ (Theorem <ref>) and privacy of $\Rec$ (Lemma <ref>).
The proof for the case of honest $\Sender$ in an asynchronous network is the same as above, except that we now rely on the
$\Z_a$-correctness of $\VSS$ in the asynchronous network (Theorem <ref>) and the
$\Z_a$-correctness of $\Rec$ in the asynchronous network (Lemma <ref>).

Next consider a corrupt $\Sender$. Let us first consider a synchronous network. Let $P_i$ be the first honest party who sets
$\flag^{(\Sender, \ReceiverSet)}$ to $1$. This implies that there exists some $v^{\star}$, such that $P_i$ outputs $[v^{\star}]$. Let $T$ be the time when
$P_i$ outputs $[v^{\star}]$ during the instance of $\VSS$ (and hence sets $\flag^{(\Sender, \ReceiverSet)}$ to $1$).
From the $\Z_s$-commitment of $\VSS$ in the synchronous network, it follows that all honest parties will output $[v^{\star}]$
(and hence set $\flag^{(\Sender, \ReceiverSet)}$ to $1$), latest by time $T + \Delta$.
Hence all honest parties will start participating in the instance of $\Rec$, latest by time $T + \Delta$.
Hence, from the $\Z_s$-correctness of $\Rec$ in the synchronous network
(Lemma <ref>), coupled with the modifications presented in Section <ref>, it follows that all honest
parties  in $\ReceiverSet$ output $v^{\star}$, except with probability $\Order(n^3 \cdot \errorAICP)$, by time $T + 2\Delta$.

The proof for the case of a  corrupt $\Sender$ in an asynchronous network is the same as above, except that we now rely on the
$\Z_a$-commitment of $\VSS$ in the asynchronous network  (Theorem <ref>) and the $\Z_a$-correctness of $\Rec$ in the asynchronous network (Lemma <ref>).

The communication complexity follows from the communication complexity of $\VSS$ and $\Rec$.

§ PROPERTIES OF THE PROTOCOL $\MDVSS$

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

We first show that if the network is synchronous, then all honest parties will compute a common candidate set of committed dealers $\CD$ set by time $\TimeSVM + 2\TimeBA$, such that all honest dealers
are guaranteed to be present in $\CD$.

If the network is synchronous and $P_{\ell} \in \PartySet$ is an honest dealer participating with input $s^{(\ell)}$, then all the following hold in $\MDVSS$, where $\Hon$ is the set of
honest parties.

– Except with probability $\Order(n^3 \cdot \errorAICP)$, all the parties in $\Hon$ will have a common $\CD$ set by time $\TimeSVM + 2\TimeBA$, where
$\Hon \subseteq \CD$. [This automatically implies that $\PartySet \setminus \CD \in \Z_s$.]

– Except with probability $\Order(n^3 \cdot \errorAICP)$, corresponding to every dealer $P_{\ell} \in \CD$ and every $S_q \in \ShareSpec_{|\Z_s|}$,
every party in $(\Hon \cap S_q)$ will have a common share, say ${s^{\star}}^{(\ell)}_q$, which is the same as $s^{(\ell)}_q$, for an honest $P_{\ell}$.

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.
From the properties of $\SVM$ in the synchronous network (Lemma <ref>),
it follows that every $P_i \in \Hon$ will set $\flag^{(P_{\ell}, S_q)}$ to $1$ at time $\TimeVSS$, corresponding to every
$P_{\ell} \in \Hon$ and every $S_q \in \ShareSpec_{\Z_s}$. Moreover, at time $\TimeSVM$, corresponding to every
$P_{\ell} \in \Hon$ and every $S_q \in \ShareSpec_{\Z_s}$, each $P_i \in (\Hon \cap S_q)$ computes the output $s^{(\ell)}_{qi}$ during the instance $\SVM^{(P_{\ell}, S_q)}$.
Furthermore, except with probability $\Order(n^3 \cdot \errorAICP)$, the value $s^{(\ell)}_{qi}$ will be the same as $s^{(\ell)}_q$.
Hence, corresponding to every $P_{\ell} \in \Hon$, every $P_i \in \Hon$ will start participating with input $1$ during the instance $\BA^{(\ell)}$, at time $\TimeSVM$.
Hence from the $\Z_s$-validity of $\BA$ in the synchronous network (Theorem <ref>), at time $\TimeSVM + \TimeBA$,
all the parties in $\Hon$ will obtain the output $1$ from the $\BA^{(\ell)}$ instances, corresponding to each $P_{\ell} \in \Hon$.
Since $\PartySet \setminus \Hon \in \Z_s$, it follows that
at time $\TimeSVM + \TimeBA$, all the parties in $\Hon$ start participating with input $0$ in any remaining instance $\BA^{(\star)}$ of $\BA$, for which no input is provided yet.
Hence from the $\Z_s$-security of $\BA$ in the synchronous network (Theorem <ref>), all the parties in $\Hon$ will compute some output in all the $n$
instances of $\BA^{(\star)}$ by time $\TimeSVM + 2\TimeBA$. Moreover, the outputs will be common for the parties in $\Hon$.
Consequently, all the parties in $\Hon$ will have a common $\CD$ set at the time $\TimeSVM + 2\TimeBA$.
Moreover, $\Hon \subseteq \CD$, since $\CD$ includes all the dealers $P_{\ell}$ such that $\BA^{(\ell)}$ outputs $1$. And as shown above
the $\BA^{(\ell)}$ instances corresponding to $P_{\ell} \in \Hon$ outputs $1$.

Next, consider an arbitrary $P_{\ell} \in \CD$. This implies that at time $\TimeSVM + \TimeBA$, at least one party from $\Hon$, say $P_k$,
has participated with input $1$ during the instance $\BA^{(\ell)}$. If not, then from the $\Z_s$-validity of $\BA$ in the synchronous network (Theorem <ref>),
all the parties in $\Hon$ would have obtained the output $0$ from the instance $\BA^{(\ell)}$ at the time $\TimeSVM + 2\TimeBA$ and hence $P_{\ell} \not \in \CD$, which is a
contradiction. This implies that by the time $\TimeSVM + \TimeBA$, party $P_k$ has set $\flag^{(P_{\ell}, S_q)}$ to $1$ during the instance $\SVM(P_{\ell}, s^{(\ell)}_q, S_q)$,
for $q = 1, \ldots, |\Z_s|$.
So consider an arbitrary $S_q \in \ShareSpec_{\Z_s}$. From the properties of $\SVM$ in the synchronous network (Lemma <ref>),
it follows that there exists some value ${s^{\star}}^{(\ell)}_q$, which is the same as $s^{(\ell)}_q$ for an honest $P_{\ell}$,
such that except with probability $\Order(n^3 \cdot \errorAICP)$,
all the parties in $\Hon$ output ${s^{\star}}^{(\ell)}_q$ during the instance $\SVM^{(P_{\ell}, S_q)}$ by time $\TimeSVM + \TimeBA + 2\Delta < \TimeSVM + 2\TimeBA$.

We next show that if the network is synchronous and if an honest dealer from $\CD$
broadcasts any set of candidate core-sets, then all honest parties will “accept" the core-sets.
Moreover, the dealer will never make public the share corresponding to the group from $\ShareSpec_{\Z_s}$ consisting of only honest parties while making public these core-sets.
Furthermore, each honest dealer in $\CD$ will start making
public at least one candidate set of core-sets, namely the one computed with respect to the group from  $\ShareSpec_{\Z_s}$,
consisting of only honest parties. A consequence of all these properties is that if the dealer is honest, the adversary will not learn any information about the dealer's input.

If the network is synchronous and $P_{\ell} \in \CD$ is an honest dealer participating with input $s^{(\ell)}$, then all the following hold in $\MDVSS$ except with
probability $\Order(n^3 \cdot \errorAICP)$, where $\Hon$ is the set of honest parties.

–  If $S_p = \Hon$, then $P_{\ell}$ will broadcast
$(\CandidateCoreSets, P_{\ell}, S_p, \{ \W^{(\ell)}_{p, q}\}_{q = 1, \ldots, |\Z_s|},  \BroadcastSet^{(\ell)}_p, \allowbreak \{ s^{(\ell)}_q\}_{q \in \BroadcastSet^{(\ell)}_p})$ at time
$\TimeSVM + 2\TimeBA + \TimeAuth + \TimeBC$.

– If $P_{\ell}$ broadcasts any $(\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})$ at time
$T$, then every honest $P_i \in \PartySet$ will include $(P_{\ell}, S_p)$ to $\C_i$ at time $T + \TimeBC$.
Moreover, the following will hold.

– If $S_q = \Hon$, then $q \not \in \BroadcastSet^{(\ell)}_p$.

– For $q = 1, \ldots, |\Z_s|$, each $\W^{(\ell)}_{p, q}$ will be either $S_q$ or $(S_p \cap S_q)$. Moreover,
$\Z_s$ will satisfy the $\Q^{(1)}(\W^{(\ell)}_{p, q}, \Z_s)$ condition.

– If  $q \not \in \BroadcastSet^{(\ell)}_p$, then every honest $P_i \in S_q$ will have the share $s^{(\ell)}_q$.
Moreover, every honest $P_i \in \W^{(\ell)}_{p, q}$ will have $\ICSig(P_j, P_i, P_k, s^{(\ell)}_q)$ of every $P_j \in \W^{(\ell)}_{p, q}$ for every $P_k \in \PartySet$.
Furthermore, if any corrupt $P_j \in \W^{(\ell)}_{p, q}$ have $\ICSig(P_i, P_j, P_k, s'^{(\ell)}_q)$ of any honest $P_i \in \W^{(\ell)}_{p, q}$ for any $P_k \in \PartySet$, then
$s'^{(\ell)}_q = s^{(\ell)}_q$ holds. Also, all the underlying IC-signatures will satisfy the linearity property.

– The view of the adversary will be independent of $s^{(\ell)}$.

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.
Since the dealer $P_{\ell}$ is honest, from Lemma <ref> it follows that corresponding to
every $S_q \in \ShareSpec_{\Z_s}$, every party in $(\Hon \cap S_q)$ will have the share $s^{(\ell)}_{qi}$, by time $\TimeSVM + 2\TimeBA$, except with probability $\Order(n^3 \cdot \errorAICP)$, where
$s^{(\ell)}_{qi} = s^{(\ell)}_q$.
Now consider an arbitrary $S_q \in \ShareSpec_{\Z_s}$.
At time $\TimeSVM + 2\TimeBA$, each party $P_i \in (S_q \cap \Hon)$ starts giving
$\ICSig(P_i, P_j, P_k, s^{(\ell)}_{qi})$ to every $P_j \in S_q$, for every $P_k \in \PartySet$, where $s^{(\ell)}_{qi} = s^{(\ell)}_q$ holds.
Then from the $\Z_s$-correctness of $\Auth$  in the synchronous network (Theorem <ref>),
it follows that at time $\TimeSVM + 2\TimeBA + \TimeAuth$, each party $P_i \in (S_q \cap \Hon)$ will receive
$\ICSig(P_j, P_i, P_k, s^{(\ell)}_{qj})$ from every $P_j \in (S_q \cap \Hon)$, for every $P_k \in \PartySet$, such that $s^{(\ell)}_{qj} = s^{(\ell)}_{qi} = s^{(\ell)}_q$ holds.
Since $S_q$ is arbitrary, it follows that at time $\TimeSVM + 2\TimeBA + \TimeAuth$, every party $P_i \in \Hon$ broadcasts an $\OK^{(\ell)}(i, j)$ message, corresponding to every
$P_j \in \Hon$. From the $\Z_s$-validity of $\BC$ in the synchronous network (Theorem <ref>), it follows that
these $\OK^{(\ell)}(i, j)$ messages are received by every party in $\Hon$ through regular-mode at time $\TimeSVM + 2\TimeBA + \TimeAuth + \TimeBC$.
Consequently, the set $\Hon$ constitutes a clique in the consistency graph $G^{(\ell, i)}$ of every party $P_i \in \Hon$ at time $\TimeSVM + 2\TimeBA + \TimeAuth + \TimeBC$.
Note that the set $\Hon \in \ShareSpec_{\Z_s}$. Let $S_p$ be the set from $\ShareSpec_{\Z_s}$, such that $S_p = \Hon$.
From the protocol steps, it then follows that at time $\TimeSVM + 2\TimeBA + \TimeAuth + \TimeBC$, the dealer $P_{\ell}$  will compute core-sets $\W^{(\ell)}_{p, q}$
for $q = 1, \ldots, |\Z_s|$ and broadcast-set $\BroadcastSet^{(\ell)}_p$ with respect to $S_p$ as follows.

– If $S_q$ constitutes a clique in the graph $G^{(\ell, \ell)}$, then $\W^{(\ell)}_{p, q}$ is set as $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 $\W^{(\ell)}_{p, q}$ is set as $(S_p \cap S_q)$.

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

After computing the core-sets and  broadcast-set, $P_{\ell}$ will broadcast
$(\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})$ at time
$\TimeSVM + 2\TimeBA + \TimeAuth + \TimeBC$. This proves the first part of the lemma.

We next proceed to prove the second part of the lemma. So consider an arbitrary $S_p \in \ShareSpec_{\Z_s}$, such that $P_{\ell}$ compute core-sets $\W^{(\ell)}_{p, q}$
for $q = 1, \ldots, |\Z_s|$ and broadcast-set $\BroadcastSet^{(\ell)}_p$ with respect to $S_p$ and broadcasts
$(\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})$ at time $T$.
This means at time $T$, the parties in $S_p$ constitute a clique in the graph $G^{(\ell, \ell)}$.
We also note that $T \geq \TimeSVM + 2\TimeBA + \TimeAuth + \TimeBC$. This is because any instance of $\BC$ takes at least $\TimeBC$ time in a synchronous network to generate an output.
And the parties in $\Hon$ start participating in any $\BC$ instance invoked for broadcasting any $\OK^{(\ell)}(\star, \star)$ message, only after time $\TimeSVM + 2\TimeBA + \TimeAuth$.
any $\OK^{(\ell)}(\star, \star)$ message received by $P_{\ell}$, must be after time $\TimeSVM + 2\TimeBA + \TimeAuth + \TimeBC$.
We also note that any edge $(P_j, P_k)$ which is present in the graph $G^{(\ell, \ell)}$ of $P_{\ell}$ at time $T$, is bound to be present in the graph $G^{(\ell, i)}$ of every $P_i \in \Hon$, latest
by time $T + \Delta$. This is because the edge $(P_j, P_k)$ is added to $G^{(\ell, \ell)}$ upon the receipt of $\OK^{(\ell)}(j, k)$ and $\OK^{(\ell)}(k, j)$ messages from the broadcast of $P_j$
and $P_k$ respectively. And from the $\Z_s$-validity, $\Z_s$-consistency and $\Z_s$-fallback consistency of $\BC$ in the synchronous network, these $\OK^{(\ell)}(\star, \star)$
messages will be received by every party $P_i \in \Hon$, latest by time $T + \Delta$.
Since $P_{\ell}$ is assumed to be honest, it follows that the sets $\{ \W^{(\ell)}_{p, q}\}_{q = 1, \ldots, |\Z_s|}$ and $\BroadcastSet^{(\ell)}_p$ satisfy the following properties.

– If $S_q$ constitutes a clique in the graph $G^{(\ell, \ell)}$, then $\W^{(\ell)}_{p, q}$ is set as $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 $\W^{(\ell)}_{p, q}$ is set as $(S_p \cap S_q)$.

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

We also note that if $S_q = \Hon$, then $q \not \in \BroadcastSet^{(\ell)}_p$ and consequently, $P_{\ell}$ will not make the share $s^{(\ell)}_q$ public.
This is because $T \geq \TimeSVM + 2\TimeBA + \TimeAuth + \TimeBC$. And as shown in the proof of the first part, the set $\Hon$ will constitute a clique in the graph $G^{(\ell, \ell)}$ at time
$ \TimeSVM + 2\TimeBA + \TimeAuth + \TimeBC$. Since $P_{\ell}$ is honest, from the $\Z_s$-validity of $\BC$ in the synchronous network, it follows that all the parties in
$\Hon$ will receive $(\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})$
through the regular-mode at time $T + \TimeBC$. Moreover, each party $P_i \in \Hon$ will include $(P_{\ell}, S_p)$ to the set $\C_i$ at time $T + \TimeBC$.
This is because since $P_{\ell}$ has computed the sets
$\{ \W^{(\ell)}_{p, q}\}_{q = 1, \ldots, |\Z_s|}$ and $\BroadcastSet^{(\ell)}_p$ honestly, these sets will pass all the verifications for each $P_i \in \Hon$ at time $T + \Delta$.

Next consider an arbitrary $q \not \in \BroadcastSet^{(\ell)}_p$. This implies that $P_{\ell}$ has set $\W^{(\ell)}_{p, q}$ as $(S_p \cap S_q)$ because
the parties in $(S_p \cap S_q)$ constitutes a clique in the graph $G^{(\ell, \ell)}$. Now consider an arbitrary $P_i \in (\Hon \cap S_q)$.
This implies that $P_i$ has computed $s^{(\ell)}_{qi}$ during the instance $\SVM(P_{\ell}, s^{(\ell)}_q, S_q)$
at time $\TimeSVM$, which will be the same as $s^{(\ell)}_q$, since $P_{\ell}$ is honest.
Next consider arbitrary $P_i, P_j \in \W^{(\ell)}_{p, q}$, such that $P_j \neq P_i$. This implies that the edge $(i, j)$ is present in the graph $G^{(\ell, \ell)}$, which further implies that
$P_i$ has broadcasted the message $\OK^{(\ell)}(i, j)$. This further implies that $P_i$ must have received
$\ICSig(P_j, P_i, P_k, s^{(\ell)}_{qj})$ from $P_j$, for every $P_k \in \PartySet$, such that $s^{(\ell)}_{qj} = s^{(\ell)}_{qi}$ holds.
Since $s^{(\ell)}_{qi} = s^{(\ell)}_q$, it follows that $\ICSig(P_j, P_i, P_k, s^{(\ell)}_{qj})$ is the same as $\ICSig(P_j, P_i, P_k, s^{(\ell)}_{q})$.
On the other hand, consider an arbitrary $P_j \in \W^{(\ell)}_{p, q}$, such that $P_j$ is corrupt and where $P_j$ has received
$\ICSig(P_i, P_j, P_k, s'^{(\ell)}_{q})$ from $P_i$, for any $P_k  \in \PartySet$.
Then from the protocol steps, it follows that $s'^{(\ell)}_{q} = s^{(\ell)}_{qi}$, since $P_i$ gives the IC-signature on the share $s^{(\ell)}_{qi}$, received from $P_{\ell}$.
And since $s^{(\ell)}_{qi} = s^{(\ell)}_q$, it follows that  $\ICSig(P_i, P_j, P_k, s'^{(\ell)}_{q})$ is the same as  $\ICSig(P_i, P_j, P_k, s^{(\ell)}_{q})$.
The linearity of the underlying IC-signatures follow from the fact the parties follow the linearity principle while generating IC-signatures.

Finally, the privacy of $s^{(\ell)}$ follows from the fact that throughout the protocol, adversary does not learn anything about the share $s^{(\ell)}_q$, provided $S_q = \Hon$.
Namely, during the instance $\SVM(P_{\ell}, s^{(\ell)}_q, S_q)$ where
$(S_q \cap Z^{\star}) = \emptyset$, the view of the adversary remains independent of $s^{(\ell)}_q$, which follows from the privacy of $\SVM$ (Lemma <ref>).
Moreover, as shown above, $P_{\ell}$ never makes public the share  $s^{(\ell)}_q$, as $q \not \in \BroadcastSet^{(\ell)}_p$.
Furthermore, since the set $\Hon$ will consists of only honest parties, from the privacy of ICP (see Theorem <ref>), it follows that the adversary does not learn any additional information about
$s^{(\ell)}_q$, when the parties in $\Hon$ exchange IC-signed $s^{(\ell)}_q$ during the pairwise consistency tests.

We next show that if the network is synchronous, then any candidate set of core-sets “accepted" on the behalf of a corrupt dealer
by any honest party at the time $T$, is bound to be accepted by all honest parties, latest by time $T + \Delta$.

If the network is synchronous and if in $\MDVSS$ any honest party $P_i$ receives
$(\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})$ from the broadcast of any
corrupt dealer $P_{\ell} \in \CD$
and includes $(P_{\ell}, S_p)$ to $\C_i$ at time $T$, then all honest parties $P_j$ will receive
$(\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})$ from the broadcast of $P_{\ell}$
and include  $(P_{\ell}, S_p)$ to $\C_j$ by time $T + \Delta$.
Moreover, for $q = 1, \ldots, |\Z_s|$, the following holds, except with probability $\Order(n^3 \cdot \errorAICP)$.

– $\W^{(\ell)}_{p, q}$ is either $S_q$ or $(S_p \cap S_q)$. Moreover, $\Z_s$ satisfies the
$\Q^{(1)}(\W^{(\ell)}_{p, q} , \Z_s)$ condition.

– If  $q \not \in \BroadcastSet^{(\ell)}_p$, then every honest $P_i \in S_q$ will have a common share, say ${s^{\star}}^{(\ell)}_q$.
Moreover, every honest $P_i \in \W^{(\ell)}_{p, q}$ will have $\ICSig(P_j, P_i, P_k, {s^{\star}}^{(\ell)}_q)$ of every $P_j \in \W^{(\ell)}_{p, q}$ and for every $P_k \in \PartySet$.
Furthermore, if any corrupt $P_j \in \W^{(\ell)}_{p, q}$ has $\ICSig(P_i, P_j, P_k, s'^{(\ell)}_q)$ of any honest $P_i \in \W^{(\ell)}_{p, q}$ for any $P_k \in \PartySet$, then
$s'^{(\ell)}_q = {s^{\star}}^{(\ell)}_q$ holds. Also, all the underlying IC-signatures will satisfy the linearity principle.

The proof follows very closely the proof of Lemma <ref>. 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. Now consider
an arbitrary corrupt dealer $P_{\ell} \in \CD$ and an arbitrary $P_i \in \Hon$, such that
$P_i$ receives
$(\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})$ from the broadcast of
and includes $(P_{\ell}, S_p)$ to $\C_i$ at time $T$. Now consider another arbitrary $P_j \in \Hon$, such that $P_j \neq P_i$.
From the $\Z_s$-consistency and $\Z_s$-fallback consistency of $\BC$ in the synchronous network, it follows that $P_j$ is bound to receive
$(\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})$
from the broadcast of $P_{\ell}$, latest by time $T + \Delta$. We wish to show that $P_j$ will include $(P_{\ell}, S_p)$ to $\C_j$, by time $T + \Delta$.
For this, we note that since $P_i$ has included $(P_{\ell}, S_p)$ to $\C_i$ at time $T$,
all the following conditions hold for $P_i$ at time $T$,
for $q = 1, \ldots, |\Z_s|$.

– 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.

We claim that all the above conditions will hold even for $P_j$ by time $T + \Delta$. This is because all the edges which are present in the consistency graph $G^{(\ell, i)}$
at time $T$ are bound to be present in the consistency graph $G^{(\ell, j)}$ by time $T + \Delta$.
This follows from the $\Z_s$-validity, $\Z_s$-consistency and $\Z_s$-fallback consistency of $\BC$ in the synchronous network (see Theorem <ref>)
and the fact that the edges in the graph $G^{(\ell, i)}$ are based on $\OK^{(\ell)}(\star, \star)$ messages, which are received through various $\BC$ instances.

Next consider an arbitrary $q \not \in \BroadcastSet^{(\ell)}_p$. This implies that $\W^{(\ell)}_{p, q}$ is set as $(S_p \cap S_q)$ and
all the parties in $(S_p \cap S_q)$ constitute a clique in the consistency graph of every party in $\Hon$.
From the properties of $\SVM$ in the synchronous network, all honest parties in $S_q$ compute a common output, say ${s^{\star}}^{(\ell)}_q$, during the instance
$\SVM(P_{\ell}, s^{(\ell)}_q, S_q)$.
Next consider an arbitrary $P_i \in (\Hon \cap \W^{(\ell)}_{p, q})$ and any arbitrary $P_j \in \W^{(\ell)}_{p, q}$.
This implies that $P_i$ has broadcasted the message $\OK^{(\ell)}(i, j)$, after receiving
$\ICSig(P_j, P_i, P_k, s^{(\ell)}_{qj})$ from $P_j$, for every $P_k \in \PartySet$,
and verifying that the share $s^{(\ell)}_{qj}$ is the same as the one, computed during the instance $\SVM^{(P_{\ell}, s^{(\ell)}_q, S_q)}$.
Since the share computed by $P_i$ during $\SVM(P_{\ell}, s^{(\ell)}_q, S_q)$ is ${s^{\star}}^{(\ell)}_q$, it follows that
$\ICSig(P_j, P_i, P_k, s^{(\ell)}_{qj})$ is the same as $\ICSig(P_j, P_i, P_k, {s^{\star}}^{(\ell)}_q)$.
On the other hand, since $P_i$ gives its IC-signature on ${s^{\star}}^{(\ell)}_q$ to every $P_j \in S_q$, it follows that
if any corrupt $P_j \in \W^{(\ell)}_{p, q}$ has $\ICSig(P_i, P_j, P_k, s'^{(\ell)}_q)$ from $P_i$ for any $P_k \in \PartySet$, then
$s'^{(\ell)}_q = {s^{\star}}^{(\ell)}_q$ holds. The linearity of the underlying IC-signatures follow from the fact that the parties follow the linearity principle while generating the IC-signatures.

Now based on the previous two lemmas, we show that in a synchronous network, all honest parties will output a “legitimate"
set of parties $\Core$ after time $\TimeSVM + \TimeAuth + 2\TimeBC + 6\TimeBA$, such that at least one honest party is present in $\Core$.
And corresponding to every party in $\Core$, there exists some value, which is linearly secret-shared with IC-signatures. Moreover, the values corresponding to the honest parties remain private.

If the network is synchronous, then in $\MDVSS$, except with probability $\Order(n^3 \cdot \errorAICP)$,
at the time $\TimeMDVSS = \TimeSVM  + \TimeAuth + 2\TimeBC + 6\TimeBA$, all honest parties output a common set $\Core$,
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}$,
which is the input of $P_{\ell}$ for $\MDVSS$,
such that the values $\{  {s^{\star}}^{(\ell)}  \}_{P_{\ell} \in \Core}$ are linearly secret-shared with IC-signatures. Furthermore,
if $P_{\ell}$ is honest, then adversary's view is independent of $s^{(\ell)}$.

that the following hold.

– For $q = 1, \ldots, |\Z_s|$, every honest $P_i \in \W_q$ will have the share $[{s^{\star}}^{(\ell)}]_q$.

– For $q = 1, \ldots, |\Z_s|$, corresponding to every $P_j \in \W_q$ and every $P_k \not \in \W_q$, each honest party $P_i$ will have $\ICSig(P_j, P_i, P_k, [{s^{\star}}^{(\ell)}]_q)$.
And corresponding to each honest $P_i \in \W_q$ and every $P_k \not \in \W_q$, if any corrupt $P_j \in \W_q$ has
$\ICSig(P_j, P_i, P_k, s'^{(\ell)}_q)$, then $s'^{(\ell)}_q = [{s^{\star}}^{(\ell)}]_q$.

– If $P_{\ell}$ is honest, then the view of the adversary remains independent of $s^{(\ell)}$.

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.
From Lemma <ref>,  except with probability $\Order(n^3 \cdot \errorAICP)$, all the parties in $\Hon$ will have a common set of committed dealers
$\CD$ by the time $\TimeSVM + 2\TimeBA$, where
$\Hon \subseteq \CD$. Moreover, corresponding to every dealer $P_{\ell} \in \CD$ and every $S_q \in \ShareSpec_{|\Z_s|}$,
every party in $(\Hon \cap S_q)$ will have a common share, say ${s^{\star}}^{(\ell)}_q$, which is the same as $s^{(\ell)}_q$, for an $P_{\ell}$.
We begin by showing that once the set of committed dealers $\CD$ is decided, then all the $|\Z_s|$ instances $\BA^{(1, \star)}$ of $\BA$
and then all the $|\CD|$ instances $\BA^{(2, \star)}$ of $\BA$ will produce some output, for all the parties in $\Hon$, by time $\TimeMDVSS$.

Consider the set $S_p \in \ShareSpec_{\Z_s}$, such that $S_p = \Hon$.
Then corresponding to each $P_{\ell} \in (\Hon \cap \CD)$, every $P_i \in \Hon$ will receive
$(\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})$
from the broadcast of $P_{\ell}$
and includes $(P_{\ell}, S_p)$ to $\C_i$ at time  $\TimeSVM + 2\TimeBA + \TimeAuth + 2\TimeBC$ (see Lemma <ref>).
Since $\PartySet \setminus \Hon \in \Z_s$ and $\Hon \subseteq \CD$,
it follows that at the time  $\TimeSVM + 2\TimeBA+ \TimeAuth + 2\TimeBC$, every party $P_i \in \Hon$ will have a set ${\cal A}_{p, i}$ (namely ${\cal A}_{p, i} = \Hon$),
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}$.
Consequently, each $P_i \in \Hon$ starts participating in the instance $\BA^{(1, p)}$
with input $1$, at the time $\TimeSVM + 2\TimeBA + \TimeAuth + 2\TimeBC$.
From the $\Z_s$-security of $\BA$ in the synchronous network (see Theorem <ref>),
it follows that at the time $\TimeSVM + \TimeAuth + 2\TimeBC + 3 \TimeBA$, every $P_i \in \Hon$ obtains the output $1$ from the instance $\BA^{(1, p)}$.
Consequently, at the time $\TimeSVM +  \TimeAuth + 2\TimeBC + 3 \TimeBA$,
every party in $\Hon$ will start participating in the remaining $\BA^{(1, \star)}$ instances for which no input has been provided yet (if there are any), with input $0$.
And from the $\Z_s$-security of $\BA$ in the synchronous network,
these $\BA^{(1, \star)}$  instances will produce common outputs, for every party in $\Hon$, at the time $\TimeSVM + \TimeAuth + 2\TimeBC + 4\TimeBA$.
As a result, at the time $\TimeSVM + \TimeAuth + 2\TimeBC + 4\TimeBA$, all the parties in $\Hon$ will compute a $\qcore$. Moreover, $\qcore$ will be common for all the
parties in $\Hon$, since it corresponds to the least-indexed $\BA^{(1, \star)}$ instance among $\BA^{(1, 1)}, \ldots, \BA^{(1, |\Z_s|)}$, which produces output $1$. And from the
$\Z_s$-security of $\BA$ in the synchronous network, each $\BA^{(1, q)}$ instance produces a common output for every party in $\Hon$.
We also note that $\qcore$ will be indeed set to some value from the set $\{1, \ldots, |\Z_s| \}$. This is because as shown above, the index $p$ where $S_p = \Hon$ always constitute a candidate

We next claim that corresponding to $S_{\qcore}$,
there exists a subset of parties ${\cal B}_{\qcore}$, where $\CD \setminus {\cal B}_{\qcore} \in \Z_s$, such that corresponding to every $P_j \in {\cal B}_{\qcore}$,
the ordered pair $(P_j, S_{\qcore})$ is present in the set $\C_i$ of every $P_i \in \Hon$, at the time $\TimeSVM  + \TimeAuth + 2\TimeBC + 4\TimeBA$.
Assuming that the claim is true, it implies that all the parties in $\Hon$ will participate with input $1$ in the instances $\BA^{(2, j)}$, corresponding to every
$P_j \in {\cal B}_{\qcore}$, at the time $\TimeSVM +  \TimeAuth + 2\TimeBC + 4\TimeBA$. And hence from the $\Z_s$-security of the $\BA$ in the synchronous network (Theorem <ref>),
all the parties will obtain the output $1$ in the $\BA^{(2, j)}$ instances, corresponding to every
$P_j \in {\cal B}_{\qcore}$, at the time $\TimeSVM  + \TimeAuth + 2\TimeBC + 5\TimeBA$. As a result, at time $\TimeSVM + \TimeAuth + 2\TimeBC + 5\TimeBA$, all the parties in $\Hon$ will start participating
in the remaining $\BA^{(2, \star)}$ instances for which no input has been provided yet (if there are any), with input $0$.
Consequently, from the $\Z_s$-security of the $\BA$ in the synchronous network (Theorem <ref>),
at the time $\TimeMDVSS$, all the parties in $\Hon$ will have some output from all the $|\CD|$ instances of $\BA^{(2, \star)}$.
Moreover, the outputs will be common for all the parties in $\Hon$. Furthermore, the parties in $\Hon$ will have a subset $\Core$, which corresponds to all the
$\BA^{(2, j)}$ instances, which have produced output $1$. Note that $(\Hon \cap \Core) \neq \emptyset$. This is because ${\cal B}_{\qcore} \subseteq \Core$ and $\Hon \subseteq \CD$.
Consequently, $(\Hon \cap {\cal B}_{\qcore}) \neq \emptyset$, as otherwise $\Z_s$ does not satisfy the $\Q^{(2)}(\PartySet, \Z_s)$ condition, which is a contradiction.

We next proceed to prove our claim. Since the instance $\BA^{(1, \qcore)}$ has produced output $1$, it follows that at least one party from $\Hon$, say $P_k$, have participated with input $1$
in the instance $\BA^{(1, \qcore)}$. This is because if all the parties in $\Hon$ participates with input $0$ in the instance  $\BA^{(1, \qcore)}$, then from the $\Z_s$-validity of $\BA$ in the
synchronous network (Theorem <ref>), all the parties in $\Hon$ would have obtained the output $0$ from the instance $\BA^{(1, \qcore)}$, which is a contradiction.
We also note that $P_k$ would have started participating with input $1$ in the instance $\BA^{(1, \qcore)}$, latest by time $\TimeSVM + \TimeAuth + 2\TimeBC + 3 \TimeBA$.
This is because as argued above, by time $\TimeSVM   + \TimeAuth + 2\TimeBC + 3\TimeBA$, all the parties in $\Hon$ would have started participating in all the $|\Z_s|$ instances
of $\BA^{(1, \star)}$, with some input. Now since $P_k$ has participated with input $1$
in the instance $\BA^{(1, \qcore)}$, it follows that at the time $\TimeSVM + \TimeAuth + 2\TimeBC + 3\TimeBA$, there exists a subset of parties ${\cal A}_{\qcore, k}$, where
$\CD \setminus {\cal A}_{\qcore, k} \in \Z_s$, such that $(P_{\ell}, S_{\qcore})$ is present in the set $\C_k$, corresponding to every $P_{\ell} \in {\cal A}_{\qcore, k}$.
We show that the set ${\cal A}_{\qcore, k}$ constitutes the candidate ${\cal B}_{\qcore}$. For this, note that for any $P_{\ell} \in {\cal A}_{\qcore, k}$,
party $P_k$ includes $(P_{\ell}, S_{\qcore})$ to $\C_i$, only after receiving
a message $(\CandidateCoreSets, P_{\ell}, S_{\qcore}, \{ \W^{(\ell)}_{\qcore, q}\}_{q = 1, \ldots, |\Z_s|},  \BroadcastSet^{(\ell)}_{\qcore},  \{ s^{(\ell)}_q\}_{q \in \BroadcastSet^{(\ell)}_{\qcore}})$
from the broadcast of $P_{\ell}$
and verifying it. Moreover, $P_k$ must have received the message
$(\CandidateCoreSets, P_{\ell}, S_{\qcore}, \{ \W^{(\ell)}_{\qcore, q}\}_{q = 1, \ldots, |\Z_s|},  \BroadcastSet^{(\ell)}_{\qcore},  \{ s^{(\ell)}_q\}_{q \in \BroadcastSet^{(\ell)}_{\qcore}})$ from
each $P_{\ell} \in {\cal A}_{\qcore, k}$, latest by time $\TimeSVM  + \TimeAuth + 2\TimeBC + 3\TimeBA$.
It then follows from Lemma <ref> that by time $\TimeSVM + \TimeAuth + 2\TimeBC + 3\TimeBA + \Delta < \TimeSVM + \TimeAuth + 2\TimeBC + 4\TimeBA$,
every party in $\Hon$ would have received
$(\CandidateCoreSets, P_{\ell}, S_{\qcore}, \{ \W^{(\ell)}_{\qcore, q}\}_{q = 1, \ldots, |\Z_s|},  \BroadcastSet^{(\ell)}_{\qcore},  \{ s^{(\ell)}_q\}_{q \in \BroadcastSet^{(\ell)}_{\qcore}})$ from
each $P_{\ell} \in {\cal A}_{\qcore, k}$. And hence each party $P_i \in \Hon$ would include $(P_{\ell}, S_{\qcore})$ to the set $\C_i$, corresponding to every $P_{\ell} \in {\cal A}_{\qcore, k}$,
by time $\TimeSVM + \TimeAuth + 2\TimeBC + 4\TimeBA$. This proves our claim.

We next claim that at the time $\TimeMDVSS$, corresponding to every $P_{\ell} \in \Core$, every $P_i \in \Hon$ would have received a message
$(\CandidateCoreSets, P_{\ell}, S_{\qcore}, \{ \W^{(\ell)}_{\qcore, q}\}_{q = 1, \ldots, |\Z_s|},  \BroadcastSet^{(\ell)}_{\qcore},  \{ s^{(\ell)}_q\}_{q \in \BroadcastSet^{(\ell)}_{\qcore}})$ from
the broadcast of $P_{\ell}$. The proof for this is very similar to the proof of the previous claim and relies on the properties of $\BA$. So consider an arbitrary $P_{\ell} \in \Core$.
This implies that the instance  $\BA^{(2, \ell)}$ has produced output $1$ for all the parties in $\Hon$, which further implies that at least one party from $\Hon$, say $P_m$, has participated with input
$1$ during the instance $\BA^{(2, \ell)}$. If not, then from the $\Z_s$-validity of $\BA$ in the synchronous network (Theorem <ref>), the instance $\BA^{(2, \ell)}$
would have produced output $0$ for all the parties in $\Hon$, which is a contradiction.
We also note that $P_m$ must have started participating in the instance  $\BA^{(2, \ell)}$, latest by time $\TimeSVM + \TimeAuth + 2\TimeBC + 5\TimeBA$.
This is because as shown above, by time $\TimeSVM + \TimeAuth + 2\TimeBC + 5\TimeBA$, all the parties in $\Hon$ would have started participating in all the $|\CD|$
instances of $\BA^{(2, \star)}$, with some input. Now since $P_m$ participates with input $1$ in the instance $\BA^{(2, \ell)}$, it follows that by time
$\TimeSVM + \TimeAuth + 2\TimeBC + 5\TimeBA$, party $P_m$ must have received a message
$(\CandidateCoreSets, P_{\ell}, S_{\qcore}, \{ \W^{(\ell)}_{\qcore, q}\}_{q = 1, \ldots, |\Z_s|},  \BroadcastSet^{(\ell)}_{\qcore},  \{ s^{(\ell)}_q\}_{q \in \BroadcastSet^{(\ell)}_{\qcore}})$
from the broadcast of $P_{\ell}$ and included $(P_{\ell}, S_{\qcore})$ to $\C_m$.
It then follows from Lemma <ref> that by time $\TimeSVM + \TimeAuth + 2\TimeBC + 5\TimeBA + \Delta < \TimeSVM + \TimeAuth + 2\TimeBC + 6\TimeBA$,
every party $P_i$ in $\Hon$ would have received
$(\CandidateCoreSets, P_{\ell}, S_{\qcore}, \{ \W^{(\ell)}_{\qcore, q}\}_{q = 1, \ldots, |\Z_s|},  \BroadcastSet^{(\ell)}_{\qcore},  \{ s^{(\ell)}_q\}_{q \in \BroadcastSet^{(\ell)}_{\qcore}})$ from
$P_{\ell}$ and would include $(P_{\ell}, S_{\qcore})$ to $\C_i$.

Till now we have shown that all the all the $|\Z_s|$ instances $\BA^{(1, \star)}$ of $\BA$
and then all the $|\CD|$ instances $\BA^{(2, \star)}$ of $\BA$ will produce some output, for all the parties in $\Hon$, by time $\TimeMDVSS$. Moreover, at the time
$\TimeMDVSS$, all the parties in $\Hon$ will have a common $\qcore \in \{1, \ldots, |\Z_s| \}$ and a common set $\Core \subseteq \PartySet$, where $\Core$ has at least one honest party.
Furthermore, corresponding to every $P_{\ell} \in \Core$, each $P_i \in \Hon$ would have received a message
$(\CandidateCoreSets, P_{\ell}, S_{\qcore}, \{ \W^{(\ell)}_{\qcore, q}\}_{q = 1, \ldots, |\Z_s|},  \BroadcastSet^{(\ell)}_{\qcore},  \{ s^{(\ell)}_q\}_{q \in \BroadcastSet^{(\ell)}_{\qcore}})$
from the broadcast of $P_{\ell}$. Furthermore, from Lemma <ref>, corresponding to each $P_{\ell} \in \Core$, the set
$\W^{(\ell)}_{\qcore, q}$ will be either the set $S_q$ or $(S_{\qcore} \cap S_q)$, for $q = 1, \ldots, |\Z_s|$. If
$\W^{(\ell)}_{\qcore, q} = S_q$ for every $P_{\ell} \in \Core$, then all the parties in $\Hon$ will set $\W_q$ to $S_q$.
On the other hand, if $\W^{(\ell)}_{\qcore, q} = (S_{\qcore} \cap S_q)$ for any $P_{\ell} \in \Core$, then all the parties in
$\Hon$ will set $\W_q$ to $(S_{\qcore} \cap S_q)$. Irrespective of the case, all the parties in $\Hon$ would set $\W_q$ to a common subset.
We also note that irrespective of the case, $S_q \setminus \W_q \in \Z_a$ holds. This is because from Lemma <ref>
and Lemma <ref>, the condition $S_q \setminus \W^{(\ell)}_{\qcore, q} \in \Z_a$ holds, corresponding to every
$P_{\ell} \in \Core$.

Finally consider an arbitrary $P_{\ell} \in \Core$ and an arbitrary $S_q \in \ShareSpec_{\Z_s}$. We claim that at the time $\TimeMDVSS$, all the parties in $(\Hon \cap S_q)$
will have a common share, say ${s^{\star}}^{(\ell)}_q$, where ${s^{\star}}^{(\ell)}_q = s^{(\ell)}_q$ for an honest $P_{\ell}$. For this, we consider two possible cases.
If $q \in \BroadcastSet^{(\ell)}_{\qcore}$, then each $P_i \in (\Hon \cap S_q)$ would have received  $s^{(\ell)}_q$ from the broadcast of $P_{\ell}$, as part of the
$(\CandidateCoreSets, P_{\ell}, S_{\qcore}, \{ \W^{(\ell)}_{\qcore, q}\}_{q = 1, \ldots, |\Z_s|},  \BroadcastSet^{(\ell)}_{\qcore},  \{ s^{(\ell)}_q\}_{q \in \BroadcastSet^{(\ell)}_{\qcore}})$
message. Consequently, in this case ${s^{\star}}^{(\ell)}_q$ is the same as $s^{(\ell)}_q$, received from the broadcast of $P_{\ell}$.
On the other hand, if  $q \not \in \BroadcastSet^{(\ell)}_{\qcore}$, then from Lemma <ref>,
each $P_i \in (\Hon \cap S_q)$ would have a common share, say ${s^{(\star)}}^{(\ell)}_q$; moreover, from Lemma <ref>,
if $P_{\ell}$ is honest, then ${s^{(\star)}}^{(\ell)}_q = s^{(\ell)}_q$  holds. We define

\[ {s^{\star}}^{(\ell)} \defined \displaystyle \sum_{q = 1, \ldots, |\Z_s|}  {s^{(\star)}}^{(\ell)}_q,     \]

where ${s^{\star}}^{(\ell)} = s^{(\ell)}$ for an honest $P_{\ell}$.
Hence at time $\TimeMDVSS$, each party in $(\Hon \cap S_q)$ has $[{s^{\star}}^{(\ell)}]_q$.
We also note that if $q \in \BroadcastSet^{(\ell)}_{\qcore}$, then every $P_i \in \W_q$ sets $\ICSig(P_j, P_i, P_k, [{s^{\star}}^{(\ell)}]_q)$
to the default value, corresponding to every $P_j \in \W_q$ and every $P_k \in \PartySet$.
On the other hand, if $q \not \in  \BroadcastSet^{(\ell)}_{\qcore}$,
then every $P_i \in (\Hon \cap S_q)$ will have $\ICSig(P_j, P_i, P_k, {s^{\star}}^{(\ell)}_q)$ of every $P_j \in \W_q$ and for every $P_k \in \PartySet$.
Furthermore, if any corrupt $P_j \in \W_q$ has $\ICSig(P_i, P_j, P_k, s'^{(\ell)}_q)$ of any $P_i \in (\Hon \cap S_q)$ for any $P_k  \in \PartySet$, then
$s'^{(\ell)}_q = {s^{\star}}^{(\ell)}_q$ holds.
Moreover, from Lemma <ref>, if $P_{\ell}$ is honest, then ${s^{\star}}^{(\ell)}_q$ in the IC-signatures mentioned above will be the same as
$s^{(\ell)}_q$. It then follows that ${s^{\star}}^{(\ell)}$ will be linearly secret-shared; the linearity of the underlying IC-signatures
follows since the (honest) parties follow the linearity principle, while generating the IC-signatures.

The privacy of $s^{(\ell)}$ for an honest $P_{\ell}$ follows from Lemma <ref>.

We next consider an asynchronous network. We first prove an analogue of Lemma <ref> in the asynchronous network.

If the network is asynchronous and $P_{\ell} \in \PartySet$ is an honest dealer participating with input $s^{(\ell)}$, then all the following hold in $\MDVSS$, where $\Hon$ is the set of
honest parties.

– Except with probability $\Order(n^3 \cdot \errorAICP)$, almost-surely, all the parties in $\Hon$ will eventually have a common $\CD$ set, where
$\PartySet \setminus \CD \in \Z_s$.

– Except with probability $\Order(n^3 \cdot \errorAICP)$, corresponding to every dealer $P_{\ell} \in \CD$ and every $S_q \in \ShareSpec_{|\Z_s|}$,
every party in $(\Hon \cap S_q)$ will eventually have a common share, say ${s^{\star}}^{(\ell)}_q$, which is the same as $s^{(\ell)}_q$, for an honest $P_{\ell}$.

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. Note that $\Hon \in \ShareSpec_{\Z_s}$, since $\Z_a \subset \Z_s$.
From the properties of $\SVM$ in the asynchronous network (Lemma <ref>),
it follows that every $P_i \in \Hon$ will eventually set $\flag^{(P_{\ell}, S_q)}$ to $1$ during the instance $\SVM(P_{\ell}, s^{(\ell)}_q, S_q)$, corresponding to every
$P_{\ell} \in \Hon$ and every $S_q \in \ShareSpec_{\Z_s}$. Moreover, corresponding to every
$P_{\ell} \in \Hon$ and every $S_q \in \ShareSpec_{\Z_s}$, each $P_i \in (\Hon \cap S_q)$ eventually computes an output $s^{(\ell)}_{qi}$ during the instance $\SVM((P_{\ell}, s^{(\ell)}_q, S_q)$.
Furthermore, except with probability $\Order(n^3 \cdot \errorAICP)$, the value $s^{(\ell)}_{qi}$ will be the same as $s^{(\ell)}_q$.

We first claim that there always exists a subset of parties ${\cal D}$, where $\PartySet \setminus {\cal D} \in \Z_s$, such that the $\BA$ instance $\BA^{(\ell)}$ eventually produces output $1$ for all the
parties in $\Hon$, corresponding to every $P_{\ell} \in {\cal D}$. Assuming that the claim is true, it implies that all the parties in $\Hon$ will eventually participate with some input in the $\BA$ instances
$\BA^{(1)}, \ldots, \BA^{(n)}$. This is because from the protocol steps, once the $\BA^{(\star)}$ instances corresponding to the parties in ${\cal D}$ produce output $1$, all the parties in $\Hon$ will start participating with input
$0$ in the remaining instances $\BA^{(\star)}$ of $\BA$ (if any), for which no input has been provided yet.
And hence from the $\Z_a$-security of $\BA$ in the asynchronous network, it follows that almost-surely, all these $\BA$ instances will eventually produce some output
for all the parties in $\Hon$. Moreover, the outputs will be the same for all the parties in $\Hon$. Consequently, all the parties in $\Hon$ will eventually obtain a common $\CD$ set. Moreover,
$\PartySet \setminus \CD \in \Z_s$, since $\CD$ consists of all those parties $P_{\ell}$, such that the instance $\BA^{(\ell)}$ produces output $1$. And according to our claim, ${\cal D} \subseteq \CD$ holds. We now
proceed to prove our claim.

There are two possible cases. Consider the case when some $P_i \in \Hon$ starts participating with input $0$ in any $\BA^{(\star)}$ instance. This implies that for $P_i$, there exists a subset of parties
$\CD_i$ where $\PartySet \setminus \CD_i \in \Z_s$, such that corresponding to every $P_{\ell} \in \CD_i$, the instance $\BA^{(\ell)}$ has produced output $1$ for $P_i$. In this case, the set $\CD_i$ is the
candidate ${\cal D}$ set, whose existence we want to prove. Next, consider the case when no party in $\Hon$ has started participating with input $0$ in any of the $\BA^{(\star)}$ instances.
In this case, the set $\Hon$ constitutes the candidate ${\cal D}$ set. This is because as shown above, every $P_i \in \Hon$ will eventually set $\flag^{(P_{\ell}, S_q)}$ to $1$, corresponding to every