Network Agnostic MPC with Statistical Security

Ananya AppanWork done as a student at IIIT Bangalore.1
Ashish Choudhury 2

SAP Labs, Bangalore India

<EMAIL_ADDRESS>Bangalore, India

In this work, we initiate the study of network agnostic MPC protocols with statistical security. Network agnostic MPC protocols give the best possible security guarantees,
irrespective of the underlying network type. While network agnostic MPC
protocols have been designed earlier with perfect and computational security, nothing is known in the literature regarding the possibility of
network agnostic MPC protocols with statistical security. We consider the general-adversary model, where the adversary is characterized by an adversary structure, which enumerates all possible candidate subsets of corrupt parties. Given an unconditionally-secure PKI setup (a.k.a pseudo-signature setup),
known statistically-secure synchronous MPC (SMPC) protocols are secure against adversary structures satisfying the
$\Q^{(2)}$ condition, meaning that the union of any two subsets from the adversary structure does not cover the entire set of parties.
On the other hand, known statistically-secure asynchronous MPC (AMPC) protocols
can tolerate $\Q^{(3)}$ adversary structures where the union of any three subsets from the adversary structure does not cover the entire set of parties.

Fix a set of $n$ parties $\PartySet = \{P_1, \ldots, P_n \}$ and adversary structures $\Z_s$ and $\Z_a$, satisfying the $\Q^{(2)}$ and $\Q^{(3)}$ conditions respectively, where
$\Z_a \subset \Z_s$.  Then given an unconditionally-secure PKI, we ask whether it is possible to design a statistically-secure MPC protocol, which is resilient against $\Z_s$
and $\Z_a$ in a synchronous
and an asynchronous
network respectively, even if the parties in $\PartySet$ are unaware of the network type. We show that it is possible iff
$\Z_s$ and $\Z_a$ satisfy the $\Q^{(2, 1)}$ condition, meaning that the union of any two subsets from $\Z_s$ and any one subset from $\Z_a$
is a proper subset of $\PartySet$.
Enroute our MPC protocol, we design several important network agnostic building blocks with the $\Q^{(2, 1)}$ condition, such as Byzantine broadcast,
Byzantine agreement (BA), information checking protocol (ICP), verifiable secret-sharing (VSS) and secure multiplication protocol, whose
complexity is polynomial in $n$ and $|\Z_s|$.

§ INTRODUCTION

A  secure multiparty computation (MPC) protocol [53, 36, 13, 52]  allows a set of $n$ mutually distrusting parties
$\PartySet = \{P_1, \ldots, P_n \}$ with private inputs to securely compute any known function $f$ of their inputs.
This is achieved even if a subset of the parties are under the control of a centralized adversary and behave maliciously in a Byzantine fashion
during the protocol execution.
In any MPC protocol, the parties need to interact
over the underlying communication network. Two types of networks have been predominantly considered.
The more popular synchronous MPC (SMPC) protocols operate over a synchronous network, where
every message sent is delivered within a known $\Delta$ time.
Hence, if a receiving party does not receive an expected
message within $\Delta$ time,
then it knows that the corresponding sender party is corrupt.
The synchronous model does not capture real world networks like the Internet appropriately, where messages can be arbitrarily delayed.
Such networks are better modelled by the asynchronous communication model [19]. In any asynchronous MPC (AMPC) protocol [12, 14], there are no
timing assumptions on message delays and messages can be arbitrarily, yet finitely delayed. The only guarantee is that every message sent will be eventually delivered.
The major challenge here is that no participant will know how long it has to wait for an expected message
and cannot distinguish a “slow" sender party from a corrupt sender party.
Consequently, in any AMPC protocol, a party cannot afford to receive messages from all the parties,
to avoid an endless wait. Hence, to make “progress", as soon a party receives messages from a “subset" of the parties, it has to process them
as per the protocol, thus ignoring messages from a subset of potentially non-faulty but slow parties.

SMPC protocols are relatively simpler and enjoy better fault-tolerance (which is the maximum number of faults tolerable) compared to AMPC protocols.
However, SMPC protocols become completely insecure even if a single message
(from a non-faulty party) gets delayed. AMPC protocols do not suffer from this shortcoming.
On the negative side, AMPC protocols are far more complex than SMPC protocols and enjoy poor fault-tolerance.
Moreover, every AMPC protocol suffers from input deprivation [10] where, to avoid an endless wait, inputs of all non-faulty parties
may not be considered for the computation of $f$.

Network Agnostic MPC Protocols.

There is a third category of protocols called network agnostic MPC protocols, where
the parties will not be knowing the network type
and the protocol should provide the best possible security guarantees depending upon the network type.
Such protocols are practically motivated, since the parties need not have to worry about the network type.

§.§ Our Motivation and Results

One of the earliest demarcations made in the literature is to categorize MPC protocols based on the computing power of the underlying adversary. The two main categories are
unconditionally-secure protocols, which remain secure even against  computationally-unbounded adversaries, and
conditionally-secure MPC protocols (also called cryptographically-secure), which remain
secure only against computationally-bounded adversaries [53, 36].
Unconditionally-secure protocols can be further categorized as perfectly-secure [13, 12] or statistically-secure [52, 14],
depending upon whether the security guarantees are error-free or achieved
except with a negligible probability. The fault-tolerance of statistically-secure MPC protocols are significantly better
compared to perfectly-secure protocols.
The above demarcation carries over even for network agnostic MPC protocols. While perfectly-secure and cryptographically-secure network agnostic MPC protocols have been investigated earlier,
nothing is known regarding network agnostic statistically-secure MPC protocols.
In this work we derive necessary and sufficient condition for such protocols for the first time.

Existing Results for Statistically-Secure MPC.

Consider the threshold setting, where the maximum number of corrupt parties under the adversary's control is upper bounded by a given threshold.
In this model, it is known that statistically-secure SMPC tolerating up to $t_s$ faulty parties is possible iff $t_s < n/2$ [52],
provided the parties are given some unconditionally-secure PKI (a.k.a pseudo-signature setup) [50, 34].[The setup realizes
unconditionally-secure Byzantine agreement  [49] with $t_s < n/2$.]
On the other hand, statistically-secure AMPC tolerating up to $t_a$ faulty parties is possible iff $t_a < n/3$ [14, 2].

A more generalized form of corruption is the general adversary model (also called non-threshold model) [38].
Here, the adversary is specified through a publicly known adversary structure $\Z \subset 2^{\PartySet}$, which is the set of all subsets of potentially
corruptible parties during the protocol execution. The adversary is allowed to choose any one subset from $\Z$ for corruption. There are several “merits" of studying the
general adversary model.  For example,
it provides more flexibility to model corruption in a fine-grained fashion.
A threshold adversary is always a “special" type of non-threshold adversary.
Consequently, a protocol in the non-threshold setting always implies a protocol in the threshold setting.
Also, the protocols in this model are relatively simpler and based on simpler primitives, compared to protocols against threshold adversaries based
on complex properties of bivariate polynomials.
The downside is that the complexity of the protocols in the non-threshold model is polynomial in $n$ and $|\Z|$, where the latter could be $\Order(2^n)$ in the worst case.
In fact, as noted in [38, 39], this is unavoidable.

Following [38], given a subset of parties $\PartySet' \subseteq \PartySet$ and $\Z$, we say that
$\Z$ satisfies the $\Q^{(k)}(\PartySet', \Z)$ condition, if the union of any $k$ subsets from $\Z$ does not “cover" $\PartySet'$. That is, for any subsets $Z_{i_1}, \ldots, Z_{i_k} \in \Z$,
the condition $(Z_{i_1} \cup \ldots \cup Z_{i_k}) \subset \PartySet'$ holds.

In the non-threshold model, statistically-secure SMPC is possible if the underlying adversary structure $\Z_s$ satisfies the $\Q^{(2)}(\PartySet, \Z_s)$ condition, provided the parties are
given an unconditionally-secure PKI setup [40], while statistically-secure AMPC requires the underlying adversary structure $\Z_a$ to satisfy the $\Q^{(3)}(\PartySet, \Z_a)$ condition [40, 5].

Our Results for Network Agnostic Statistically-Secure MPC.

We consider the most generic form of corruption and ask the following question:

Given an unconditionally-secure PKI, a synchronous adversary structure $\Z_s$ and an asynchronous adversary structure $\Z_a$ satisfying the
$\Q^{(2)}(\PartySet, \Z_s)$  and  $\Q^{(3)}(\PartySet, \Z_a)$ conditions respectively, where $\Z_a \subset \Z_s$, does there exist a statistically-secure MPC protocol, which remains secure against
$\Z_s$ and $\Z_a$ in a synchronous and an asynchronous network respectively?

We answer the above question affirmatively, iff $\Z_s$ and $\Z_a$ satisfy the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition,  where
by $\Q^{(k, k')}(\PartySet, \Z_s, \Z_a)$ condition, we mean that for any $Z_{i_1}, \ldots, Z_{i_k} \in \Z_s$ and ${\mathsf Z}_{j_1}, \ldots, {\mathsf Z}_{j_{k'}} \in \Z_a$, the following

\[ (Z_{i_1} \cup \ldots \cup Z_{i_k} \cup {\mathsf Z}_{j_1} \cup \ldots \cup {\mathsf Z}_{j_k'}) \subset \PartySet.\]

Our results when applied against threshold adversaries imply that given an unconditionally-secure PKI, and thresholds $0 < t_a <  \frac{n}{3} < t_s < \frac{n}{2}$, network agnostic
statistically-secure MPC tolerating $t_s$ and $t_a$ corruptions in the synchronous and asynchronous network is
possible, iff $2t_s + t_a < n$ holds. Our results in the context of relevant literature are summarized in
Table <ref>.

Network Type     Corruption Scenario     Security     Condition     Reference

Synchronous     Threshold $(t)$     Perfect     $t < n/3$     [13]

Synchronous     Non-threshold $(\Z)$     Perfect     $\Q^{(3)}(\PartySet, \Z)$     [38]

Synchronous     Threshold $(t)$     Statistical     $t < n/2$     [52]

Synchronous     Non-threshold $(\Z)$     Statistical     $\Q^{(2)}(\PartySet, \Z)$     [40]

Asynchronous     Threshold $(t)$     Perfect     $t < n/4$     [12]

Asynchronous     Non-threshold $(\Z)$     Perfect     $\Q^{(4)}(\PartySet, \Z)$     [42]

Asynchronous     Threshold $(t)$     Statistical     $t < n/3$     [14, 2]

Asynchronous     Non-threshold $(\Z)$     Statistical     $\Q^{(3)}(\PartySet, \Z)$     [5]

Network Agnostic     Threshold $(t_s, t_a)$     Perfect     $0 < t_a < n/4 < t_s < n/3$     [3]

and $3t_s + t_a < n$

Network Agnostic     Non-threshold $(\Z_s, \Z_a)$     Perfect     $\Z_a \subset \Z_s, \Q^{(3)}(\PartySet, \Z_s), \Q^{(4)}(\PartySet, \Z_a)$     [4]

and $\Q^{(3, 1)}(\PartySet, \Z_s, \Z_a)$

Network Agnostic     Threshold $(t_s, t_a)$     Computational     $0 < t_a < n/3 < t_s < n/2$     [17]

and $2t_s + t_a < n$

Network Agnostic     Non-threshold $(\Z_s, \Z_a)$     Statistical     $\Z_a \subset \Z_s, \Q^{(2)}(\PartySet, \Z_s), \Q^{(3)}(\PartySet, \Z_a)$     This work

and $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$

Network Agnostic     Threshold $(t_s, t_a)$     Statistical     $0 < t_a < n/3 < t_s < n/2$     This work

and $2t_s + t_a < n$

Various conditions for MPC in different settings

§.§ Detailed Technical Overview

We perform shared circuit-evaluation [13, 52],
where $f$ is abstracted as an arithmetic circuit $\ckt$ over a finite field $\F$ and the goal is to securely evaluate each gate
in $\ckt$ in a secret-shared fashion. For every value during the circuit-evaluation, each party holds a share, such that the shares of the corrupt parties do not reveal any additional information.
Once the function output is secret-shared, it is publicly reconstructed.
We deploy a linear secret-sharing scheme, which enables the parties to evaluate linear gates in $\ckt$ in a non-interactive fashion. Non-linear gates are evaluated using Beaver's method [8] by deploying secret-shared random multiplication-triples which are generated beforehand.

To instantiate the above approach with statistical security, we need the following ingredients:
a Byzantine agreement (BA) protocol [49],
an information checking protocol (ICP) [52],
a verifiable secret sharing (VSS) protocol [22],
a reconstruction protocol and finally, a secure multiplication protocol.
All existing statistically-secure SMPC [52, 26, 9, 37, 40] and AMPC [14, 48, 24, 25, 5] protocols have instantiations of the above building blocks,
either in the synchronous or asynchronous setting.
However, in a network agnostic setting, we face several challenges to instantiate the above building blocks.
We now take the reader through a detailed tour of the technical challenges and how we deal with them.

§.§.§ Network Agnostic BA with $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ Condition

A BA protocol [49] allows the parties in $\PartySet$ with private input bits
to agree on a common output bit (consistency), which is the input of the
non-faulty parties, if they have the same input bit (validity).
Given an unconditionally-secure PKI, synchronous BA (SBA) is possible iff the underlying adversary structure $\Z_s$ satisfies the $\Q^{(2)}(\PartySet, \Z_s)$ condition [50, 33, 34], while
asynchronous BA (ABA) requires the underlying adversary structure $\Z_a$ to satisfy the $\Q^{(3)}(\PartySet, \Z_a)$ condition [23].
Existing SBA protocols become completely insecure in an asynchronous network.
On the other hand, any ABA protocol becomes insecure when executed in a synchronous network, since
$\Z_s$ need not
satisfy the $\Q^{(3)}(\PartySet,\Z_s)$ condition.
Hence, we design a network agnostic BA protocol with $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition.
The protocol is obtained by generalizing the blueprint for network agnostic BA against threshold adversaries, first proposed in [15] and later used in [3].
While [15] proposed it for computational security
with conditions $0 < t_a < \frac{n}{3} < t_s < \frac{n}{2}$ and $2t_s + t_a < n$ in the presence of a computationally-secure PKI, later,
[3] modified it for perfect security
and used it with conditions $t_a, t_s < n/3$.[Unlike computationally-secure BA, the necessary condition for perfectly-secure BA is $t < n/3$ for both SBA as well as ABA, where $t$ is
the maximum number of faults.] We replace the computationally-secure PKI with an unconditionally-secure PKI and generalize the building blocks of [15] against non-threshold adversaries
and upgrade their security to unconditional-security.
Additionally, we also generalize certain
primitives from [3] and adapt them to work with the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition.
Since this part mostly follows the existing works, we refer to Section <ref> for full details.

§.§.§ Network Agnostic ICP with $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ Condition

An ICP [52, 26] is used for authenticating data in the presence of a
computationally-unbounded adversary.
In an ICP, there are four entities, a signer $\mathsf{S} \in \PartySet$,
an  intermediary $\mathsf{I} \in \PartySet$, a receiver
$\mathsf{R} \in \PartySet$ and all the parties in $\PartySet$ acting as verifiers
(note that $\mathsf{S}, \mathsf{I}$ and $\mathsf{R}$ also act as verifiers).
An ICP has two sub-protocols, one for the authentication phase and one for
the revelation phase.

In the authentication phase, $\mathsf{S}$ has a private input
$s \in \F$, which it distributes to $\mathsf{I}$ along with some authentication information.
Each verifier is provided with some verification information, followed by the parties verifying whether $\mathsf{S}$ has distributed “consistent" information.
If the verification is “successful", then the
data held by $\mathsf{I}$ at the end of this phase is called  $\mathsf{S}$'s IC-Signature on $s$ for intermediary $\mathsf{I}$ and receiver $\mathsf{R}$, denoted by
$\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$.
Later, during the revelation phase, $\mathsf{I}$ reveals $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$ to $\mathsf{R}$,
who “verifies" it with respect to the verification information provided by the verifiers and either accepts or rejects
$s$. We require the same security guarantees from ICP as expected from cryptographic signatures,
namely correctness (if $\mathsf{S, I}$ and $\mathsf{R}$ are all honest, then $\mathsf{R}$ should accept $s$), unforgeability
(a corrupt $\mathsf{I}$ should fail to reveal an honest $\mathsf{S}$'s signature on $s' \neq s$) and non-repudiation
(if an honest $\mathsf{I}$ holds some $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$, then later an honest $\mathsf{R}$ should accept
$s$, even if $\mathsf{S}$ is corrupt).
Additionally, we need privacy, guaranteeing that if
$\mathsf{S, I}$ and $\mathsf{R}$ are all honest, then $\Adv$ does not learn
$s$.[IC-signatures are different from pseudo-signatures.
Pseudo-signatures are “transferable", where a party can transfer a signed message to other parties for verification (depending upon the allowed level
of transferability), while IC-signatures can be verified only by the designated $\mathsf{R}$ and cannot be further transferred.
Due to the same reason, IC-signatures satisfy the privacy property unlike pseudo-signatures. Most importantly, IC-signatures are generated from the scratch, assuming a pseudo-signature
setup which is used to instantiate the instances of broadcast in the ICP.]

The only known instantiation of ICP in the synchronous network [40] is secure against $\Q^{(2)}$ adversary structures and becomes insecure
in the asynchronous setting. On the other hand, the only known instantiation of ICP in the asynchronous setting [5] can tolerate only
$\Q^{(3)}$ adversary structures. Our network agnostic
ICP is a careful adaptation of the asynchronous ICP of [5].
We first try to naively adapt the ICP to deal with the network agnostic setting, followed by the technical problems in the naive adaptation
and the modifications needed.

During authentication phase, $\mathsf{S}$ embeds $s$ in a random $t$-degree polynomial $F(x)$ at $x = 0$, where
$t$ is the cardinality of the maximum-sized subset in $\Z_s$, and gives $F(x)$ to $\mathsf{I}$. In addition, each verifier $P_i$ is given a random verification-point
$(\alpha_i, v_i)$ on $F(x)$.
To let the parties securely verify that it has distributed consistent information, $\mathsf{S}$
additionally distributes a random $t$-degree polynomial $M(x)$ to $\mathsf{I}$, while
each verifier $P_i$ is given a point on $M(x)$ at $\alpha_i$. Each verifier, upon receiving
its verification-points, publicly confirms the same.
Upon receiving these confirmations, $\mathsf{I}$ identifies a
a subset of supporting verifiers $\R$ which have confirmed the receipt of their verification-points.
To avoid an endless wait, $\mathsf{I}$ waits until
$\PartySet \setminus \R \in \Z_s$.
After this, the parties publicly check the consistency of the $F(x), M(x)$ polynomials
and the points distributed to $\R$, with respect to a random linear combination of these polynomials and points, where the linear combiner is selected by
This ensures that $\mathsf{S}$ has no knowledge beforehand about the random combiner
and hence, any “inconsistency" will be detected with a high probability.
If no inconsistency is detected, the parties proceed to the revelation phase, where
$\mathsf{I}$ reveals $F(x)$ to $\mathsf{R}$, while each verifier in $\R$
reveals its verification-point to $\mathsf{R}$, who accepts $F(x)$ (and hence $F(0)$) if it
sure that the verification point of at least one non-faulty verifier in $\R$ is “consistent" with the revealed $F(x)$.
This would ensure that the revealed $F(x)$ is indeed correct with a high probability, since a corrupt $\mathsf{I}$ will have no information about the verification point of any
non-faulty verifier in $\R$, provided $\S$ is non-faulty.

To avoid an endless wait, once $\mathsf{R}$
finds a subset of verifiers $\R' \subseteq \R$, where
$\R \setminus \R' \in \Z_s$, whose verification-points are found to be “consistent" with $F(x)$, it outputs $F(0)$.

A Technical Problem and Way-out.

The protocol outlined above will achieve all the properties in an asynchronous network, due to the
$\Q^{(3)}(\PartySet, \Z_a)$ condition.
However, it fails to satisfy the
unforgeability property in a synchronous network. Namely, a corrupt
$\mathsf{I}$ may not include all the non-faulty verifiers in $\R$ and may purposely exclude a subset of non-faulty verifiers belonging to $\Z_s$.
Let $\Hon_{\R}$ be the set of non-faulty verifiers in $\R$ and let $\C_{\R}$ be the set of corrupt verifiers in $\R$. Due to the above strategy,
the condition $\Q^{(1)}(\Hon_\R, \Z_s)$ may not be satisfied and $\R \setminus \C_\R = \Hon_\R \in \Z_s$ may hold.
As a result, during the revelation phase, $\mathsf{I}$ may produce an incorrect $F'(x) \neq F(x)$ and the verifiers in $\C_{\R}$ may change their verification points to
“match" $F'(x)$,
while only the verification points of the verifiers in $\Hon_\R$ may turn out to be inconsistent with $F'(x)$. Consequently, $\R' = \C_\R$
and if $\Hon_\R \in \Z_s$, then clearly $s' = F'(0)$ will be the output
of $\mathsf{R}$, thus breaking the
unforgeability property.

To deal with the above issue, we let $\S$ identify and announce $\R$. This ensures that all
honest verifiers are present in $\R$, if $\S$ is honest and the network is synchronous, provided $\S$ waits for “sufficient" time to let the verifiers announce the receipt of their verification points.
Consequently, now the condition $\Q^{(1)}(\Hon_\R, \Z_s)$ will be satisfied.
Hence, if a corrupt $\mathsf{I}$ reveals an incorrect $F(x)$, then it will not be accepted,
as the condition $\R \setminus \C_\R \in \Z_s$ no longer holds.

Linearity of ICP.

Our ICP satisfies the linearity property (which will be useful later in our VSS),
provided “special care" is taken while generating the IC-signatures.
Consider a fixed $\mathsf{S}, \mathsf{I}$ and $\mathsf{R}$ and let $s_a$ and $s_b$ be two values, such that $\mathsf{I}$ holds $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s_a)$ and
$\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s_b)$, where all the following conditions are satisfied during the underlying instances of the authentication phase.

– The set of supporting verifiers $\R$ are the same during both the instances.

– For $i = 1, \ldots, n$, corresponding to the verifier $P_i$, signer $\mathsf{S}$ uses the same $\alpha_i$, to compute the verification points, during
both the instances.

– $\mathsf{I}$ uses the same linear combiner to verify the consistency of the distributed data in both the instances.

Let $s \defined c_1 \cdot s_a + c_2 \cdot s_b$, where $c_1, c_2$ are publicly known constants from $\F$. It then follows that if all the above conditions are satisfied, then $\INT$
can locally compute $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$ from $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s_a)$ and $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s_b)$,
while each verifier in $\R$ can locally compute their corresponding verification information.

