$\Pi_{\mathsf{BC}}$, corresponding to every $P_{j}\in\mathcal{R}_{h}$. This is
because the subset of parties $\mathcal{H}\cap\mathcal{R}$ constitutes a
candidate $\mathcal{R}_{h}$. Consequently, $P_{h}$ will set $b$ as its input
for the instance of $\Pi_{\mathsf{ABA}}$, thus proving the claim.

The communication complexity, both in a synchronous as well as in an
asynchronous network, follows easily from the protocol steps and from the
communication complexity of $\Pi_{\mathsf{SBA}}$ and $\Pi_{\mathsf{ABA}}$.

##  Appendix 0.D Properties of the Best-of-Both-Worlds VSS Protocol

In this section we prove the properties of the protocol $\Pi_{\mathsf{VSS}}$
(see Fig 3 for the formal description of the protocol). Recall that we want to
prove the properties of $\Pi_{\mathsf{VSS}}$ assuming an adversary
$\mathcal{A}$ characterized by an adversary structure $\mathcal{Z}_{s}$ in a
synchronous network, and an adversary structure $\mathcal{Z}_{a}$ in an
asynchronous network, satisfying the following conditions.

  * –

$\mathcal{Z}_{s}\neq\mathcal{Z}_{a}$;

  * –

For every subset $Z\in\mathcal{Z}_{a}$, there exists a subset
$Z^{\prime}\in\mathcal{Z}_{s}$, such that $Z\subseteq Z^{\prime}$;

  * –

$\mathcal{Z}_{s}$ and $\mathcal{Z}_{a}$ satisfy the
$\mathcal{Q}^{(3,1)}(\mathcal{P},\mathcal{Z}_{s},\mathcal{Z}_{a})$ condition.

Moreover, we are considering the sharing specification
$\mathbb{S}=\\{S_{m}:S_{m}=\mathcal{P}\setminus Z_{m}\;\mbox{ and
}\;Z_{m}\in\mathcal{Z}_{s}\\}$. Note that the above conditions automatically
imply that $\mathcal{Z}_{s}$ satisfies the
$\mathcal{Q}^{(3)}(\mathcal{P},\mathcal{Z}_{s})$ condition and
$\mathcal{Z}_{a}$ satisfies the
$\mathcal{Q}^{(4)}(\mathcal{P},\mathcal{Z}_{a})$ condition. Before proving the
properties, we prove a related property, which will later be useful while
proving the properties of $\Pi_{\mathsf{VSS}}$.

###### Lemma 9

In protocol $\Pi_{\mathsf{VSS}}$ if the network is synchronous and if the
output of $\Pi_{\mathsf{BA}}$ is $1$, then the following hold.

  * –

All honest parties participated in the instance of $\Pi_{\mathsf{BA}}$ with
input $1$.

  * –

Corresponding to every $S_{m}\in\mathbb{S}$, all honest parties in
$\mathcal{C}_{m}$ received a common share from $\mathsf{D}$ by time $\Delta$.

###### Proof

Let the network be synchronous and let all the honest parties output $1$
during the instance of $\Pi_{\mathsf{BA}}$. This implies at least one honest
party, say $P_{h}$, has participated in $\Pi_{\mathsf{BA}}$ with input $1$. If
this is not the case and if all honest parties participated with input $0$ in
$\Pi_{\mathsf{BA}}$, then from the $\mathcal{Z}_{s}$-validity of
$\Pi_{\mathsf{BA}}$ in the synchronous network, all honest parties would
compute the output $0$ during the instance of $\Pi_{\mathsf{BA}}$, which is a
contradiction.

Since $P_{h}$ has participated with input $1$ in the instance of
$\Pi_{\mathsf{BA}}$, it implies that $P_{h}$ has received the sets
$\mathcal{C}_{1},\ldots,\mathcal{C}_{q}$ from the broadcast of $\mathsf{D}$ at
time $2\Delta+2T_{\mathsf{BC}}$ through regular-mode and accepted these sets.
From the $\mathcal{Z}_{s}$-validity and $\mathcal{Z}_{s}$-consistency of
$\Pi_{\mathsf{BC}}$ in the synchronous network, every other honest party would
also receive these sets from the broadcast of $\mathsf{D}$ at time
$2\Delta+2T_{\mathsf{BC}}$. Since $P_{h}$ has accepted
$\mathcal{C}_{1},\ldots,\mathcal{C}_{q}$, it implies that $P_{h}$ has checked
that all the following hold.

  * –

For $m=1,\ldots,q$, the set $\mathcal{C}_{m}$ constitutes a clique in the
consistency graph $G_{h}^{(m)}$ of $P_{h}$ at time $2\Delta+T_{\mathsf{BC}}$.
That is, for every $P_{i},P_{j}\in\mathcal{C}_{m}$, the messages
$\texttt{OK}(m,i,j)$ and $\texttt{OK}(m,j,i)$ have been received from the
broadcast of $P_{i}$ and $P_{j}$ respectively by time
$2\Delta+T_{\mathsf{BC}}$. By the $\mathcal{Z}_{s}$-validity and
$\mathcal{Z}_{s}$-consistency of $\Pi_{\mathsf{BC}}$ in the synchronous
network, these messages are also received by every other honest party by time
$2\Delta+T_{\mathsf{BC}}$. Consequently,
$\mathcal{C}_{1},\ldots,\mathcal{C}_{q}$ will constitute a clique in the
consistency graphs $G_{k}^{(1)},\ldots,G_{k}^{(m)}$ respectively of every
honest party at time $2\Delta+T_{\mathsf{BC}}$.

  * –

For $m=1,\ldots,q$, the condition
$S_{m}\setminus\mathcal{C}_{m}\in\mathcal{Z}_{s}$ holds. It is easy to see
that every honest party will find that this condition holds.

  * –

For $m=1,\ldots,q$, if $\texttt{NOK}(m,j)$ was received from the broadcast of
any $P_{j}\in S_{m}$ through regular mode at time $2\Delta+T_{\mathsf{BC}}$,
then the following hold at time $2\Delta+2T_{\mathsf{BC}}$.

    * –

$\texttt{Resolve}(m,s^{(m)})$ is received from the broadcast of $\mathsf{D}$
through regular-mode.

    * –

$\texttt{Resolve}(m,s^{(m)})$ is received from the broadcast of a subset of
parties $\mathcal{C}^{\prime}_{m}$ through regular-mode, where
$\mathcal{C}^{\prime}_{m}\subseteq\mathcal{C}_{m}$ and
$\mathcal{C}_{m}\setminus\mathcal{C}^{\prime}_{m}\in\mathcal{Z}_{s}$.

From the $\mathcal{Z}_{s}$-validity and $\mathcal{Z}_{s}$-consistency of
$\Pi_{\mathsf{BC}}$ in the synchronous network, the above conditions will be
also satisfied for every honest party. In more detail, if any
$\texttt{NOK}(m,j)$ was received by $P_{h}$ from the broadcast of any
$P_{j}\in S_{m}$ through regular-mode at time $2\Delta+T_{\mathsf{BC}}$, then
the same $\texttt{NOK}(m,j)$ message would be received through regular-mode at
time $2\Delta+T_{\mathsf{BC}}$ by every honest party. Due to a similar reason,
any corresponding $\texttt{Resolve}(m,s^{(m)})$ message which is received by
$P_{h}$ through regular-mode at time $2\Delta+2T_{\mathsf{BC}}$, either from
the broadcast of $\mathsf{D}$ or from the broadcast of any party in
$\mathcal{C}_{m}$, will also be received by every honest party.

It thus follows that the conditions for accepting the
$\mathcal{C}_{1},\ldots,\mathcal{C}_{q}$ will hold for every honest party at
time $2\Delta+2T_{\mathsf{BC}}$ and so, all honest parties participate with
input $1$ during the instance of $\Pi_{\mathsf{BA}}$. This proves the first
part of the lemma.

We now prove the second part of the lemma. The statement is obviously true, if
$\mathsf{D}$ is honest. So, we consider a corrupt $\mathsf{D}$. Let $S_{m}$ be
an arbitrary set in $\mathbb{S}$. We first note that all the honest parties in
$\mathcal{C}_{m}$ received a common share, say $s^{(m)}$, from $\mathsf{D}$.
This is because, from the proof of the first part of the lemma, there exists
some honest party $P_{h}$, who has received $\mathcal{C}_{m}$ from the
broadcast of $\mathsf{D}$ through regular-mode at time
$2\Delta+2T_{\mathsf{BC}}$ and has accepted $\mathcal{C}_{m}$. And while
accepting $\mathcal{C}_{m}$, party $P_{h}$ has verified that $\mathcal{C}_{m}$
constitutes a clique in its consistency graph $G_{h}^{(m)}$ at time
$2\Delta+T_{\mathsf{BC}}$. Hence, the messages $\texttt{OK}(m,i,j)$ and
$\texttt{OK}(m,j,i)$ have been received by $P_{h}$ from the broadcast of every
honest $P_{i},P_{j}\in\mathcal{C}_{m}$ by time $2\Delta+T_{\mathsf{BC}}$. This
automatically implies that $s_{i}^{(m)}=s_{j}^{(m)}$ holds, where
$s_{i}^{(m)}$ and $s_{j}^{(m)}$ denotes the shares received from $\mathsf{D}$
by $P_{i}$ and $P_{j}$ respectively, corresponding to $S_{m}$. We wish to show
that both $P_{i}$ and $P_{j}$ would have received their respective shares
within time $\Delta$.

On the contrary, let $P_{i}$ receive $s^{(m)}_{i}$ from $\mathsf{D}$ at time
$\Delta+\delta$, where $\delta>0$. From the protocol steps, $P_{i}$ starts
performing pairwise consistency checks only when its local time becomes a
multiple of $\Delta$. Hence, $P_{i}$ must have started sending its share
$s^{(m)}_{i}$ to the other parties at time $c\cdot\Delta$, where $c>1$.
Similarly, from the protocol steps, $P_{j}$ will start broadcasting the
$\texttt{OK}(m,j,i)$ message, only at time $(c+1)\cdot\Delta$, since it waits
till its local time becomes a multiple of $\Delta$, before broadcasting any OK
or NOK messages. Now, by the $\mathcal{Z}_{s}$-validity of $\Pi_{\mathsf{BC}}$
in the synchronous network, it takes $T_{\mathsf{BC}}$ time for the
$\texttt{OK}(m,j,i)$ messages to be received by any honest party. Hence, the
edge $(P_{i},P_{j})$ gets added in the consistency graph $G_{k}^{(m)}$ of
every honest party only at time $(c+1)\cdot\Delta+T_{\mathsf{BC}}$. However,
this is a contradiction, since
$(c+1)\cdot\Delta+T_{\mathsf{BC}}>2\Delta+T_{\mathsf{BC}}$.

We now proceed to prove the properties of the protocol $\Pi_{\mathsf{VSS}}$.
We start with the correctness property in the synchronous network.

###### Lemma 10

In protocol $\Pi_{\mathsf{VSS}}$, if $\mathsf{D}$ is honest and participates
with input $s$, then in a synchronous network, $s$ is secret-shared, with
respect to the sharing specification $\mathbb{S}$, at time
$T_{\mathsf{VSS}}=2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$.

###### Proof

Let $Z_{s}^{\star}\in\mathcal{Z}_{s}$ be the set of corrupt parties, and let
$\mathcal{H}_{s}\stackrel{{\scriptstyle def}}{{=}}\mathcal{P}\setminus
Z_{s}^{\star}$ be the set of honest parties. We show that corresponding to
every $S_{m}\in\mathbb{S}$, all honest parties in $S_{m}$ output the share
$s^{(m)}$ at time $T_{\mathsf{VSS}}$, where $s^{(m)}$ is the share picked by
$\mathsf{D}$, corresponding to $S_{m}$. The lemma then follows from the fact
that since $\mathsf{D}$ is honest, it selects the shares
$s^{(1)},\ldots,s^{(q)}$, satisfying the condition $s^{(1)}+\ldots+s^{(q)}=s$.
So, consider an arbitrary $S_{m}\in\mathbb{S}$, and let
$\mathcal{H}_{m}=S_{m}\setminus Z_{s}^{\star}$ be the set of honest parties in
$S_{m}$.

During Phase I, every $P_{i}\in\mathcal{H}_{m}$ receives the share
$s^{(m)}_{i}$ from $\mathsf{D}$ within time $\Delta$, where
$s^{(m)}_{i}=s^{(m)}$. During Phase II, every $P_{i}\in\mathcal{H}_{m}$ sends
$s_{i}^{(m)}$ to every $P_{j}\in S_{m}$, which takes at most $\Delta$ time to
be delivered. Hence, by time $2\Delta$, every $P_{i}\in\mathcal{H}_{m}$
receives $s^{(m)}_{j}$ from every $P_{j}\in\mathcal{H}_{m}$, such that
$s^{(m)}_{i}=s^{(m)}_{j}$ holds. Consequently, during Phase III, every
$P_{i}\in\mathcal{H}_{m}$ broadcasts $\texttt{OK}(m,i,j)$ corresponding to
every $P_{j}\in\mathcal{H}_{m}$, and vice versa. From the
$\mathcal{Z}_{s}$-validity of $\Pi_{\mathsf{BC}}$ in the synchronous network,
it follows that all the parties in $\mathcal{H}_{m}$ receive the
$\texttt{OK}(m,i,j)$ and $\texttt{OK}(m,j,i)$ messages through regular-mode at
time $2\Delta+T_{\mathsf{BC}}$, from the broadcast of every
$P_{i}\in\mathcal{H}_{m}$ and every $P_{j}\in\mathcal{H}_{m}$. Hence,
corresponding to every $P_{i},P_{j}\in\mathcal{H}_{m}$, the edge
$(P_{i},P_{j})$ will be added to the graph $G_{k}^{(m)}$ of every
$P_{k}\in\mathcal{H}_{m}$. Furthermore, from the $\mathcal{Z}_{s}$-consistency
property of $\Pi_{\mathsf{BC}}$ in the synchronous network, the graph
$G_{k}^{(m)}$ will be the same for every $P_{k}\in\mathcal{H}_{m}$ (including
$\mathsf{D}$) at time $2\Delta+T_{\mathsf{BC}}$.

