To $d$-share $s$, $\mathsf{D}$ picks a random degree-$d$ Shamir-sharing
polynomial $q(\cdot)$ with $q(0)=s$ and embeds it in a random degree-$(d,t)$
bivariate polynomial $F(x,y)$ at $y=0$. Thus the row and column-polynomials
have different degrees. This is in contrast to the earlier schemes where
$q(\cdot)$ has degree-$t$ and where $q(\cdot)$ is embedded at $x=0$ (instead
of $y=0$) in a random degree-$(t,t)$ bivariate polynomial. $\mathsf{D}$ then
distributes the row and column-polynomials and the parties publicly announce
the results of pair-wise consistency checks and build consistency-graphs.
$\mathsf{D}$ then proves that it has distributed consistent polynomials to
“sufficiently many” parties, derived from a single degree-$(d,t)$ bivariate
polynomial, say ${F}^{\star}(x,y)$ (where ${F}^{\star}(x,y)=F(x,y)$ for an
honest $\mathsf{D}$). This stage is different from
$\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ and constitutes the core of
$\mathsf{PCR\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$. In a more detail,
$\mathsf{D}$ publicly proves that it has delivered degree-$d$ row-polynomials
lying on ${F}^{\star}(x,y)$, to at least $n-t=3t+1$ parties $\mathcal{E}$ and
degree-$t$ column-polynomials lying on ${F}^{\star}(x,y)$, to at least
$n-t=3t+1$ parties $\mathcal{F}$ (the sets $\mathcal{E}$ and $\mathcal{F}$
need not be the same). Once the existence of $(\mathcal{E},\mathcal{F})$ is
confirmed (we will discuss in the sequel how such sets are identified),
$\mathsf{D}$’s sharing is completed by ensuring that every $P_{i}$ gets its
degree-$d$ column-polynomial $g_{i}(y)$. Party $P_{i}$ can then output
$g_{i}(0)$ (which is the same as ${F}^{\star}(\alpha_{i},0)$) as its share and
the value $s^{\star}={F}^{\star}(0,0)$ will be $d$-shared through
${F}^{\star}(x,0)$. If $P_{i}\in\mathcal{F}$ then it will already have its
$g_{i}(y)$ polynomial. For $P_{i}\not\in\mathcal{F}$, we observe that every
$P_{j}\in\mathcal{E}$ possesses a share on $g_{i}(y)$ in the form of a point
on $P_{j}$’s row-polynomial and which $P_{j}$ would have sent to $P_{i}$ as
part of pair-wise consistency test. Since there are at least $3t+1$ such
parties $P_{j}$ in $\mathcal{E}$ and since $g_{i}(y)$ has degree-$t$, party
$P_{i}$ can reconstruct $g_{i}(y)$ by using the OEC mechanism.

If $\mathsf{D}$ is honest, then $\mathsf{Adv}$ learns at most $t$ rows and
column-polynomials lying on $F(x,y)$. Now similar to Lemma 2.8, one can show
that the probability distribution of these polynomials will be independent of
$q(\cdot)=F(0,y)$. That is, for every candidate degree-$d$ polynomial
$q(\cdot)$, there exists some degree-$(d,t)$ bivariate polynomial, consistent
with the row and column-polynomials learnt by $\mathsf{Adv}$. Intuitively this
is because $(d+1)(t+1)$ distinct points are required to uniquely determine
$F(x,y)$, but $\mathsf{Adv}$ learns at most $t(d+1)+t$ distinct points on
$F(x,y)$ through the polynomials of corrupt parties, leaving $d+1-t$ “degree
of freedom” from the view-point of $\mathsf{Adv}$. This ensures the privacy of
$\mathsf{D}$’s input. We next discuss how the $(\mathcal{E},\mathcal{F})$ sets
are identified.

Dealer first finds a $\mathsf{star}$ $(\mathcal{C},\mathcal{D})$ in its
consistency-graph, proving that the row and column-polynomials of the honest
parties in $\mathcal{C}$ and $\mathcal{D}$ respectively lie on
${F}^{\star}(x,y)$. This follows from Lemma 2.7 and the fact that the
degree-$d$ row-polynomials and the degree-$t$ column-polynomials of honest
parties in $\mathcal{C}$ and $\mathcal{D}$ respectively are pair-wise
consistent, where $\mathcal{C}$ and $\mathcal{D}$ has $t+1$ and $n-2t=d+1$
honest parties respectively. To find $(\mathcal{E},\mathcal{F})$, the dealer
finds additional “supportive parties” whose row and column-polynomials also
lie on ${F}^{\star}(x,y)$. The idea is that for an honest $\mathsf{D}$, the
row and column-polynomials of all honest parties lie on $F(x,y)$ and there are
$n-t$ honest parties. To hunt for these additional supportive parties,
$\mathsf{D}$ follows the following two-stage non-intuitive approach.

  * $\bullet$

It first tries to “expand” ${\mathcal{D}}$ by identifying additional parties
whose degree-$t$ column-polynomials also lie on ${F}^{\star}(x,y)$. The
expanded set ${\mathcal{F}}$, includes all the parties having edges with at
least $2t+1$ parties from ${\mathcal{C}}$. Thus
$\mathcal{D}\subseteq\mathcal{F}$. It is easy to see that the column-
polynomial of every $P_{j}\in\mathcal{F}$ lies on ${F}^{\star}(x,y)$, as it
will be pair-wise consistent with the row-polynomials of at least $t+1$ honest
parties from $\mathcal{C}$, all of which lie on ${F}^{\star}(x,y)$.

  * $\bullet$

$\mathsf{D}$ then tries to “expand” ${\mathcal{C}}$ by searching for the
parties $P_{j}$, who have an edge with at least $d+t+1$ parties from
${\mathcal{F}}$. This will guarantee that $P_{j}$’s degree-$d$ row-polynomial
lies on ${F}^{\star}(x,y)$, as it will be pair-wise consistent with the
column-polynomials of at least $d+1$ honest parties from $\mathcal{F}$, all of
which lie on ${F}^{\star}(x,y)$. Such parties $P_{j}$ are included by
$\mathsf{D}$ in a set ${\mathcal{E}}$. Notice that the parties in
${\mathcal{C}}$ will satisfy the above condition and so
$\mathcal{C}\subseteq{\mathcal{E}}$.

Once $\mathsf{D}$ finds $(\mathcal{E},\mathcal{F})$, it broadcasts them and
then the parties verify whether indeed they satisfy the above conditions.
However there is a subtle issue, as an honest $\mathsf{D}$ may have to wait
indefinitely for the “expansion” of $\mathcal{D}$ and $\mathcal{C}$ sets,
beyond their initial cardinalities. For instance, let $n=4t+1$, $d=2t$ and let
$\mathcal{C}$ and $\mathcal{D}$ be of size $2t+1$ and $3t+1$ respectively,
containing $t$ corrupt parties. If the corrupt parties $P_{i}$ in
$\mathcal{C}$ choose to be inconsistent with the parties $P_{j}$ outside
$\mathcal{D}$ (by not broadcasting the $(\texttt{OK},i,j)$ messages), then the
honest parties $P_{j}$ outside $\mathcal{D}$ will have edges with only $t+1$
parties from $\mathcal{C}$ and will not be included in the set $\mathcal{F}$.
So $\mathcal{F}$ will remain the same as $\mathcal{D}$. Similarly, the corrupt
parties in $\mathcal{F}$ may choose to be inconsistent with the parties
outside $\mathcal{C}$, due to which $\mathcal{E}$ will remain the same as
$\mathcal{C}$. To deal with the above, Patra et al. [50] observed that if
$\mathsf{D}$ is honest then eventually the honest parties form a clique in the
consistency-graph. Moreover, if the star-finding algorithm is executed on
“this” instance of the consistency graph, then the $\mathcal{C}$ component of
the obtained $\mathsf{star}$ will have at least $2t+1$ honest parties. Now if
$\mathcal{C}$ contains at least $2t+1$ honest parties, then eventually
$\mathcal{D}$ will expand to $\mathcal{F}$, which will contain all $n-t$
honest parties and eventually $\mathcal{C}$ will expand to $\mathcal{E}$
containing $n-t=3t+1$ parties. This crucial observation is at the heart of
$\mathsf{PCR\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$. However, it is difficult for
$\mathsf{D}$ to identify an instance of its dynamic consistency-graph that
contains a clique involving at least $n-t$ honest parties. The way-out is to
repeatedly run the star-finding algorithm and try the expansion of every
instance of $\mathsf{star}$ $(\mathcal{C},\mathcal{D})$ obtained in the
consistency-graph.

Sharing Phase: Protocol $\mathsf{PCR\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$
$\bullet$ Stage I : Distributing Polynomials — same steps as
$\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ except that the Shamir-sharing
polynomial $q(\cdot)$ is of degree-$d$, the bivariate polynomial $F(x,y)$ is
of degree-$(d,t)$ and $F(x,0)=q(\cdot)$. $\bullet$ Stage II : Pair-wise
consistency checks and building consistency-graph — same as
$\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$. $\bullet$ Stage III : Finding
$(\mathcal{E},\mathcal{F})$ in the consistency-graph — the dealer $\mathsf{D}$
does the following – After every update in $G_{D}$, run the star-finding
algorithm to check for the presence of a $\mathsf{star}$. Let there are
$\alpha$ number of distinct $\mathsf{star}$s that are found till now in
$G_{D}$, where $\alpha\geq 0$.  – If a new $\mathsf{star}$
$(\mathcal{C}_{\alpha+1},{\mathcal{D}}_{\alpha+1})$ is found in $G_{D}$, then
do the following: 1. Add $P_{j}$ to a set ${\mathcal{F}}_{\alpha+1}$ if
$P_{j}$ has an edge with at least $2t+1$ parties from
${\mathcal{C}}_{\alpha+1}$ in $G_{D}$. 2. Add $P_{j}$ to a set
${\mathcal{E}}_{\alpha+1}$ if $P_{j}$ has an edge with at least $d+t+1$
parties from ${\mathcal{F}}_{\alpha+1}$ in $G_{D}$. 3. For
$\beta=1,\ldots,\alpha$, update the existing ${\mathcal{F}}_{\beta}$ and
${\mathcal{E}}_{\beta}$ sets as follows:  $\bullet$ Add $P_{j}$ to
${\mathcal{F}}_{\beta}$, if $P_{j}\not\in{\mathcal{F}}_{\beta}$ and $P_{j}$
has an edge with at least $2t+1$ parties from ${\mathcal{C}}_{\beta}$ in
$G_{D}$. $\bullet$ Add $P_{j}$ to ${\mathcal{E}}_{\beta}$, if
$P_{j}\not\in{\mathcal{E}}_{\beta}$ and $P_{j}$ has an edge with at least
$d+t+1$ parties from ${\mathcal{F}}_{\beta}$ in $G_{D}$. – If no new
$\mathsf{star}$ is obtained, then update the existing sets
${\mathcal{F}}_{\beta},{\mathcal{E}}_{\beta}$ by executing the step $3$ as
above. – Let $({\mathcal{E}}_{\gamma},{\mathcal{F}}_{\gamma})$ be the first
pair among the generated pairs $({\mathcal{E}}_{\beta},{\mathcal{F}}_{\beta})$
such that $|{\mathcal{E}}_{\gamma}|\geq 3t+1$ and
$|{\mathcal{F}}_{\gamma}|\geq 3t+1$. Then broadcast
$(({\mathcal{C}}_{\gamma},{\mathcal{D}}_{\gamma}),({\mathcal{E}}_{\gamma},{\mathcal{F}}_{\gamma}))$.
$\bullet$ Stage IV : share computation — each party $P_{i}$ does the following
– If
$(({\mathcal{C}}_{\gamma},{\mathcal{D}}_{\gamma}),({\mathcal{E}}_{\gamma},{\mathcal{F}}_{\gamma}))$
is received from the broadcast of $\mathsf{D}$, accept it if all the following
hold.  – $|{\mathcal{E}}_{\gamma}|\geq 3t+1$ and $|{\mathcal{F}}_{\gamma}|\geq
3t+1$ and $({\mathcal{C}}_{\gamma},{\mathcal{D}}_{\gamma})$ is a
$\mathsf{star}$ in the consistency-graph $G_{i}$. – Every party
$P_{j}\in{\mathcal{F}}_{\gamma}$ has an edge with at least $2t+1$ parties from
${\mathcal{C}}_{\gamma}$ in $G_{i}$. – Every party
$P_{j}\in{\mathcal{E}}_{\gamma}$ has an edge with at least $d+t+1$ parties
from ${\mathcal{F}}_{\gamma}$ in $G_{i}$. – If
$(({\mathcal{C}}_{\gamma},{\mathcal{D}}_{\gamma}),({\mathcal{E}}_{\gamma},{\mathcal{F}}_{\gamma}))$
is accepted, then compute the share $s_{i}$ as follows and terminate.  – If
$P_{i}\in\mathcal{F}_{\gamma}$, then set $s_{i}=g_{i}(0)$, where $g_{i}(y)$ is
the degree-$t$ column-polynomial received from $\mathsf{D}$. – Else initialize
$W_{i}$ to $\emptyset$. Upon receiving $f_{ji}$ from $P_{j}\in\mathcal{E}$,
include $f_{ji}$ to $W_{i}$. Keep updating $W_{i}$ and keep executing
$\mathsf{OEC}(W_{i},t)$ till a degree-$t$ polynomial $g_{i}(y)$ is obtained.
Then set $s_{i}=g_{i}(0)$.
Reconstruction Phase: Protocol
$\mathsf{PCR\mbox{-}AVSS}\mbox{-}{\mathsf{Rec}}$ Same steps as
$\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Rec}}$, except that the parties now
run $\mathsf{OEC}(\star,d)$ to recover a degree-$d$ polynomial.

Figure 14: The perfectly-secure AVSS scheme of Patra, Choudhury and Rangan
[50].

###  6.3 $\mathsf{CHP\mbox{-}AVSS}$ Scheme

Protocol $\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ requires a
communication of $\mathcal{O}(n^{2}\log{|\mathbb{F}|})$ bits over the pair-
wise channels, apart from the broadcast of $\Theta(n^{2})$ OK messages and the
broadcast of $\mathsf{star}$. The protocol generates $t$-sharing of a single
secret. If $\mathsf{D}$ wants to $t$-share $L$ secrets, then it can invoke $L$
instances of $\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$. This makes the
broadcast-complexity (namely the number of bits to be broadcast) proportional
to $L$. Instead Choudhury, Hirt and Patra [21] proposed a modification of
888It is easy to see that the communication complexity of
$\mathsf{PCR\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ is the same as
$\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$.
$\mathsf{PCR\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$, which allows $\mathsf{D}$ to
$t$-share $L$ secrets for any given $L\geq n-3t$, without incurring any
additional communication complexity. The broadcast-complexity of
$\mathsf{CHP\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ will be independent of $L$,
which is a significant saving. This is because each instance of the broadcast
in the asynchronous setting needs to be emulated by running the costly
Bracha’s ACast protocol.

We explain the idea of $\mathsf{CHP\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$
assuming $L=n-3t$. If $L>n-3t$, then $\mathsf{D}$ can divide its inputs into
multiple batches of $n-3t$ and invoke an instance of
$\mathsf{CHP\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ for each batch. Recall that in
$\mathsf{PCR\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$, if $\mathsf{D}$ is honest,
then the adversary’s view leaves $d+1-t$ “degree of freedom” in the
degree-$(d,t)$ bivariate polynomial $F(x,y)$, where $t<d<n-2t$. If we consider
the maximum value $d_{max}$ of $d$ which is $n-2t-1$, this implies $n-3t$
degree of freedom. While $\mathsf{PCR\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ uses
this degree of freedom for generating a $d_{max}$-sharing of a single secret
by embedding a single degree-$d_{max}$ sharing-polynomial in $F(x,y)$,
$\mathsf{CHP\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ uses it for $t$-sharing of
$n-3t$ values by embedding $n-3t$ degree-$t$ Shamir-sharing polynomials in
$F(x,y)$.

In a more detail, given $s^{(1)},\ldots,s^{(n-3t)}$ for $t$-sharing,
$\mathsf{D}$ picks $n-3t$ random degree-$t$ Shamir-sharing polynomials
$q^{(1)}(\cdot),\ldots,q^{(n-3t)}(\cdot)$, where $q^{(k)}(0)=s^{(k)}$. These
polynomials are embedded in a degree-$(d_{max},t)$ bivariate polynomial, which
is otherwise a random polynomial, except that $F(\beta_{k},y)=q^{(k)}(\cdot)$
holds. Here $\beta_{1},\ldots,\beta_{n-3t}$ are distinct, publicly-known non-
zero elements from $\mathbb{F}$, different from the evaluation-points
$\alpha_{1},\ldots,\alpha_{n}$ (this requires $|\mathbb{F}|>2n-3t$). Notice
that the embedding and the degree of the sharing-polynomials are different in
$\mathsf{PCR\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ and
$\mathsf{CHP\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$. Accordingly, the shares of
the parties are different (see Fig 15). The shares of $P_{i}$ in
$\mathsf{CHP\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ will be
$\\{F(\beta_{k},\alpha_{i})\\}_{k\in\\{1,\ldots,n-3t\\}}$. And to compute
them, $P_{i}$ should get its row-polynomial $f_{i}(x)=F(x,\alpha_{i})$, as
$P_{i}$ can then compute its shares by evaluating $f_{i}(x)$ at
$x=\beta_{1},\ldots,\beta_{n-3t}$.

$[s]_{d_{max}},s=q(0)$$[s^{(1)}]_{t}$$[s^{(L)}]_{t}$$f_{i}(x)$$\Rightarrow$$q(\cdot)$$\Rightarrow$$g_{j}(y)$$\Downarrow$$q^{(1)}(\cdot)$$\Downarrow$$q^{(L)}(\cdot)$$\Downarrow$$s^{(1)}=q^{(1)}(0)$$s^{(L)}=q^{(L)}(0)$$F(\alpha_{1},\alpha_{1})$$\ldots$$F(\alpha_{j},\alpha_{1})$$\ldots$$F(\alpha_{n},\alpha_{1})$
. . . . . . . . . . . . . . .
$F(\alpha_{1},\alpha_{i})$$\ldots$$F(\alpha_{j},\alpha_{i})$$\ldots$$F(\alpha_{n},\alpha_{i})$
. . . . . . . . . . . . . . .
$F(\alpha_{1},\alpha_{n})$$\ldots$$F(\alpha_{j},\alpha_{n})$$\ldots$$F(\alpha_{n},\alpha_{n})$$\Downarrow$$\ldots$$\Downarrow$$\ldots$$\Downarrow$$g_{1}(0)$$\ldots$$g_{j}(0)$$\ldots$$g_{n}(0)$$\Rightarrow$
. . . $\Rightarrow$ . . . $\Rightarrow$$f_{1}(\beta_{1})=q^{(1)}(\alpha_{1})$
. . . $f_{i}(\beta_{1})=q^{(1)}(\alpha_{i})$ . . .
$f_{n}(\beta_{1})=q^{(1)}(\alpha_{n})$$\ldots$ . . . $\ldots$ . . .
$\ldots$$f_{1}(\beta_{L})=q^{(L)}(\alpha_{1})$ . . .
$f_{i}(\beta_{L})=q^{(L)}(\alpha_{i})$ . . .
$f_{n}(\beta_{L})=q^{(L)}(\alpha_{n})$ Figure 15: Values distributed by
$\mathsf{D}$ in $\mathsf{PCR\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ and
$\mathsf{CHP\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ on degree-$(d_{max},t)$
polynomial $F(x,y)$, where $d_{max}=n-2t-1$. In
$\mathsf{PCR\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$, $s$ is $d_{max}$-shared
through $F(x,0)$ (shown in red color), while in
$\mathsf{CHP\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$, $s^{(1)},\ldots,s^{(L)}$ are
$t$-shared through $F(\beta_{1},y),\ldots,F(\beta_{L},y)$ (shown in blue
color), where $L=n-3t$.

To achieve the above goal, we observe that if $\mathsf{D}$ invokes
$\mathsf{PCR\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ (with the above modifications)
and if the protocol terminates, then it ensures that $\mathsf{D}$ has
“committed” a degree-$(d_{max},t)$ bivariate polynomial ${F}^{\star}(x,y)$,
such that each (honest) party $P_{j}$ possesses its column-polynomial
$g_{j}(y)={F}^{\star}(\alpha_{j},y)$. We also observe that for each row-
polynomial $f_{i}(x)={F}^{\star}(x,\alpha_{i})$, every $P_{j}$ holds a share
${F}^{\star}(\alpha_{j},\alpha_{i})$ in the form of $g_{j}(\alpha_{i})$.
Moreover, the degree of $f_{i}(x)$ is $d_{max}=n-2t-1$. Hence, if every party
$P_{j}$ sends its share $g_{j}(\alpha_{i})$ of $f_{i}(x)$ to $P_{i}$, then
$P_{i}$ can reconstruct its desired row-polynomial $f_{i}(x)$ by applying OEC
on the received values. Hence the values
$\vec{S}^{\prime}=({F}^{\star}(\beta_{1},0),\ldots,{F}^{\star}(\beta_{n-3t},0))$
will be $t$-shared, where $\vec{S}^{\prime}=(s^{(1)},\ldots,s^{(n-3t)})$ for
an honest $\mathsf{D}$.

Part III : Hybrid Communication Setting

##  7 Preliminaries and Definitions for Hybrid Communication Setting

Even though the asynchronous model is practically more relevant compared to
the synchronous setting, there are some inherent downsides in general with
asynchronous protocols. Synchronous protocols offer better resilience,
compared to asynchronous protocols (for instance $t<n/4$ for AVSS compared to
$t<n/3$ for VSS). Additionally, asynchronous protocols are more complex. An
inherent drawback of asynchronous MPC (AMPC) protocols is the lack of input-
provision from all honest parties; i.e. inputs of up to $t$ honest parties may
not be considered for the computation [7]. To get rid of these drawbacks,
several forms of “synchronization” have been considered in the literature
([27, 9, 35, 45, 2, 51]). One of these is the hybrid communication setting [7,
9, 50, 51, 20, 19], which is a “mix” of synchronous and asynchronous setting.
Namely, the first $R$ rounds are assumed to be synchronous, after which the
network behaves asynchronously. There are several practical advantages of the
hybrid setting compared to a completely asynchronous setting. For instance,
one can guarantee input-provision in MPC protocols. Moreover, one can design
protocols with the same resilience, as synchronous protocols, without letting
the network to be synchronous for the entire duration of the protocol. Also,
it is theoretically interesting to study the trade-off between network
synchrony and resilience, round and communication-complexity of various
distributed-computing tasks. In the context of VSS, Patra and Ravi [51] have
shown that one can design a Type-II perfectly-secure AVSS satisfying
Definition 5.1 with $t<n/3$ in the hybrid setting (which otherwise would
require $t<n/4$ in a completely asynchronous setting), where $R=1$. Notice
that the protocol has optimal resilience as well as it requires the optimal
number of synchronous rounds.

We next define weak polynomial sharing (WPS), which is used in [51]. The
primitive allows a dealer $\mathsf{D}$ to distribute shares of a degree-$t$
polynomial held by $\mathsf{D}$. If $\mathsf{D}$ is honest, then every honest
party should eventually terminate with its share. Moreover, even if
$\mathsf{D}$ is corrupt and some honest party terminates $\mathsf{Sh}$, then
it is ensured that $\mathsf{D}$ has distributed shares of some degree-$t$
polynomial to at least $t+1$ honest parties. Property-wise, WPS is a weaker
primitive than WSS, as it has only a sharing phase and may not allow even a
“weak reconstruction” of $\mathsf{D}$’s shared polynomial.

######  Definition 7.1 (Weak Polynomial Sharing (WPS) [51]).

Let $\mathsf{Sh}$ be protocol for the $n$ parties in the hybrid setting, where
a designated dealer $\mathsf{D}\in\mathcal{P}$ has a degree-$t$ polynomial
$f(x)$ over $\mathbb{F}$ as input for $\mathsf{Sh}$. Then $\mathsf{Sh}$
constitutes a perfectly-secure WPS, if all the following hold.

  * $\bullet$

Termination and Privacy: Same as AVSS.

  * $\bullet$

Correctness: If some honest party terminates $\mathsf{Sh}$, then there exists
a degree-$t$ weakly committed polynomial ${f}^{\star}(x)$ over $\mathbb{F}$
such that.

    * –

If $\mathsf{D}$ is honest, then ${f}^{\star}(x)=f(x)$ and each honest $P_{i}$
outputs $f(\alpha_{i})$ at the end of $\mathsf{Sh}$.

    * –

If $\mathsf{D}$ is corrupt, then every honest $P_{i}$ outputs either
${f}^{\star}(\alpha_{i})$ or some default value $\perp$, with at least $t+1$
honest parties outputting ${f}^{\star}(\alpha_{i})$.

##  8 Hybrid AVSS Protocol with $t<n/3$

In the AVSS schemes, the parties not receiving their shares from $\mathsf{D}$,
deploy OEC to recompute their shares from the sub-shares received from the
parties, who have received their shares from $\mathsf{D}$. This inherently
requires $n>4t$. On contrary, the hybrid AVSS of Patra et al. [51] is designed
with $n>3t$. The presence of a synchronous round at the beginning simplifies
certain aspects of verifiability and completely avoids the need for OEC. We
first start with the WPS construction of [51], which is similar to the
$\mathsf{3KKK\mbox{-}WSS}\mbox{-}{\mathsf{Sh}}$ protocol. The dealer embeds
its degree-$t$ polynomial in a random symmetric degree-$(t,t)$ bivariate
polynomial and distributes its row-polynomials. In parallel, the parties pair-
wise exchange random pads. Since the pads are exchanged during the synchronous
round, each $P_{i}$ receives the pad selected for it by every other party, at
the end of the synchronous round. The sent and received pads are also
“registered” with $\mathsf{D}$ for the comparison purpose. Based on this,
$\mathsf{D}$ sends to $P_{i}$ its list of conflicting-parties
$\mathcal{C}_{i}$, who did not concur on the pads. Based on $\mathcal{C}_{i}$,
party $P_{i}$ broadcasts its common values in a masked fashion for the parties
who are not in $\mathcal{C}_{i}$ and in an unmasked fashion for the parties
who are in $\mathcal{C}_{i}$. The dealer then checks whether $P_{i}$’s public
values are consistent with the bivariate polynomial and the pads registered
with $\mathsf{D}$ and accordingly includes $P_{i}$ to a set $\mathcal{W}$.
Once $\mathcal{W}$ achieves the size of $2t+1$ (which eventually happens for
an honest $\mathsf{D}$), $\mathsf{D}$ broadcasts $\mathcal{W}$. It is then
publicly verified that no pair of parties in $\mathcal{W}$ publicly conflicts
over their supposedly common values that are either in padded or in clear
form.

If $\mathcal{W}$ is successfully verified, then the row-polynomials of the
(honest) parties in $\mathcal{W}$ lie on a single degree-$(t,t)$ symmetric
bivariate polynomial ${F}^{\star}(x,y)$. While every $P_{i}\in\mathcal{W}$ can
output the constant term of its row-polynomial as its share, any
$P_{i}\not\in\mathcal{W}$ tries to compute its row-polynomial by interpolating
the common values with the parties in $\mathcal{W}$. If $P_{i}$ has a conflict
with any party in $\mathcal{W}$, then the common value is publicly available.
Else, it subtracts the pad it sent to that party in the synchronous round from
the padded value available publicly. If the interpolation does not give a
degree-$t$ polynomial (which can happen only for a corrupt $\mathsf{D}$), then
$P_{i}$ outputs $\bot$.  Synchronous Phase $\bullet$ Sending polynomials and
exchanging random pads: – $\mathsf{D}$ with input $f(\cdot)$ chooses a random
symmetric degree-$(t,t)$ bivariate $F(x,y)$ such that $F(0,y)=f(\cdot)$ and
sends $f_{i}(x)=F(x,\alpha_{i})$ to each party $P_{i}\in\mathcal{P}$ – Each
party $P_{i}\in\mathcal{P}$ picks a random pad $r_{ij}$ for every
$P_{j}\in\mathcal{P}$ and sends $r_{ij}$ to $P_{j}$. – Each $P_{i}$ sends
$\\{r_{ij}\\}_{P_{j}\in\mathcal{P}}$ to $\mathsf{D}$. Let
$\\{r^{(1)}_{ij}\\}_{P_{j}\in\mathcal{P}}$ be the list of sent-pads received
by $\mathsf{D}$ from $P_{i}$.
Asynchronous Phase $\bullet$ Verifying masks: – Each $P_{i}$ sends the pads
$\\{r^{\prime}_{ji}\\}_{P_{j}\in\mathcal{P}}$ received from various parties to
$\mathsf{D}$. Let $\\{r_{ji}^{(2)}\\}_{P_{j}\in\mathcal{P}}$ be the list of
received-pads which $\mathsf{D}$ receives from $P_{i}$. – Upon receiving
$\\{r_{ji}^{(2)}\\}_{P_{j}\in\mathcal{P}}$ from $P_{i}$, dealer $\mathsf{D}$
sends to $P_{i}$ a set $\mathcal{C}_{i}=\\{P_{j}:r_{ji}^{(2)}\neq
r_{ji}^{(1)}\\}$. $\bullet$ Broadcasting masked/unmasked common values — each
party $P_{i}$: Broadcasts $(\mathcal{A}_{i},\mathcal{B}_{i},\mathcal{C}_{i})$,
where:  –
$\mathcal{A}_{i}=\\{a_{ij}=f_{i}(\alpha_{j})+r_{ij}\\}_{P_{j}\in\mathcal{P}}$.
– $\mathcal{B}_{i}=\\{b_{ij}\\}_{P_{j}\in\mathcal{P}}$, where
$b_{ij}=f_{i}(\alpha_{j})$ if $P_{j}\in\mathcal{C}_{i}$ and
$b_{ij}=f_{i}(\alpha_{j})+r^{\prime}_{ji}$ otherwise. $\bullet$ Constructing
and broadcasting $\mathcal{W}$ — Dealer $\mathsf{D}$ does the following:  –
Upon receiving $(\mathcal{A}_{i},\mathcal{B}_{i},\mathcal{C}_{i})$ from
$P_{i}$, mark $P_{i}$ as correct and include in $\mathcal{W}$, if all the
following holds. – $a_{ij}-r^{(1)}_{ij}=F(\alpha_{j},\alpha_{i})$ –
$b_{ij}=F(\alpha_{j},\alpha_{i})$ for all $P_{j}\in\mathcal{C}_{i}$ and
$b_{ij}-r^{(2)}_{ji}=F(\alpha_{j},\alpha_{i})$ otherwise – $\mathcal{C}_{i}$
is the same set sent by $\mathsf{D}$ to $P_{i}$. – Wait until
$|\mathcal{W}|\geq 2t+1$ and then broadcast $\mathcal{W}$. $\bullet$ Verifying
$\mathcal{W}$ — each party $P_{i}$: Accept $\mathcal{W}$ received from the
broadcast of $\mathsf{D}$ if all the following hold.  – $|\mathcal{W}|\geq
2t+1$ and $(\mathcal{A}_{j},\mathcal{B}_{j},\mathcal{C}_{j})$ is received from
the broadcast of each $P_{j}\in\mathcal{W}$. – Every
$P_{j},P_{k}\in\mathcal{W}$ are pair-wise consistent, as per the following
conditions.  – if $P_{j}\in\mathcal{C}_{k}$ and $P_{k}\in\mathcal{C}_{j}$ then
$b_{jk}=b_{kj}$ – if $P_{j}\in\mathcal{C}_{k}$ and
$P_{k}\not\in\mathcal{C}_{j}$ then $a_{kj}=b_{jk}$ – if
$P_{j}\not\in\mathcal{C}_{k}$ and $P_{k}\in\mathcal{C}_{j}$ then
$a_{jk}=b_{kj}$ – Else $a_{jk}=b_{kj}$ and $a_{kj}=b_{jk}$ $\bullet$ Output
stage — each party $P_{i}$: If $\mathcal{W}$ is accepted, then terminate with
output $s_{i}$, computed as follows.  – If $P_{i}\in\mathcal{W}$ then set
$s_{i}=f_{i}(0)$. – Else interpolate the points
$\\{(\alpha_{j},s_{ij})\\}_{P_{j}\in\mathcal{W}}$ where $s_{ij}=b_{ji}$ if
$P_{i}\in\mathcal{C}_{j}$ and $s_{ij}=b_{ji}-r_{ij}$ otherwise. If the
interpolation outputs a degree-$t$ polynomial $f_{i}(x)$ then set
$s_{i}=f_{i}(0)$, else set $s_{i}=\bot$.

Figure 16: WPS protocol of Patra and Ravi [51].

##### From WPS to VSS

$\mathsf{WPS}$ fails to serve as a VSS because if $\mathsf{D}$ is corrupt,
then the parties outside $\mathcal{W}$ may output $\bot$. Protocol
$\mathsf{PR}\mbox{-}{\mathsf{Sh}}$ fixes this shortcoming. The protocol has
two “layers” of communication. The first layer is similar to $\mathsf{WPS}$
and identifies a set $\mathcal{V}$ of $2t+1$ parties whose row-polynomials lie
on a single degree-$(t,t)$ symmetric bivariate polynomial ${F}^{\star}(x,y)$.
The second layer enables the parties outside $\mathcal{V}$ to obtain their
row-polynomials lying on ${F}^{\star}(x,y)$. In a more detail, every $P_{j}$
picks a random blinding-polynomial $r_{j}(\cdot)$ and shares it by invoking an
instance $\mathsf{WPS}_{j}$ of $\mathsf{WPS}$. Additionally, it makes public
the polynomial $r_{j}(\cdot)+f_{j}(x)$. The idea is that if later $P_{j}$ is a
part of $\mathcal{V}$, then any $P_{i}\not\in\mathcal{V}$ can compute the
point $f_{j}(\alpha_{i})$ (which is the same as $f_{i}(\alpha_{j})$) on
$P_{i}$’s row-polynomial, if $P_{i}$ obtains the output $r_{j}(\alpha_{i})$
during $\mathsf{WPS}_{j}$. While an honest $P_{j}\in\mathcal{V}$ makes public
the correct $r_{j}(\cdot)+f_{j}(x)$, care has to be taken to ensure that even
a corrupt $P_{j}\in\mathcal{V}$ has made public the correct polynomial. This
is done as follows. First, each $P_{k}$ participates conditionally during
$\mathsf{WPS}_{j}$ only if the blinded polynomial of $P_{k}$ is consistent
with respect to its received point on $r_{k}(\cdot)$ during $\mathsf{WPS}_{k}$
and the supposedly common value $f_{k}(j)$. Second, $P_{j}$ is included in
$\mathcal{V}$ only when during $\mathsf{WPS}_{j}$ the generated $\mathcal{W}$
set $\mathcal{W}_{j}$ is accepted and which has an overlap of $2t+1$ with
$\mathcal{V}$.

For a corrupt $P_{j}\in\mathcal{V}$, an honest $P_{i}\not\in\mathcal{V}$ may
end up obtaining $\bot$ during $\mathsf{WPS}_{j}$. However there will be at
least $t+1$ honest $P_{j}\in\mathcal{V}$, corresponding to whom $P_{i}$
eventually obtains $r_{j}(\alpha_{i})$ during $\mathsf{WPS}_{j}$, using which
$P_{i}$ obtains $t+1$ points on $f_{i}(x)$, which are sufficient to compute
$f_{i}(x)$.  Synchronous Phase $\mathsf{D}$ and parties execute the same steps
as in the synchronous phase of $\mathsf{WPS}$. Additionally, each $P_{i}$
picks a random degree-$t$ blinding-polynomial $r_{i}(\cdot)$ and as a dealer
invokes an instance $\mathsf{WPS}_{i}$ of $\mathsf{WPS}$ to share
$r_{i}(\cdot)$. Moreover, $P_{i}$ also participates in the synchronous phase
of the instance $\mathsf{WPS}_{j}$ for every $P_{j}\in\mathcal{P}$.
Asynchronous Phase $\bullet$ Verifying masks: Parties and $\mathsf{D}$ execute
the same steps as in $\mathsf{WPS}$. $\bullet$ Broadcasting values — each
party $P_{i}$: Broadcast
$(\mathcal{A}_{i},\mathcal{B}_{i},\mathcal{C}_{i},d_{i}(x))$, where
$\mathcal{A}_{i},\mathcal{B}_{i},\mathcal{C}_{i}$ are same as in
$\mathsf{WPS}$ and $d_{i}(x)=r_{i}(\cdot)+f_{i}(x)$. $\bullet$ Participating
in $\mathsf{WPS}$ instances — each party $P_{i}$: For $j=1,\ldots,n$,
participate in $\mathsf{WPS}_{j}$ if a degree-$t$ polynomial $d_{j}(x)$ is
received from the broadcast of $P_{j}$ and if
$d_{j}(\alpha_{i})=r_{j}(\alpha_{i})+f_{i}(\alpha_{j})$ holds. $\bullet$
Computing and Broadcasting $\mathcal{V}$ — the $\mathsf{D}$: compute and
broadcast $(\mathcal{V},\\{\mathcal{W}_{i}\\}_{P_{i}\in\mathcal{V}})$, such
that:  – Every $P_{i}\in\mathcal{V}$ is marked as correct (by satisfying the
same conditions as in $\mathsf{WPS}$). – For every $P_{i}\in\mathcal{V}$, the
set $\mathcal{W}_{i}$ is accepted during the instance $\mathsf{WPS}_{i}$. –
$|\mathcal{V}|\geq 2t+1$ and $|\mathcal{V}\cap\mathcal{W}_{i}|\geq 2t+1$ for
every $P_{i}\in\mathcal{V}$. $\bullet$ Verifying $\mathcal{V}$ — each party
$P_{i}$: Accept $(\mathcal{V},\\{\mathcal{W}_{i}\\}_{P_{i}\in\mathcal{V}})$
received from the broadcast of $\mathsf{D}$, if:  – Every
$P_{j},P_{k}\in\mathcal{V}$ are pair-wise consistent (using the same criteria
as in $\mathsf{WPS}$). – For all $P_{j}\in\mathcal{V}$, the set
$\mathcal{W}_{j}$ is accepted during the instance $\mathsf{WPS}_{j}$. –
$|\mathcal{V}|\geq 2t+1$ and for every $P_{j}\in\mathcal{V}$, the condition
$|\mathcal{V}\cap\mathcal{W}_{j}|\geq 2t+1$ holds. $\bullet$ Output stage —
each party $P_{i}$: If
$(\mathcal{V},\\{\mathcal{W}_{i}\\}_{P_{i}\in\mathcal{V}})$ is accepted then
terminate with output $s_{i}$, where:  $\bullet$ If $P_{i}\in\mathcal{V}$ then
set $s_{i}=f_{i}(0)$. $\bullet$ Else compute the output $r_{ji}$ in
$\mathsf{WPS}_{j}$ for every $P_{j}\in\mathcal{V}$, interpolate degree-$t$
polynomial $f_{i}(x)$ through the points
$\\{(\alpha_{i},s_{ij}=d_{j}(\alpha_{i})-r_{ji})\\}_{P_{j}\in\mathcal{V}\wedge
r_{ji}\neq\bot}$ and set $s_{i}=f_{i}(0)$.

Figure 17: The hybrid AVSS protocol of Patra and Ravi [51].

##  9 Open Problems

We identify the following open problems in the domain of perfectly-secure VSS.

  * $\bullet$

The communication complexity of existing efficient VSS schemes with a
$3$-round sharing phase is $n$ times more compared to the VSS schemes which
allow four or more rounds in the sharing phase (see Table 1). It is
interesting to see if one can close this gap.

  * $\bullet$

We are unaware of any non-trivial lower bound on the communication complexity
of perfectly-secure VSS schemes. One could explore deriving any non-trivial
lower bound.

  * $\bullet$

The broadcast complexity (namely the number of bits broadcasted) of all VSS
schemes with $n>3t$ is proportional to the number of values $L$ shared by the
scheme (namely $\mathcal{O}(L\cdot n^{3}\log{|\mathbb{F}|})$ bits). This is
unlike the AVSS scheme of Patra et al. [21], where the broadcast complexity is
$\mathcal{O}(n^{2}\log n)$ for sharing $L$ values. Given that each instance of
broadcast needs to be emulated by running a costly reliable broadcast (RB)
protocol, it is interesting to see if one can design a VSS scheme with $n>3t$
where the broadcast complexity is independent of $L$.

  * $\bullet$

The $\mathsf{3AKP\mbox{-}VSS}$ VSS scheme [3] uses the broadcast channel
during two rounds, while the optimal usage is one round. One could explore to
achieve the same properties as the $\mathsf{3AKP\mbox{-}VSS}$ scheme, with the
broadcast channel being used only during one round.

## References

  * [1] I. Abraham, D. Dolev, and G. Stern.  Revisiting Asynchronous Fault Tolerant Computation with Optimal Resilience.  In PODC, pages 139–148. ACM, 2020.
  * [2] I. Abraham, D. Malkhi, K. Nayak, L. Ren, and M. Yin.  Sync HotStuff: Simple and Practical Synchronous State Machine Replication.  In IEEE Symposium on Security and Privacy, pages 106–118. IEEE, 2020.
  * [3] B. Applebaum, E. Kachlon, and A. Patra.  The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency.  In FOCS, pages 1277–1284. IEEE, 2020.
  * [4] G. Asharov and Y. Lindell.  A Full Proof of the BGW Protocol for Perfectly Secure Multiparty Computation.  J. Cryptology, 30(1):58–151, 2017.
  * [5] M. Backes, A. Kate, and A. Patra.  Computational Verifiable Secret Sharing Revisited.  In ASIACRYPT, volume 7073 of Lecture Notes in Computer Science, pages 590–609. Springer, 2011.
  * [6] L. Bangalore, A. Choudhury, and G. Garimella.  Round Efficient Computationally Secure Multi-Party Computation Revisited.  In ICDCN, pages 292–301. ACM, 2019.
  * [7] Z. Beerliová-Trubíniová and M. Hirt.  Simple and Efficient Perfectly-Secure Asynchronous MPC.  In ASIACRYPT, volume 4833 of Lecture Notes in Computer Science, pages 376–392. Springer, 2007.
  * [8] Z. Beerliová-Trubíniová and M. Hirt.  Perfectly-Secure MPC with Linear Communication Complexity.  In TCC, volume 4948 of Lecture Notes in Computer Science, pages 213–230. Springer, 2008.
  * [9] Z. Beerliová-Trubíniová, M. Hirt, and J. B. Nielsen.  On the Theoretical Gap Between Synchronous and Asynchronous MPC Protocols.  In PODC, pages 211–218. ACM, 2010.
  * [10] A. Beimel.  Secret-Sharing Schemes: A Survey.  In IWCC, volume 6639 of Lecture Notes in Computer Science, pages 11–46. Springer, 2011.
  * [11] M. Ben-Or, R. Canetti, and O. Goldreich.  Asynchronous Secure Computation.  In STOC, pages 52–61. ACM, 1993.
  * [12] M. Ben-Or, S. Goldwasser, and A. Wigderson.  Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract).  In STOC, pages 1–10. ACM, 1988.
  * [13] M. Ben-Or, B. Kelmer, and T. Rabin.  Asynchronous Secure Computations with Optimal Resilience (Extended Abstract).  In PODC, pages 183–192. ACM, 1994.
  * [14] G. R. Blakley.  Safeguarding Cryptographic Keys.  In AFIPS National Computer Conference, pages 313–317. IEEE, 1979\.
  * [15] G. Bracha.  An Asynchronous [(n-1)/3]-Resilient Consensus Protocol.  In PODC, pages 154–162. ACM, 1984.
  * [16] R. Canetti.  Studies in Secure Multiparty Computation and Applications.  PhD thesis, Weizmann Institute, Israel, 1995.
  * [17] R. Canetti.  Universally Composable Security.  J. ACM, 67(5):28:1–28:94, 2020.
  * [18] B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch.  Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults (Extended Abstract).  In FOCS, pages 383–395. IEEE Computer Society, 1985.
  * [19] A. Choudhury.  Brief Announcement: Almost-surely Terminating Asynchronous Byzantine Agreement Protocols with a Constant Expected Running Time.  In PODC, pages 169–171. ACM, 2020.
  * [20] A. Choudhury and A. Hegde.  High Throughput Secure MPC over Small Population in Hybrid Networks (Extended Abstract).  In INDOCRYPT, volume 12578 of Lecture Notes in Computer Science, pages 832–855. Springer, 2020.
  * [21] A. Choudhury, M. Hirt, and A. Patra.  Asynchronous Multiparty Computation with Linear Communication Complexity.  In DISC, volume 8205 of Lecture Notes in Computer Science, pages 388–402. Springer, 2013.
  * [22] A. Choudhury, K. Kurosawa, and A. Patra.  The Round Complexity of Perfectly Secure General VSS.  In ICITS, volume 6673 of Lecture Notes in Computer Science, pages 143–162. Springer, 2011.
  * [23] A. Choudhury and N. Pappu.  Perfectly-Secure Asynchronous MPC for General Adversaries (Extended Abstract).  In INDOCRYPT, volume 12578 of Lecture Notes in Computer Science, pages 786–809. Springer, 2020.
  * [24] A. Choudhury and A. Patra.  An Efficient Framework for Unconditionally Secure Multiparty Computation.  IEEE Trans. Inf. Theory, 63(1):428–468, 2017.
  * [25] R. Cramer, I. Damgård, S. Dziembowski, M. Hirt, and T. Rabin.  Efficient Multiparty Computations Secure Against an Adaptive Adversary.  In J. Stern, editor, EUROCRYPT, volume 1592 of Lecture Notes in Computer Science, pages 311–326. Springer, 1999.
  * [26] R. Cramer, I. Damgård, and U. M. Maurer.  General Secure Multi-party Computation from any Linear Secret-Sharing Scheme.  In B. Preneel, editor, EUROCRYPT, volume 1807 of Lecture Notes in Computer Science, pages 316–334. Springer Verlag, 2000.
  * [27] I. Damgård, M. Geisler, M. Krøigaard, and J. B. Nielsen.  Asynchronous Multiparty Computation: Theory and Implementation.  In PKC, volume 5443 of Lecture Notes in Computer Science, pages 160–179. Springer, 2009.
  * [28] I. Damgård and J. B. Nielsen.  Scalable and Unconditionally Secure Multiparty Computation.  In CRYPTO, volume 4622 of Lecture Notes in Computer Science, pages 572–590. Springer, 2007.
  * [29] D. Dolev, C. Dwork, O. Waarts, and M. Yung.  Perfectly Secure Message Transmission.  J. ACM, 40(1):17–47, 1993.
  * [30] P. Feldman and S. Micali.  An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement.  SIAM J. Comput., 26(4):873–933, 1997.
  * [31] M. J. Fischer and N. A. Lynch.  A Lower Bound for the Time to Assure Interactive Consistency.  Inf. Process. Lett., 14(4):183–186, 1982.
  * [32] M. Fitzi, J. A. Garay, S. Gollakota, C. Pandu Rangan, and K. Srinathan.  Round-Optimal and Efficient Verifiable Secret Sharing.  In TCC, volume 3876 of Lecture Notes in Computer Science, pages 329–342. Springer, 2006.
  * [33] R. Gennaro, Y. Ishai, E. Kushilevitz, and T. Rabin.  The Round Complexity of Verifiable Secret Sharing and Secure Multicast.  In STOC, pages 580–589. ACM, 2001.
  * [34] O. Goldreich.  The Foundations of Cryptography - Volume 2, Basic Applications.  Cambridge University Press, 2004.
  * [35] Y. Guo, R. Pass, and E. Shi.  Synchronous, with a Chance of Partition Tolerance.  In CRYPTO, volume 11692 of Lecture Notes in Computer Science, pages 499–529. Springer, 2019.
  * [36] M. Hirt.  Multi Party Computation: Efficient Protocols, General Adversaries, and Voting.  PhD thesis, ETH Zurich, Zürich, Switzerland, 2001.
  * [37] M. Ito, A. Saito, and T. Nishizeki.  Secret Sharing Schemes Realizing General Access Structures).  In Global Telecommunication Conference, Globecom, pages 99–102. IEEE Computer Society, 1987.
  * [38] J. Katz and C. Y. Koo.  On Expected Constant-Round Protocols for Byzantine Agreement.  In CRYPTO, volume 4117 of Lecture Notes in Computer Science, pages 445–462. Springer, 2006.
  * [39] J. Katz, C. Y. Koo, and R. Kumaresan.  Improving the Round Complexity of VSS in Point-to-point Networks.  Inf. Comput., 207(8):889–899, 2009.
  * [40] R. Kumaresan, A. Patra, and C. Pandu Rangan.  The Round Complexity of Verifiable Secret Sharing: The Statistical Case.  In ASIACRYPT, volume 6477 of Lecture Notes in Computer Science, pages 431–447. Springer, 2010.
  * [41] E. Kushilevitz, Y. Lindell, and T. Rabin.  Information-Theoretically Secure Protocols and Security under Composition.  SIAM J. Comput., 39(5):2090–2112, 2010.
  * [42] C. Liu-Zhang and U. Maurer.  Synchronous Constructive Cryptography.  In TCC, volume 12551 of Lecture Notes in Computer Science, pages 439–472. Springer, 2020.
  * [43] N. A. Lynch.  Distributed Algorithms.  Morgan Kaufmann, 1996.
  * [44] F. J. MacWilliams and N. J. A. Sloane.  The Theory of Error Correcting Codes.  North-Holland Publishing Company, 1978.
  * [45] D. Malkhi, K. Nayak, and L. Ren.  Flexible Byzantine Fault Tolerance.  In CCS, pages 1041–1053. ACM, 2019.
  * [46] U. M. Maurer.  Secure Multi-Party Computation Made Simple.  Discret. Appl. Math., 154(2):370–381, 2006.
  * [47] R. J. McEliece and D. V. Sarwate.  On Sharing Secrets and Reed-Solomon Codes.  Commun. ACM, 24(9):583–584, 1981.
  * [48] A. Patra, A. Choudhary, T. Rabin, and C. P. Rangan.  The Round Complexity of Verifiable Secret Sharing Revisited.  In CRYPTO, volume 5677 of Lecture Notes in Computer Science, pages 487–504. Springer, 2009.
  * [49] A. Patra, A. Choudhury, and C. Pandu Rangan.  Asynchronous Byzantine Agreement with Optimal Resilience.  Distributed Comput., 27(2):111–146, 2014.
  * [50] A. Patra, A. Choudhury, and C. Pandu Rangan.  Efficient Asynchronous Verifiable Secret Sharing and Multiparty Computation.  J. Cryptology, 28(1):49–109, 2015.
  * [51] A. Patra and D. Ravi.  On the power of hybrid networks in multi-party computation.  IEEE Transactions on Information Theory, 64(6):4207–4227, 2018\.
  * [52] M. C. Pease, R. E. Shostak, and L. Lamport.  Reaching Agreement in the Presence of Faults.  J. ACM, 27(2):228–234, 1980.
  * [53] T. P. Pedersen.  A Threshold Cryptosystem without a Trusted Party (Extended Abstract).  In EUROCRYPT, volume 547 of Lecture Notes in Computer Science, pages 522–526. Springer, 1991.
  * [54] T. Rabin and M. Ben-Or.  Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract).  In STOC, pages 73–85. ACM, 1989.
  * [55] A. Shamir.  How to Share a Secret.  Commun. ACM, 22(11):612–613, 1979.