§.§.§ Network Agnostic VSS and Reconstruction

In the network agnostic setting, to ensure privacy,
all the values during the circuit evaluation need to be secret-shared “with respect" to $\Z_s$
irrespective of the network type.
We follow the notion of additive secret-sharing [41], also used in the earlier MPC protocols [44, 40, 5].
Given $\Z_s = \{Z_1, \ldots, Z_{|\Z_s|} \}$, we consider the sharing specification $\ShareSpec_{\Z_s} = \{S_1, \ldots, S_{|\Z_s|} \}$, where each $S_q = \PartySet \setminus Z_q$.
Hence there exists at least one subset $S_q \in \ShareSpec_{|\Z_s|}$ which does not contain any faulty party, irrespective of the network type (since $\Z_a \subset \Z_s$).
A value $s \in \F$ is said to be secret-shared, if there exist shares $s_1, \ldots, s_{|\Z_s|}$ which sum up to $s$, such that all (non-faulty) parties in $S_q$ have the share $s_q$.
We denote a secret-sharing of $s$ by $[s]$, with $[s]_q$ denoting the share corresponding to $S_q$. If $[s]_1, \ldots, [s]_{|\Z_s|}$ are randomly chosen, then the probability
distribution of the shares learnt by the adversary will be independent of $s$, since at least one share will be missing for the adversary.
We also note that the above secret-sharing is linear since, given secret-sharings $[a]$ and $[b]$ and publicly known constants $c_1, c_2 \in \F$,
the condition $c_1 \cdot [a] + c_2 \cdot [b] = [c_1 \cdot a + c_2 \cdot b]$ holds.
Consequently, the parties can non-interactively compute any publicly known linear function of secret-shared values.
Unfortunately, the above secret-sharing does not allow for the
robust reconstruction of a secret-shared value. This is because the corrupt parties may produce incorrect shares at the time of reconstruction.
To deal with this, we “augment" the above secret-sharing. As part of secret-sharing $s$,
we also have publicly known core-sets
$\W_1, \ldots, \W_{|\Z_s|}$, where each $W_q \subseteq S_q$ such that $\Z_s$ satisfies the $\Q^{(1)}(\W_q, \Z_s)$ condition (ensuring $\W_q$ has at least one non-faulty party).
Moreover, each (non-faulty) $P_i \in \W_q$ will have the IC-signature
$\ICSig(P_j, P_i, P_k, [s]_q)$ of every $P_j \in \W_q$, for every $P_k \not \in S_q$, such that the underlying IC-signatures satisfy the linearity property.

We call this augmented secret sharing as linear secret-sharing with IC-signatures, which is still denoted as $[s]$.
Now to robustly reconstruct a secret-shared $s$, we ask the parties in $\W_q$ to make public the share $[s]_q$, along
with the IC-signatures of all the parties in $\W_q$ on $[s]_q$.
Any party $P_k$ can then verify whether $[s]_q$ revealed by $P_i$ is correct by verifying the IC-signatures.
If $P_i$ is corrupt then, due to the unforgeability if ICP, it will fail to forge IC-signature of a non-faulty $P_j$ on an incorrect $[s]_q$.
On the other hand, a non-faulty $P_i$ will be able to reveal the correct $[s]_q$ and the IC-signature of every $P_j \in \W_q$ on $[s]_q$, which are accepted even if
$P_j$ is corrupt (follows from non-repudiation of ICP).

We design a network agnostic VSS protocol $\VSS$, which allows a designated dealer $\D \in \PartySet$ with input $s \in \F$ to verifiably generate
$[s]$, where $s$ remains private for a non-faulty $s$.
If $\D$ is faulty then either no non-faulty party obtains any output (if $\D$ does not invoke the protocol) or there exists some $s^{\star} \in \F$ such that the parties
output $[s^{\star}]$.
To design $\VSS$, we use certain ideas from the statistically-secure
synchronous VSS (SVSS) and asynchronous VSS (AVSS)
of [40] and [5] respectively, along with some new counter-intuitive ideas. In the sequel, we first give a brief outline of the SVSS and AVSS of [40, 5], followed by the technical challenges
arising in the network agnostic setting and how we deal with them.

Statistically-Secure SVSS of [40] with $\Q^{(2)}(\PartySet, \Z_s)$ Condition.

The SVSS of [40]
proceeds as a sequence of synchronized phases. During the first phase, $\D$ picks random shares $s_1, \ldots, s_{|\Z_s|}$ which sum up to $s$ and sends $s_q$ to the parties in $S_q$.
To verify whether $\D$ has distributed consistent shares to the parties in $S_q$, during the second phase,
every pair of parties $P_i, P_j \in S_q$ exchange the supposedly common shares received from $\D$,
along with their respective IC-signatures. That is $P_i$, upon receiving $s_{qi}$ from $\D$, gives $\{\ICSig(P_i, P_j, P_k, s_{qi})\}_{P_k \in \PartySet}$ to $P_j$ while
$P_j$, upon receiving $s_{qj}$ from $\D$, gives $\{\ICSig(P_j, P_i, P_k, s_{qj})\}_{P_k \in \PartySet}$ to $P_i$.
Then during the third phase, the parties in $S_q$ publicly complain about any “inconsistency", in response to which $\D$ makes public the share
$s_q$ corresponding to $S_q$ during the fourth phase.
Hence, by the end of fourth phase it is ensured that, for every $S_q$, either the share $s_q$ is publicly known (if any complaint was reported for $S_q$)
or all (non-faulty) parties in $S_q$ have the same share (along with the respective IC-signatures of each other on it).
The privacy of $s$ is maintained for a non-faulty $\D$, since the share $s_q$ corresponding to the set $S_q$ consisting of only non-faulty parties  is never made public.

Statistically-Secure AVSS of [5] with $\Q^{(3)}(\PartySet, \Z_a)$ Condition.

Let  $\Z_a = \{\mathsf{Z}_1, \ldots, \mathsf{Z}_{|\Z_a|} \}$ and $\ShareSpec_{\Z_a} = \{\S_1, \ldots, \S_{|\Z_a|} \}$, where each $\S_q = \PartySet \setminus \mathsf{Z}_q$.
The AVSS protocol of [5] also follows an idea similar to the SVSS of [40].
However, now the parties cannot afford to wait for all the parties in $\S_q$ to report
the statuses of pairwise consistency tests, as the corrupt parties in $\S_q$ may never turn up.

Hence instead of looking for inconsistencies in $\S_q$, the parties rather check how many parties in $\S_q$ are reporting the pairwise consistency of their supposedly
common share. The idea is that if $\D$ has not cheated, then a subset of parties $\W_q$ where $\S_q \setminus \W_q \in \Z_a$ should eventually confirm the receipt of a common share
from $\D$. Hence, the parties check for core-sets $\W_1, \ldots, \W_{|\Z_a|}$, where each $\S_q \setminus \W_q \in \Z_a$, such that the parties
in $\W_q$ have confirmed the receipt of a common share from $\D$.
Note that irrespective of $\D$, each $\W_q$ is bound to have at least one non-faulty party, since $\Z_a$ will satisfy the $\Q^{(1)}(\W_q, \Z_a)$ condition.

The existence of $\W_1, \ldots, \W_{|\Z_a|}$ does not imply that all non-faulty parties in $\S_q$ have received a common share, even if $\D$ is non-faulty, since there might be
non-faulty parties outside $\W_q$. Hence,
after the confirmation of the sets $\W_1, \ldots, \W_{|\Z_a|}$, the goal is to ensure that every (non-faulty) party in $\S_q \setminus \W_q$
also gets the common share held by the (non-faulty) parties in $\W_q$. For this,
the parties in $\W_q$ reveal their shares to these “outsider" parties, along with the required IC-signatures.
The outsider parties then “filter" out the correctly revealed shares.
The existence of at least one non-faulty party in each $\W_q$ guarantees that the shares filtered by the outsider parties are indeed correct.

Technical Challenges for Network Agnostic VSS and Way Out.