From the above arguments, the set of parties in $\mathcal{H}_{m}$ will
constitute a clique in the consistency graph of all the parties in
$\mathcal{H}_{m}$. Moreover, $S_{m}\setminus\mathcal{H}_{m}\subseteq
Z_{s}^{\star}\in\mathcal{Z}_{s}$. Hence, during Phase IV, $\mathsf{D}$ will be
able to find a candidate $\mathcal{C}_{m}$ set and broadcast it, which will be
received by all the parties in $\mathcal{H}_{s}$ through regular-mode within
time $2\Delta+2T_{\mathsf{BC}}$ (follows from the $\mathcal{Z}_{s}$-validity
of $\Pi_{\mathsf{BC}}$ in the synchronous network). Now, consider an arbitrary
honest party $P_{k}$, who receives the message $\texttt{NOK}(m,j)$ from a
party $P_{j}\in S_{m}$ through regular-mode at time $2\Delta+T_{\mathsf{BC}}$.
From the $\mathcal{Z}_{s}$-validity and $\mathcal{Z}_{s}$-consistency
properties of $\Pi_{\mathsf{BC}}$ in the synchronous network, this
$\texttt{NOK}(m,j)$ message will be received by all the parties in
$\mathcal{H}_{m}$ through regular-mode at time $2\Delta+T_{\mathsf{BC}}$.
Consequently, all the parties in $\mathcal{H}_{m}$ (including $\mathsf{D}$)
will respond by broadcasting the $\texttt{Resolve}(m,s^{(m)})$ message, which
will be received by all the honest parties through regular mode at time
$2\Delta+2T_{\mathsf{BC}}$. Since
$\mathcal{C}_{m}\setminus\mathcal{H}_{m}\subseteq
Z_{s}^{\star}\in\mathcal{Z}_{s}$, it follows that the conditions for accepting
$\mathcal{C}_{m}$ will hold for all the honest parties at time
$2\Delta+2T_{\mathsf{BC}}$. Consequently, all honest parties will participate
with input $1$ in the instance of $\Pi_{\mathsf{BA}}$ and from the
$\mathcal{Z}_{s}$-validity and $\mathcal{Z}_{s}$-guaranteed liveness
properties of $\Pi_{\mathsf{BA}}$ in the synchronous network, all honest
parties will compute the output $1$ in the instance of $\Pi_{\mathsf{BA}}$ at
time $2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$.

Finally, we show that all the parties in $\mathcal{H}_{m}$ output $s^{(m)}$ at
time $2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$. For this, we consider the
following possible cases with respect to $\mathcal{C}_{m}$.

  1. 1.

An $\texttt{NOK}(m,\star)$ message was received at time
$2\Delta+T_{\mathsf{BC}}$ through regular-mode from the broadcast of some
party in $S_{m}$: Since all honest parties accept $\mathcal{C}_{m}$, it
implies that corresponding to this NOK message, all honest parties have
received a $(\texttt{Resolve},s^{(m)})$ message from the broadcast of
$\mathsf{D}$ through regular-mode, as well as from the broadcast of a subset
of parties $\mathcal{C}^{\prime}_{m}\subseteq\mathcal{C}_{m}$ through regular-
mode, where
$\mathcal{C}_{m}\setminus\mathcal{C}^{\prime}_{m}\in\mathcal{Z}_{s}$, at time
$2\Delta+2T_{\mathsf{BC}}$. Hence, according to the protocol steps, every
honest party in $S_{m}$ outputs $s^{(m)}$ as the share, corresponding to
$S_{m}$. Also, it is easy to see that the honest parties output $s^{(m)}$ as
the share at time $2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$.

  2. 2.

No $\texttt{NOK}(m,\star)$ message was received through regular-mode from the
broadcast of any party in $S_{m}$ within time $2\Delta+T_{\mathsf{BC}}$: From
Lemma 9, all parties in $\mathcal{H}_{m}\cap\mathcal{C}_{m}$ would have
received the common share $s^{(m)}$ from $\mathsf{D}$, corresponding to the
set $S_{m}$, within time $\Delta$. As part of the pairwise consistency test,
the share $s^{(m)}$ from all the parties in
$\mathcal{H}_{m}\cap\mathcal{C}_{m}$ would have been delivered to all the
honest parties in $S_{m}$ within time $2\Delta$. This implies that within time
$2\Delta$, all honest parties would have received $s^{(m)}$ from a subset of
parties $\mathcal{C}^{\prime\prime}_{m}\subseteq\mathcal{C}_{m}$, where
$\mathcal{C}_{m}\setminus\mathcal{C}^{\prime\prime}_{m}\in\mathcal{Z}_{s}$.
This is because the set $(\mathcal{C}_{m}\cap\mathcal{H}_{m})$ definitely
constitutes a candidate $\mathcal{C}^{\prime\prime}_{m}$. Moreover, no honest
party would have ever received a value different from $s^{(m)}$ within time
$2\Delta$, from any party in $S_{m}$. On the contrary, if any honest $P_{i}$
receives $s_{j}^{(m)}$ from $P_{j}$ and $s_{k}^{(m)}$ from $P_{k}$ within time
$2\Delta$, where $P_{j},P_{k}\in S_{m}$ and where $s_{j}^{(m)}\neq
s_{k}^{(m)}$, then $P_{i}$ would have broadcasted an $\texttt{NOK}(m,i)$
message at time $2\Delta$, which would have been received by all honest
parties through regular-mode at time $2\Delta+T_{\mathsf{BC}}$, which is a
contradiction.

Hence, in this case also, every honest party in $S_{m}$ outputs $s^{(m)}$ as
the share, corresponding to $S_{m}$. Also, it is easy to see that the honest
parties output $s^{(m)}$ as the share at time
$2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$.

We next prove the correctness property in an asynchronous network.

###### Lemma 11

In protocol $\Pi_{\mathsf{VSS}}$, if $\mathsf{D}$ is honest and participates
with input $s$, then in an asynchronous network, almost-surely $s$ is
eventually secret-shared with respect to the sharing specification
$\mathbb{S}$.

###### Proof

Let $Z_{a}^{\star}\in\mathcal{Z}_{s}$ be the set of corrupt parties, and let
$\mathcal{H}_{a}\stackrel{{\scriptstyle def}}{{=}}\mathcal{P}\setminus
Z_{a}^{\star}$ be the set of honest parties. We show that corresponding to
every $S_{m}\in\mathbb{S}$, almost-surely, all honest parties in $S_{m}$
eventually output the share $s^{(m)}$, where $s^{(m)}$ is the share picked by
$\mathsf{D}$ corresponding to $S_{m}$. The $\mathcal{Z}_{a}$-correctness then
follows from the fact that since $\mathsf{D}$ is honest, it selects the shares
$s^{(1)},\ldots,s^{(q)}$, satisfying the condition $s^{(1)}+\ldots+s^{(q)}=s$.
So consider an arbitrary $S_{m}\in\mathbb{S}$ and let
$\mathcal{H}_{m}=S_{m}\setminus Z_{a}^{\star}$ be the set of honest parties in
$S_{m}$.

We first note that every honest party participates with some input in the
instance of $\Pi_{\mathsf{BA}}$ at local time $2\Delta+2T_{\mathsf{BC}}$.
Hence from the $\mathcal{Z}_{a}$-almost-surely liveness and
$\mathcal{Z}_{a}$-consistency properties of $\Pi_{\mathsf{BA}}$ in the
asynchronous network, all honest parties eventually compute a common output,
during the instance of $\Pi_{\mathsf{BA}}$. Now there are two possible cases
with respect to the output of $\Pi_{\mathsf{BA}}$, according to which the
parties proceed to compute their shares.

  * 1.

The output of $\Pi_{\mathsf{BA}}$ is 1: Since the output of
$\Pi_{\mathsf{BA}}$ is $1$, due to the $\mathcal{Z}_{a}$-validity of
$\Pi_{\mathsf{BA}}$ in the asynchronous network, at least one honest party,
say $P_{h}$, has received the sets $\mathcal{C}_{1},\ldots,\mathcal{C}_{q}$
from the broadcast of $\mathsf{D}$ through regular-mode, within time
$2\Delta+T_{\mathsf{BC}}$ and accepted these sets. It then follows that all
honest parties also receive the sets $\mathcal{C}_{1},\ldots,\mathcal{C}_{q}$
from the broadcast of $\mathsf{D}$, either through regular-mode or through
fallback-mode. This follows from the $\mathcal{Z}_{a}$-weak validity and
$\mathcal{Z}_{a}$-fallback validity properties of $\Pi_{\mathsf{BC}}$ in the
asynchronous network. Since $P_{h}$ has accepted $\mathcal{C}_{m}$, it has
verified that $\mathcal{C}_{m}$ constitutes a clique in the consistency graph
$G_{h}^{(m)}$. This implies that corresponding to $S_{m}$, all honest parties
in $\mathcal{C}_{m}$ have received the same share from $\mathsf{D}$, which is
$s^{(m)}$, since we are considering an honest $\mathsf{D}$. We will show that
all honest parties in $S_{m}$ eventually output $s^{(m)}$ as the share,
corresponding to $S_{m}$.

So consider an arbitrary honest $P_{i}\in S_{m}$. From the protocol steps, if
the output of $\Pi_{\mathsf{BA}}$ is $1$, then $P_{i}$ computes its share
corresponding to $S_{m}$, based on one of the following three conditions.
Assuming that at least one of these conditions eventually hold for $P_{i}$, we
first show that the share computed by $P_{i}$ corresponding to $S_{m}$, is
bound to be $s^{(m)}$. This is followed by showing that indeed at least one of
these conditions eventually hold for $P_{i}$.

    * –

Condition A: At time $2\Delta+2T_{\mathsf{BC}}$, party $P_{i}$ received the
$\texttt{Resolve}(m,s^{(m)})$ message from the broadcast of $\mathsf{D}$, as
well as from the broadcast of a subset of parties
$\mathcal{C}^{\prime}_{m}\subseteq\mathcal{C}_{m}$ through regular-mode, where
$\mathcal{C}_{m}\setminus\mathcal{C}^{\prime}_{m}\in\mathcal{Z}_{s}$. Clearly,
in this case, $P_{i}$ outputs $s^{(m)}$ as the share corresponding to $S_{m}$.

    * –

Condition B: At time $2\Delta$, there exists a subset of parties
$\mathcal{C}^{\prime\prime}_{m}\subseteq\mathcal{C}_{m}$ where
$\mathcal{C}_{m}\setminus\mathcal{C}^{\prime\prime}_{m}\in\mathcal{Z}_{s}$,
such that $P_{i}$ received a common value from all the parties in
$\mathcal{C}^{\prime\prime}_{m}$. We claim that the subset
$\mathcal{C}^{\prime\prime}_{m}$ is bound to contain at least one honest party
from $\mathcal{C}_{m}$, which would have sent $s^{(m)}$ to $P_{i}$, due to
which $P_{i}$ will output $s^{(m)}$ as the share corresponding to $S_{m}$. In
more detail, let $S_{m}\setminus\mathcal{C}_{m}=Z_{\alpha}\in\mathcal{Z}_{s}$,
and
$\mathcal{C}_{m}\setminus\mathcal{C}^{\prime\prime}_{m}=Z_{\beta}\in\mathcal{Z}_{s}$.
Also, note that $\mathcal{P}\setminus S_{m}=Z_{m}\in\mathcal{Z}_{s}$. Now, if
$\mathcal{C}^{\prime\prime}_{m}$ does not contain any honest party from
$\mathcal{C}_{m}$, it implies that $\mathcal{C}^{\prime\prime}_{m}\subseteq
Z_{a}^{\star}\in\mathcal{Z}_{a}$. This further implies that
$\mathcal{P}\subseteq Z_{m}\cup Z_{\alpha}\cup Z_{\beta}\cup Z_{a}^{\star}$,
which is a contradiction to the
$\mathcal{Q}^{(3,1)}(\mathcal{P},\mathcal{Z}_{s},\mathcal{Z}_{a})$ condition.

    * –

Condition C: There exists a subset of parties
$\mathcal{C}^{\prime\prime\prime}_{m}\subseteq\mathcal{C}_{m}$, where
$\mathcal{C}_{m}\setminus\mathcal{C}^{\prime\prime\prime}_{m}\in\mathcal{Z}_{a}$,
such that $P_{i}$ received a common value from all the parties in
$\mathcal{C}^{\prime\prime\prime}_{m}$. In this case also, one can show that
the subset $\mathcal{C}^{\prime\prime\prime}_{m}$ is bound to contain at least
one honest party from $\mathcal{C}_{m}$, who would have sent $s^{(m)}$ to
$P_{i}$. This is because $\mathcal{Z}_{s}$ and $\mathcal{Z}_{a}$ satisfy the
$\mathcal{Q}^{(3,1)}(\mathcal{P},\mathcal{Z}_{s},\mathcal{Z}_{a})$ condition
and every subset in $\mathcal{Z}_{a}$ is a subset of some subset in
$\mathcal{Z}_{s}$. Clearly, $P_{i}$ outputs $s^{(m)}$ as the share
corresponding to $S_{m}$.

Thus, we have shown that irrespective of the way $P_{i}$ would have computed
its output share corresponding to $S_{m}$, it is bound to be the same as
$s^{(m)}$. To complete the proof, we just need to show that at least one of
the conditions from A, B and C above eventually holds for $P_{i}$. For this,
we note that in the worst case, the condition C is bound to eventually hold,
irrespective of conditions A and B. This is because the set of honest parties
in $\mathcal{C}_{m}$, namely the parties in $\mathcal{C}_{m}\setminus
Z_{a}^{\star}$, always constitute a candidate
$\mathcal{C}^{\prime\prime\prime}_{m}$ set for $P_{i}$. This follows from the
fact that the share $s^{(m)}$ from all the parties in
$\mathcal{C}_{m}\setminus Z_{a}^{\star}$ will be eventually delivered to
$P_{i}$.

  * 2.

The output of $\Pi_{\mathsf{BA}}$ is 0: Since $\mathsf{D}$ is honest, every
pair of parties $P_{j},P_{k}\in\mathcal{H}_{m}$ eventually broadcast
$\texttt{OK}(m,j,k)$ and $\texttt{OK}(m,k,j)$ messages, as they eventually
receive the same share $s^{(m)}$ from $\mathsf{D}$ and exchange among
themselves. From the $\mathcal{Z}_{a}$-validity of $\Pi_{\mathsf{BC}}$ in the
asynchronous network, these messages are eventually delivered to every honest
party. Also from the $\mathcal{Z}_{a}$-consistency of $\Pi_{\mathsf{BC}}$ in
the asynchronous network, any OK message which is received by $\mathsf{D}$
from the broadcast of any corrupt party, will eventually be received by every
other honest party as well. Since
$S_{m}\setminus\mathcal{H}_{m}\in\mathcal{Z}_{a}$, it follows that all honest
parties will eventually find a subset of parties $\mathcal{E}_{m}\subseteq
S_{m}$, where $S_{m}\setminus\mathcal{E}_{m}\in\mathcal{Z}_{a}$, which
constitutes a clique in the consistency graph $G^{(m)}$ of all honest parties.
This is because the set $\mathcal{H}_{m}$ constitutes such a candidate
$\mathcal{E}_{m}$. Consequently, $\mathsf{D}$ eventually finds and broadcasts
$\mathcal{E}_{m}$. From the $\mathcal{Z}_{a}$-weal validity and
$\mathcal{Z}_{a}$-fallback validity properties of $\Pi_{\mathsf{BC}}$ in the
asynchronous network, $\mathcal{E}_{m}$ will be eventually received and
accepted by all honest parties.