Since, in our context, the parties will not be knowing the network type, our approach will be to follow the AVSS of [5], where we look for pairwise consistency of supposedly the common share in each group.
Namely, $\D$ on having the input $s$, picks random shares $s_1, \ldots, s_{|\Z_s|}$ which sum up to $s$ and distributes $s_q$ to each $S_q \in \ShareSpec_{|\Z_s|}$[Recall that we need
$[s]$ with respect to $\Z_s$, irrespective of the network type.]. The parties in $S_q$ then exchange IC-signed versions of their supposedly common share.
To avoid an endless wait,
the parties can only afford to wait till a subset of parties $\W_q \subseteq S_q$ have confirmed
the receipt of a common share from $\D$, where $S_q \setminus \W_q \in \Z_s$ holds.
Unfortunately, $S_q \setminus \W_q \in \Z_s$ need not guarantee that $\W_q$ has at least one non-faulty party, since $\Z_s$ need not satisfy the
$\Q^{(1)}(\W_q, \Z_s)$ condition, which is desired as per our semantics of linear secret-sharing with IC-signatures.

To deal with the above problem, we note that if $\D$ has distributed the shares consistently, then the subset of parties $\specialS \in \ShareSpec_{\Z_s}$
which consists of only non-faulty parties will publicly report the pairwise consistency of their supposedly common share.
Hence, we now let $\D$ search for a candidate set $S_p$ of parties from $\ShareSpec_{\Z_s}$ which have publicly confirmed the pairwise consistency of their supposedly common share.
Once $\D$ finds such a candidate $S_p$, it computes and make public the core-sets $\W_q$ as per the following rules, for $q = 1, \ldots, |\Z_s|$.

– If all the parties in $S_q$ have confirmed the pairwise consistency of their supposedly common share, then set $\W_q = S_q$. (A)

– Else if $\Z_s$ satisfies the $\Q^{(1)}(S_p \cap S_q, \Z_s)$ condition
the parties in $(S_p \cap S_q)$ have confirmed the consistency of their supposedly common share, then
set  $\W_q = (S_p \cap S_q)$. (B)

– Else set $\W_q = S_q$ and make public the share $s_q$.  (C)

The parties wait till they see $\D$ making public some set $S_p \in \ShareSpec_{\Z_s}$, along with sets $\W_1, \ldots, \W_{|\Z_s|}$. Upon receiving, the parties verify and “approve" these sets
as valid, provided all parties in $S_p$ have confirmed the pairwise consistency of their supposedly common share and if each
$\W_q$ is computed as per the rule (A), (B) or (C). If $\W_1, \ldots, \W_{|\Z_s|}$ are approved, then they indeed satisfy the requirements of core-sets as per our semantics of
linear secret-sharing with IC-signatures. While this is trivially true if any $\W_q$ is computed either using rule (A) or rule (B), the same holds even if
$\W_q$ is computed using rule (C). This is because, in this case, the parties publicly set $[s]_q = s_q$. Moreover, the parties take a “default" (linear) IC-signature of $s_q$ on the behalf of $S_q$,
where the IC-signature as well as verification points are all set to $s_q$.

If $\D$ is non-faulty, then irrespective of the network type, it will always find a candidate $S_p$ and hence, compute and make public
$\W_1, \ldots, \W_{|\Z_s|}$ as per the above rules. This is because the set $\specialS$ always constitutes a candidate $S_p$.
Surprisingly we can show that even if the core-sets are computed with respect to some different candidate $S_p \neq \specialS$, a non-faulty
$\D$ will never make public the share corresponding to $\specialS$, since the rule (C) will not be applicable over $\specialS$,
implying the privacy of $s$.
If the network is synchronous, then the parties in $S_p$ as well as $\specialS$ would report
the pairwise consistency of their respective supposedly common share at the same time.
This is ensured by maintaining sufficient “timeouts" in the protocol to report pairwise consistency of supposedly common shares.
Consequently, rule (A) will be applied on $\specialS$.
For an asynchronous network, rule (B) will be applicable for $\specialS$, as
$\Z_s$ will satisfy the $\Q^{(1)}(S_p \cap \specialS, \Z_s)$ condition,
due to the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition and the fact that $\specialS = \PartySet \setminus Z$ for some $Z \in \Z_a$ in the asynchronous network.

§.§.§ Network Agnostic VSS for Multiple Dealers with Linearity

Technical Challenge in $\VSS$ for Multiple Dealers.

If  different dealers invoke instances of $\VSS$ to secret-share their inputs, then the linearity property of $[\cdot]$-sharing need not hold,
since the underlying core-sets might be different.
In more detail, let $\D_a$ and $\D_b$ be two different dealers  which invoke instances $\VSS^{(a)}$ and $\VSS^{(b)}$
to generate $[a]$ and $[b]$ respectively. Let $\W_1^{(a)}, \ldots, \W_{|\Z_s|}^{(a)}$ and $\W_1^{(b)}, \ldots, \W_{|\Z_s|}^{(b)}$ be the underlying core-sets for
$\VSS^{(a)}$ and $\VSS^{(b)}$ respectively.  Now consider a scenario where, for some $q \in \{1, \ldots, |\Z_s| \}$, the core-sets
$\W_q^{(a)}$ and $\W_q^{(b)}$ are different, even though
$\Z_s$ satisfies the $\Q^{(1)}(\W_q^{(a)} , \Z_s)$ and $\Q^{(1)}(\W_q^{(b)} , \Z_s)$ conditions.
Let $c \defined a + b$.
Then the parties in $S_q$ can compute $[c]_q = [a]_q + [b]_q$.
As part of $[a]$, every (non-faulty) $P_i \in \W_q^{(a)}$ has the IC-signature $\{ \ICSig(P_j, P_i, P_k, [a]_q) \}_{P_j \in \W_q^{(a)}, P_k \not \in S_q}$, while as part of
$[b]$, every (non-faulty) $P_e \in \W_q^{(b)}$ has the IC-signature $\{ \ICSig(P_d, P_e, P_f, [b]_q) \}_{P_d \in \W_q^{(b)}, P_f \not \in S_q}$, where the underlying IC-signatures satisfy the linearity property.
However, since  $\W_q^{(a)} \neq \W_q^{(b)}$, it is not guaranteed that we have a core-set $\W_q^{(c)}$ as part of $[c]$, where
$\Z_s$ satisfies the $\Q^{(1)}(\W_q^{(c)} , \Z_s)$ condition,
such that every
(non-faulty) $P_i \in \W_q^{(c)}$ has the IC-signature $\{ \ICSig(P_j, P_i, P_k, [c]_q) \}_{P_j \in \W_q^{(c)}, P_k \not \in S_q}$.
If $\W_q^{(a)} = \W_q^{(b)}$, then the parties could set $\W_q^{(c)}$ to $\W_q^{(a)}$ and the linearity of IC-signatures would have ensured that
(non-faulty) $P_i \in \W_q^{(c)}$ non-interactively computes $\{ \ICSig(P_j, P_i, P_k, [c]_q) \}_{P_j \in \W_q^{(c)}, P_k \not \in S_q}$ from
the IC-signatures, held by $P_i$ as part of $[a]$ and $[b]$. In the absence of any core-set $\W_q^{(c)}$, robust reconstruction of $[c]_q$
will fail, which further implies failure of shared circuit-evaluation of $\ckt$, where the inputs for $\ckt$ are shared by different parties.

Way Out.

To deal with the above problem, we ensure that the core-sets are common for all the secret-shared values during the circuit-evaluation. Namely, there exist global core-sets
${\GW}_1, \ldots, {\GW}_{|\Z_s|}$, which constitute the core-sets for
all the secret-shared values during the circuit-evaluation, where for each ${\GW}_q$,
$\Z_s$ satisfies the $\Q^{(1)}({\GW}_q, \Z_s)$ condition.
Maintaining common core-sets is challenging,
especially in an asynchronous network and  $\VSS$ alone is not sufficient to achieve this goal. Rather we use a different approach. We generate a “bunch" of linearly secret-shared
random values with IC-signatures and common core-sets ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ in advance through another protocol called $\Rand$ (discussed in the next section).
Later, if any party $P_i$ needs to secret-share some $x$, then one of these random values is reconstructed only towards $P_i$, which uses it as a one-time pad (OTP) and makes public an OTP-encryption of
$x$. The parties can then take the “default" secret-sharing of the OTP-encryption with IC-signatures and ${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ as the core-sets and then non-interactively “remove" the
pad from the OTP-encryption. This results in $[x]$, with
${\GW}_1, \ldots, {\GW}_{|\Z_s|}$ as core-sets.
To ensure privacy, we need to generate $L$ random values
through $\Rand$, if $L$ is the maximum number of values which need to be secret-shared by different parties during the circuit-evaluation.
We show that  $L \leq n^3 \cdot c_M + 4n^2 \cdot c_M + n^2 + n$ where $c_M$ is the number of multiplication gates in $\ckt$.

§.§.§ Secret-Shared Random Values with Global Core Sets

Protocol $\Rand$ generates linearly secret-shared random values with IC-signatures and common core-sets.
We explain the idea behind the protocol for generating one random value.
The “standard" way will be
to let each $P_i$ pick a random value $r^{(i)}$ and generate $[r^{(i)}]$ by invoking an instance of $\VSS$.
To avoid an endless wait, the parties only wait for the completion of $\VSS$ instances invoked by a set of dealers $\PartySet \setminus Z$ for some $Z \in \Z_s$.
To identify
the common subset of dealers for which the corresponding $\VSS$ instances have completed, the parties run an instance of agreement on a common subset (ACS) primitive [14, 19]. This involves
invoking $n$ instances of our network agnostic BA, one on behalf of each dealer, to decide the $\VSS$ instances of which dealers have completed. Let $\C$ be the set of common dealers identified through
ACS, where $\PartySet \setminus \C \in \Z_s$. The set $\C$ has at least one non-faulty party who has shared a random value.
Hence, the sum of the values shared by the dealers in $\C$ will be random for the adversary.

Technical Challenges.

The above approach fails in our context due to the following two “problems" in the protocol $\VSS$, when executed by different dealers.

Problem I: The first challenge is to maintain the linearity of underlying IC-signatures.
To understand the issue, consider a triplet of parties $P_i, P_j, P_k$, acting as $\S, \mathsf{I}$ and $\mathsf{R}$ respectively
in various instances of $\VSS$ invoked by different dealers.
Recall that, to maintain the linearity of IC-signatures, it is necessary that $P_i$ selects the same set of supporting-verifiers
$\R$ in all the instances of  authentication phase involving $P_j$ and $P_k$.
This is possible only if $P_i$
knows all the values on which it wants to generate the IC-signature for $P_j$
and $P_k$ and starts invoking all the instances of authentication phase.
Instead, if $P_i$ invokes instances of authentication phase as and when it has some data to be authenticated for $P_j$ and $P_k$,
then it may not be possible to have the same $\R$ in all the instances of authentication phase, involving $P_i, P_j$ and $P_k$ in the above roles, especially in an
asynchronous network. Since, in $\VSS$, IC-signatures are generated on the supposedly common shares (after receiving them from the underlying dealer)
and multiple instances of $\VSS$ are invoked (by different dealers),
this means that $P_i$ should first have the data from all the dealers for the various instances of $\VSS$ and before invoking instances of authentication phase to generate
IC-signatures on these values for $P_j$.
This may not be possible,
since $P_i$ need not know beforehand which dealers it will be receiving shares from as part of $\VSS$.

Way Out.

To deal with the above issue, we now let the dealers publicly commit their shares for the $\VSS$ instances through secure verifiable multicast (SVM).
The primitive allows a designated sender $\Sender \in \PartySet$ with input $v$ to “verifiably" send $v$ to a designated set of receivers  $\ReceiverSet \subseteq \PartySet$, without
leaking any additional information.
The verifiability guarantees that even if $\Sender$ is corrupt, if the non-faulty
parties in $\ReceiverSet$ get any value from $\Sender$, then it will be common and all the (non-faulty) parties in $\PartySet$ will
“know" that $\Sender$ has sent some value to $\ReceiverSet$.
Our instantiation of SVM is very simple: $\Sender$ acts as a dealer and generates $[v]$ through $\VSS$. Once $[v]$ is generated, the parties know
that $\Sender$ has
“committed" to some unknown value. The next step is to let only the parties in $\ReceiverSet$ reconstruct $v$.

Using SVM, we now let the various dealers distribute the shares
during the underlying instances of $\VSS$ (for $\Rand$) as follows.
Consider the dealer $P_{\ell}$ who has invoked an instance of $\VSS$ with input $r^{(\ell)}$. For this, it picks
random shares
$r^{(\ell)}_1, \ldots, r^{(\ell)}_{|\Z_s|}$ which sum up to $r^{(\ell)}$.
Now instead of directly sending send $r^{(\ell)}_q$ to the parties in $S_q$, it invokes $|\Z_s|$ instances of SVM with input $r^{(\ell)}_1, \ldots, r^{(\ell)}_{|\Z_s|}$ and
$S_1, \dots, S_{|\Z_s|}$ as the designated set of receivers respectively.
This serves two purposes. First, it guarantees that all the parties in $S_q$ receive a common share from $P_{\ell}$.
Second and more importantly, all the parties in $\PartySet$ will now know that $P_{\ell}$ has distributed shares to each set from $\ShareSpec_{\Z_s}$.
The parties then run an instance of ACS to identify a common subset of committed dealers $\CD \subseteq \PartySet$, where
$\PartySet \setminus \CD \in \Z_s$, which have invoked the desired instances of SVM and delivered the required shares to each group $S_q \in \ShareSpec_{|\Z_s|}$.
The way timeouts are maintained as part of the ACS, it will be ensured that in a synchronous network, all non-faulty dealers are present in $\CD$.
Once the set $\CD$ is identified, it is guaranteed that every non-faulty party $P_i$ will have the shares from all the dealers in $\CD$. And once it has the shares from all the dealers in $\CD$, it starts
generating the IC-signatures on these shares for the designated parties as part of the $\VSS$ instances corresponding to the dealers in $\CD$ and ensures that all the pre-requisites are satisfied
to guarantee the linearity of the underlying IC-signatures.
Now instead of selecting the set of dealers $\C$ (for $\Rand$) from $\PartySet$, the parties run an instance of ACS over the set of committed dealers $\CD$ to
select $\C$ where $\CD \setminus \C \in \Z_s$ holds.
We stress that irrespective of the network type, the set $\C$ is still guaranteed to have at least one non-faulty party.
While this is trivially true in an asynchronous network where $\Z_a$ satisfies the $\Q^{(1)}(\C, \Z_a)$ condition, the same is true in the synchronous network because
$\CD$ will have all non-faulty dealers.

Problem II:

The second problem (in the proposed $\Rand$) is that
the underlying core-sets might be different for the values shared by the dealers in $\CD$ (and hence $\C$).
Instead, we require every dealer in $\CD$ to secret-share random values with common underlying core-sets. Only then will it be ensured that the random values
generated through $\Rand$ are secret-shared with common core-sets.

Way Out. Getting rid of the above problem is not possible if we let every dealer in $\CD$ compute individual core-sets during their respective instances of $\VSS$, as per the steps of
$\VSS$. Recall that in $\VSS$, the dealer $\D$ computes the underlying core-sets with respect to the “first" set of parties $S_p$ from $\ShareSpec_{|\Z_s|}$ which confirm
the pairwise consistency of their supposedly common share after exchanging IC-signatures on these values.
As a result, different dealers (in $\Rand$) may end up computing different core-sets in their instances of $\VSS$ with respect to different
candidate $S_p$ sets.
To deal with this issue, we instead let each dealer in $\CD$ continue computing and publishing different “legitimate" core-sets with respect to various “eligible" candidate
$S_p$ sets from $\ShareSpec_{\Z_s}$. The parties run an instance of ACS to identify a common subset of dealers $\C \in \CD$ where $\CD \setminus \C \in \Z_s$, such that all the dealers
have computed and published “valid" core-sets, computed with the respect to the same $S_p \in \ShareSpec_{\Z_s}$.
The idea here is that there always exists a set $\specialS \in \ShareSpec_{\Z_s}$ consisting of only non-faulty parties.
So if the set of non-faulty dealers $\Hon$ in $\CD$ keep computing and publishing all possible candidate core-sets  in their $\VSS$ instances, then they will
publish core-sets with respect to $\specialS$.

Hence, $\Hon$ and $\specialS$ always constitute the candidate $\CD$ and the common $S_p$ set.

Note that identifying $\C$ out of $\CD$ through ACS satisfying the above requirements
is non-trivial and requires carefully executing
the underlying instances of BA in  “two-dimensions".
We first run $|\Z_s|$ instances of $\BA$, one on the behalf of each set in $\ShareSpec_{\Z_s}$, where the $q^{th}$ instance is executed to decide whether a subset of dealers in $\CD \setminus Z$ for some
$Z \in \Z_s$
have published valid core-sets with respect to the set $S_q \in \ShareSpec_{\Z_s}$.
This enables the parties to identify a common set $S_{\qcore} \in \ShareSpec_{\Z_s}$, such that it is guaranteed that a subset of
dealers in $\CD \setminus Z$ for some
$Z \in \Z_s$
have indeed published valid core-sets with respect to the set $S_{\qcore}$.
Once the set $S_{\qcore}$ is identified, the parties then run $|\CD|$ instances of BA to decide which dealers in $\CD$ have
published core-sets with respect to $S_{\qcore}$.

§.§.§ Network Agnostic Secure Multiplication

To generate secret-shared random multiplication-triples for evaluating the multiplication gates in $\ckt$ (using Beaver's trick), we need a network agnostic secure multiplication protocol which securely generates
a secret-sharing of the product of two secret-shared values.
The key subprotocol behind our multiplication protocol is a non-robust multiplication protocol $\BasicMult$ (standing for basic multiplication), which takes inputs
$[a]$ and $[b]$ and an existing set of globally discarded parties $\Discarded$, which contains only corrupt parties.
The protocol securely generates $[c]$  without
revealing any additional  information about $a, b$ (and $c$).
If no party in $\PartySet \setminus \Discarded$ cheats, then $c = a \cdot b$ holds.
The idea behind the protocol is to let each summand $[a]_p \cdot [b]_q$ be secret-shared by a summand-sharing party. Then $[a \cdot b]$ can be computed
from the secret-sharing of each summand, owing to the linearity property.
Existing multiplication protocols in the synchronous and asynchronous setting [40, 5] also use an
instantiation of $\BasicMult$, based on the above idea.
In the sequel, we recall them, followed by the technical challenges faced in the network agnostic setting and how we deal with them.

$\BasicMult$ in the Synchronous Setting with $\Q^{(2)}(\PartySet, \Z_s)$ Condition [40].

In [40], each summand $[a]_p \cdot [b]_q$ is statically assigned to a designated summand-sharing party through some deterministic assignment,
which is possible since
$[a]_p$ and $[b]_q$ are held by the parties in $(S_p \cap S_q)$. This is non-empty, since the
$\Q^{(2)}(\PartySet, \Z_s)$ condition holds.
Since the parties in $\Discarded$ are already known to be corrupted, all the shares $[a]_p, [b]_p$ held by the parties in $\Discarded$
are publicly reconstructed and instead of letting the parties in $\Discarded$ secret-share their assigned summands, the parties take the “default" secret-sharing
of these summands.

$\BasicMult$ in the Asynchronous Setting with $\Q^{(3)}(\PartySet, \Z_a)$ Condition [5].

The idea of statically designating each summand $[a]_p \cdot [b]_q$ to a unique party in $\PartySet \setminus \Discarded$
need not work in the asynchronous setting, since the designated party may be corrupt and need not secret-share any summand, thus resulting in an endless wait.
To deal with this challenge, [5] dynamically selects the summand-sharing parties for each summand.
In more detail, let
$\Z_a = \{\mathsf{Z}_1, \ldots, \mathsf{Z}_{|\Z_a|} \}$ and $\ShareSpec_{\Z_a} = \{\S_1, \ldots, \S_{|\Z_a|} \}$, where each $\S_r = \PartySet \setminus \mathsf{Z}_r$.
Since the $\Q^{(3)}(\PartySet, \Z_a)$ condition is satisfied and $\Discarded \in \Z_a$, it follows that $(\S_p \cap \S_q) \setminus \Discarded \neq \emptyset$.
This implies that there exists at least one non-faulty party in $(\S_p \cap \S_q)$ who can secret-share
the summand $[a]_p \cdot [b]_q$. Hence, every party in $\PartySet \setminus \Discarded$ is allowed to secret-share all the summands it is “capable" of, with special care taken to ensure
that each summand $[a]_p \cdot [b]_q$ is considered exactly once.
For this, the protocol now proceeds in “hops", where in each hop all the parties in $\PartySet \setminus \Discarded$ secret-share all the summands they are capable of, but a single
summand sharing party is finally selected for the hop through ACS. Then, all the summands which have been shared by the elected summand-sharing party
are “marked" as shared and not considered for sharing in the future hops. Moreover, a party who has already served as a summand-sharing party is not
selected in the future hops.

Technical Challenges in the Network Agnostic Setting.

The asynchronous $\BasicMult$ based on dynamically selecting summand-sharing parties
will fail in the synchronous network, since the $\Q^{(3)}$ condition need not be satisfied.
On the other hand,  synchronous $\BasicMult$ based on statically selecting summand-sharing parties will fail if a designated summand-sharing party does not secret-share the required summands,
resulting in an endless wait.
The way out is to select summand-sharing parties in three phases. We
first select summand-sharing parties dynamically in hops, following the approach of [5], till we find a subset of parties from $\ShareSpec_{\Z_s}$ which have shared all the summands
they are capable of. Then in the second phase, the remaining summands which are not yet secret-shared are statically assigned and shared by the respective designated summand-sharing
parties. To avoid an endless wait in this phase,
the parties wait only for a “fixed" time required for the parties to secret-share the assigned summands (corresponding to the time taken in a synchronous
network) and run instances of BA to identify which of the designated summand-sharing parties have shared their summands up during the second phase.
During the third phase, any “leftover" summand which is not yet shared is publicly reconstructed by reconstructing the
corresponding shares and a default sharing is taken for such summands.

The idea here is the following: all non-faulty parties will
share the summands which are assigned to them, either statically or dynamically, irrespective of the network type.
Consequently, the first phase will be always over, since the set consisting of only non-faulty parties always constitutes a candidate
set of summand-sharing parties which the parties look for to complete of the first phase.
Once the first phase is over, the second phase is bound to be over since the parties wait only for a fixed time.
The third phase is always bound to be over, once the first two phases are over, since it involves publicly reconstructing the leftover summands.
The way summands are assigned across the three phases, it will be always guaranteed that every summand is considered for sharing once in exactly one of the three phases and no summand will be left out.
The crucial point here is that the
the shares held only by the non-faulty parties never get publicly reconstructed, thus guaranteeing that the adversary does not learn any additional information about $a$ and $b$.
This is obviously true in a synchronous network because  we always have the second phase where every non-faulty party
who is not selected as a summand-sharing party during the first phase
will get the opportunity
to secret-share its assigned summands.
On the other hand, in an asynchronous network, it can be shown that all the summands which involve any share held by the non-faulty parties would have been secret-shared
during the first phase itself. In more detail, let $Z^{\star} \in \Z_a$ be the set of corrupt parties and let $\Hon = \PartySet \setminus Z^{\star}$ be the set of honest parties.
Moreover, let $S_h \in \ShareSpec_{\Z_s}$ be the group consisting of only non-faulty parties which
hold the shares $[a]_h$ and $[b]_h$.
Consider an arbitrary summand $[a]_h \cdot [b]_q$. Suppose the first phase gets over because
every party in $S_{\ell} \in \ShareSpec_{\Z_s}$
has been selected as a summand-sharing party during the first phase.
Then consider the set $(S_{\ell} \cap \Hon  \cap S_q)$, which is not empty due to
the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition.
Hence, there exists some
$P_j \in (\Hon \cap S_{\ell} \cap S_q)$,
who would have shared $[a]_h \cdot [b]_q$ when selected as a summand-sharing party during some hop in the first phase.
Due to a similar reason, any summand of the form $[a]_q \cdot [b]_h$ would have been secret-shared during the first phase itself.

§.§ Other Related Works

The domain of network agnostic cryptographic protocols is relatively new and almost all the existing works have considered threshold adversaries.
The work of  [16] presents a network agnostic cryptographically-secure atomic broadcast protocol.
The work of [45] studies
Byzantine fault tolerance and state machine replication protocols for multiple thresholds, including $t_s$ and $t_a$.
The work of [35] presents a network agnostic protocol for the task of approximate agreement using the condition
$2t_s + t_a < n$. The same condition has been used to design a network agnostic distributed key-generation (DKG) protocol in [6].
A recent work [28] has studied the problem of network agnostic perfectly-secure message transmission (PSMT) [29] over incomplete graphs.

§.§ Open Problems

There are several interesting directions to explore for network agnostic MPC protocols. Here we mention few of them.
It is not known whether the condition $3t_s + t_a < n$ (resp. $\Q^{(3, 1)}(\PartySet, \Z_s, \Z_a)$)
is necessary for the network agnostic MPC with perfect security against threshold (resp. non-threshold) adversary.
An abundant amount of research effort has been spent to improve both the theoretical as well as practical efficiency of (unconditionally-secure) SMPC and AMPC protocols.
The works of [3, 4] and this work just focus on the possibility of unconditionally-secure network agnostic MPC.
Upgrading the efficiency of these protocols to those of state of the art SMPC and AMPC protocols seems to require a significant research effort.
Even though the complexity of our MPC protocol is polynomial in $n$ and $|\Z_s|$, when instantiated for threshold adversaries (where $|\Z_s|$ has all subsets of $\PartySet$ of size up to $t_s$),
it may require an exponential (in $n$) amount of computation and communication. This is unlike the case for perfect security, where we have a network agnostic MPC
protocol against threshold adversaries
with a complexity polynomial (in $n$) [3]. Hence, designing network agnostic MPC protocol against threshold adversaries with statistical security and polynomial complexity is left as a challenging open

However, non-repudiation is not guaranteed in a synchronous network, since a potentially corrupt $\S$ may not include all the honest verifiers
in $\R$. Consequently, the verification-point of all corrupt verifiers in $\R$ may end up being not accepted, while the accepted
verification-points, revealed by the honest verifiers
in $\R$ may not be in “sufficient number" to accept the revealed $F(x)$. To deal with this, we now additionally check, if the verification-points which are not accepted
(at an appropriate time), correspond to a set of parties $\R''$ where $\R'' \in \Z_s$. And if so, then $\Receiver$ still accepts $F(x)$, if it finds a candidate $\R'$.
The protocol is presented in Fig <ref>, where all instances of broadcast happen through protocol $\BC$.

§ PRELIMINARIES AND DEFINITIONS

We assume the pair-wise secure channel model, where
the parties in  $\PartySet$ are assumed to be connected
by pair-wise secure channels.
The underlying communication network can be either synchronous or asynchronous, with parties
being unaware about the exact network type.
In a synchronous network, every message sent is delivered within a known time
In an asynchronous network, messages can be delayed arbitrarily, but finitely, with every message sent
being delivered eventually. The distrust among $\PartySet$ is modelled by a malicious (Byzantine)
adversary $\Adv$, who can corrupt a subset of the parties in $\PartySet$ and force them to behave in any
arbitrary fashion during the execution of a protocol.
The parties not under the control of $\Adv$ are called honest.
We assume
the adversary to be static, who
decides the set of corrupt parties at the beginning of the protocol execution.
As our main goal is to show the possibility of statistically-secure network agnostic MPC, we keep the formalities to a bare minimum and prove
the security of our protocols using the property-based
definition, by listing the security properties achieved by our protocols. However,
our protocols can also be proven to be secure using the more rigorous
Universal Composability (UC) definitional framework [20], without affecting their

Adversary $\Adv$ can corrupt any one subset of parties from $\Z_s$ and $\Z_a$ in synchronous
and asynchronous network respectively.
The adversary structures are monotone, implying that if $Z \in \Z_s$ ($Z \in \Z_a$ resp.), then every subset of $Z$ also belongs to
$\Z_s$ (resp. $\Z_a$).
We assume that $\Z_s$ and $\Z_a$ satisfy the conditions $\Q^{(2)}(\PartySet, \Z_s)$ and $\Q^{(3)}(\PartySet, \Z_a)$ respectively, which are necessary for
statistically-secure MPC in the synchronous and asynchronous network respectively.
Additionally, we assume that $\Z_a \subset \Z_s$. Moreover,
$\Z_s$ and $\Z_a$ satisfy the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition.

In our protocols,
all computations are done over a finite field $\F$, where $|\F| > n^5 \cdot 2^{\ssec}$ and $\ssec$ is the underlying statistical security parameter.
Looking ahead, this will ensure that the error probability in our MPC protocol is upper bounded by $2^{-\ssec}$.
Without loss of generality, we assume that each $P_i$ has an input $x_i \in \F$,
and the parties want to securely compute a function $f:\F^n \rightarrow \F$,
represented by an arithmetic circuit $\ckt$ over $\F$,
consisting of linear and non-linear (multiplication) gates, where
$\ckt$ has $c_M$ multiplication gates and a multiplicative depth of $D_M$.

We assume the existence of an unconditionally-secure public-key infrastructure (PKI),
for an unconditionally-secure signature scheme, also called pseudo-signature  [50, 34].
We briefly explain the requirements from such a setup and refer to [34] for complete formal details.
There exists a publicly known vector of public keys $(pk_1, \ldots, pk_n)$, where
each honest  $P_i$ holds the generated secret key $sk_i$, associated with $pk_i$.[Corrupt parties may choose their keys arbitrarily.]
A valid signature $\tau$ on message $m$ from $P_i$ is one for which $\mathsf{Verify}_{pk_i}(m, \tau) = 1$, where
$\mathsf{Verify}$ is the verification function of the underlying signature scheme.
For simplicity, we make the standard convention of treating signatures as idealized objects
during our protocol analysis; i.e., we assume that the signatures are
perfectly unforgeable and hence $\Adv$ will fail to forge signature of an honest party on any message, which is not signed by the party.
We also assume that the signatures are transferable and any party upon receiving a valid signature from a party can send and get it verified by any other party.
However, unlike the standard digital signatures which are computationally-secure and offer arbitrary number of transfers, pseudo-signatures offer a “limited"
number of transfers, which is typically bounded as a function of the number of parties in the protocol where pseudo-signature is used as a primitive.
We assume that the given setup supports the required number of transfers demanded by our protocols. We use $|\sigma|$ to represent the size of a pseudo-signature in bits.
If $P_i$ signs a message $m$, then we denote the resultant signed message as $\sign{m}_{i}$.

Termination Guarantees of Our Sub-Protocols:

As done in [3, 5],  for simplicity, we will not be specifying any termination criteria
for our sub-protocols. The parties will keep on participating in these sub-protocol instances even after computing
their outputs. The termination criteria of our MPC protocol will ensure the
termination of all underlying sub-protocol instances. We will be using an existing randomized ABA protocol [23]
which ensures that the
honest parties (eventually) obtain their respective output almost-surely with probability $1$.
This means that the probability that an honest party obtains its output after participating for infinitely many rounds approaches $1$ asymptotically [1, 47, 7].
That is:

\[ \underset{T \rightarrow \infty}{\mbox{lim}} \mbox{Pr}[\mbox{An honest } P_i \mbox{ obtains its output by local time } T] = 1,\]

where the probability is over the random coins of the honest parties and the adversary in the
The  property of almost-surely obtaining the output carries over to the “higher" level protocols, where
ABA is used as a building block.
We will say that the “honest parties obtain some output almost-surely from protocol $\Pi$" to mean that
every honest $P_i$ asymptotically obtains its output in $\Pi$ with probability $1$, in the above sense.

§ NETWORK AGNOSTIC UNCONDITIONALLY SECURE BYZANTINE AGREEMENT

We recall the definition of BA from [4], which is
adapted from [15, 3].

Let $\Pi$ be a protocol for $\Partyset$, where every party $P_i$ has an input $b_i \in \{0, 1\}$ and a possible output from  $\{0, 1, \bot \}$.
Moreover, let $\Adv$ be a computationally-unbounded adversary, characterized by adversary structure $\AdvStructure$, where $\Adv$ can corrupt
any subset of parties from $\AdvStructure$ during the execution of $\Pi$.

– $\AdvStructure$-Guaranteed Liveness: $\Pi$ has $\AdvStructure$-guaranteed liveness
if all honest parties obtain an output.

– $\AdvStructure$-Almost-Surely Liveness: $\Pi$ has $\AdvStructure$-almost-surely liveness
if, almost-surely, all honest parties obtain some output.

– $\AdvStructure$-Validity: $\Pi$ has $\AdvStructure$-validity if the following holds:
If all honest parties have input $b$, then every honest party with an output, outputs $b$.

– $\AdvStructure$-Weak Validity: $\Pi$ has $\AdvStructure$-weak validity if the following holds:
If all honest parties have input $b$, then every honest party with an output, outputs $b$ or $\bot$.

– $\AdvStructure$-Consistency: $\Pi$ has $\AdvStructure$-consistency
if all honest parties with an output, output the same value (which can be $\bot$).

– $\AdvStructure$-Weak Consistency: $\Pi$ has $\AdvStructure$-weak consistency
if all honest parties with an output, output either a common $v \in \{0, 1 \}$ or $\bot$.

$\Pi$ is called a $\AdvStructure$-secure synchronous BA (SBA) if, in a synchronous network, it achieves
$\AdvStructure$-guaranteed liveness, $\AdvStructure$-validity, and $\AdvStructure$-consistency.
$\Pi$ is called a $\AdvStructure$-secure
asynchronous BA (ABA) if, in an asynchronous network it has
$\AdvStructure$-almost-surely liveness,  $\AdvStructure$-validity and
$\AdvStructure$-consistency.[The seminal FLP impossibility result [32] rules out the possibility of any deterministic ABA, where there always exists a “bad" execution in which
the honest parties may keep on running the protocol forever, without obtaining any output. To circumvent this, one can opt for randomized ABA protocols and hope that the bad executions occur asmptotically
with probability $0$.]

To design our network agnostic BA protocol, we will be using a special type of broadcast protocol. We next review the definition of broadcast
from [4] which is further
adapted from [15, 3].

Let $\Pi$ be a protocol, where a designated sender $\Sender \in \Partyset$ has input $m \in \{0, 1\}^{\ell}$, and parties obtain a possible output,
including $\bot$.
Moreover, let $\Adv$ be a computationally-unbounded adversary, characterized by an adversary structure $\AdvStructure$, where $\Adv$ can corrupt
any subset from $\AdvStructure$ during $\Pi$.

– $\AdvStructure$-Liveness: $\Pi$ has $\AdvStructure$-liveness if
all honest parties obtain some output.

– $\AdvStructure$-Validity: $\Pi$ has $\AdvStructure$-validity if the following holds:
if $\Sender$ is honest, then every honest party with an output, outputs $m$.

– $\AdvStructure$-Weak Validity: $\Pi$ has $\AdvStructure$-weak validity if the following holds:
if $\Sender$ is honest, then every honest party with an output, outputs either $m$ or $\bot$.

– $\AdvStructure$-Consistency: $\Pi$ has $\AdvStructure$-consistency if the following holds:
if $\Sender$ is corrupt, then every honest party with an output, outputs a common value.

– $\AdvStructure$-Weak Consistency: $\Pi$ has $\AdvStructure$-weak consistency if the
following holds: if $\Sender$ is corrupt, then every honest party with an output, outputs a common
$m^{\star} \in \{0, 1 \}^{\ell}$ or $\bot$.

$\Pi$ is called a $\AdvStructure$-secure broadcast protocol if it has $\AdvStructure$-Liveness,
$\AdvStructure$-Validity, and $\AdvStructure$-Consistency.

We next recall a blueprint for network agnostic BA from [15, 3].

§.§ A Blueprint for Network Agnostic BA [15, 3]

To design our network agnostic BA, we assume the existence of the following sub-protocols.

– Synchronous BA with Asynchronous Guarantees: we assume the existence of a protocol $\SBA$, which is a $\Z_s$-secure SBA and which has $\Z_a$-weak validity and
$\Z_a$-guaranteed liveness in the asynchronous network. At (local) time $\TimeSBA$, all
honest parties will have an output (which could be $\bot$), irrespective of the network type.

–  Asynchronous BA with Synchronous Guarantees: we assume the existence of a protocol $\ABA$, which is a $\Z_a$-secure ABA. Moreover, in a synchronous
network, the protocol has $\Z_s$-validity, with all honest parties computing their output within time $\TimeABA = c \cdot \Delta$ in this case, for some known constant $c$.[Thus $\ABA$ has
$\Z_s$-guaranteed liveness in the synchronous network,
if all honest parties have the same input. However, if the honest parties have different inputs, then $\ABA$ need not provide guaranteed liveness or consistency guarantees in
the synchronous network.]

Based on $\SBA$ and $\ABA$, one can design a network agnostic
BA protocol $\BA$ as follows, following the blueprint of [15, 3]. The parties first invoke an instance of $\SBA$, assuming a synchronous network.
If the network is indeed synchronous, then the (honest) parties should have a binary output at time $\TimeSBA$. The parties check the same
and either switch their input to the output of $\SBA$, if it is not $\bot$, or stick to their original input. The parties then invoke an instance of $\ABA$ with “updated" inputs and the output of
$\ABA$ is set to be the overall output. The description of $\BA$, taken from [3], is presented in
Fig <ref>.

$\BA$Network agnostic BA protocol from $\SBA$ and $\ABA$. The above code is executed
by $P_i$.fig:BA

– On having input $b_i$, participate in an instance of $\SBA$ with input $b_i$ and  wait till the local time becomes
$\TimeSBA$. Let $v_i$ be the output from $\SBA$
at time $\TimeSBA$.
If $v_i \neq \bot$, then set $v_i^{\star} = v_i$.  Else set $v_i^{\star} = b_i$.

– Participate in an instance of $\ABA$ with input $v_i^{\star}$. Output the result of $\ABA$, when it is available.

Theorem <ref>, follows from [3], given that $\SBA$ and $\ABA$ achieve the stated properties. For completeness, the theorem is proved in Appendix <ref>.

Let $\Z_a \subset \Z_s$ such that $\Z_s$ and $\Z_a$ satisfy the
conditions $\Q^{(2)}(\PartySet, \Z_s)$ and $\Q^{(3)}(\PartySet, \Z_a)$ respectively.
Moreover, let
$\Z_s$ and $\Z_a$ satisfy the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition.
Then protocol $\BA$ achieves the following.[As the number of invocations of $\BA$ in our MPC protocol will be independent of
$|\ckt|$, we do not focus on its exact complexity. However, we confirm that it will be polynomial in $n$ and $|\Z_s|$.]

– Synchronous Network: the protocol is a $\Z_s$-secure SBA, where all honest parties get their output at time $\TimeBA = \TimeSBA + \TimeABA$.

– Asynchronous Network: the protocol is a $\Z_a$-secure ABA.

We now proceed to instantiate protocols $\SBA$ and $\ABA$.

§.§ $\SBA$: Synchronous BA with Asynchronous Weak Validity and Guaranteed Liveness

To design protocol $\SBA$, we again follow the blueprint of [3], which design $\SBA$ based on three components.

§.§.§ SBA with Asynchronous Guaranteed Liveness

The first component for designing $\SBA$ is an SBA protocol, which has just guaranteed liveness in an asynchronous network.
In [50], the authors have presented an SBA protocol against threshold adversaries, tolerating up to $t_s < n/2$ faults.
The protocol which we denote as $\PiPW$, modifies the
Dolev-Strong BA protocol [30], by replacing digital signatures with
pseudo-signatures. We note that $\PiPW$ can be easily generalized, if $\Z_s$ satisfies the $\Q^{(2)}(\PartySet, \Z_s)$ condition.
To achieve guaranteed liveness in an asynchronous network, the parties run the protocol till the supposed timeout in the synchronous network and check if any output is computed
and in case no output is computed, $\bot$ is taken as the output.
Since the protocol is an easy generalization of the existing protocol against threshold adversaries,
protocol $\PiPW$ and proof of Lemma <ref> are available in Appendix <ref>.

Protocol $\PiPW$ achieves the following, where
$t$ is the cardinality of the maximum-sized subset in $\Z_s$.

– Synchronous Network: The protocol is a $\Z_s$-secure SBA protocol, where all honest parties compute their output at time $\TimePW \defined (t + 1) \cdot \Delta$.

– Asynchronous Network: The protocol achieves $\Z_a$-guaranteed liveness, where all honest parties compute their output at time $\TimePW$.

– Communication Complexity: $\Order(n^4 \cdot \ell \cdot |\sigma|)$ bits are sent by the honest parties, if the inputs of the parties are of size $\ell$ bits.

§.§.§ Asynchronous Broadcast with Synchronous Guarantees

The second component for designing $\SBA$ is an asynchronous broadcast protocol $\Acast$ (also called Acast), which provides
liveness, validity and a “variant" of consistency in a synchronous
network. The variant guarantees that if $\Sender$ is corrupt
and the honest parties compute an output in a synchronous network, then they may not do it at the same time
and there might be a gap in the time at which the honest parties compute an output.
In [43, 4], an instantiation of $\Acast$ is provided against
$\Q^{(3)}$ adversary structures.[The protocol is a generalization of the classic Bracha's threshold Acast protocol [18], tolerating
$t < n/3$ corruptions.]
Unfortunately, the protocol fails to provide any security guarantees in a synchronous network against $\Q^{(2)}$
adversary structures. So we provide a different instantiation of Acast for our setting (see Fig <ref>). The protocol is obtained by generalizing the ideas used in the
broadcast protocol of [46]. The protocol of [46] uses a computational PKI, which we replace with
an unconditional PKI. The protocol consists of three phases and each (honest) party executes a phase at most once.

$\Acast(\Sender, m, \Z_s, \Z_a)$Asynchronous broadcast with synchronous guarantees. The above code is executed by each
$P_i \in \PartySet$ including the designated sender $\Sender$fig:Acast

Each $P_i \in \PartySet$ executes each of the following phases at most once.

* (Propose): If $P_i = \Sender$, then on having the input $m$, send
$\sign{(\propose, m)}_{\Sender}$ to all the parties.