Next, consider an arbitrary $P_{i}\in\mathcal{H}_{m}$. We wish to show that
$P_{i}$ eventually outputs $s^{(m)}$ as the share, corresponding to $S_{m}$.
Now, there are two possible cases. If $P_{i}\in\mathcal{E}_{m}$, then from the
protocol steps, $P_{i}$ indeed outputs $s^{(m)}$ as its share, corresponding
to $S_{m}$. So, consider the other case when $P_{i}\not\in\mathcal{E}_{m}$.
Note that all the parties in $\mathcal{H}_{m}$ eventually receive the common
share $s^{(m)}$ from $\mathsf{D}$, since $\mathsf{D}$ is honest. Also note
that $\mathcal{E}_{m}\setminus\mathcal{H}_{m}\in\mathcal{Z}_{s}$; this is
because every subset in $\mathcal{Z}_{a}$ is a subset of some subset in
$\mathcal{Z}_{s}$. Hence, it follows that party $P_{i}$ will eventually find a
candidate subset $\mathcal{E}^{\prime}_{m}\subseteq\mathcal{E}_{m}$, where
$\mathcal{E}_{m}\setminus\mathcal{E}^{\prime}_{m}\in\mathcal{Z}_{s}$, such
that $P_{i}$ receives a common value from all the parties in
$\mathcal{E}^{\prime}_{m}$ and set that value as its share, corresponding to
$S_{m}$. This is because the subset $(\mathcal{H}_{m}\cap\mathcal{E}_{m})$
always constitute such a candidate $\mathcal{E}^{\prime}_{m}$ set. Hence, it
is confirmed that $P_{i}$ is guaranteed to output some share corresponding to
$S_{m}$. To complete the proof, we need to show that this share is the same as
$s^{(m)}$.

So, let $P_{i}$ find a candidate $\mathcal{E}^{\prime}_{m}$ set, satisfying
the above conditions, based on which it computes its output share
corresponding to $S_{m}$. We claim that this set $\mathcal{E}^{\prime}_{m}$
contains at least one honest party from $\mathcal{H}_{m}$; i.e.
$\mathcal{H}_{m}\cap\mathcal{E}^{\prime}_{m}\neq\emptyset$. On the contrary,
let the candidate $\mathcal{E}^{\prime}_{m}$ for $P_{i}$ consists of only
corrupt parties. That is, $\mathcal{E}^{\prime}_{m}\subseteq Z_{a}^{\star}$.
We consider the worst case scenario where $Z_{a}^{\star}\in\mathcal{Z}_{s}$ as
well, since every subset in $\mathcal{Z}_{a}$ is assumed to be a subset of
some subset in $\mathcal{Z}_{s}$. Also note that $S_{m}=\mathcal{P}\setminus
Z_{m}$, where $Z_{m}\in\mathcal{Z}_{s}$. Let
$S_{m}\setminus\mathcal{E}_{m}\subseteq Z_{\beta}\in\mathcal{Z}_{a}$. And let
$\mathcal{E}_{m}\setminus\mathcal{E}^{\prime}_{m}\subseteq
Z_{\alpha}\in\mathcal{Z}_{s}$. Hence, we get that $\mathcal{P}\subseteq
Z_{m}\cup Z_{a}^{\star}\cup Z_{\alpha}\cup Z_{\beta}$, which is a
contradiction, since $\mathcal{Z}_{s}$ and $\mathcal{Z}_{a}$ satisfy the
$\mathcal{Q}^{(3,1)}(\mathcal{P},\mathcal{Z}_{s},\mathcal{Z}_{a})$ condition.

We next prove the privacy property.

###### Lemma 12

In protocol $\Pi_{\mathsf{VSS}}$, if $\mathsf{D}$ is honest and participates
with input $s$, then irrespective of the type of network, the view of the
adversary remains independent of $s$.

###### Proof

We prove privacy in a synchronous network. The privacy in an asynchronous
network automatically follows, since every subset in $\mathcal{Z}_{a}$ is a
subset of some subset in $\mathcal{Z}_{s}$. So, consider a synchronous
network, and let $\mathsf{D}$ be honest. Let $Z_{c}\in\mathcal{Z}_{s}$ be the
set of corrupt parties. Then consider the set $S_{c}\in\mathbb{S}$, where
$S_{c}\stackrel{{\scriptstyle def}}{{=}}\mathcal{P}\setminus Z_{c}$. We claim
that, throughout the protocol, the adversary does not learn anything about the
share $s^{(c)}$, and its view remains independent of $s^{(c)}$. The
$\mathcal{Z}_{s}$-privacy then follows from the fact that $\mathsf{D}$ selects
the share $s^{(c)}$ randomly, and the probability distribution of $s^{(c)}$ is
independent of $s$.

Since $\mathsf{D}$ is honest, it sends the share $s^{(c)}$, only to the
parties in $S_{c}$, which consists of only honest parties. Similarly, as part
of the pairwise consistency tests, the share $s^{(c)}$ is exchanged only among
the parties in $S_{c}$. Moreover, since $S_{c}$ consists of no corrupt
parties, it follows that no party from $S_{c}$ ever broadcasts an
$\texttt{NOK}(c,\star)$ message, corresponding to $S_{c}$. Consequently, no
party from $S_{c}$, as well as $\mathsf{D}$, ever broadcasts a
$\texttt{Resolve}(c,s^{(c)})$ message. Thus, throughout the protocol, the view
of the adversary remains independent of the share $s^{(c)}$.

We next proceed to prove the commitment properties. We start with the
synchronous network.

###### Lemma 13

In protocol $\Pi_{\mathsf{VSS}}$, if $\mathsf{D}$ is corrupt, then either no
honest party obtains any output, or there exists a value
$s^{\star}\in\mathbb{K}$ held by $\mathsf{D}$, which is secret-shared with
respect to the sharing specification $\mathbb{S}$, such that the following
hold.

  * –

If any honest party outputs its shares at time
$T_{\mathsf{VSS}}=2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$, then all honest
parties output their shares at time $T_{\mathsf{VSS}}$.

  * –

If any honest party outputs its shares at time $T>T_{\mathsf{VSS}}$, then
every honest party outputs its shares by time $T+2\Delta$.

###### Proof

If no honest party obtains any output, then the lemma holds trivially. So,
consider the case when some honest party, say $P_{h}$, obtains an output. We
note that every honest party participates with some input in the instance of
$\Pi_{\mathsf{BA}}$ at time $2\Delta+2T_{\mathsf{BC}}$. Hence, by the
$\mathcal{Z}_{s}$-consistency and $\mathcal{Z}_{s}$-guaranteed liveness
properties of $\Pi_{\mathsf{BA}}$ in the synchronous network, the instance of
$\Pi_{\mathsf{BA}}$ generates an output at time
$2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$ for every honest party. Now there
are two possible cases.

  1. 1.

The output of $\Pi_{\mathsf{BA}}$ is $1$: In this case, from Lemma 9, it
follows that all honest parties participated with input $1$ at time
$2\Delta+2T_{\mathsf{BC}}$ during the instance of $\Pi_{\mathsf{BA}}$. This
implies that all honest parties received
$\mathcal{C}_{1},\ldots,\mathcal{C}_{q}$ from the broadcast of $\mathsf{D}$
through regular-mode at time $2\Delta+2T_{\mathsf{BC}}$ and accepted these
sets. We next claim that corresponding to every $S_{m}\in\mathbb{S}$, all
honest parties in $S_{m}$ output some common share say $s^{(m)}$,
corresponding to $S_{m}$, at time $2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$.
Let $s^{\star}\stackrel{{\scriptstyle def}}{{=}}s^{(1)}+\ldots+s^{(m)}$. It
will then follow that the value $s^{\star}$ is secret-shared at time
$2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$.

The proof of the above claim closely follows the $\mathcal{Z}_{s}$-correctness
proof in the synchronous network (see the proof of Lemma 10). Consider an
arbitrary $S_{m}\in\mathbb{S}$. Then there are two possible cases.

     * –

An $\texttt{NOK}(m,\star)$ message was received at time
$2\Delta+T_{\mathsf{BC}}$ through regular-mode from the broadcast of some
party in $S_{m}$: In this case, all honest parties in $S_{m}$ will output some
common share, say $s^{(m)}$, corresponding to $S_{m}$ at time
$2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$. The proof for this is exactly the
same as the proof of Lemma 10 for the same case.

     * –

No $\texttt{NOK}(m,\star)$ message was received within time
$2\Delta+T_{\mathsf{BC}}$ through regular-mode from the broadcast of any party
in $S_{m}$: Let $\mathcal{H}_{m}$ be the set of honest parties in $S_{m}$.
Since $\mathcal{C}_{m}$ is accepted by all the honest parties, it follows that
the parties in $\mathcal{H}_{m}\cap\mathcal{C}_{m}$ constitute a clique in the
consistency graph $G^{(m)}$ of all honest parties. This further implies that
all the parties in $\mathcal{H}_{m}\cap\mathcal{C}_{m}$ received a common
share from $\mathsf{D}$ corresponding to $S_{m}$, say $s^{(m)}$. Moreover,
from Lemma 9, all the parties in $\mathcal{H}_{m}\cap\mathcal{C}_{m}$ would
have received $s^{(m)}$ from $\mathsf{D}$, within time $\Delta$. Now similar
to the proof for the same case in Lemma 10, it can be concluded that all
honest parties output $s^{(m)}$ as the share corresponding to $S_{m}$, at time
$2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$.

  2. 2.

The output of $\Pi_{\mathsf{BA}}$ is $0$: Since $P_{h}$ has obtained an
output, it implies that it has received sets
$\mathcal{E}_{1},\ldots,\mathcal{E}_{q}$ from the broadcast of $\mathsf{D}$
and accepted them. Let $T$ be the time at which $P_{h}$ accepted
$\mathcal{E}_{1},\ldots,\mathcal{E}_{q}$. Note that
$T>2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$. This is because from the
protocol steps, the honest parties start participating in the instance of
$\Pi_{\mathsf{BC}}$ of $\mathsf{D}$ for broadcasting
$\mathcal{E}_{1},\ldots,\mathcal{E}_{q}$, only after time
$2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$. By the
$\mathcal{Z}_{s}$-consistency and $\mathcal{Z}_{s}$-fallback consistency of
$\Pi_{\mathsf{BC}}$ in the synchronous network, all honest parties will
receive and accept the sets $\mathcal{E}_{1},\ldots,\mathcal{E}_{q}$, latest
by time $T+2\Delta$. Since the parries have accepted
$\mathcal{E}_{1},\ldots,\mathcal{E}_{q}$, it implies that corresponding to
every $S_{m}\in\mathbb{S}$, all the honest parties in $\mathcal{E}_{m}$ have
received a common value from $\mathsf{D}$, say $s^{(m)}$. We claim that all
the honest parties in $S_{m}$ output $s^{(m)}$ as the share, corresponding to
$S_{m}$, latest by time $T+2\Delta$. This will automatically imply that the
value $s^{\star}\stackrel{{\scriptstyle def}}{{=}}s^{(1)}+\ldots+s^{(m)}$ is
secret-shared, latest by time $T+2\Delta$.

The proof for the above claim is exactly the same as the proof of Lemma 11,
for the case when the output of $\Pi_{\mathsf{BA}}$ is $0$ and is omitted.

We finally prove the commitment property in an asynchronous network.

###### Lemma 14

In protocol $\Pi_{\mathsf{VSS}}$, if $\mathsf{D}$ is corrupt, then either no
honest party obtains any output or there exists some value
$s^{\star}\in\mathbb{K}$ held by $\mathsf{D}$, such that almost-surely
$s^{\star}$ is secret-shared, with respect to the sharing specification
$\mathbb{S}$.

###### Proof

If no honest party obtains an output, then the lemma holds trivially. So,
consider the case when some honest party, say $P_{h}$, has obtained an output
in $\Pi_{\mathsf{VSS}}$. Note that every honest party participates with some
input in the instance of $\Pi_{\mathsf{BA}}$ at local time
$2\Delta+2T_{\mathsf{BC}}$. Hence, from the $\mathcal{Z}_{a}$-almost-surely
liveness and $\mathcal{Z}_{a}$-consistency properties of $\Pi_{\mathsf{BA}}$
in the asynchronous network, it follows that the instance of
$\Pi_{\mathsf{BA}}$ eventually generates a common output for every honest
party. Now, there are two possible cases.

  * 1.

The output of $\Pi_{\mathsf{BA}}$ instance is $1$: This implies that all
honest parties eventually receive the sets
$\mathcal{C}_{1},\ldots,\mathcal{C}_{q}$ from the broadcast of $\mathsf{D}$
(either through regular-mode or fallback-mode), and accept these sets. The
proof for this is identical to the case “when the output of
$\Pi_{\mathsf{BA}}$ instance is $1$”, in the proof of Lemma 11. This further
implies that corresponding to each $S_{m}\in\mathbb{S}$, all the honest
parties in $\mathcal{C}_{m}$ have received a common value from $\mathsf{D}$,
say $s^{(m)}$, since the honest parties in $\mathcal{C}_{m}$ constitute a
clique. We claim that all the honest parties in $S_{m}$ eventually output
$s^{(m)}$ as the share, corresponding to the set $S_{m}$. This will
automatically imply that the value $s^{\star}\stackrel{{\scriptstyle
def}}{{=}}s^{(1)}+\ldots+s^{(q)}$ is eventually secret-shared among the
parties. The proof for the claim again closely follows the case “when the
output of $\Pi_{\mathsf{BA}}$ instance is $1$”, in the proof of Lemma 11.

So, consider an arbitrary honest $P_{i}\in S_{m}$, and let $Z_{a}^{\star}$ be
the set of corrupt parties. From the protocol steps, $P_{i}$ computes its
share corresponding to $S_{m}$ based on one of the following three conditions.
Assuming that at least one of these conditions eventually hold for $P_{i}$, we
first show that the share computed by $P_{i}$ corresponding to $S_{m}$ is
bound to be $s^{(m)}$. This is followed by showing that at least one of these
conditions eventually hold for $P_{i}$.

    * –