* (Vote): Upon receiving the first $\propose$ message
$\sign{(\propose, m)}_{\Sender}$
from $\Sender$ with valid signature, send $\sign{(\propose, m)}_{\Sender}$ to all the parties
wait till the local time increases by $\Delta$. If
$\sign{(\propose, m')}_{\Sender}$ is not received from any party where $m' \neq m$, then send
$\sign{(\vote, m)}_i$ to all the parties.

* (Output): Upon receiving a $\vote$ message $\sign{(\vote, m)}_{j}$ with valid
signature corresponding to every $P_j \in \PartySet \setminus Z$ for some $Z \in \Z_s$, do the following:

– Let $\cert{m}$ denote the collection of signed $\sign{(\vote, m)}_{j}$ messages.

– Send $\cert{m}$ to all the parties and output $m$.

The proof of Lemma <ref> is available in Appendix <ref>.

Protocol $\Acast$ achieves the following properties.

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

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

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

Terminologies for Using $\Acast$.

In the protocol $\Acast$, any party from $\PartySet$ can be designated as $\Sender$. In the rest of the paper
we will say that “$P_i$ Acasts $m$" to mean that $P_i$ acts as $\Sender$ and
invokes an instance of $\Acast$ with input m, and the parties participate in this instance. Similarly,
“$P_j$ receives $m$ from the Acast of $P_i$" means that $P_j$ outputs $m$ in the corresponding instance of $\Acast$.

§.§.§ Synchronous Broadcast with Asynchronous Guarantees

The third component for designing $\SBA$ is a broadcast protocol $\BC$, which is secure in a synchronous network and which also provides
liveness, weak validity and
weak consistency in an asynchronous network.  Note that the guarantees
of $\BC$ are different from that of $\Acast$. The design of $\BC$ is based on the idea from [4],
by carefully combining protocols $\Acast$ and $\PiPW$.
In the protocol, $\Sender$ first Acasts
its message. If the network is synchronous, then at time $3\Delta$, all honest parties should have an output.
To confirm this, the parties start participating in an instance of $\PiPW$, with whatever output has been obtained from
the $\Acast$ instance at time $3\Delta$;
in case no output is obtained, then the input is $\bot$.
Finally, at time $3\Delta + \TimePW$, the parties output
an $m^{\star}$, if it is the output of the $\Acast$ instance as well as the output of $\PiPW$, else the output of the parties will be $\bot$.
We recall the description of $\BC$ from [4] and present it in Fig <ref>.

Protocol $\BC$ as a Network Agnostic Secure Broadcast.

Protocol $\BC$ only guarantees weak validity and weak consistency  in an asynchronous network, since
only a subset of honest parties may receive $\Sender$'s message from the Acast of $\Sender$ within time $3\Delta + \TimePW$.
Note that maintaining the time-out is essential, as we need liveness from
$\BC$ (irrespective of the network type) when
used later in protocol $\SBA$.
Looking ahead, we will use $\BC$ in our VSS protocol for broadcasting values.
The weak validity and consistency may lead to a situation
where, in an asynchronous network,
one subset of honest parties may output a value different from $\bot$ at the end of the time-out $3\Delta + \TimePW$, while
others may output $\bot$. For the security of the VSS protocol, we would require the latter category of parties
to eventually output the common non-$\bot$ value if the parties continue participating in $\BC$.
Following [3, 4], we
make a provision for this in $\BC$. Namely,
$P_i$ who outputs $\bot$ at time $3\Delta + \TimePW$ “switches" its output to $m^{\star}$, if
$P_i$ eventually receives $m^{\star}$ from $\Sender$'s Acast.
We stress that this switching is only for the parties who obtained $\bot$
at time $3\Delta + \TimePW$.
To differentiate between the two ways of obtaining output, we use the terms regular-mode
and fallback-mode. Regular-mode is the process of deciding the output at time $3\Delta + \TimePW$, while
fallback-mode is the process of deciding the output beyond time $3\Delta + \TimePW$.

$\BC(\Sender, m, \Z_s, \Z_a)$Synchronous broadcast with asynchronous guarantees.fig:BC

(Regular Mode)

–  Sender $\Sender$ on having the input $m$, Acasts $m$.

–  At time $3\Delta$, each $P_i \in \Partyset$ participates in an instance of $\PiPW$, where the input of $P_i$ is $m^{\star}$ if
$m^{\star} \in \{0, 1\}^{\ell}$ is received from the Acast of
$\Sender$, else the input is $\bot$.

– (Local Computation):  At time $3\Delta + \TimePW$, each $P_i \in \Partyset$ does the following.

– If some $m^{\star} \in \{0, 1 \}^{\ell}$ is received from the Acast of $\Sender$ and $m^{\star}$ is
computed as the output during the instance of $\PiPW$, then output $m^{\star}$.
Else output $\bot$.

(Fallback Mode)

–  Each $P_i \in \Partyset$ who outputs $\bot$ at time $3\Delta + \TimePW$,
changes it to $m^{\star}$, if $m^{\star}$ is received from Acast of $\Sender$.

Theorem <ref> follows from [4] and is proved in
Appendix <ref>.

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

– Synchronous network:

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

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

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

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

– Asynchronous Network:

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

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

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

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

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

In the rest of the paper, we use the following terminologies while using $\BC$.

Terminologies for $\BC$:

We say that  $P_i$ broadcasts $m$ to mean that $P_i$ invokes an instance of
$\BC$ as  $\Sender$
with input $m$, and the parties participate in this instance. Similarly, we say that $P_j$ receives $m$ from the broadcast
of $P_i$ through regular-mode (resp. fallback-mode),
to mean that $P_j$ has the output $m$
at time $\TimeBC$ (resp. after time $\TimeBC$)
during the instance of $\BC$.

§.§.§ $\BC \rightarrow \SBA$

Finally, using $\BC$ we instantiate protocol $\SBA$, following the
blueprint of [4].
In the protocol, every party broadcasts its input bit (for $\SBA$) through an instance of $\BC$.
At time $\TimeBC$, the parties check if “sufficiently many"  instances of $\BC$ have produced a binary output
(which should have happened in a synchronous network) and if so, they output the “majority" of those values.
Otherwise, the network is asynchronous, in which case the parties output $\bot$.
The description of $\SBA$ is recalled from [4] and presented in Fig <ref>.

$\SBA(\Z_s, \Z_a)$Synchronous BA with asynchronous guaranteed liveness and weak validity.
The above code is executed by every $P_i \in \PartySet$.fig:SBA

On having input $b_i \in \{0, 1 \}$, broadcast $b_i$.

– For $j = 1, \ldots, n$, let $b_i^{(j)} \in \{0, 1, \bot \}$ be received from the broadcast of $P_j$ through  regular-mode.
Include $P_j$ to a set $\R$ if $b_i^{(j)} \neq \bot$.

– If
$\PartySet \setminus \R \in \Z_s$, then compute the output as follows.

– If there exists a subset of parties $\R_i \subseteq \R$, such that $\R \setminus \R_i  \in \Z_s$
and $b_i^{(j)} = b$ for all the parties $P_j \in \R_i$, then output
$b$.[If there are multiple such $\R_i$, then break the tie using some
pre-determined rule.]

– Else output $1$.

– Else output $\bot$.

Theorem <ref> follows from [4] and is  proved in Appendix <ref>.

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

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

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

§.§ $\ABA$: Asynchronous BA with Synchronous Validity

To the best of our knowledge, the only known unconditionally-secure ABA protocol is due to [23], which generalizes the framework of
randomized ABA [51, 11, 21, 31] against general adversaries. The protocol of [23] uses a graded agreement (GA) protocol (also known as the vote protocol),
along with a secure coin-flip protocol. Unfortunately, both these primitives provide security (in an asynchronous network) against $\Q^{(3)}$ adversary structures
and fail to provide any security guarantees against $\Q^{(2)}$ adversary structures in a synchronous network. Consequently, the ABA protocol of [23] fails
to provide any security guarantees in a synchronous network against $\Q^{(2)}$ adversary structures.[Recall that we need validity, coupled with guaranteed liveness  from
$\ABA$, when used in our network agnostic BA protocol $\BA$.] We give a different instantiation of $\ABA$ by generalizing a few ideas used in [15]. Our instantiation of $\ABA$ is based
on following two components.

Component I: Asynchronous Graded Agreement with Synchronous Validity.

We assume the existence of a GA protocol $\Vote$, where each party has a binary input. The output for each party is a value from $\{0, 1, \bot \}$, along with a grade from $\{0, 1, 2\}$.
The protocol achieves the following properties.

– Asynchronous Network — The following properties are achieved, even if the adversary corrupts any subset from $\Z_a$: (a): $\Z_a$-Liveness: If all honest parties participate in the protocol, then each honest party eventually obtains an output.
(b) $\Z_a$-Graded Validity: If every honest party's input is $b$, then all honest parties with an output, output $(b, 2)$.
(c) $\Z_a$-Graded Consistency: If two honest parties output grades $g, g'$, then $|g - g'| \leq 1$ holds; moreover,
if two honest parties output $(v, g)$ and $(v', g')$ with $g, g' \geq 1$, then $v = v'$.

– Synchronous Network — The following properties are achieved, even if the adversary corrupts any subset from $\Z_s$: (a): $\Z_s$-Liveness:
If all honest parties participate in the protocol with the same input, then after some fixed time $\TimeVote$,
all honest parties obtain an output.
(b) $\Z_s$-Graded Validity: If every honest party's input is $b$, then all honest parties with an output, output $(b, 2)$.

Note that we do not require any form of consistency from $\Vote$ in the synchronous network.
We give an instantiation of $\Vote$ with the $\Q^{(2, 1)}(\PartySet, \Z_s, \Z_a)$ condition, by generalizing the threshold GA protocol of [15] with condition $2t_s + t_a < n$, such that
$\TimeVote = 4 \cdot \Delta$.
The protocol of [15] uses digital signatures (hence, is computationally secure),
which we replace with pseudo-signatures.
For the description of $\Vote$ and its properties, see Appendix <ref>.

Component II: Asynchronous Coin-Flipping with Synchronous Liveness.

We assume the existence of a $p$-coin-flipping protocol $\CoinFlip$, where $0 < p < 1$ is a parameter.
In the protocol, the parties participate with random inputs and the output of each party is a bit satisfying the following properties.

– Asynchronous Network: The following properties are achieved even if the adversary corrupts any subset from $\Z_a$: (a): $\Z_a$-Almost-Surely Liveness:
If all honest parties participate in the protocol, then almost-surely, all honest parties eventually get an output.
(b): $(\Z_a, p)$-Commonness: With probability $p$, the output of all honest parties is a random bit $b \in \{0, 1 \}$.

– Synchronous Network: The following property is achieved even if the adversary corrupts any subset from $\Z_s$: (a): $\Z_s$-Guaranteed Liveness:
If all honest parties participate in the protocol, then all honest parties get an output, after some fixed time $\TimeCoinFlip$.

In [23], the authors presented an instantiation of $\CoinFlip$, which achieves $\Z_a$-Almost-Surely Liveness as well as $(\Z_a, p)$-Commonness in an asynchronous network,
where $p = \frac{1}{n}$, provided $\Z_a$ satisfies the $\Q^{(3)}(\PartySet, \Z_a)$ condition. The protocol incurs an expected communication of $\Order(\poly(n, |\Z_s|, \log{|\F|}))$ bits.
Interestingly, the protocol also achieves $\Z_s$-Guaranteed Liveness in a synchronous network, irrespective of $\Z_s$.
Namely, after time $\TimeCoinFlip =  20 \cdot \Delta$, all honest parties will have an output,
with (honest)
parties communicating $\Order(\poly(n, |\Z_s|, \log{|\F|}))$ bits.

§.§.§ $\Vote + \CoinFlip \rightarrow \ABA$

Once we have instantiations of $\Vote$ and $\CoinFlip$, we can easily combine it using the framework of [51, 11, 21, 31] to get the protocol $\ABA$.
The protocol consists of several iterations, where in each iteration, the parties run two instances of $\Vote$, along with an instance of $\CoinFlip$.
Using the first instance of $\Vote$, the parties check if they all have the same input. Independent of this finding, they then run an instance of $\CoinFlip$. Finally, they again run an instance of
$\Vote$, with inputs being carefully chosen. Namely, if a party obtained an output with the highest grade from the first instance of $\Vote$, then it participates with this input,
else it participates with the coin-output. Finally, based on the output received from the second instance of $\Vote$, the parties update their input for the next iteration as follows:
if a bit with a non-zero grade is obtained, then it is set as the updated input, else the updated input is set to the input of the second instance of $\Vote$.
During each iteration, the parties keep a tab on whether they have received an output bit with the highest grade from the second instance of $\Vote$, in which case, they
indicate it to the others by sending a signed $\ready$ message and the bit. Once “sufficiently many" parties send the same signed $\ready$ bit, it is taken as the output of the protocol.

The idea here is that if the honest parties start an iteration with the same input bit $b$, then the output of $\CoinFlip$ is not considered
(irrespective of the network type) and all instances of $\Vote$ output $(b, 2)$. Thus, all honest parties will send a signed $\ready$ message for $b$. Consequently, all honest parties will output $b$.
This ensures validity, coupled with guaranteed liveness, both in synchronous and asynchronous networks.
On the other hand, if the honest parties start an iteration with different inputs, then with probability at least $p \cdot \frac{1}{2} = \frac{1}{n} \cdot \frac{1}{2}$, all of them will have the
same input for the second instance of $\Vote$. And consequently, all honest parties will have the same input from the next iteration onward and consistency is achieved
(in the asynchronous network).
The description of $\ABA$ based on $\Vote$ and $\CoinFlip$ is recalled from [23] and presented in Fig <ref>.

$\ABA(\PartySet, \Z_s, \Z_a)$The ABA protocol. The above code is executed by every $P_i \in \PartySet$ with input $b_i$fig:ABA

* Initialisation: Set $b = b_i$, $\committed = \false$ and $k=1$. Then do the

* Participate in an instance of $\Vote$ protocol with input $b$ and  wait for time $\TimeVote$.

* Once an output $(b, g)$ is received from the instance of $\Vote$, participate in an
instance of $\CoinFlip$ and  wait for time $\TimeCoinFlip$. Let $\Coin_k$ denote the output received from $\CoinFlip$.

* If $g < 2$, then set $b = \Coin_k$.

* Participate in an instance of $\Vote$ protocol with input $b$ and  wait for time $\TimeVote$. Let $(b', g')$ be
the output received. If $g' > 0$, then set $b = b'$.

* If $g' = 2$ and $\committed = \false$, then set $\committed = \true$ and send
$\sign{(\ready, b)}_i$ to all the parties.

* Set $k = k + 1$ and repeat from $1$.

* Output Computation:

– Upon receiving  $\sign{(\ready, b)}_j$ messages with valid signatures corresponding to every $P_j \in \PartySet \setminus Z$ for some $Z \in \Z_s$, send
$(b,\cert{b})$ to all the parties and
output $b$. Here $\cert{b}$ denotes the collection of signed $\sign{(\ready, b)}_j$ messages.

– Upon receiving $(b, \cert{b})$ where $\cert{b}$ has valid signatures  corresponding to every $P_j \in \PartySet \setminus Z$ for some $Z \in \Z_s$,
send $(b, \cert{b})$ to all the parties and
output $b$.

Theorem <ref> follows from [15] and is proved in Appendix <ref>.

Protocol $\ABA$ achieves the following where $\TimeABA = \TimeCoinFlip + 2\TimeVote + \Delta$.

– Synchronous Network: If all honest parties have the same input $b \in \{ 0, 1\}$, then all honest parties output $b$,
at time $\TimeABA$. Moreover, $\Order(\poly(n, |\Z_s|, \log{|\F|}))$ bits
are communicated by the honest parties.

– Asynchronous Network: the protocol is a $\Z_a$-secure ABA, incurring an expected communication of $\Order(\poly(n, |\Z_s|, \log{|\F|}))$ bits.

§ NETWORK AGNOSTIC INFORMATION CHECKING PROTOCOL

In this section, we present our network agnostic ICP protocol (Fig <ref>). A detailed overview of the protocol has been already presented in Section <ref>.
The protocol consists of two subprotocols $\Auth$ and $\Reveal$, implementing the authentication and revelation phase respectively,
where the parties participate in the revelation phase only upon completing the authentication phase.
During the authentication phase, $\mathsf{S}$ distributes the authentication and verification information, followed by parties publicly verifying the consistency of distributed information and once the consistency is established, the
authentication phase is over. During the revelation phase, $\mathsf{I}$ reveals the IC-signature which is verified by $\mathsf{R}$ with respect to the verification information revealed by a “selected" subset of the verifiers.

$\ICP(\PartySet, \Z_s, \Z_a, \mathsf{S},\mathsf{I},\mathsf{R})$The network-agnostic ICPfig:ICP

Protocol $\Auth(\PartySet,\Z_s, \Z_a, \mathsf{S},\mathsf{I},\mathsf{R},s)$: $t \defined \max\{ |Z| :  Z \in \AdvStruct_s 	\}$

– Distributing Data: $\mathsf{S}$ executes the following steps.

* Randomly select $t$-degree signing-polynomial $F(x)$ and $t$-degree masking-polynomial $M(x)$,
where $F(0) = s$.
For $i = 1,\ldots,n$, randomly select $\alpha_i \in \F \setminus \{0\}$, and compute
$v_i = F(\alpha_i)$ and $m_i = M(\alpha_i)$.

* Send $(F(x), M(x))$ to $\mathsf{I}$. For $i = 1, \ldots, n$,
send $(\alpha_i, v_i, m_i)$ to party $P_i$.

– Confirming Receipt of Verification Points: Each party $P_i$ (including $\mathsf{S}, \mathsf{I}$ and $\mathsf{R}$), upon receiving $(\alpha_i, v_i, m_i)$ from $\mathsf{S}$, broadcasts $(\Received,i)$.

– Announcing Set of Supporting Verifiers: only $\S$ does the following.

* Initialize the set of supporting verifiers $\R$ to $\emptyset$, and  wait till the local time is $\Delta + \TimeBC$.
Upon receiving $(\Received,i)$ from the broadcast of $P_i$,
add $P_i$ to $\R$. Once $\PartySet \setminus \R \in \AdvStructure_s$, broadcast the set $\R$.

– Announcing Masked Polynomial: only $\INT$ does the following.

*  Wait till the local time is $\Delta + 2\TimeBC$. Upon receiving $\R$ from the broadcast of $\mathsf{S}$ such that $\PartySet \setminus \R \in \Z_s$,
wait till $(\Received,i)$ is received from the broadcast of every
$P_i \in \R$. Then randomly pick $d \in \F \setminus \{0\}$ and broadcast $(d,B(x))$, where $B(x) \defined dF(x) + M(x)$.

– Announcing Validity of Masked Polynomial: only $\S$ does the following.

*  Wait till the local time is $\Delta + 3\TimeBC$. Upon receiving $(d,B(x))$ from the broadcast of $\mathsf{I}$,
broadcast $\OK$, if $B(x)$ is a $t$-degree polynomial and if
$dv_j + m_j = B(\alpha_j)$ holds
for every $P_j \in \R$.

– Deciding Whether Authentication is Successful: each $P_i \in \PartySet$ (including $\mathsf{S}, \mathsf{I}$ and $\mathsf{R}$)  waits till the local time is $\Delta + 4\TimeBC$.
Upon receiving $\R$ and $(d, B(x))$ from the broadcast of $\mathsf{S}$ and $\mathsf{I}$ respectively, where $\PartySet \setminus \R \in \Z_s$,
it set the variable $\authCompleted_{(\S, \INT, \Receiver)}$ to $1$ if $\OK$ is received from the broadcast of $\mathsf{S}$.
Upon setting $\authCompleted_{(\S, \INT, \Receiver)}$ to $1$, $\INT$ sets
$\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s) = F(x)$.

Protocol $\Reveal(\PartySet,\AdvStructure_s, \AdvStructure_a, \mathsf{S},\mathsf{I},\mathsf{R},s)$

– Revealing Signing Polynomial and Verification Points:  Each party $P_i$ (including $\mathsf{S}, \mathsf{I}$ and $\mathsf{R}$)
does the following, if
$\authCompleted_{(\S, \INT, \Receiver)}$ is set to $1$.

* If $P_i = \mathsf{I}$ then send
$F(x)$ to $\mathsf{R}$, if $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$ is set to $F(x)$ during $\Auth$.

* If $P_i \in \R$, then send $(\alpha_i, v_i, m_i)$ to $\mathsf{R}$.

– Accepting the IC-Signature: The following steps are executed only by $\mathsf{R}$, if
$\authCompleted_{(\S, \INT, \Receiver)}$ is set to $1$  during the protocol $\Auth$.

–  Wait till the local time becomes a multiple of $\Delta$.
Upon receiving $F(x)$ from $\mathsf{I}$, where $F(x)$ is a $t$-degree polynomial, proceed as follows.

1. If $(\alpha_i, v_i, m_i)$ is received from $P_i \in \R$, then accept $(\alpha_i, v_i, m_i)$ if either
$v_i = F(\alpha_i)$ or $B(\alpha_i) \neq dv_i + m_i$, where $B(x)$ is received from the broadcast of $\mathsf{I}$ during $\Auth$. Otherwise,
reject $(\alpha_i, v_i, m_i)$.

2. Wait till a subset of parties $\R' \subseteq \R$ is found, such that $\R \setminus \R' \in \AdvStruct_s$,
and for every $P_i \in \R'$, the corresponding revealed point $(\alpha_i, v_i, m_i)$ is accepted. Then, output $s = F(0)$.

The proof of Theorem <ref> is available in Appendix <ref>.

Protocols $(\Auth, \Reveal)$ satisfy the following properties, except with
probability at most $\errorAICP \defined \frac{nt}{|\F| - 1}$, where
$t = \max\{ |Z| :  Z \in \Z_s \}$.

– If $\mathsf{S}, \mathsf{I}$ and $\mathsf{R}$ are honest, then the following hold.

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

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

– Privacy: The view of $\Adv$ is independent of $s$, irrespective of the network.

– Unforgeability: If $\mathsf{S}, \mathsf{R}$ are honest, $\mathsf{I}$ is corrupt
and if $\mathsf{R}$ outputs $s' \in \F$ during $\Reveal$, then $s' = s$ holds, irrespective of the network type.

– If $\mathsf{S}$ is corrupt, $\mathsf{I}, \mathsf{R}$ are honest
and if $\mathsf{I}$ sets $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s) = F(x)$ during $\Auth$, then the following holds.

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

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