Condition A: At time $2\Delta+2T_{\mathsf{BC}}$, there exists some value
$s^{\prime(m)}$ such that party $P_{i}$ received the
$\texttt{Resolve}(m,s^{\prime(m)})$ message from the broadcast of
$\mathsf{D}$, as well as from the broadcast of a subset of parties
$\mathcal{C}^{\prime}_{m}\subseteq\mathcal{C}_{m}$ through regular-mode, where
$\mathcal{C}_{m}\setminus\mathcal{C}^{\prime}_{m}\in\mathcal{Z}_{s}$. And
consequently $P_{i}$ sets $s^{\prime(m)}$ as its share corresponding to
$S_{m}$.

We argue that $\mathcal{C}^{\prime}_{m}$ is bound to contain at least one
honest party from $\mathcal{C}_{m}$, which broadcasts
$\texttt{Resolve}(m,s^{\prime(m)})$ message, where $s^{\prime(m)}=s^{(m)}$. In
more detail, let $S_{m}\setminus\mathcal{C}_{m}=Z_{\alpha}\in\mathcal{Z}_{s}$
and
$\mathcal{C}_{m}\setminus\mathcal{C}^{\prime}_{m}=Z_{\beta}\in\mathcal{Z}_{s}$.
Also, note that $\mathcal{P}\setminus S_{m}=Z_{m}\in\mathcal{Z}_{s}$. Now if
$\mathcal{C}^{\prime}_{m}$ does not contain any honest party from
$\mathcal{C}_{m}$, it implies that $\mathcal{C}^{\prime}_{m}\subseteq
Z_{a}^{\star}\in\mathcal{Z}_{a}$. This further implies that
$\mathcal{P}\subseteq Z_{m}\cup Z_{\alpha}\cup Z_{\beta}\cup Z_{a}^{\star}$,
which is a contradiction to the
$\mathcal{Q}^{(3,1)}(\mathcal{P},\mathcal{Z}_{s},\mathcal{Z}_{a})$ condition.

    * –

Condition B: At time $2\Delta$, there exists a subset of parties
$\mathcal{C}^{\prime\prime}_{m}\subseteq\mathcal{C}_{m}$, where
$\mathcal{C}_{m}\setminus\mathcal{C}^{\prime\prime}_{m}\in\mathcal{Z}_{s}$,
such that $P_{i}$ received a common value from all the parties in
$\mathcal{C}^{\prime\prime}_{m}$, say $s^{\prime(m)}$. And consequently,
$P_{i}$ sets $s^{\prime(m)}$ as its share corresponding to $S_{m}$.

We claim that the subset $\mathcal{C}^{\prime\prime}_{m}$ is bound to contain
at least one honest party from $\mathcal{C}_{m}$, who would have sent
$s^{\prime(m)}=s^{(m)}$ to $P_{i}$ within time $2\Delta$. The proof for the
claim is similar to the case above where we have shown that
$\mathcal{C}^{\prime}_{m}$ is bound to contain at least one honest party from
$\mathcal{C}_{m}$.

    * –

Condition C: There exists a subset of parties
$\mathcal{C}^{\prime\prime\prime}_{m}\subseteq\mathcal{C}_{m}$ where
$\mathcal{C}_{m}\setminus\mathcal{C}^{\prime\prime\prime}_{m}\in\mathcal{Z}_{a}$,
such that $P_{i}$ received a common value from all the parties in
$\mathcal{C}^{\prime\prime\prime}_{m}$, say $s^{\prime(m)}$. And consequently,
$P_{i}$ sets $s^{\prime(m)}$ as its share, corresponding to $S_{m}$. In this
case also, one can show that the subset $\mathcal{C}^{\prime\prime\prime}_{m}$
is bound to contain at least one honest party from $\mathcal{C}_{m}$, who
would have sent $s^{\prime(m)}=s^{(m)}$ to $P_{i}$. This is because
$\mathcal{Z}_{s}$ and $\mathcal{Z}_{a}$ satisfy the
$\mathcal{Q}^{(3,1)}(\mathcal{P},\mathcal{Z}_{s},\mathcal{Z}_{a})$ condition
and every subset in $\mathcal{Z}_{a}$ is a subset of some subset in
$\mathcal{Z}_{s}$.

Thus, we have shown that irrespective of the way $P_{i}$ would have computed
its output share corresponding to $S_{m}$, it is bound to be the same as
$s^{(m)}$. Now it is easy to see that at least one of the conditions A, B and
C above, eventually holds for $P_{i}$. Specially, the condition C is bound to
eventually hold, irrespective of conditions A and B. This is because the set
of honest parties in $\mathcal{C}_{m}$, namely the parties in
$\mathcal{C}_{m}\setminus Z_{a}^{\star}$, always constitute a candidate
$\mathcal{C}^{\prime\prime\prime}_{m}$ set for $P_{i}$. This follows from the
fact that the share $s^{(m)}$ from all the parties in
$\mathcal{C}_{m}\setminus Z_{a}^{\star}$ will be eventually delivered to
$P_{i}$.

  * 2.

The output of $\Pi_{\mathsf{BA}}$ instance is $0$: Since $P_{h}$ has computed
its output, it follows that it has received the sets
$\mathcal{E}_{1},\ldots,\mathcal{E}_{q}$ from the broadcast of $\mathsf{D}$,
and accepted these sets. From the $\mathcal{Z}_{a}$-weak consistency and
$\mathcal{Z}_{a}$-fallback consistency properties of $\Pi_{\mathsf{BC}}$ in
the asynchronous network, it follows that all honest parties eventually
receive these sets and accept them. We also note that corresponding to every
$S_{m}\in\mathbb{S}$, all honest parties in $\mathcal{E}_{m}$ received the
same share from $\mathsf{D}$, say $s^{(m)}$. Now similar to the proof for the
case “the output of $\Pi_{\mathsf{BA}}$ instance is $0$” in the proof of Lemma
14, it can be shown that all honest parties in $S_{m}$ eventually set
$s^{(m)}$ as the share, corresponding to $S_{m}$. This automatically implies
that the value $s^{\star}\stackrel{{\scriptstyle
def}}{{=}}s^{(1)}+\ldots+s^{(q)}$ is eventually secret-shared.

###### Lemma 15

Protocol $\Pi_{\mathsf{VSS}}$ incurs a communication of
$\mathcal{O}(|\mathcal{Z}_{s}|\cdot(n^{4}\log{|\mathbb{K}|}+n^{5}(\log
n+\log{|\mathcal{Z}_{s}|})))$ bits and invokes one instance of
$\Pi_{\mathsf{BA}}$.

###### Proof

During phase I, corresponding to every $S_{m}\in\mathbb{S}$, dealer
$\mathsf{D}$ needs to send a share, consisting of one element of $\mathbb{K}$,
to all the parties in $S_{m}$. This incurs a total communication of
$\mathcal{O}(|\mathcal{Z}_{s}|\cdot n)$ elements from $\mathbb{K}$. During
phase II, every party in $S_{m}$ sends an element from $\mathbb{K}$ to every
other party in $S_{m}$. This incurs a total communication of
$\mathcal{O}(|\mathcal{Z}_{s}|\cdot n^{2})$ elements from $\mathbb{K}$. During
phase III, every party in $S_{m}$ may broadcast an OK message for every other
party in $S_{m}$. This requires broadcasting
$\mathcal{O}(|\mathcal{Z}_{s}|\cdot n^{2}\cdot(\log
n+\log{|\mathcal{Z}_{s}|}))$ bits, as each OK message encodes the identity of
two parties and the identity of a set from $\mathcal{Z}_{s}$, requiring $2\log
n+\log{|\mathcal{Z}_{s}|}$ bits. Additionally, during phase III, corresponding
to any $S_{m}\in\mathbb{S}$, each party in $S_{m}$ may broadcast an NOK
message. This requires broadcasting $\mathcal{O}(|\mathcal{Z}_{s}|\cdot
n\cdot(\log{|\mathcal{Z}_{s}|}+\log{n}))$ bits, as each NOK message encodes
the identity of a party and the identity of a set from $\mathcal{Z}_{s}$.
During phase IV, corresponding to each $S_{m}\in\mathbb{S}$, up to
$\mathcal{O}(n)$ elements from $\mathbb{K}$ may be broadcasted to resolve the
conflicts. This incurs a total broadcast of
$\mathcal{O}(|\mathcal{Z}_{s}|\cdot n)$ elements from $\mathbb{K}$.
Additionally, $\mathsf{D}$ may broadcast sets
$\mathcal{C}_{1},\ldots,\mathcal{C}_{q}$, where each set can be encoded by an
$n$-bit vector.

The communication complexity now follows by summing up all the above costs and
from the communication complexity of the protocol $\Pi_{\mathsf{BC}}$, along
with the fact that each element from $\mathbb{K}$ can be represented by
$\log{|\mathbb{K}|}$ bits, and the fact that $q=|\mathcal{Z}_{s}|$.

######  Remark 2 (Further improvement in the communication complexity of
$\Pi_{\mathsf{VSS}}$)

The complexity of the phase III can be significantly reduced by making the
following modification: party $P_{i}$ now broadcasts a single
$\texttt{OK}(i,j)$ message corresponding to $P_{j}$, if the pairwise
consistency test is positive between $P_{i}$’s and $P_{j}$’s share across all
the sets in $\mathbb{S}$, to which both $P_{i}$ and $P_{j}$ belongs. That is,
if corresponding to every $S_{m}\in\mathbb{S}$ such that $P_{i},P_{j}\in
S_{m}$, the condition $s_{i}^{(m)}=s_{j}^{(m)}$ holds. Consequently, during
phase III, only $\mathcal{O}(n^{2})$ OK messages need to be broadcasted, where
the size of each message will now be only $\mathcal{O}(\log n)$ bits. This
will reduce the communication complexity of $\Pi_{\mathsf{VSS}}$ to
$\mathcal{O}(|\mathcal{Z}_{s}|\cdot
n^{4}\cdot(\log{|\mathbb{K}|}+\log{|\mathcal{Z}_{s}|}+\log n)+n^{5}\log n)$
bits, along with one instance of $\Pi_{\mathsf{BA}}$.

The proof of the following theorem now follows from Lemma 10-15 and Remark 2.

Theorem 4.1. Let $\mathcal{A}$ be an adversary characterized by an adversary
structure $\mathcal{Z}_{s}$ in a synchronous network and adversary structure
$\mathcal{Z}_{a}$ in an asynchronous network satisfying the following
conditions.

  * –

$\mathcal{Z}_{s}\neq\mathcal{Z}_{a}$;

  * –

For every subset $Z\in\mathcal{Z}_{a}$, there exists a subset
$Z^{\prime}\in\mathcal{Z}_{s}$, such that $Z\subseteq Z^{\prime}$;

  * –

$\mathcal{Z}_{s}$ and $\mathcal{Z}_{a}$ satisfy the
$\mathcal{Q}^{(3,1)}(\mathcal{P},\mathcal{Z}_{s},\mathcal{Z}_{a})$ condition.

Moreover, let $\mathbb{S}=\\{S_{m}:S_{m}=\mathcal{P}\setminus Z_{m}\;\mbox{
and }\;Z_{m}\in\mathcal{Z}_{s}\\}$. Then protocol $\Pi_{\mathsf{VSS}}$
achieves the following properties, where $\mathsf{D}$ has a private input
$s\in\mathbb{K}$ for $\Pi_{\mathsf{VSS}}$.

  * –

If $\mathsf{D}$ is honest, then the following hold.

    * –

$\mathcal{Z}_{s}$-correctness: In a synchronous network, $s$ is secret-shared
with respect to $\mathbb{S}$, at time
$T_{\mathsf{VSS}}=2\Delta+2T_{\mathsf{BC}}+T_{\mathsf{BA}}$.

    * –

$\mathcal{Z}_{a}$-correctness: In an asynchronous network, almost-surely, $s$
is eventually secret-shared, with respect to $\mathbb{S}$.

    * –

Privacy: The view of $\mathcal{A}$ remains independent of $s$, irrespective of
the network type.

  * –

If $\mathsf{D}$ is corrupt, then either no honest party obtains any output or
there exists some $s^{\star}\in\mathbb{K}$, such that the following hold.

    * –

$\mathcal{Z}_{a}$-commitment: In an asynchronous network, almost-surely,
$s^{\star}$ is eventually secret-shared, with respect to $\mathbb{S}$.

    * –

$\mathcal{Z}_{s}$-commitment: In a synchronous network, $s^{\star}$ is secret-
shared, with respect to $\mathbb{S}$, such that the following hold.

      * –

If any honest party outputs its shares at time $T_{\mathsf{VSS}}$, then all
honest parties output their shares at time $T_{\mathsf{VSS}}$.

      * –

If any honest party outputs its shares at time $T>T_{\mathsf{VSS}}$, then
every honest party outputs its shares by time $T+2\Delta$.

  * –

Communication Complexity: The protocol incurs a communication of
$\mathcal{O}(|\mathcal{Z}_{s}|\cdot
n^{4}\cdot(\log{|\mathbb{K}|}+\log{|\mathcal{Z}_{s}|}+\log n)+n^{5}\log n)$
bits and invokes one instance of $\Pi_{\mathsf{BA}}$.

##  Appendix 0.E Properties of the Preprocessing Phase Protocol

In this section, we formally present our preprocessing phase protocol and
prove its properties. We first start with the description of our ACS protocol
and proof of its properties.

###  0.E.1 Protocol $\Pi_{\mathsf{ACS}}$ and Its Properties

For simplicity, we present $\Pi_{\mathsf{ACS}}$ when $L=1$; the modifications
for a general $L$ are straightforward.  – Phase I — Secret Sharing the Input:
If $P_{i}\in\mathcal{Q}$, the do the following.  – On having the input
$x_{i}$, act as a dealer $\mathsf{D}$ and invoke an instance
$\Pi_{\mathsf{VSS}}^{(i)}$ of $\Pi_{\mathsf{VSS}}$ with input $x_{i}$. –
Participate in the instance $\Pi_{\mathsf{VSS}}^{(j)}$ invoked by every
$P_{j}\in\mathcal{Q}$, and  wait for time $T_{\mathsf{VSS}}$. Initialize a set
$\mathcal{C}_{i}=\emptyset$ after time $T_{\mathsf{VSS}}$ and include
$P_{j}\in\mathcal{Q}$ in $\mathcal{C}_{i}$ if an output is computed in the
instance $\Pi_{\mathsf{VSS}}^{(j)}$. – Phase II — Identifying the Common Set
of Selected Parties:  – Corresponding to every $P_{j}\in\mathcal{Q}$,
participate in an instance of $\Pi_{\mathsf{BA}}^{(j)}$ of $\Pi_{\mathsf{BA}}$
with input $1$, if $P_{j}\in\mathcal{C}_{i}$. – Once $1$ has been obtained as
the output from instances of $\Pi_{\mathsf{BA}}$ corresponding to a set of
parties in $\mathcal{Q}\setminus Z$ for some $Z\in\mathcal{Z}_{s}$,
participate with input $0$ in all the $\Pi_{\mathsf{BA}}$ instances
$\Pi_{\mathsf{BA}}^{(j)}$, such that $P_{j}\in\mathcal{Q}$ and
$P_{j}\not\in\mathcal{C}_{i}$. – Once all the instances of $\Pi_{\mathsf{BA}}$
corresponding to the parties in $\mathcal{Q}$ have produced a binary output,
then output $\mathcal{CS}$, which is the set of parties $P_{j}\in\mathcal{Q}$
such that $1$ is obtained as the output in the instance
$\Pi_{\mathsf{BA}}^{(j)}$.

Figure 8: Agreement on a common subset of parties. The above code is for each
$P_{i}\in\mathcal{P}$.

We next prove the properties of the protocol $\Pi_{\mathsf{ACS}}$, assuming
$L=1$.

###### Lemma 16

. Let $\mathcal{A}$ be an adversary characterized by an adversary structure
$\mathcal{Z}_{s}$ in a synchronous network and adversary structure
$\mathcal{Z}_{a}$ in an asynchronous network satisfying the following
conditions.

  * –

$\mathcal{Z}_{s}\neq\mathcal{Z}_{a}$;

  * –

For every subset $Z\in\mathcal{Z}_{a}$, there exists a subset
$Z^{\prime}\in\mathcal{Z}_{s}$, such that $Z\subseteq Z^{\prime}$;

  * –

$\mathcal{Z}_{s}$ and $\mathcal{Z}_{a}$ satisfy the
$\mathcal{Q}^{(3,1)}(\mathcal{P},\mathcal{Z}_{s},\mathcal{Z}_{a})$ condition.

Moreover, let $\mathbb{S}=\\{S_{m}:S_{m}=\mathcal{P}\setminus Z_{m}\;\mbox{
and }\;Z_{m}\in\mathcal{Z}_{s}\\}$. Furthermore, let
$\mathcal{Q}\subseteq\mathcal{P}$, such that $\mathcal{Z}_{s}$ and
$\mathcal{Z}_{a}$ either satisfy the
$\mathcal{Q}^{(1,1)}(\mathcal{Q},\mathcal{Z}_{s},\mathcal{Z}_{a})$ condition
or the $\mathcal{Q}^{(3,1)}(\mathcal{Q},\mathcal{Z}_{s},\mathcal{Z}_{a})$
condition. Then, $\Pi_{\mathsf{ACS}}$ achieves the following, where every
(honest) $P_{i}\in\mathcal{Q}$ has input $x_{i}\in\mathbb{K}$ for
$\Pi_{\mathsf{ACS}}$.

  * –

$\mathcal{Z}_{s}$-correctness: If the network is synchronous, then at time
$T_{\mathsf{ACS}}\stackrel{{\scriptstyle
def}}{{=}}T_{\mathsf{VSS}}+2T_{\mathsf{BA}}$, all honest parties output a
common subset of parties $\mathcal{CS}\subseteq\mathcal{Q}$, where
$\mathcal{Q}\setminus\mathcal{CS}\in\mathcal{Z}_{s}$, such that the following
hold.

    * –

All honest parties from $\mathcal{Q}$ will be present in $\mathcal{CS}$.

    * –

Corresponding to every $P_{j}\in\mathcal{CS}$, there exists some
$x^{\star}_{j}\in\mathbb{K}$, where $x^{\star}_{j}=x_{j}$ for an honest
$P_{j}$, such that $x^{\star}_{j}$ is secret-shared with respect to
$\mathbb{S}$.

  * –

$\mathcal{Z}_{a}$-correctness: If the network is asynchronous, then almost-
surely, the honest parties eventually output a subset
$\mathcal{CS}\subseteq\mathcal{Q}$ where
$\mathcal{Q}\setminus\mathcal{CS}\in\mathcal{Z}_{s}$. Moreover, corresponding
to every $P_{j}\in\mathcal{CS}$, there exists an $x^{\star}_{j}\in\mathbb{K}$,
where $x^{\star}_{j}=x_{j}$ for an honest $P_{j}$, such that $x^{\star}_{j}$
is eventually secret-shared with respect to $\mathbb{S}$.

  * –

Privacy: Irrespective of the network type, the view of the adversary remains
independent of the inputs $x_{i}$ corresponding to the honest parties
$P_{i}\in\mathcal{Q}$.

  * –

Communication Complexity: The protocol incurs a communication of
$\mathcal{O}(|\mathcal{Z}_{s}|\cdot
n^{5}\cdot(\log{|\mathbb{K}|}+\log{|\mathcal{Z}_{s}|}+\log{n})+n^{6}\log n)$
bits and invokes $\mathcal{O}(n)$ instances of $\Pi_{\mathsf{BA}}$.

###### Proof

The privacy property simply follows from the privacy property of
$\Pi_{\mathsf{VSS}}$, while communication complexity follows from the
communication complexity of $\Pi_{\mathsf{VSS}}$ and the fact that up to
$\mathcal{O}(n)$ instances of $\Pi_{\mathsf{VSS}}$ may be involved, since
$|\mathcal{Q}|=\mathcal{O}(n)$. We next prove the correctness property.

We first consider a synchronous network. Let $Z_{s}^{\star}\in\mathcal{Z}_{s}$
be the set of corrupt parties, and let $\mathcal{H}\stackrel{{\scriptstyle
def}}{{=}}\mathcal{Q}\setminus\mathcal{Z}_{s}^{\star}$ be the set of honest
parties. We note that $\mathcal{H}\neq\emptyset$, since it is given that
$\mathcal{Z}_{s}$ and $\mathcal{Z}_{a}$ either satisfy the
$\mathcal{Q}^{(1,1)}(\mathcal{Q},\mathcal{Z}_{s},\mathcal{Z}_{a})$ condition
or $\mathcal{Q}^{(3,1)}(\mathcal{Q},\mathcal{Z}_{s},\mathcal{Z}_{a})$
condition. Corresponding to each $P_{j}\in\mathcal{H}$, every honest $P_{i}$
obtains the output $\\{[x_{j}]_{m}\\}_{P_{i}\in S_{m}}$ at time
$T_{\mathsf{VSS}}$ during $\Pi_{\mathsf{VSS}}^{(j)}$, which follows from the
$\mathcal{Z}_{s}$-correctness of $\Pi_{\mathsf{VSS}}$ in the synchronous
network. Consequently, at time $T_{\mathsf{VSS}}$, the set $\mathcal{C}_{i}$
of every honest $P_{i}$ will satisfy the condition
$\mathcal{Q}\setminus\mathcal{C}_{i}\in\mathcal{Z}_{s}$. This is because
$\mathcal{H}\subseteq\mathcal{C}_{i}$ will hold at time $T_{\mathsf{VSS}}$.
Now, corresponding to each $P_{j}\in\mathcal{H}$, each $P_{i}\in\mathcal{H}$
starts participating with input $1$ in the instance $\Pi_{\mathsf{BA}}^{(j)}$
at time $T_{\mathsf{VSS}}$. Hence, from the $\mathcal{Z}_{s}$-validity and
$\mathcal{Z}_{s}$-guaranteed liveness properties of $\Pi_{\mathsf{BA}}$ in the
synchronous network, it follows that at time
$T_{\mathsf{VSS}}+T_{\mathsf{BA}}$, every $P_{i}\in\mathcal{H}$ obtains the
output $1$ during the instance $\Pi_{\mathsf{BA}}^{(j)}$ corresponding to
every $P_{j}\in\mathcal{H}$. Consequently, at time
$T_{\mathsf{VSS}}+T_{\mathsf{BA}}$, every honest party will start
participating in the remaining $\Pi_{\mathsf{BA}}$ instances for which no
input has been provided yet (if there are any), and from the
$\mathcal{Z}_{s}$-guaranteed liveness and $\mathcal{Z}_{s}$-consistency
properties of $\Pi_{\mathsf{BA}}$ in the synchronous network, these
$\Pi_{\mathsf{BA}}$ instances will produce common outputs for every honest
party at time $T_{\mathsf{ACS}}=T_{\mathsf{VSS}}+2T_{\mathsf{BA}}$. Hence, at
time $T_{\mathsf{ACS}}$, every honest party outputs a common $\mathcal{CS}$,
where $\mathcal{Q}\setminus\mathcal{CS}\in\mathcal{Z}_{s}$, and where each
$P_{j}\in\mathcal{H}$ will be present in $\mathcal{CS}$. We next wish to show
that corresponding to every $P_{j}\in\mathcal{CS}$, there exists some value
which is secret-shared among the parties with respect to $\mathbb{S}$.

Consider an arbitrary party $P_{j}\in\mathcal{CS}$. If $P_{j}\in\mathcal{H}$,
then as argued above, every $P_{i}\in\mathcal{H}$ computes the shares
$\\{[x_{j}]_{m}\\}_{P_{i}\in S_{m}}$ at time $T_{\mathsf{VSS}}$ itself. Next,
consider a corrupt $P_{j}\in\mathcal{CS}$. Since $P_{j}\in\mathcal{CS}$, it
follows that the instance $\Pi_{\mathsf{BA}}^{(j)}$ produces the output $1$
for all honest parties. This further implies that at least one honest $P_{i}$
must have computed some output during the instance $\Pi_{\mathsf{VSS}}^{(j)}$
by time $T_{\mathsf{VSS}}+T_{\mathsf{BA}}$ (implying that
$P_{j}\in\mathcal{C}_{i}$) and participated with input $1$ in the instance
$\Pi_{\mathsf{BA}}^{(j)}$. This is because if, at time
$T_{\mathsf{VSS}}+T_{\mathsf{BA}}$, party $P_{j}$ does not belong to the
$\mathcal{C}_{i}$ set of any honest $P_{i}$, then it implies that all honest
parties start participating with input $0$ in the instance
$\Pi_{\mathsf{BA}}^{(j)}$ at time $T_{\mathsf{VSS}}+T_{\mathsf{BA}}$. Then,
from the $\mathcal{Z}_{s}$-validity of $\Pi_{\mathsf{BA}}$ in the synchronous
network, every honest party would have obtained the output $0$ in the instance
$\Pi_{\mathsf{BA}}^{(j)}$ and hence, $P_{j}$ will not be present in
$\mathcal{CS}$, which is a contradiction. Now, if $P_{i}$ has computed some
output during $\Pi_{\mathsf{VSS}}^{(j)}$ at time
$T_{\mathsf{VSS}}+T_{\mathsf{BA}}$, then from the $\mathcal{Z}_{s}$-commitment
of $\Pi_{\mathsf{VSS}}$ in the synchronous network, it follows that there
exists some value $x_{j}^{\star}$, such that $x_{j}^{\star}$ will be secret-
shared with respect to $\mathbb{S}$ by time
$T_{\mathsf{VSS}}+T_{\mathsf{BA}}+2\Delta$. Since $2\Delta<T_{\mathsf{BA}}$,
it follows that at time $T_{\mathsf{ACS}}$, every $P_{i}\in\mathcal{H}$ has
$\\{[x^{\star}_{j}]_{m}\\}_{P_{i}\in S_{m}}$, thus proving the correctness
property in a synchronous network.

We next consider an asynchronous network. Let
$Z_{a}^{\star}\in\mathcal{Z}_{a}$ be the set of corrupt parties, and let
$\mathcal{H}\stackrel{{\scriptstyle
def}}{{=}}\mathcal{Q}\setminus\mathcal{Z}_{a}^{\star}$ be the set of honest
parties. Notice that $\mathcal{Q}\setminus\mathcal{H}\in\mathcal{Z}_{s}$,
since every subset in $\mathcal{Z}_{a}$ is a subset of some subset in
$\mathcal{Z}_{s}$. Now, irrespective of the way messages are scheduled, there
will eventually be subset of parties $\mathcal{Q}\setminus Z$ for some
$Z\in\mathcal{Z}_{s}$, such that all the parties in $\mathcal{H}$ participate
with input $1$ in the instances of $\Pi_{\mathsf{BA}}$ corresponding to the
parties in $\mathcal{Q}\setminus Z$. This is because corresponding to every
$P_{j}\in\mathcal{H}$, every $P_{i}\in\mathcal{H}$ eventually computes an
output during the instance $\Pi_{\mathsf{VSS}}^{(j)}$, which follows from the
$\mathcal{Z}_{a}$-correctness of $\Pi_{\mathsf{VSS}}$ in the asynchronous
network. So, even if the corrupt parties $P_{j}$ do not invoke their
respective $\Pi_{\mathsf{VSS}}^{(j)}$ instances, there will be a set of
$\Pi_{\mathsf{BA}}$ instances corresponding to the parties in
$\mathcal{Q}\setminus Z$ for some $Z\in\mathcal{Z}_{s}$ in which all the
parties in $\mathcal{H}$ eventually participate with input $1$. Consequently,
from the $\mathcal{Z}_{a}$-almost-surely liveness and
$\mathcal{Z}_{a}$-consistency properties of $\Pi_{\mathsf{BA}}$ in the
asynchronous network, these $\Pi_{\mathsf{BA}}$ instances eventually produce
the output $1$ for all the parties in $\mathcal{H}$. Hence, all the parties in
$\mathcal{H}$ eventually participate with some input in the remaining
$\Pi_{\mathsf{BA}}$ instances, which almost-surely produce some output for
every honest party eventually. From the properties of $\Pi_{\mathsf{BA}}$ in
the asynchronous network, it then follows that all the honest parties output
the same $\mathcal{CS}$.

Now, consider an arbitrary $P_{j}\in\mathcal{CS}$. It implies that the honest
parties computed the output $1$ during the instance $\Pi_{\mathsf{BA}}^{(j)}$,
which further implies that at least one honest $P_{i}$ participated with input
$1$ in $\Pi_{\mathsf{BA}}^{(j)}$ after computing its output in the instance
$\Pi_{\mathsf{VSS}}^{(j)}$. If $P_{j}$ is honest, then the
$\mathcal{Z}_{a}$-correctness of $\Pi_{\mathsf{VSS}}$ in the asynchronous
network guarantees that $x_{j}$ will be eventually secret-shared with respect
to $\mathbb{S}$, during $\Pi_{\mathsf{VSS}}^{(j)}$. On the other hand, if
$P_{j}$ is corrupt, then the $\mathcal{Z}_{a}$-commitment of
$\Pi_{\mathsf{VSS}}$ in the asynchronous network guarantees that there exists
some $x^{\star}_{j}\in\mathbb{K}$, such that $x^{\star}_{j}$ will eventually
be secret-shared with respect to $\mathbb{S}$, during
$\Pi_{\mathsf{VSS}}^{(j)}$.