– Communication Complexity: Irrespective of the network type, $\Auth$ incurs a communication of $\Order(n^5 \cdot \log{|\F|} \cdot |\sigma|)$ bits, while
$\Reveal$ incurs a communication of $\Order(n \cdot \log{|\F|})$ bits.

Looking ahead, in our VSS protocols, there will be several instances of ICP running, with different parties playing the role of $\S, \INT$ and $\Receiver$. It will be convenient to use the following notations while invoking instances of

[for ICP]

While using $(\Auth, \Reveal)$, we will say that:

– “$P_i$ gives  $\ICSig(P_i, P_j, P_k, s)$ to $P_j$" to mean that $P_i$ acts as $\mathsf{S}$ and invokes an instance of
$\Auth$ with input $s$, where $P_j$ and $P_k$ play the role of $\mathsf{I}$ and $\mathsf{R}$ respectively.

–  “$P_j$ receives $\ICSig(P_i, P_j, P_k, s)$ from $P_i$" to mean that
$P_j$, as $\mathsf{I}$, has set
$\authCompleted_{(P_i, P_j, P_k)}$ to $1$
and $\ICSig(P_i, P_j, P_k, s)$ to some $t$-degree polynomial with $s$ as the constant term
during the instance of $\Auth$, where $P_i$ and $P_k$
play the role of $\mathsf{S}$ and $\mathsf{R}$ respectively.

– “$P_j$ reveals $\ICSig(P_i, P_j, P_k, s)$ to $P_k$" to mean $P_j$, as $\mathsf{I}$, invokes an instance
of $\Reveal$, with $P_i$ and $P_k$ playing the role of $\mathsf{S}$
and $\mathsf{R}$ respectively.

– “$P_k$ accepts $\ICSig(P_i, P_j, P_k, s)$" to mean that
$P_k$, as $\mathsf{R}$, outputs $s$ during the instance of $\Reveal$,
invoked by $P_j$ as $\mathsf{I}$, with $P_i$ playing the role of $\mathsf{S}$.

§.§ Linearity of IC Signature

Our ICP satisfies the linearity property, provided “special care" is taken while generating the IC-signatures. In more detail,
consider a fixed $\mathsf{S}, \mathsf{I}$ and $\mathsf{R}$ and let $s_a$ and $s_b$ be two values, such that $\mathsf{I}$ has received $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s_a)$ and
$\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s_b)$ from $\mathsf{S}$,
through instances $\Auth^{(a)}$ and $\Auth^{(b)}$ of $\Auth$ respectively, where all the following conditions are satisfied.

– Supporting verifiers $\R_a$ and $\R_b$, during $\Auth^{(a)}$ and $\Auth^{(b)}$, are the same.

– For $i = 1, \ldots, n$, corresponding to the verifier $P_i$, $\mathsf{S}$ has used the same $\alpha_i \in \F \setminus \{0\}$, to compute the verification points, during
$\Auth^{(a)}$ and $\Auth^{(b)}$

– $\mathsf{I}$ has used the same linear combiner $d \in \F \setminus \{ 0\}$ during the instances $\Auth^{(a)}$ and $\Auth^{(b)}$, to compute the linearly-combined masked polynomials.

Let $s \defined c_1 \cdot s_a + c_2 \cdot s_b$, where $c_1, c_2$ are publicly known constants from $\F$. It then follows that if all the above conditions are satisfied, then $\INT$
can locally compute $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$ from $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s_a)$ and $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s_b)$.
Namely, $\INT$ can set $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s) = c_1 \cdot \ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s_a) + c_2 \cdot \ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s_b)$.
On the other hand, let the verifier $P_i \in \R_a$ hold the verification points $(\alpha_i, v_{a, i}, m_{a, i})$ and $(\alpha_i, v_{b, i}, m_{b, i})$, corresponding to
$\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s_a)$ and $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s_b)$ respectively. Then
$P_i$ can locally compute $(\alpha_i, v_i, m_i)$ as its verification point corresponding to $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$, where
$v_i = c_1 \cdot v_{a, i} + c_2 \cdot v_{b, i}$ and $m_i = c_1 \cdot m_{a, i} + c_2 \cdot m_{b, i}$. During the protocol $\Reveal$,
to reveal $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$,
the intermediary $\INT$
can reveal $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$ to $\Receiver$, while each verifier $P_i \in \R_a$ can reveal the verification information $(\alpha_i, v_i, m_i)$.
To accept $(\alpha_i, v_i, m_i)$, the receiver $\Receiver$ either checks for the “consistency" of $(\alpha_i, v_i)$ with $\ICSig(\mathsf{S}, \mathsf{I}, \mathsf{R}, s)$,
or the “inconsistency" of masked polynomial $B(x) \defined c_1 \cdot B_a(x) + c_2 \cdot B_b(x)$ with $(d, v_i, m_i)$; here
$B_a(x)$ and $B_b(x)$ denote the masked polynomials, made public by $\INT$, during the instances $\Auth^{(a)}$ and $\Auth^{(b)}$ respectively, both computed with respect to the linear
combiner $d$.

Looking ahead, we will require the linearity property from ICP, when used in our VSS protocols, where there will be multiple instances of $\Auth$ running, involving the same
$(\S, \INT, \Receiver)$ triplet.
To achieve this, we will ensure that in all the $\Auth$ instances invoked during VSS
involving the same triplet  $(\S, \INT, \Receiver)$, the signer uses the same non-zero evaluation point $\alpha_{\S, \INT, \Receiver, i}$ for the verifier $P_i$, while distributing
verification information to $P_i$, as part of the respective $\Auth$ instances. Similarly, $\S$ should find and
make public a common set of supporting verifiers $\R$, on behalf of all the instances of $\Auth$.
And finally, $\INT$ should use the same non-zero random linear combiner $d$, to compute the masked polynomials for all the instances of $\Auth$ and once computed, it should together
make public
$d$ and the masked polynomials for all the instances of $\Auth$.

In the rest of the paper, we will use the term “parties follow linearity principle while generating IC-signatures", to mean
that the underlying instances of $\Auth$ are invoked as above.

§.§ Default IC Signature

In our VSS protocols, we will also encounter situations where some publicly known value $s$ and a triplet $(\S, \INT, \Receiver)$ exist. Then $\INT$ can
locally compute $\ICSig(\S, \INT, \Receiver, s)$ by setting $\ICSig(\S, \INT, \Receiver, s)$ to the constant polynomial $F(x) = s$. Each verifier $P_i \in \PartySet$ locally sets $(\alpha_{\S, \INT, \Receiver, i}, v_i, m_i)$ as its verification information, where $v_i = m_i = s$.
Moreover, the set of supporting verifiers $\R$ is set as $\PartySet$.
Notice that the way in which $\ICSig(\S, \INT, \Receiver, s)$ and the verification information is set guarantees that, later, if an honest $\INT$ reveals
$\ICSig(\S, \INT, \Receiver, s)$ to an honest $\Receiver$ during $\Reveal$, then $\Receiver$ always outputs $s$.

In the rest of the paper, we will use the term “parties set $\ICSig(\S, \INT, \Receiver, s)$ to the default value", to mean the above.

§ NETWORK AGNOSTIC VERIFIABLE SECRET SHARING (VSS)

This section presents our network-agnostic VSS protocol, which allows a designated dealer to generate a linear secret-sharing with IC-signatures for its input. We first define the notion of linear
secret-sharing with IC-signatures.

A value $s \in \F$ is said to be linearly secret-shared with IC-signatures, if there exist shares $s_1, \ldots, s_{|\Z_s|} \in \F$ where $s = s_1 + \ldots + s_{|\Z_s|}$. Moreover, for $q = 1, \ldots, |\Z_s|$,
there exists some publicly-known core-set $\W_q \subseteq S_q$, such that all the following hold.

– $\Z_s$ satisfies the $\Q^{(1)}(\W_q, \Z_s)$ condition and
all (honest) parties in the set $S_q$ have the share $s_q$.

– Every honest $P_i \in \W_q$ has the IC-signature
$\ICSig(P_j, P_i, P_k, s_q)$ of every $P_j \in \W_q$ for every $P_k \not \in S_q$.
Moreover, if any corrupt $P_j \in \W_q$ has $\ICSig(P_j, P_i, P_k, s'_q)$ of any honest $P_i \in \W_q$ for any $P_k  \not \in S_q$, then
$s'_q = s_q$ holds. Furthermore, all the underlying IC-signatures satisfy the linearity property.

The vector of information corresponding to a linear secret-sharing with IC-signature of $s$ is denoted by $[s]$, which includes the share $s_1, \ldots, s_{|\Z_s|}$, the core sets $\W_1, \ldots, \W_{|\Z_s|}$
and IC-signatures $\{ \ICSig(P_j, P_i, P_k, s_q) \}_{P_j, P_i \in \W_q, P_k  \not \in S_q}$. For convenience, we denote the $q^{th}$ share of $s$, corresponding to $S_q$, by

A vector of values $\vec{S} = (s^{(1)}, \ldots, s^{(L)})$ where $L \geq 1$ is said to be linearly secret-shared with IC-signatures, if each $s^{(\ell)} \in \vec{S}$ is linearly secret-shared with IC-signatures
and if there exist common core sets $\W_1, \ldots, \W_{|\Z_s|}$, corresponding to the secret-sharings $[s^{(1)}], \ldots, [s^{(\ell)}]$.

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

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

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

§.§ The VSS Protocol

We present a network-agnostic VSS protocol $\VSS$ (Fig <ref>). In the protocol, there exists a designated dealer $\D \in \PartySet$ with input $s$ (the protocol can be easily generalized if
$\D$ has $L$ inputs). The protocol allows $\D$ to “verifiably" generate a linear secret-sharing of
$s$ with IC-signatures. In a synchronous network, the (honest) parties output
$[s]$ after a “fixed" time, while in an asynchronous network, they do so eventually, such that
$s$ remains private. The verifiability here guarantees that if $\D$ is corrupt and some honest party gets an output, then there exists some value, say $s^{\star}$ (which could be different from $s$),
such that $s^{\star}$ is linearly secret-shared with IC-signatures. Note that in this case, we cannot bound the time within which $s^{\star}$ will be secret-shared, since a potentially corrupt $\D$ may delay sending the
required messages and the parties will not be knowing the exact network type. A detailed overview of the protocol has been already presented in Section <ref> and so we directly present the protocol.

$\VSS(\D, \Z_s, \Z_a, s, \SharingSpec_{\Z_s})$The network agnostic VSS protocolfig:VSS

– Distribution of Shares: $\D$,
on having input $s$, randomly chooses $s_1,\dots,s_{|\Z_s|} \in \F$,
such that $s = s_1 + \dots + s_{|\Z_s|}$. It then sends $s_q$ to all $P_i \in S_q$, for $q = 1, \ldots, |\Z_s|$.

– Exchanging IC-Signed Values: Each $P_i \in \PartySet$ (including $\D$),  waits till the local time becomes $\Delta$.
Then, for each $S_q \in \ShareSpec_{\Z_s}$ such that $P_i \in S_q$,
upon receiving $s_{qi}$ from $\D$,  give $\ICSig(P_i, P_j, P_k, s_{qi})$ to every $P_j \in S_q$,  for every $P_k \in \PartySet$, such that  the parties
follow the linearity principle while generating IC-signatures (see Section <ref>).

– Announcing Results of Pairwise Consistency Tests:
Each $P_i \in \PartySet$ (including $\D$)  waits till the local time becomes $\Delta + \TimeAuth$
and then does the following.

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

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

– Constructing Consistency Graph: Each $P_i \in \PartySet$ (including $\D$)  waits till the local time becomes $\Delta + \TimeAuth + \TimeBC$
and then constructs an undirected consistency graph $G^{(i)}$ with $\PartySet$ as the vertex set, where
the edge $(P_j, P_k)$ is added to $G^{(i)}$, provided $\OK(j, k)$ and $\OK(k, j)$ is received from the broadcast of $P_j$ and $P_k$ respectively (through any mode).

– Identification of Core Sets and Public Announcement by the Dealer: $\D$  waits till its local time is $\Delta + \TimeAuth + \TimeBC$, and then
executes the following steps to compute core sets.

– Once any $S_p \in \ShareSpec_{\Z_s}$
forms a clique in the graph $G^{(\D)}$, then for $q = 1, \ldots, |\Z_s|$, compute core-set $\W_{q}$
and broadcast-set $\BroadcastSet$ with respect to $S_p$ as follows, followed by broadcasting
$(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$.[If there are multiple $S_p$ from $\ShareSpec_{\Z_s}$ which
constitute a clique in $G^{(\D)}$, then consider the one with the smallest index.]

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

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

– Else set $\W_{q} = S_q$ and include $q$ to $\BroadcastSet$.

– Identifying Valid Core Sets: Each $P_i \in \PartySet$  waits till its local time is $\Delta + \TimeAuth + 2\TimeBC$ and then initializes a set $\C_i = \emptyset$. For
$p = 1, \ldots, |\Z_s|$, party $P_i$ includes $(\D, S_p)$ to $\C_i$ (initialized to $\emptyset$), provided all the following hold.

–   $(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$
is received from the broadcast of $\D$, such that  for $q = 1, \ldots, |\Z_s|$, the following hold.

– If $q \in \BroadcastSet$, then the set $\W_{q} = S_q$.

– If $(q \not \in \BroadcastSet)$, then $\W_{q}$ is either $S_q$ or  $(S_p \cap S_q)$, such that:

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

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

– Computing Output: Each $P_i \in \PartySet$ does the following, once $\C_i \neq \emptyset$.

– For every $S_q \in \ShareSpec_{\Z_s}$ such that $P_i \in \W_q$, corresponding to every
$P_j \in \W_q$, reveal $\ICSig(P_j, P_i, P_k, [s]_q)$ to every $P_k \in \S_q \setminus \W_q$ upon computing $[s]_q$ and $\ICSig(P_j, P_i, P_k, [s]_q)$ as follows.

– If $q \in \BroadcastSet$, then set $[s]_q = s_q$, where $s_q$ is received from the broadcast of $\D$,
as part of the message
$(\CandidateCoreSets, \D, S_p, \{ \W_{q}\}_{q = 1, \ldots, |\Z_s|}, \BroadcastSet, \{ s_q\}_{q \in \BroadcastSet})$. Moreover, for every $P_j \in S_q$ and every $P_k \in \PartySet$, set
$\ICSig(P_j, P_i, \allowbreak P_k, [s]_q)$ to the default value.

– Else, set $[s]_q$ to $s_{qi}$, where $s_{qi}$ was received from $\D$. Moreover, for every $P_j \in \W_q$ and every $P_k \in \PartySet$, set
$\ICSig(P_j, P_i, P_k, [s]_q)$ to  $\ICSig(P_j, P_i, P_k, s_{qj})$, received from $P_j$.

– For every $S_q \in \ShareSpec_{\Z_s}$ such that $P_i \in S_q \setminus W_q$, compute $[s]_q$ as follows.

– Check if there exists any $P_j \in \W_q$ and a value $s_{qj}$, such that $P_i$ has accepted
$\ICSig(P_k, P_j, P_i, s_{qj})$, corresponding to every $P_k \in \W_q$. Upon finding such a $P_j$,
set $[s]_q = s_{qj}$.

–  Wait till the local time becomes $\Delta + \TimeAuth + 2\TimeBC + \TimeReveal$. Upon setting $\{[s]_q\}_{P_i \in S_q}$ to some value, output $\W_1, \ldots, \W_{|\Z_s|}$,
$\{[s]_q\}_{P_i \in S_q}$ and $\ICSig(P_j, P_i, P_k, [s]_q)_{P_j, P_i \in \W_q, P_k \not \in S_q}$.

The properties of $\VSS$ as stated in Theorem <ref> are proved in Appendix <ref>.

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

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

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

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

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

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

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

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

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

$\VSS(\D, \Z_s, \Z_a, s, \SharingSpec_{\Z_s})$The statistically-secure VSS protocolfig:VSS

– Distribution of Shares: $\D$,
on having input $s$, randomly chooses $s_1,\dots,s_{|\Z_s|} \in \F$,
such that $s = s_1 + \dots + s_{|\Z_s|}$. It then sends $s_q$ to all $P_i \in S_q$, for $q = 1, \ldots, |\Z_s|$.

– Exchanging IC-Signed Values: Each $P_i \in \PartySet$ (including $\D$),  waits till the local time becomes $\Delta$.
Then, for each $S_q \in \ShareSpec_{\Z_s}$ such that $P_i \in S_q$,
upon receiving $s_{qi}$ from $\D$,  give $\ICSig(P_i, P_j, P_k, s_{qi})$ to every $P_j \in S_q$,  corresponding to every $P_k \in \PartySet$.

– Announcing Results of Pairwise Consistency Tests:
Each $P_i \in \PartySet$ (including $\D$)  waits till the local time becomes $\Delta + \TimeAuth$
and then does the following.

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

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

– Constructing Consistency Graph: Each $P_i \in \PartySet$ (including $\D$)  waits till the local time becomes $\Delta + \TimeAuth + \TimeBC$
and then constructs an undirected consistency graph $G^{(i)}$ with $\PartySet$ as the vertex set, where
the edge $(P_j, P_k)$ is added to $G^{(i)}$, provided $\OK(j, k)$ and $\OK(k, j)$ is received from the broadcast of $P_j$ and $P_k$ respectively (through any mode).

– Identification of Core Sets and Public Announcement by the Dealer: $P_{\D}$  waits till its local time is $\Delta + \TimeAuth + \TimeBC$, and then
executes the following steps to compute core sets $\W_1, \ldots, \W_{\Z_s}$ (all initialized to $\emptyset$).

– For every $S_q \in \ShareSpec_{\Z_s}$, if $S_q$ forms a clique in the graph $G^{(\D)}$, then include $S_q$ to $\C$ (initialized to $\emptyset$) and set $\W_q = S_q$.

– Once $\C$ becomes non-empty, then for the remaining $S_q \not \in \C$, do the following.

– If there exists some $S_p \in \C$, such that the parties in $(S_p \cap S_q)$ constitute a clique in $G^{(\D)}$ and where
$S_q \setminus (S_p \cap S_q) \in \Z_a$, then set $\W_q = (S_p \cap S_q)$.[If there are multiple candidates $S_p$ from $\C$, then select
any one of them arbitrarily.]

– Else set $\W_q = S_q$. Additionally, include  $q$ to the set $\BroadcastSet$ (initialized to $\emptyset$).

Broadcast $(\C, \BroadcastSet, \{s_q \}_{q \in \BroadcastSet}, \{\W_1, \ldots, \W_{\Z_s}\})$, once $\W_1, \ldots, \W_{\Z_s}$ become non-empty.

– Deciding Whether to go for the Fallback Mode:  At time $\Delta + \TimeAuth + 2\TimeBC$, each party $P_i \in \PartySet$ (including $\D$) participates with input $0$ in an instance of the
BoBW BA protocol $\BA$, provided all the following hold, else $P_i$ participates with input $1$. Moreover, $P_i$  waits for time $\TimeBA$.

– $(\C, \BroadcastSet, \{s_q \}_{q \in \BroadcastSet}, \{\W_1, \ldots, \W_{\Z_s}\})$ is received from the broadcast of $\D$ through regular-mode, such that
$\C \neq \emptyset$ and each $S_q \in \C$ also belongs to $\ShareSpec_{\Z_s}$.

– Each $S_q \in \C$ is a clique in $G^{(i)}$ at time $\Delta + \TimeAuth + \TimeBC$ and $\W_q = S_q$ for each $S_q \in \C$.

– For every $q \in \BroadcastSet$, the set $\W_q = S_q$.

– For every $q \not \in \BroadcastSet$, the set
$\W_q = (S_p \cap S_q)$ for some $S_p \in \C$, such that $\W_q$ is a
clique in $G^{(i)}$ at local time $\Delta + \TimeAuth + \TimeBC$ and
$S_q \setminus \W_q \in \Z_a$.

– Share Computation Without Fallback: Each $P_i \in \PartySet$ (including $\D$)  waits till the local time become $\Delta + \TimeAuth + 2\TimeBC + \TimeABA$. If the output of $\BA$ is $0$,
then $P_i$ does the following.

– If $(\C, \BroadcastSet, \{s_q \}_{q \in \BroadcastSet}, \{\W_1, \ldots, \W_{\Z_s}\})$
is not yet received from the broadcast of $\D$, then wait to receive them from the broadcast of $\D$ through fallback-mode.

– Upon receiving $(\C, \BroadcastSet, \{s_q \}_{q \in \BroadcastSet}, \{\W_1, \ldots, \W_{\Z_s}\})$,
compute the shares for each $S_q \in \ShareSpec_{\Z_s}$, such that $P_i \in \W_q$, as follows. ((a))

– If $q \in \BroadcastSet$, then set $[s]_q = s_q$, where $s_q$ was received from the broadcast of $\D$. Moreover, for every $P_j \in S_q$ and every $P_k \not \in \W_q$, set
$\ICSig(P_j, P_i, P_k, s_q)$ to a default value.

– Else, set $[s]_q$ to $s_{qi}$, where $s_{qi}$ was received from $\D$.

Once the shares are computed, output $\W_1, \ldots, \W_{|\Z_s|}$,
$\{[s]_q\}_{P_i \in \W_q}$ and $\ICSig(P_j, P_i, P_k, [s]_q)_{P_j, P_i \in \W_q, P_k \not \in \W_q}$.

– Share Computation with Fallback:  If the output of $\BA$ is $1$,
then each $P_i$ (including $\D$) does the following.

– Wait till some $(\C, \BroadcastSet, \{s_q \}_{q \in \BroadcastSet}, \{\W_1, \ldots, \W_{\Z_s}\})$ is received from the broadcast of $\D$ (through any mode). Upon receiving, mark
$\C, \BroadcastSet$ and $ \{\W_1, \ldots, \W_{\Z_s}\}$ as valid, provided $\C \neq \emptyset$ and all the following hold.

– Each $S_q \in \C$ also belongs to $\ShareSpec_{\Z_s}$. Moreover, $\W_q = S_q$ for each $S_q \in \C$.

– For every $q \in \BroadcastSet$, the set $\W_q$ is the same as $S_q$.

– For every $q \not \in \BroadcastSet$, the set
$\W_q = (S_p \cap S_q)$ for some $S_p \in \C$, such that $\W_q$ is a
clique in $G^{(i)}$ and
$S_q \setminus \W_q \in \Z_a$.

– Upon marking $\C, \BroadcastSet$ and $ \{\W_1, \ldots, \W_{\Z_s}\}$ as valid,
compute the shares and output, by following the same steps, labelled as (a) above.

§ NETWORK AGNOSTIC RECONSTRUCTION PROTOCOLS AND SECURE VERIFIABLE MULTICAST

Let $s$ be a value which is linearly secret-shared with IC-signatures and let $S_q \in \ShareSpec_{\Z_s}$. Moreover, let $\ReceiverSet \subseteq \PartySet$
be a designated set.  Then protocol
$\RecShare([s], S_q, \ReceiverSet)$ allows all the (honest) parties in $\ReceiverSet$ to reconstruct the share $[s]_q$ without disclosing any additional information.
For this, every $P_i \in \W_q$ reveals
$[s]_q$ to all the parties outside $\W_q$, who are in $\ReceiverSet$
(the parties in $\W_q$ who are in $\ReceiverSet$ already have $[s]_q$). To ensure that $P_i$ does not cheat, $P_i$ actually reveals the IC-signature of every party in
$\W_q$ on the revealed $[s]_q$. The idea here is that since $\W_q$ has at least one honest party (irrespective of the network type),
a potentially corrupt $P_i$ will fail to reveal the signature of an honest party from $\W_q$ on an incorrect $[s]_q$.
On the other hand, an honest $P_i$ will be able to reveal the signature of all the parties in $\W_q$ on $[s]_q$.

Based on $\RecShare$, we design another protocol $\Rec([s], \ReceiverSet)$, which allows all the (honest) parties in $\ReceiverSet$ to reconstruct $s$.
The idea is to run an instance of $\RecShare$ for every $S_q \in \ShareSpec_{\Z_s}$.
Since the protocols are standard, we present them
and prove there properties (Lemma <ref> and Lemma <ref>)
in Appendix <ref>.

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

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

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

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

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

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

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

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

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

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

§.§ $\VSS$ and Reconstruction Protocol for Superpolynomial $|\Z_s|$

From Theorem <ref> and Lemma <ref>, the error probability of $\VSS$ and $\Rec$ depend linearly on $|\ShareSpec_{\Z_s}|$, which is the same as $|\Z_s|$.
This is because there are $\Omega(|\Z_s|)$ instances of $\Auth/\Reveal$ in which the
unforgeability/non-repudiation properties might get violated with probability $\errorAICP$. This might be
problematic for a “large-sized" $\Z_s$. To avoid this, we use the idea of local dispute control
used in [40, 4], which ensures that irrespective of the number of instances of $\Auth/\Reveal$, the overall error probability is only
$\Order(n^3 \cdot \errorAICP)$. This is done by ensuring that the unforgeability/non-repudiation properties get violated only
$\Order(n^3)$ times across all these instances.
The idea here is that the parties start locally discarding corrupt parties the “moment"
they are caught cheating during any instance of $\Auth$ or $\Reveal$.
Once a party $P_j$ is locally discarded by any party $P_i$, then $P_i$
“behaves" as if $P_j$ has certainly behaved maliciously in all the “future” instances of $\Auth$ or $\Reveal$, even
if this is not the case.
This restricts the number of attempts of cheating for the adversary to a “fixed" number and consequently,
the total error probability of arbitrary many instances of $\Auth/\Reveal$ will no longer depend on $|\Z_s|$.
To incorporate the above idea, each party $P_i$ now maintains a list of locally discarded parties $\LD^{(i)}$, which
it keeps populating across all the instances of $\Auth$ and $\Reveal$, as soon as $P_i$ identifies any party
cheating. It will be ensured that an honest $P_i$ never includes an honest $P_j$ to $\LD^{(i)}$.
We next discuss the modifications in $\Auth$ and $\Reveal$ and
how the parties populate their $\LD$ sets across instances of $\Auth$ and $\Reveal$.

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

In any instance of $\Auth$, if $P_i$ is present in the corresponding set of supporting verifiers $\R$ (i.e. $P_i \in \R$),
then $P_i$ includes the corresponding signer $P_j$ of the $\Auth$ instance to $\LD^{(i)}$ if the following condition holds during $\Auth$:

\[ (P_j \mbox{ broadcasts } \OK) \quad \wedge \quad (B(\alpha_i) \neq dv_i + m_i),      \]

where $B(x)$ is the masked polynomial broadcasted by the corresponding $\INT$ of the $\Auth$ instance.
The idea here is that if $P_i$ is honest and if the above condition holds, then clearly the signer $P_j$ is corrupt and is trying to break the non-repudiation
Once $P_j \in \LD^{(i)}$, then in any pair of $(\Auth, \Reveal)$ instances involving $P_j$ as the signer,
if $P_i$ is present in the corresponding set $\R$, then in the $\Reveal$ instance,
$P_i$ reveals $\bot$ as its verification information to the corresponding receiver
$\Receiver$.[This serves as an indicator for $\Receiver$ that $P_i$ is in conflict with the signer $P_j$.]
Upon receiving $\bot$ as the verification information, the strategy for $\Receiver$ is to always accepts it without doing any verification,
irrespective of the polynomial $F(x)$
revealed as $\ICSig$ by the corresponding $\INT$.

The above modification ensures that if in any instance of $\Auth$ involving a corrupt signer $P_j$ and an honest $\INT$,