We next discuss the modifications needed in the protocol $\Pi_{\mathsf{ACS}}$
when each party in $\mathcal{Q}$ has $L$ inputs.

####  $\Pi_{\mathsf{ACS}}$ for $L$ Inputs:

Protocol $\Pi_{\mathsf{ACS}}$ can be easily extended if each party has $L$
inputs. Now, each $P_{j}$ shares $L$ values through instances of
$\Pi_{\mathsf{VSS}}$. Moreover, the parties participate with input $1$ in the
instance $\Pi_{\mathsf{BA}}^{(j)}$ if they have computed some output in all
the $L$ instances of $\Pi_{\mathsf{VSS}}$ invoked by $P_{j}$ as a dealer. The
rest of the protocol steps remain the same. The protocol will now incur a
communication of $\mathcal{O}(L\cdot|\mathcal{Z}_{s}|\cdot
n^{5}(\log{|\mathbb{K}|}+\log{|\mathcal{Z}_{s}|})+n^{6}\log n)$ bits and
invokes $\mathcal{O}(n)$ instances of $\Pi_{\mathsf{BA}}$.

###  0.E.2 Multiplication Protocol and Its Properties

In this section, we formally present our multiplication protocol
$\Pi_{\mathsf{Mult}}$ and prove its properties. For simplicity, we first
consider the case when $L=1$, and present the formal details of the protocol
in Fig 9.  Let $[a]_{1},\ldots,[a]_{q}$ and $[b]_{1},\ldots,[b]_{q}$ be the
shares, corresponding to $[a]$ and $[b]$ respectively, where every
$P_{i}\in\mathcal{P}$ holds the shares $\\{[a]_{m},[b_{m}]\\}_{P_{i}\in
S_{m}}$.  – For every ordered pair
$(l,m)\in\\{1,\ldots,q\\}\times\\{1,\ldots,q\\}$, the parties do the following
to compute $[a_{l}\cdot b_{m}]$, where $a_{l}\stackrel{{\scriptstyle
def}}{{=}}[a]_{l}$ and $b_{m}\stackrel{{\scriptstyle def}}{{=}}[b]_{m}$.  –
Let $\mathcal{Q}_{l,m}\stackrel{{\scriptstyle def}}{{=}}S_{l}\cap S_{m}$. The
parties execute an instance $\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$ of
$\Pi_{\mathsf{ACS}}$, where every $P_{i}\in\mathcal{Q}_{l,m}$ participates
with the input $a_{l}\cdot b_{m}$. – Let
$\mathcal{R}_{l,m}\subseteq\mathcal{Q}_{l,m}$ be the common subset of parties
obtained as the output from the instance
$\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$, where
$\mathcal{Q}_{l,m}\setminus\mathcal{R}_{l,m}\in\mathcal{Z}_{s}$. Let
$r\stackrel{{\scriptstyle def}}{{=}}|\mathcal{R}_{l,m}|$ and let
$\mathcal{R}_{l,m}=\\{P_{\alpha_{1}},\ldots,P_{\alpha_{r}}\\}$. Moreover,
corresponding to $P_{\alpha_{i}}\in\mathcal{R}_{l,m}$, let $v_{i}$ be the
value which is secret-shared on the behalf of $P_{\alpha_{i}}$ during
$\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$.141414If $P_{\alpha_{i}}$ is honest,
then $v_{i}=a_{l}\cdot b_{m}$ holds.. – The parties publicly check whether
$v_{1},\ldots,v_{r}$ are all equal. For this, the parties locally compute
$r-1$ differences $[d_{1}]\stackrel{{\scriptstyle
def}}{{=}}[v_{1}]-[v_{2}],\ldots,[d_{r-1}]\stackrel{{\scriptstyle
def}}{{=}}[v_{1}]-[v_{r}]$. This is followed by publicly reconstructing the
differences $d_{1},\ldots,d_{r-1}$ by invoking instances of
$\Pi_{\mathsf{Rec}}$, and checking if all of them are $0$.  – If
$d_{1}=\ldots=d_{r-1}=0$, then the parties set $[a_{l}\cdot b_{m}]=[v_{1}]$. –
Else, the parties publicly reconstruct $[a]_{l}$ and $[b]_{m}$ by invoking
instances $\Pi_{\mathsf{Rec}}([a]_{l},\mathbb{S})$ and
$\Pi_{\mathsf{Rec}}([b]_{m},\mathbb{S})$ of $\Pi_{\mathsf{Rec}}$. The parties
then set $[a_{l}\cdot b_{m}]$ to the default sharing of $a_{l}\cdot b_{m}$,
where $[a_{l}\cdot b_{m}]_{1}=a_{l}\cdot b_{m}$ and $[a_{l}\cdot
b_{m}]_{2}=\ldots=[a_{l}\cdot b_{m}]_{q}=0$.151515The vector of shares
$(s,0,\ldots,0)$ can be considered as a default sharing of any given
$s\in\mathbb{K}$. – The parties output $[a\cdot
b]=\displaystyle\sum_{(l,m)\in\\{1,\ldots,q\\}\times\\{1,\ldots,q\\}}[a_{l}\cdot
b_{m}]$.

Figure 9: The perfectly-secure multiplication protocol

We next prove the properties of $\Pi_{\mathsf{Mult}}$. We first start with a
helping lemma.

###### Lemma 17

In protocol $\Pi_{\mathsf{Mult}}$, the following hold for every ordered pair
$(l,m)\in\\{1,\ldots,q\\}\times\\{1,\ldots,q\\}$.

  * –

$\mathcal{Z}_{s}$ and $\mathcal{Z}_{a}$ satisfy the
$\mathcal{Q}^{(1,1)}(\mathcal{Q}_{l,m},\mathcal{Z}_{s},\mathcal{Z}_{a})$
condition, where $\mathcal{Q}_{l,m}=S_{l}\cap S_{m}$.

  * –

In a synchronous network, at time $T_{\mathsf{ACS}}$, all honest parties will
compute a set $\mathcal{R}_{l,m}\subseteq\mathcal{Q}_{l,m}$, where
$\mathcal{Q}_{l,m}\setminus\mathcal{R}_{l,m}\in\mathcal{Z}_{s}$, such that
$\mathcal{R}_{l,m}$ contains all honest parties from $\mathcal{Q}_{l,m}$.

  * –

In an asynchronous network, almost-surely, all honest parties will eventually
compute a set $\mathcal{R}_{l,m}\subseteq\mathcal{Q}_{l,m}$, where
$\mathcal{Q}_{l,m}\setminus\mathcal{R}_{l,m}\in\mathcal{Z}_{s}$, such that
$\mathcal{R}_{l,m}$ contains at least one honest party from
$\mathcal{Q}_{l,m}$.

###### Proof

The first property follows from the fact that $\mathcal{Z}_{s}$ and
$\mathcal{Z}_{a}$ satisfy the
$\mathcal{Q}^{(3,1)}(\mathcal{P},\mathcal{Z}_{s},\mathcal{Z}_{a})$ condition,
and $\mathcal{Q}_{l,m}\stackrel{{\scriptstyle def}}{{=}}S_{l}\cap
S_{m}=\mathcal{P}\setminus(Z_{l}\cup Z_{m})$. Hence, if $\mathcal{Z}_{s}$ and
$\mathcal{Z}_{a}$ do not satisfy the
$\mathcal{Q}^{(1,1)}(\mathcal{P},\mathcal{Z}_{s},\mathcal{Z}_{a})$ condition,
then it implies that there exist sets $Z_{\alpha}\in\mathcal{Z}_{s}$ and
$Z_{\beta}\in\mathcal{Z}_{a}$ such that $\mathcal{Q}_{l,m}\subseteq
Z_{\alpha}\cup Z_{\beta}$. This further implies that $Z_{\alpha}\cup
Z_{\beta}\cup Z_{l}\cup Z_{m}\subseteq\mathcal{P}$, which contradicts the fact
that $\mathcal{Z}_{s}$ and $\mathcal{Z}_{a}$ satisfy the
$\mathcal{Q}^{(3,1)}(\mathcal{P},\mathcal{Z}_{s},\mathcal{Z}_{a})$ condition.

For proving the second property, we consider a synchronous network. Let
$Z_{s}^{\star}\in\mathcal{Z}_{s}$ be the set of corrupt parties. Since
$\mathcal{Z}_{s}$ and $\mathcal{Z}_{a}$ satisfy the
$\mathcal{Q}^{(1,1)}(\mathcal{Q}_{l,m},\mathcal{Z}_{s},\allowbreak\mathcal{Z}_{a})$
condition, from the $\mathcal{Z}_{s}$-correctness of $\Pi_{\mathsf{ACS}}$ in
the synchronous network, it follows that all honest parties will compute
$\mathcal{R}_{l,m}$ as the output of the instance
$\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$, such that
$\mathcal{Q}_{l,m}\setminus\mathcal{R}_{l,m}\in\mathcal{Z}_{s}$. Moreover, all
the parties from $\mathcal{Q}_{l,m}\setminus Z_{s}^{\star}$ will be present in
$\mathcal{R}_{l,m}$. This proves the second property.

We next consider an asynchronous network. Let
$Z_{a}^{\star}\in\mathcal{Z}_{a}$ be the set of corrupt parties. From the
$\mathcal{Z}_{a}$-correctness of $\Pi_{\mathsf{ACS}}$ in the asynchronous
network, it follows that, almost-surely, all honest parties will eventually
compute $\mathcal{R}_{l,m}$ as the output of the instance
$\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$ such that
$\mathcal{Q}_{l,m}\setminus\mathcal{R}_{l,m}\in\mathcal{Z}_{s}$. Moreover,
$\mathcal{R}_{l,m}\not\subset Z_{a}^{\star}$, as otherwise, $\mathcal{Z}_{s}$
and $\mathcal{Z}_{a}$ do not satisfy the
$\mathcal{Q}^{(1,1)}(\mathcal{Q}_{l,m},\mathcal{Z}_{s},\mathcal{Z}_{a})$
condition, which is a contradiction. Consequently, $\mathcal{R}_{l,m}$ will
consists of at least one honest party from $\mathcal{Q}_{l,m}$.

We now proceed to prove the properties of $\Pi_{\mathsf{Mult}}$.

###### Lemma 18

In a synchronous network, all honest parties output $[c]$ within time
$T_{\mathsf{{Mult}}}=T_{\mathsf{ACS}}+2\Delta$, where $c=a\cdot b$. Moreover,
the view of the adversary remains independent of $a$ and $b$.

###### Proof

To prove the lemma, we claim that for each ordered pair
$(l,m)\in\\{1,\ldots,q\\}\allowbreak\times\\{1,\ldots,q\\}$, all honest
parties securely compute a secret-sharing of the summand
$[a]_{l}\cdot[b]_{m}$, within time $T_{\mathsf{ACS}}+2\Delta$, without
revealing any additional information to the adversary. The proof then follows
from the fact that the following holds:

$[c]=[a\cdot
b]=\displaystyle\sum_{(l,m)\in\\{1,\ldots,q\\}\times\\{1,\ldots,q\\}}[[a]_{l}\cdot[b]_{m}].$

We now proceed to prove our claim, for which we consider an arbitrary ordered
pair $(l,m)\in\\{1,\ldots,q\\}\times\\{1,\ldots,q\\}$.

From Lemma 17, at time $T_{\mathsf{ACS}}$, all honest parties will compute the
set $\mathcal{R}_{l,m}$ as the output of the instance
$\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$, where
$\mathcal{R}_{l,m}\subseteq\mathcal{Q}_{l,m}$, and where all honest parties
from $\mathcal{Q}_{l,m}$ will be present in $\mathcal{R}_{l,m}$. Let
$|\mathcal{R}_{l,m}|=r$ and
$\mathcal{R}_{l,m}=\\{P_{\alpha_{1}},\ldots,P_{\alpha_{r}}\\}$. Moreover,
without loss of generality, let $P_{\alpha_{1}}$ be honest. From the
$\mathcal{Z}_{s}$-correctness of $\Pi_{\mathsf{ACS}}$ in the synchronous
network, corresponding to every $P_{\alpha_{j}}\in\mathcal{R}_{l,m}$, there
exists some value, $v_{j}$, which will be secret-shared among the parties on
the behalf of $P_{\alpha_{j}}$ during the instance
$\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$. Moreover, since $P_{\alpha_{1}}$ is
assumed to be honest, from the protocol steps, $v_{1}=[a]_{l}\cdot[b]_{m}$.

Now there are two possible cases:

  * $\bullet$

Every party in $\mathcal{R}_{l,m}$ participates with input
$[a]_{l}\cdot[b]_{m}$ during $\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$: In this
case, $v_{1}=v_{2}=\ldots=v_{r}=[a]_{l}\cdot[b]_{m}$ and hence
$d_{1}=\ldots=d_{r-1}=0$. From the properties of $\Pi_{\mathsf{Rec}}$, within
time $T_{\mathsf{ACS}}+\Delta$, the honest parties reconstruct the $r-1$
differences $d_{1},\ldots,d_{r-1}$ and find all of them to be $0$. Hence, they
set $[[a]_{l}\cdot[b]_{m}]$ to $[v_{1}]$, where $v_{1}$ is the same as
$[a]_{l}\cdot[b]_{m}$. The privacy in this case follows from privacy of
$\Pi_{\mathsf{ACS}}$ and the fact that the adversary only learns the $r-1$
differences, which are all $0$.

  * $\bullet$

Some party in $\mathcal{R}_{l,m}$ participates with an input, which is
different from $[a]_{l}\cdot[b]_{m}$, during
$\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$: Let $P_{i}\in\mathcal{R}_{l,m}$ be a
corrupt party, corresponding to which $v_{i}$ is shared during
$\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$, where $v_{i}\neq[a]_{l}\cdot[b]_{m}$.
Since $v_{i}\neq v_{1}$, it follows that at least one of the $r-1$ differences
$d_{1},\ldots,d_{r-1}$ will be non-zero, and the parties detect the same when
these differences are publicly reconstructed at time
$T_{\mathsf{ACS}}+\Delta$. In this case, the parties reconstruct the shares
$[a]_{l}$ and $[b]_{m}$ at time $T_{\mathsf{ACS}}+2\Delta$, and take a default
secret-sharing of $[a]_{l}\cdot[b]_{m}$. The privacy in this case follows from
the fact that since there exists a corrupt party in $\mathcal{R}_{l,m}$, the
adversary is already aware of the shares $[a]_{l}$ and $[b]_{m}$ and hence,
publicly reconstructing these values does not add any new information to the
view of the adversary.

We next consider prove the properties in an asynchronous network.

###### Lemma 19

In an asynchronous network, almost-surely, all honest parties eventually
output $[c]$, where $c=a\cdot b$. Moreover, the view of the adversary remains
independent of $a$ and $b$.

###### Proof

The proof is very similar to the proof of Lemma 18. Namely, we show that
almost-surely, corresponding to each ordered pair
$(l,m)\in\\{1,\ldots,q\\}\allowbreak\times\\{1,\ldots,q\\}$, all honest
parties eventually and securely compute a secret-sharing of the summand
$[a]_{l}\cdot[b]_{m}$. For this, we consider an arbitrary ordered pair
$(l,m)\in\\{1,\ldots,q\\}\times\\{1,\ldots,q\\}$. From Lemma 17, almost-
surely, all honest parties will eventually compute a set $\mathcal{R}_{l,m}$
as the output of the instance $\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$, where
$\mathcal{R}_{l,m}\subseteq\mathcal{Q}_{l,m}$, and where at least one honest
party from $\mathcal{Q}_{l,m}$ will be present in $\mathcal{R}_{l,m}$. Let
$|\mathcal{R}_{l,m}|=r$ and
$\mathcal{R}_{l,m}=\\{P_{\alpha_{1}},\ldots,P_{\alpha_{r}}\\}$. Moreover,
without loss of generality, let $P_{\alpha_{1}}$ be honest. From the
$\mathcal{Z}_{a}$-correctness of $\Pi_{\mathsf{ACS}}$ in the asynchronous
network, corresponding to every $P_{\alpha_{j}}\in\mathcal{R}_{l,m}$, there
exists some value, $v_{j}$, which will be eventually secret-shared among the
parties on the behalf of $P_{\alpha_{j}}$, during the instance
$\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$. Moreover, since $P_{\alpha_{1}}$ is
assumed to be honest, from the protocol steps, $v_{1}=[a]_{l}\cdot[b]_{m}$.

Now there are two possible cases:

  * $\bullet$

Every party in $\mathcal{R}_{l,m}$ participates with input
$[a]_{l}\cdot[b]_{m}$ during $\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$: In this
case, $v_{1}=v_{2}=\ldots=v_{r}=[a]_{l}\cdot[b]_{m}$ and hence
$d_{1}=\ldots=d_{r-1}=0$. From the properties of $\Pi_{\mathsf{Rec}}$, the
honest parties eventually reconstruct the $r-1$ differences
$d_{1},\ldots,d_{r-1}$ and find all of them to be $0$. Hence they set
$[[a]_{l}\cdot[b]_{m}]$ to $[v_{1}]$, where $v_{1}$ is the same as
$[a]_{l}\cdot[b]_{m}$. The privacy in this case follows from privacy of
$\Pi_{\mathsf{ACS}}$, and the fact that the adversary only learns $r-1$
differences which are all $0$.

  * $\bullet$

Some party in $\mathcal{R}_{l,m}$ participates with an input, which is
different from $[a]_{l}\cdot[b]_{m}$, during
$\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$: Let $P_{i}\in\mathcal{R}_{l,m}$ be a
corrupt party, corresponding to which $v_{i}$ is shared during
$\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$, where $v_{i}\neq[a]_{l}\cdot[b]_{m}$.
Since $v_{i}\neq v_{1}$, it follows that at least one of the $r-1$ differences
$d_{1},\ldots,d_{r-1}$ will be non-zero, and the parties detect the same when
these differences are eventually reconstructed. In this case, the parties
eventually reconstruct the shares $[a]_{l}$ and $[b]_{m}$, and take a default
secret-sharing of $[a]_{l}\cdot[b]_{m}$. The privacy in this case follows from
the fact that since there exists a corrupt party in $\mathcal{R}_{l,m}$, the
adversary is already aware of the shares $[a]_{l}$ and $[b]_{m}$ and hence,
publicly reconstructing these values does not add any new information to the
view of the adversary.

The proof of Lemma 20 now easily follows from Lemma 18 and Lemma 19. The
communication complexity follows from the fact that
$q^{2}=|\mathcal{Z}_{s}|^{2}$ instances of $\Pi_{\mathsf{ACS}}$ are executed.

###### Lemma 20

Let $\mathcal{A}$ be an adversary, characterized by an adversary structure
$\mathcal{Z}_{s}$ in a synchronous network and adversary structure
$\mathcal{Z}_{a}$ in an asynchronous network, satisfying the conditions
$\mathsf{Con}$ (see Condition 2.1 in Section 2). Moreover, let
$\mathbb{S}=\\{S_{m}:S_{m}=\mathcal{P}\setminus Z_{m}\;\mbox{ and
}\;Z_{m}\in\mathcal{Z}_{s}\\}$. Then protocol $\Pi_{\mathsf{Mult}}$ achieves
the following properties, where the inputs of the parties are $[a]$ and $[b]$.

  * –

$\mathcal{Z}_{s}$-correctness: In a synchronous network, all honest parties
output $[c]$ within time $T_{\mathsf{{Mult}}}=T_{\mathsf{ACS}}+2\Delta$, where
$c=a\cdot b$.

  * –

$\mathcal{Z}_{a}$-correctness: In an asynchronous network, almost-surely, the
honest parties eventually output $[c]$, where $c=a\cdot b$.

  * –

Privacy: Irrespective of the network type, the view of the adversary remains
independent of $a$ and $b$.

  * –

Communication Complexity: $\Pi_{\mathsf{Mult}}$ incurs a communication of
$\mathcal{O}(|\mathcal{Z}_{s}|^{3}\cdot
n^{5}(\log{|\mathbb{K}|}+\log{|\mathcal{Z}_{s}|+\log
n})+|\mathcal{Z}_{s}|^{2}\cdot n^{6}\log n)$ bits and invokes
$\mathcal{O}(|\mathcal{Z}_{s}|^{2}\cdot n)$ instances of $\Pi_{\mathsf{BA}}$.

We next discuss the modifications needed in the protocol $\Pi_{\mathsf{Mult}}$
to handle the case when $L>1$.

#### Protocol $\Pi_{\mathsf{Mult}}$ for $L$ Pairs of Inputs:

If the input for $\Pi_{\mathsf{Mult}}$ is
$\\{([a^{(\ell)}],\allowbreak[b^{(\ell)}])\\}_{\ell=1,\ldots L}$, then during
the instance of $\Pi_{\mathsf{ACS}}(\mathcal{Q}_{l,m})$, each party in
$\mathcal{Q}_{l,m}$ will have to share $L$ summands. Similarly, corresponding
to $\mathcal{R}_{l,m}$, the parties reconstruct $(|\mathcal{R}_{l,m}|-1)\cdot
L$ number of difference values. The rest of the protocol steps remain the
same. With these modification, $\Pi_{\mathsf{Mult}}$ will now incur a
communication of $\mathcal{O}(L\cdot|\mathcal{Z}_{s}|^{3}\cdot
n^{5}(\log{|\mathbb{K}|}+\log{|\mathcal{Z}_{s}|}+\log
n)+|\mathcal{Z}_{s}|^{2}\cdot n^{6}\log n)$ bits and invokes
$\mathcal{O}(|\mathcal{Z}_{s}|^{2}\cdot n)$ instances of $\Pi_{\mathsf{BA}}$.

###  0.E.3 Protocol $\Pi_{\mathsf{PreProcessing}}$ and Its Properties

In this section, we formally present our preprocessing phase protocol
$\Pi_{\mathsf{PreProcessing}}$ and prove its properties. For the sake of
simplicity, we first explain the protocol to generate one random secret-shared
multiplication-triple. The protocol is presented in Fig 10.  – Generating
random pairs of values: The parties do the the following.  – Participate in an
instance $\Pi_{\mathsf{ACS}}(\mathcal{P})$ of $\Pi_{\mathsf{ACS}}$, where the
input of each $P_{i}$ is a random pair of values $(a_{i},b_{i})\in\mathbb{K}$.
– Let $\mathcal{R}$ be the output of the instance
$\Pi_{\mathsf{ACS}}(\mathcal{P})$, where
$\mathcal{P}\setminus\mathcal{R}\in\mathcal{Z}_{s}$. Moreover, corresponding
to $P_{i}\in\mathcal{R}$, let $(a_{i}^{\star},b_{i}^{\star})\in\mathbb{K}$ be
the pair of values such that the parties hold $[a_{i}^{\star}]$ and
$[b_{i}^{\star}]$ during the instance $\Pi_{\mathsf{ACS}}(\mathcal{P})$. – The
parties locally compute
$[a]=\displaystyle\sum_{P_{i}\in\mathcal{R}}[a^{\star}_{i}]$ and
$[b]=\displaystyle\sum_{P_{i}\in\mathcal{R}}[b^{\star}_{i}]$. – Computing the
product: The parties compute $[c]$ by executing
$\Pi_{\mathsf{Mult}}([a],[b])$.  – The parties output $([a],[b],[c])$.

Figure 10: The preprocessing phase protocol for generating a secret-sharing of
one random multiplication-triple

We next prove the properties of the protocol $\Pi_{\mathsf{PreProcessing}}$.

###### Lemma 21

Let $\mathcal{A}$ be an adversary characterized by an adversary structure
$\mathcal{Z}_{s}$ in a synchronous network and adversary structure
$\mathcal{Z}_{a}$ in an asynchronous network, satisfying the conditions
$\mathsf{Con}$ (see Condition 2.1 in Section 2). Moreover, let
$\mathbb{S}=\\{S_{m}:S_{m}=\mathcal{P}\setminus Z_{m}\;\mbox{ and
}\;Z_{m}\in\mathcal{Z}_{s}\\}$. Then $\Pi_{\mathsf{PreProcessing}}$ achieves
the following.

  * –

$\mathcal{Z}_{s}$-correctness: In a synchronous network, all honest parties
output $([a],[b],\allowbreak[c])$ within time
$T_{\mathsf{{PreProcessing}}}=T_{\mathsf{ACS}}+T_{\mathsf{{Mult}}}$, where
$c=a\cdot b$.

  * –

$\mathcal{Z}_{a}$-correctness: In an asynchronous network, almost-surely, the
honest parties eventually output $([a],[b],[c])$, where $c=a\cdot b$.

  * –

Privacy: Irrespective of the network type, the view of the adversary remains
independent of $a,b$ and $c$.

  * –

Communication Complexity: $\Pi_{\mathsf{PreProcessing}}$ incurs a
communication of $\mathcal{O}(L\cdot|\mathcal{Z}_{s}|^{3}\cdot
n^{5}(\log{|\mathbb{K}|}+\log{|\mathcal{Z}_{s}|}+\log
n)+|\mathcal{Z}_{s}|^{2}\cdot n^{6}\log n)$ bits and invokes
$\mathcal{O}(|\mathcal{Z}_{s}|^{2}\cdot n)$ instances of $\Pi_{\mathsf{BA}}$.

###### Proof

We first consider a synchronous network. From the
$\mathcal{Z}_{s}$-correctness of $\Pi_{\mathsf{ACS}}$ in the synchronous
network, it follows that at time $T_{\mathsf{ACS}}$, all honest parties will
output a common subset of parties $\mathcal{R}\subseteq\mathcal{P}$, where
$\mathcal{P}\setminus\mathcal{R}\in\mathcal{Z}_{s}$. Moreover, corresponding
to every $P_{i}\in\mathcal{R}$, there will be a pair of values
$(a_{i}^{\star},b_{i}^{\star})\in\mathbb{K}$, which will be secret-shared with
respect to $\mathbb{S}$ on the behalf of $P_{i}$, during the instance of
$\Pi_{\mathsf{ACS}}$. Furthermore,
$(a_{i}^{\star},b_{i}^{\star})=(a_{i},b_{i})$ for every honest
$P_{i}\in\mathcal{R}$. Also, if $P_{i}\in\mathcal{R}$ is honest, then the
privacy property of $\Pi_{\mathsf{ACS}}$ guarantees that the view of the
adversary remains independent of $(a_{i},b_{i})$. The
$\mathcal{Z}_{s}$-correctness property of $\Pi_{\mathsf{ACS}}$ in the
synchronous network also guarantees that all honest parties from $\mathcal{P}$
will be present in $\mathcal{R}$. Now, since the honest parties in
$\mathcal{P}$ secret-share random pairs of values during $\Pi_{\mathsf{ACS}}$,
it follows that $(a,b)$ will be random from the point of view of the
adversary. Finally, the $\mathcal{Z}_{s}$-correctness property of
$\Pi_{\mathsf{Mult}}$ in the synchronous network guarantees that the parties
output $([a],[b],[c])$ at time $T_{\mathsf{ACS}}+T_{\mathsf{{Mult}}}$, where
$c=a\cdot b$. Moreover, the privacy property of $\Pi_{\mathsf{Mult}}$ in the
synchronous network guarantees that adversary does not learn any additional
information about $a,b$ and $c$ (except that $c=a\cdot b$), during the
instance of $\Pi_{\mathsf{Mult}}$ as well.

The proof of the properties in an asynchronous network is almost the same as
above, except that we now use the $\mathcal{Z}_{a}$-correctness property of
$\Pi_{\mathsf{ACS}}$ in the asynchronous network (which guarantees that the
parties eventually compute a common $\mathcal{R}$, containing at least one
honest party) and the $\mathcal{Z}_{a}$-correctness property of
$\Pi_{\mathsf{Mult}}$ in the asynchronous network. To avoid repetition, we do
not give the formal details.

The communication complexity follows from the communication complexity of
$\Pi_{\mathsf{ACS}}$ and $\Pi_{\mathsf{Mult}}$.

We next discuss the modifications needed in the protocol
$\Pi_{\mathsf{PreProcessing}}$ to generate $c_{M}$ number of secret-shared
multiplication-triples.

####  $\Pi_{\mathsf{PreProcessing}}$ for Generating $c_{M}$ Random
Multiplication-triples:

To generate secret-sharing of $c_{M}$ random multiplication-triples, the
instance of $\Pi_{\mathsf{ACS}}$ during the first stage is executed by setting
$L=c_{M}$. Consequently, there will be $c_{M}$ pairs of secret-shared values
generated on the behalf of each party in $\mathcal{R}$. Moreover, the pairs of
values shared by the honest parties in $\mathcal{R}$ will be random from the
point of view of the adversary. Consequently, summing the secret-sharing of
the pairs of values shared by the parties in $\mathcal{R}$, leads to $c_{M}$
pairs of random values being secret-shared during the first stage. Then,
during the second stage, the parties execute an instance of
$\Pi_{\mathsf{Mult}}$, with the input being the $c_{M}$ pairs of random
secret-shared pairs of values from the first stage. This securely leads to a
secret-sharing of the product of each pair. The resultant protocol will now
incur a communication of $\mathcal{O}(c_{M}\cdot|\mathcal{Z}_{s}|^{3}\cdot
n^{5}(\log{|\mathbb{K}|}+\log{|\mathcal{Z}_{s}|}+\log
n)+|\mathcal{Z}_{s}|^{2}\cdot n^{6}\log n)$ bits, and invokes
$\mathcal{O}(|\mathcal{Z}_{s}|^{2}\cdot n)$ instances of $\Pi_{\mathsf{BA}}$.

##  Appendix 0.F The Circuit-Evaluation Protocol and Its Properties

Protocol $\Pi_{\mathsf{CirEval}}$ for securely evaluating the circuit
$\mathsf{cir}$ is presented in Fig 11.  – Preprocessing and Input-Sharing —
The parties do the following:  – Each $P_{i}\in\mathcal{P}$, on having the
input $x_{i}$ for $f$, participates in the instance
$\Pi_{\mathsf{ACS}}(\mathcal{P})$ of $\Pi_{\mathsf{ACS}}$ with input $x_{i}$.
Let $\mathcal{CS}$ be the common subset of parties obtained as the output
during $\Pi_{\mathsf{ACS}}(\mathcal{P})$, where
$\mathcal{P}\setminus\mathcal{CS}\in\mathcal{Z}_{s}$. Corresponding to every
$P_{j}\not\in\mathcal{CS}$, set $x_{j}=0$, and set $[x_{j}]$ to the default
secret-sharing, where $[x_{j}]_{1}=[x_{j}]_{2}=\ldots=[x_{j}]_{q}=0$. –
Participate in an instance of $\Pi_{\mathsf{PreProcessing}}$ to generate
$c_{M}$ number of secret-shared, random multiplication-triples
$\\{[\mathbf{a}^{(j)}],[\mathbf{b}^{(j)}],[\mathbf{c}^{(j)}]\\}_{j=1,\ldots,c_{M}}$.
– Circuit Evaluation — Let $G_{1},\ldots,G_{m}$ be a publicly-known
topological ordering of the gates of $\mathsf{cir}$. For $k=1,\ldots,m$, the
parties do the following for gate $G_{k}$:  – If $G_{k}$ is an addition gate:
the parties locally compute $[w]=[u]+[v]$, where $u$ and $v$ are gate-inputs,
and $w$ is the gate-output. – If $G_{k}$ is a multiplication-with-a-constant
gate with constant $c$: the parties locally compute $[v]=c\cdot[u]$, where $u$
is the gate-input, and $v$ is the gate-output. – If $G_{k}$ is an addition-
with-a-constant gate with constant $c$: the parties locally compute
$[v]=c+[u]$, where $u$ is the gate-input, and $v$ is the gate-output. – If
$G_{k}$ is a multiplication gate: Let $G_{k}$ be the $\ell^{th}$
multiplication gate in $\mathsf{cir}$, where $\ell\in\\{1,\ldots,c_{M}\\}$,
and let $([a^{(\ell)}],[b^{(\ell)}],[c^{(\ell)}])$ be the $\ell^{th}$ shared
multiplication-triple generated during $\Pi_{\mathsf{PreProcessing}}$.
Moreover, let $[u]$ and $[v]$ be the shared gate-inputs of $G_{k}$. Then, the
parties participate in an instance
$\Pi_{\mathsf{Beaver}}(([u],[v]),([a^{(\ell)}],[b^{(\ell)}],[c^{(\ell)}]))$ of
$\Pi_{\mathsf{Beaver}}$, and obtain $[w]$, where $w=u\cdot v$. – Output
Computation — Let $[y]$ be the secret-shared circuit-output. The parties
participate in an instance $\Pi_{\mathsf{Rec}}(y,\mathbb{S})$ of
$\Pi_{\mathsf{Rec}}$ and reconstruct $y$. – Termination: Each $P_{i}$ does the
following.  – If $y$ has been obtained during output computation, then send
the message $(\texttt{ready},y)$ to all the parties. – If the message
$(\texttt{ready},y)$ is received from a set of parties ${\cal C}$, where
${\cal C}\not\in\mathcal{Z}_{s}$, then send $(\texttt{ready},y)$ message to
all the parties if no ready message is sent earlier. – If the message
$(\texttt{ready},y)$ is received from a set of parties $\mathcal{P}\setminus
Z$, for some $Z\in\mathcal{Z}_{s}$, then terminate all sub-protocols, output
$y$, and terminate.

Figure 11: A best-of-both-worlds perfectly-secure protocol for securely
evaluating the arithmetic circuit $\mathsf{cir}$

Theorem 6.1. Let $\mathcal{A}$ be an adversary characterized by an adversary
structure $\mathcal{Z}_{s}$ in a synchronous network and adversary structure
$\mathcal{Z}_{a}$ in an asynchronous network satisfying the conditions
$\mathsf{Con}$ (see Condition 2.1 in Section 2). Moreover, let
$f:\mathbb{K}^{n}\rightarrow\mathbb{K}$ be a function represented by an
arithmetic circuit $\mathsf{cir}$ over $\mathbb{K}$, consisting of $c_{M}$
number of multiplication gates, with a multiplicative depth of $D_{M}$ and
where each party $P_{i}$ has an input $x_{i}\in\mathbb{K}$ for $f$.
Furthermore, let $\mathbb{S}=\\{S_{m}:S_{m}=\mathcal{P}\setminus Z_{m}\;\mbox{
and }\;Z_{m}\in\mathcal{Z}_{s}\\}$. Then, $\Pi_{\mathsf{CirEval}}$ incurs a
communication of $\mathcal{O}(c_{M}\cdot|\mathcal{Z}_{s}|^{3}\cdot
n^{5}(\log{|\mathbb{K}|}+\log{|\mathcal{Z}_{s}|}+\log
n)+|\mathcal{Z}_{s}|^{2}\cdot n^{6}\log n)$ bits, invokes
$\mathcal{O}(|\mathcal{Z}_{s}|^{2}\cdot n)$ instances of $\Pi_{\mathsf{BA}}$,
and achieves the following.

  * –

In a synchronous network, all honest parties output $y=f(x_{1},\ldots,x_{n})$
at time $(30n+D_{M}+6k+38)\cdot\Delta$, where $x_{j}=0$ for every
$P_{j}\not\in\mathcal{CS}$, such that
$\mathcal{P}\setminus\mathcal{CS}\in\mathcal{Z}_{s}$ and every honest party
from $\mathcal{P}$ will be present in $\mathcal{CS}$; here $k$ is the constant
from Lemma 2, as determined by the underlying (existing) perfectly-secure ABA
protocol $\Pi_{\mathsf{ABA}}$.

  * –

In an asynchronous network, almost-surely, the honest parties eventually
output $y=f(x_{1},\ldots,x_{n})$, where $x_{j}=0$ for every
$P_{j}\not\in\mathcal{CS}$, and where
$\mathcal{P}\setminus\mathcal{CS}\in\mathcal{Z}_{s}$.

  * –

The view of the adversary remains independent of the inputs of the honest
parties in $\mathcal{CS}$.

###### Proof

Consider a synchronous network. Let $Z_{s}^{\star}\in\mathcal{Z}_{s}$ be the
set of corrupt parties, and let $\mathcal{H}_{s}\stackrel{{\scriptstyle
def}}{{=}}\mathcal{P}\setminus Z_{s}^{\star}$ be the set of honest parties.
From the $\mathcal{Z}_{s}$-correctness property of
$\Pi_{\mathsf{PreProcessing}}$ in the synchronous network, at time
$T_{\mathsf{{PreProcessing}}}$, the (honest) parties will have $c_{M}$ number
of secret-shared multiplication-triples, shared with respect to $\mathbb{S}$,
from the instance of $\Pi_{\mathsf{PreProcessing}}$. From the
$\mathcal{Z}_{s}$-correctness property of $\Pi_{\mathsf{ACS}}$ in the
synchronous network, at time $T_{\mathsf{ACS}}$, the (honest) parties will
have a common subset $\mathcal{CS}$ from the instance of $\Pi_{\mathsf{ACS}}$,
where all honest parties will be present in $\mathcal{CS}$, and where
$\mathcal{P}\setminus\mathcal{CS}\in\mathcal{Z}_{s}$. Moreover, corresponding
to every $P_{j}\in\mathcal{CS}$, there will be some $x_{j}\in\mathbb{K}$ held
by $P_{j}$ (which will be the same as $P_{j}$’s input for $f$ for an honest
$P_{j}$), such that $x_{j}$ will be secret-shared with respect to
$\mathbb{S}$. As $\mathcal{CS}$ will be known publicly, the parties take a
default secret-sharing of $0$ on the behalf of the parties $P_{j}$ outside
$\mathcal{CS}$, by considering $x^{(j)}=0$. Since
$T_{\mathsf{ACS}}<T_{\mathsf{{PreProcessing}}}$, it follows that at time
$T_{\mathsf{{PreProcessing}}}$, the parties will hold a secret-sharing of
$c_{M}$ multiplication-triples and secret-sharing of $x_{1},\ldots,x_{n}$.

The circuit-evaluation will take $D_{M}\cdot\Delta$ time. This follows from
the fact that linear gates are evaluated locally (non-interactively), while
all the independent multiplication gates can be evaluated in parallel by
running the corresponding instances of $\Pi_{\mathsf{Beaver}}$ in parallel,
where each such instance requires $\Delta$ time. From the
$\mathcal{Z}_{s}$-correctness property of $\Pi_{\mathsf{Beaver}}$ in the
synchronous network, the multiplication-gates will be evaluated correctly and
hence, during the output-computation phase, the parties will hold a secret-
sharing of $y$ (with respect to $\mathbb{S}$), where
$y=f(x_{1},\ldots,x_{n})$. From the properties of $\Pi_{\mathsf{Rec}}$, it
will take $\Delta$ time for every party to reconstruct $y$. Hence, during the
termination phase, all honest parties will send a ready message for $y$. Since
$\mathcal{P}\setminus\mathcal{H}_{s}\in\mathcal{Z}_{s}$, every honest party
will then terminate with output $y$ at time
$T_{\mathsf{{PreProcessing}}}+(D_{M}+2)\cdot\Delta$. By substituting the
values of
$T_{\mathsf{{PreProcessing}}},T_{\mathsf{VSS}},T_{\mathsf{ACS}},T_{\mathsf{BC}},T_{\mathsf{BA}},T_{\mathsf{SBA}}$
and $T_{\mathsf{ABA}}$ and by noting that all instances of $\Pi_{\mathsf{BC}}$
in $\Pi_{\mathsf{CirEval}}$ are invoked with $\mathcal{Z}=\mathcal{Z}_{s}$, we
get that the parties terminate the protocol at time
$(D_{M}+30n+6k+38)\cdot\Delta$, where $k$ is the constant from Lemma 2, as
determined by the underlying (existing) perfectly-secure ABA protocol
$\Pi_{\mathsf{ABA}}$.

If we consider an asynchronous network, then the proof is similar as above,
except that we now use the security properties of the building blocks
$\Pi_{\mathsf{PreProcessing}},\allowbreak\Pi_{\mathsf{ACS}},\Pi_{\mathsf{Beaver}}$
and $\Pi_{\mathsf{Rec}}$ in the asynchronous network. Let
$Z_{a}^{\star}\in\mathcal{Z}_{a}$ be the set of corrupt parties, and let
$\mathcal{H}_{a}\stackrel{{\scriptstyle def}}{{=}}\mathcal{P}\setminus
Z_{a}^{\star}$ be the set of honest parties. During the termination phase, the
parties in $Z_{a}^{\star}$ may send ready messages for $y^{\prime}$, where
$y^{\prime}\neq y$. Since every subset in $\mathcal{Z}_{a}$ is a subset of
some subset in $\mathcal{Z}_{s}$, it follows that no honest party will
terminate with output $y^{\prime}$, where $y^{\prime}\neq y$. On the other
hand, all the parties in $\mathcal{H}_{a}$ will eventually compute the output
$y$, and will send a ready message for $y$, which is eventually delivered to
every honest party. Now, consider an honest party $P_{h}$, who terminates with
output $y$. We wish to show that every honest party eventually terminates the
protocol with output $y$. This is because $P_{h}$ must have received ready
messages for $y$ from a subset of parties $\mathcal{P}\setminus Z_{\alpha}$,
for some $Z_{\alpha}$. Since $\mathcal{Z}_{s}$ satisfies the
$\mathcal{Q}^{(3)}(\mathcal{P},\mathcal{Z}_{s})$ condition, it follows that
that $\mathcal{H}_{a}\cap(\mathcal{P}\setminus
Z_{\alpha})\not\in\mathcal{Z}_{s}$. Now the ready messages for $y$ from the
set of parties $\mathcal{H}_{a}\cap(\mathcal{P}\setminus Z_{\alpha})$ are
eventually delivered to every honest party. Consequently, irrespective of
which stage of the protocol an honest party is in, every party in
$\mathcal{H}_{a}$ (including $P_{h}$) eventually sends a ready message for
$y$, which is eventually delivered. Since
$\mathcal{P}\setminus\mathcal{H}_{a}\in\mathcal{Z}_{s}$ (as every subset in
$\mathcal{Z}_{a}$ is a subset of some subset from $\mathcal{Z}_{s}$), this
implies that every honest party eventually terminates with output $y$.

From the privacy property of $\Pi_{\mathsf{ACS}}$, corresponding to every
honest $P_{j}\in\mathcal{CS}$, the input $x_{j}$ will be random from the point
of view of the adversary. Moreover, from the privacy property of
$\Pi_{\mathsf{PreProcessing}}$, the multiplication-triples generated through
$\Pi_{\mathsf{PreProcessing}}$ will be random from the point of view of the
adversary. During the evaluation of linear gates, no interaction happens among
the parties and hence, no additional information about the inputs of the
honest parties is revealed. The same is true during the evaluation of
multiplication-gates as well, which follows from the privacy property of
$\Pi_{\mathsf{Beaver}}$.

The communication complexity of the protocol follows from the communication
complexity of $\Pi_{\mathsf{PreProcessing}},\Pi_{\mathsf{ACS}}$ and
$\Pi_{\mathsf{Beaver}}$.