Revisiting the Efficiency of Asynchronous Multi Party Computation Against General Adversaries

Ananya Appan[International Institute of Information Technology, Bangalore India.
Email<EMAIL_ADDRESS>Anirudh Chandramouli[International Institute of Information Technology, Bangalore India.
Email<EMAIL_ADDRESS> Ashish Choudhury[International Institute of Information Technology, Bangalore India.
Email<EMAIL_ADDRESS>]

In this paper, we design secure multi-party computation (MPC) protocols in the asynchronous communication setting with optimal resilience.
Our protocols are secure against
a computationally-unbounded malicious adversary, characterized by an adversary structure $\AdvStructure$,
which enumerates all possible subsets of potentially corrupt parties. Our protocols incur a communication of
$\Order(|\AdvStructure|^2)$ and $\Order(|\AdvStructure|)$ bits per multiplication for perfect and statistical security respectively. These are the first protocols with this communication complexity, as such protocols were known only in the synchronous communication setting (Hirt and Tschudi, ASIACRYPT 2013).

§ INTRODUCTION

Secure multi-party computation (MPC) [34, 19, 6, 33] is a fundamental problem in secure distributed computing. Consider a set
of $n$ mutually-distrusting parties $\PartySet = \{P_1, \ldots, P_n \}$, where a subset of parties can be corrupted
a computationally-unbounded malicious (Byzantine) adversary $\Adv$.
Informally, an MPC protocol allows the parties  to securely compute any function $f$
of their private inputs, by keeping their respective inputs private. The most popular way of characterizing $\Adv$ is  through
a threshold, by assuming that
it can corrupt any  subset of up to $t$ parties. In this setting, MPC with perfect security (where no error is allowed in the outcome)
is achievable iff $t < n/3$ [6], while statistical security (where a negligible error is allowed)
is achievable iff $t < n/2$ [33]. Hirt and Maurer [22] generalized the threshold model by introducing the
general-adversary model (also known as the non-threshold setting). In this setting, $\Adv$ is characterized by an adversary structure
$\AdvStructure = \{Z_1, \ldots, Z_h \} \subset 2^{\PartySet}$, which enumerates all possible subsets of potentially corrupt parties, where $\Adv$ can select any subset of parties $Z^{\star} \in \AdvStructure$ for corruption.
Modelling the distrust in the system through $\AdvStructure$ allows for more flexibility (compared to the threshold model), especially when
$\PartySet$ is not too large. In the general-adversary model, MPC with perfect and statistical security
is achievable iff $\AdvStructure$ satisfies the $\Q^{(3)}(\PartySet, \AdvStructure)$ and
$\Q^{(2)}(\PartySet, \AdvStructure)$  conditions respectively.[We say that
$\AdvStructure$ satisfies the $\Q^{(k)}(\PartySet, \AdvStructure)$ condition [22], if the union of no
$k$ sets from $\AdvStructure$ covers $\PartySet$.]

In terms of efficiency, MPC protocols against general adversaries are less efficient than
those against threshold adversaries, by several orders of magnitude.
Protocols against threshold adversaries
typically incur a communication of
$n^{\Order(1)}$ bits per multiplication,
compared to $|\AdvStructure|^{\Order(1)}$ bits per multiplication required against general adversaries.[The cost of any generic MPC protocol
is typically dominated by the overhead associated with the multiplication operations in $f$.]
Since $|\AdvStructure|$ could be exponentially large in $n$, the exact exponent
is very important. For instance, as noted in [23],
if $n = 25$, then $|\AdvStructure|$ is expected to be around
one million, and a protocol with a communication complexity of
$\Order(|\AdvStructure|^2 \cdot \mbox{Poly}(n))$ bits is preferred over a protocol
with a communication complexity of
$\Order(|\AdvStructure|^3 \cdot \mbox{Poly}(n))$ bits.

Our Motivation and Results:

All the above results hold in the synchronous communication setting, where the parties are assumed to be globally synchronized,
with strict upper bounds on the message delay.
Such strict time-outs are, however, extremely difficult to maintain in
real-world networks like the Internet, which are better modelled by the asynchronous communication setting [8]. Here, no timing assumptions are made and messages can be arbitrarily, but finitely delayed, with
every message sent  being delivered eventually.

Asynchronous protocols are more complex and less efficient when compared to their synchronous counter-parts, since a slow (but honest)
sender party cannot be distinguished from a corrupt sender party, who does not send any message. To avoid an endless wait, the parties cannot afford to wait to receive messages from all the parties, which results in disregarding messages from a subset of potentially honest parties.
Against threshold adversaries, perfectly-secure and statistically-secure asynchronous MPC (AMPC) is achievable, iff
$t< n/4$ [5] and $t<n/3$ [7, 1] respectively. By using the player-partitioning argument [22], these results can
be generalized to show that against general adversaries, perfect and statistical security require $\AdvStructure$ to satisfy the
$\Q^{(4)}(\PartySet, \AdvStructure)$ and $\Q^{(3)}(\PartySet, \AdvStructure)$ conditions respectively.

Compared to synchronous MPC protocols, AMPC protocols are not very well-studied [5, 7, 4, 31, 13], especially
against general adversaries.
While perfectly-secure AMPC against general adversaries has been studied
in [25, 12], to the best of our knowledge, there exists no statistically-secure AMPC protocol against general adversaries.
We design communication efficient AMPC protocols against general adversaries, both with perfect and statistical security,
whose efficiency is comparable with the most efficient MPC protocols in the synchronous communication setting.
Our results put in the context of relevant existing results are presented in Table <ref>, where
$\F$ denotes a finite field over which all computations are performed, and $\kappa$ denotes the statistical-security parameter.

3 |c| Synchronous     3 |c| Asynchronous

Security     Condition     Bits/Multiplication     Security     Condition     Bits/Multiplication

2*Perfect     2*$\Q^{(3)}$     2*$\Order(|\AdvStructure|^2 \cdot \mbox{Poly}(n, |\F|))$ [23]
2*Perfect      2*$\Q^{(4)}$     $\Order(|\AdvStructure|^3 \cdot \mbox{Poly}(n, |\F|))$ [12]

$\Order(|\AdvStructure|^2 \cdot \mbox{Poly}(n, |\F|))$ (our result)

Statistical     $\Q^{(2)}$     $\Order(|\AdvStructure| \cdot \mbox{Poly}(n, \kappa))$ [23]
Statistical     $\Q^{(3)}$     $\Order(|\AdvStructure| \cdot \mbox{Poly}(n, \kappa))$ (our result)

Communication complexity of different MPC protocols against general adversaries in terms of $|\AdvStructure|$

Our protocols are in the pre-processing model, where the parties generate random secret-shared multiplication-triples.
The parties then evaluate $\ckt$ in a secret-shared fashion, where Beaver's method [3] is used to evaluate the multiplication gates using the generated multiplication-triples. Our protocols for the pre-processing phase
closely follow [23]. However, there are several non-trivial challenges
while adapting these protocols to the asynchronous world. Since our protocols are slightly technical, we refer to Section <ref>
for the technical overview of our protocols.

§ PRELIMINARIES, DEFINITIONS AND EXISTING ASYNCHRONOUS PRIMITIVES

We assume that the parties in $\PartySet = \{P_1, \ldots, P_n\}$ are connected by pair-wise secure channels.

The adversary $\Adv$ is assumed to be malicious and static, and decides the set of corrupt parties at the beginning of the protocol execution.
Parties not under the control of $\Adv$ are called honest.
Given $\PartySet' \subseteq \PartySet$, we say that $\AdvStructure$
satisfies the $\Q^{(k)}(\PartySet', \AdvStructure)$ condition, if for every $Z_{i_1}, \ldots, Z_{i_k} \in \AdvStructure$, the condition
$\PartySet' \not \subseteq Z_{i_1} \cup \ldots \cup Z_{i_k}$ holds.

We assume  that the parties want to compute a function $f$, represented by a publicly known
arithmetic circuit $\ckt$ over a finite field $\F$ consisting of linear and non-linear gates, with
$M$ being number of multiplication gates.
Without loss of generality, we assume that
each $P_i \in \PartySet$ has an input $x^{(i)}$ for $f$, and that
all the parties want to learn the single output
$y = f(x^{(1)}, \ldots, x^{(n)})$.
We follow the asynchronous communication model of
[5, 8].

Unlike the previous unconditionally-secure AMPC protocols [7, 4, 31, 13, 12],
we prove the security of our protocols using the UC framework [9, 18, 10], whose details are presented in Appendix <ref>.

In our protocols, we use a secret-sharing
based on the one from [29], defined with respect to
a sharing specification $\ShareSpec$, which is a tuple of subsets of $\PartySet$.
A sharing specification $\ShareSpec$ is said to be $\AdvStructure$-private,
if for every $Z \in \AdvStructure$, there is an $S \in \ShareSpec$, such that $Z \cap S = \emptyset$.
A sharing specification $\ShareSpec$
satisfies the $\Q^{(k)}(\ShareSpec, \AdvStructure)$ condition if for every $Z_{i_1}, \ldots, Z_{i_k} \in \AdvStructure$ and every
$S \in \ShareSpec$, the condition
$S \not \subseteq Z_{i_1} \cup \ldots \cup Z_{i_k}$ holds.
In our protocols, we use the sharing specification
$\ShareSpec = (S_1, \ldots, S_h)
\defined \{ \PartySet \setminus Z | Z \in \AdvStructure\}$, which guarantees that $\ShareSpec$ is $\AdvStructure$-private.
This $\ShareSpec$ satisfies the $\Q^{(3)}(\ShareSpec, \AdvStructure)$ and $\Q^{(2)}(\ShareSpec, \AdvStructure)$ conditions,
if $\AdvStructure$ satisfies the $\Q^{(4)}(\PartySet, \AdvStructure)$ and $\Q^{(3)}(\PartySet, \AdvStructure)$ conditions respectively.

A value $s \in \F$ is said to be secret-shared with respect to $\ShareSpec = (S_1, \ldots, S_h)$, if
there exist shares $s_1, \ldots, s_h$, such that $s = s_1 + \ldots + s_h$ and
for $q = 1, \ldots, h$, share $s_q$ is know to every (honest) party in $S_q$.

A sharing of $s$ is denoted by $[s]$, where $[s]_q$ denotes the $q^{th}$ share. Note that
$P_i$ will hold the shares $\{[s]_q\}_{P_i \in S_q}$.
The above secret-sharing is linear, as
$[c_1s_1 + c_2 s_2] = c_1[s_1] + c_2[s_2]$ for any publicly-known $c_1, c_2 \in \F$.

Asynchronous Reliable Broadcast (Acast):

Acast allows a designated
$P_S \in \PartySet$ to identically send a message
$m \in \{0, 1 \}^{\ell}$ to all the parties.
If $P_S$ is honest, then all honest parties eventually output $m$. If $P_S$ is corrupt and
some honest party outputs $m^{\star}$, then every
other honest party eventually outputs $m^{\star}$.

The above requirements are formalized by an ideal functionality $\FAcast$, presented in Appendix <ref>.
In [27], a perfectly-secure Acast protocol is presented with a communication complexity of $\Order(n^2 \ell)$ bits, provided $\AdvStructure$ satisfies the
$\Q^{(3)}(\PartySet, \AdvStructure)$ condition. The security of the protocol in [27] is not proven in the UC framework. For completeness, we do this in Appendix <ref>.

Asynchronous Byzantine Agreement (ABA):

In an ABA protocol [32, 28, 2],
every party has a private bit and the (honest) parties eventually obtain a common output bit almost-surely with probability $1$,
where the output bit is the input bit of an honest party, if all honest parties have the same input.[From [17],
every deterministic ABA protocol must have non-terminating runs.
To circumvent this result, randomized ABA protocols are considered and the best we can hope for from such protocols is that the parties eventually obtain an output with
probability $1$.]
The above requirements are formalized through the functionality $\FABA$, presented in Appendix <ref>.
We assume the existence of a perfectly-secure ABA protocol for $\FABA$ with UC-security (see [26, 27] for such protocols if
$\AdvStructure$ satisfies the $\Q^{(3)}(\PartySet, \AdvStructure)$ condition).
The number of ABA instances will be independent of the size of $\ckt$ and so, we do not focus on the exact details.

Verifiable Secret-Sharing (VSS):

A VSS protocol allows a designated dealer $P_D \in \PartySet$ to verifiably secret-share its input $s \in \F$.
If $P_D$ is honest, then the honest parties eventually complete the protocol with $[s]$.
The verifiability guarantees that if $P_D$ is corrupt and some honest party completes the protocol, then all honest parties eventually complete the protocol with a secret-sharing
of some value.

These requirements are formalized through the functionality $\FVSS$ (Fig <ref>). The functionality, upon receiving a vector of shares
from $P_\D$, distributes the appropriate shares to the respective parties. The dealer's input is defined implicitly as the sum of provided shares.
We will use
$\FVSS$ in our protocols as follows: $P_D$ on having the input $s$, sends a random vector of shares
$(s_1, \ldots, s_h)$ to $\FVSS$ where
$s_1 + \ldots + s_h = s$.
If $P_D$ is honest, then the view of $\Adv$ will be independent of $s$, if $\ShareSpec$ is $\AdvStructure$-private. Hence, the
probability distribution of shares learnt by $\Adv$ will be independent of the dealer's input.

$\FVSS$The ideal functionality for VSS for session id $\sid$.fig:FVSS

$\FVSS$ proceeds as follows for each party $P_i \in \PartySet$ and an adversary $\Sim$, and is parametrized
by a sharing specification $\ShareSpec = (S_1, \ldots, S_h)$, adversary structure $\AdvStructure$  and a dealer $P_D$.
Let $Z^{\star}$ be the set of corrupt parties.

– On receiving $(\Dealer, \sid, P_{\D}, (s_1, \ldots, s_h))$ from $P_\D$ (or from $\Sim$ if $P_\D \in Z^{\star}$),
set $s = \sum_{q = 1, \ldots, h} s_q$ and for $q = 1, \ldots, h$, set $[s]_q = s_q$.
Generate a request-based delayed output $(\Share, \sid, P_D, \{[s]_q \}_{P_i \in S_q})$ for each
$P_i \not \in Z^{\star}$.[If $P_D$ is corrupt, then
$\Sim$ may not send any input to $\FVSS$,
in which case the functionality will not generate any output.
See Appendix <ref> for the meaning of request-based delayed output in asynchronous ideal world.]

In [12], a perfectly-secure VSS protocol $\PiPerVSS$ is presented, provided $\ShareSpec$
satisfies the $\Q^{(3)}(\ShareSpec, \AdvStructure)$ condition (which holds for our $\ShareSpec$).
The protocol (after a minor modification) incurs a communication of $\Order(|\AdvStructure| \cdot n^2 \log{|\F|} + n^4 \log{n})$
In [12], the UC-security of $\PiPerVSS$
was not shown and for completeness, we do so in Appendix <ref>.

Default Secret-Sharing:

The perfectly-secure protocol $\PiPerDefaultShare$ takes a public input $s \in \F$ and $\ShareSpec = (S_1, \ldots, S_h)$ to
non-interactively generate $[s]$, where the parties collectively set $[s]_1 = s$ and $[s]_2 = \ldots = [s]_h = 0$.

Reconstruction Protocols:

Let the parties hold $[s]$ with respect to some $\ShareSpec = (S_1, \ldots, S_h)$ which satisfies
the $\Q^{(2)}(\ShareSpec, \AdvStructure)$ condition.  Then, [12] presents a
perfectly-secure protocol $\PiPerRecShare$ to reconstruct $[s]_q$ for any given $q \in \{1, \ldots, h \}$
and a perfectly-secure protocol $\PiPerRecShare$ to reconstruct $s$.
The protocols incur a communication of $\Order(n^2 \log{|\F|})$
and $\Order(|\AdvStructure| \cdot n^2 \log{|\F|})$ bits respectively (see Appendix <ref> for the details).

§ PERFECTLY-SECURE PRE-PROCESSING PHASE PROTOCOL WITH $\Q^{(4)}(\PARTYSET, \ADVSTRUCTURE)$ CONDITION

Throughout this section, we assume that $\AdvStructure$ satisfies the
$\Q^{(4)}(\PartySet, \AdvStructure)$ condition. We present a perfectly-secure protocol which generates a secret-sharing of $M$ random multiplication-triples,
unknown to the adversary.
The protocol realizes the
ideal functionality $\FTriples$ (Fig <ref>) which allows the ideal-world adversary to specify the shares
for each of the output triples on the behalf of corrupt parties.
The functionality then “completes" the sharings of all the triples randomly, while keeping them “consistent" with the shares specified by the
adversary.[This provision is made because
in our pre-processing phase protocol, the real-world adversary will have full control over the shares of the corrupt parties corresponding to the
random multiplication-triples generated in the protocol.]

$\FTriples$The ideal functionality for the asynchronous pre-processing phase with session id $\sid$.fig:FTriples

$\FTriples$ proceeds as follows, running with the parties $\PartySet$ and an adversary $\Sim$,
and is parametrized by an adversary-structure $\AdvStructure$ and
$\AdvStructure$-private sharing specification  $\ShareSpec = (S_1, \ldots, S_h) = \{ \PartySet \setminus Z | Z \in \AdvStructure\}$.
Let $Z^{\star}$ denote the set of corrupt parties.

– If there exists a set of parties ${\cal A}$ such that $\PartySet \setminus {\cal A} \in \AdvStructure$ and every
$P_i \in {\cal A}$ has sent the message $(\triples, \sid, P_i)$, then send $(\triples, \sid, {\cal A})$ to $\Sim$
and prepare the output as follows.

* Generate secret-sharing of $M$ random multiplication-triples. To generate
one such sharing, randomly select $a, b \in \F$, compute $c = ab$ and execute the steps labelled
Single Sharing Generation
for $a, b$ and $c$.

* Let $\{([a^{(\ell)}], [b^{(\ell)}], [c^{(\ell)}] )\}_{\ell \in \{1, \ldots, M\}}$ be the resultant secret-sharing of the
Send a request-based delayed output
$(\tripleshares, \sid, \{[a^{(\ell)}]_q, [b^{(\ell)}]_q, [c^{(\ell)}]_q \}_{\ell \in \{1, \ldots, M\}, P_i \in S_q})$  to each $P_i \in \PartySet \setminus Z^{\star}$
(no need to send the respective shares to the parties in $Z^{\star}$, as $\Sim$ already has the shares of all the corrupt parties).

Single Sharing Generation: Do the following to generate a secret-sharing  of a given value $s$.

* Upon receiving $(\shares, \sid, \{s_q \}_{S_q \cap Z^{\star} \neq \emptyset})$ from $\Sim$,
randomly select $s_q \in \F$ corresponding to each $S_q \in \ShareSpec$ for which $S_q \cap Z^{\star} = \emptyset$, such that
$\displaystyle \sum_{S_q \cap Z^{\star} \neq \emptyset} s_q + \sum_{S_q \cap Z^{\star} = \emptyset} s_q = s$ holds.
[$\Sim$ cannot
delay sending the shares on the behalf of the corrupt parties indefinitely as, in our real-world protocol,
the adversary cannot indefinitely delay the generation of secret-shared multiplication-triples.]
For $q = 1, \ldots, h$, set $[s]_q = s_q$.

As the protocol is executed asynchronously, upon reconstructing the function output, the parties check whether it is “safe

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

§ STATISTICALLY-SECURE PRE-PROCESSING PHASE PROTOCOL WITH $\Q^{(3)}(\PARTYSET, \ADVSTRUCTURE)$ CONDITION

We first present an asynchronous information-checking protocol
(AICP) with $\Q^{(3)}(\PartySet, \AdvStructure)$ condition.

§ MPC PROTOCOLS IN THE PRE-PROCESSING MODEL

The MPC protocol $\PiMPC$ in the pre-processing model is standard.
The parties first generate secret-shared random multiplication-triples through
$\FTriples$. Each party then randomly secret-shares its input for $\ckt$ through $\FVSS$.
To avoid an indefinite wait,
the parties agree on a common subset of parties, whose
inputs are eventually secret-shared, through ACS.

The parties then jointly evaluate each gate in $\ckt$ in a secret-shared fashion by generating a secret-sharing of
the gate-output from a secret-sharing of the gate-input(s). Linear gates are evaluated non-interactively due to the linearity of secret-sharing.
To evaluate multiplication gates, the parties deploy Beaver's method [3], using the secret-shared
multiplication-triples generated by $\FTriples$.
Finally, the parties publicly reconstruct the  secret-shared function output.
Protocol $\PiMPC$ and the proof of Theorem <ref> are presented in Appendix <ref>.

Protocol $\PiMPC$ UC-securely realizes the functionality $\Functionality$ for securely computing  $f$ (see Fig <ref> in Appendix <ref>)
with perfect security in the $(\FTriples, \FVSS, \FABA)$-hybrid model, in the
presence of a static malicious adversary characterized by an adversary-structure $\AdvStructure$ satisfying the $\Q^{(3)}(\PartySet, \AdvStructure)$ condition.
The protocol makes one call to $\FTriples$ and $\Order(n)$ calls to $\FVSS$ and $\FABA$ and additionally incurs a communication of
$\Order(M \cdot |\AdvStructure| \cdot n^2 \log{|\F|})$ bits, where $M$ is the number of multiplication gates in the circuit $\ckt$ representing $f$.

If we replace the calls to $\FTriples$ and $\FVSS$ with perfectly-secure protocol $\PiPerTriples$ and $\PiPerVSS$ respectively, then protocol
$\PiMPC$ achieves perfect security in the $\FABA$-hybrid. On the other hand,
replacing the calls to $\FTriples$ and $\FVSS$ in $\PiMPC$ with  $\PiStatTriples$ and $\PiStatVSS$ respectively
leads to statistical-security. To bound the error probability of the statistically-secure protocol by $2^{-\kappa}$,
we select a finite field $\F$ such that $|\F| > n^4 2^{\kappa}$. Based on the above discussion, we get the following corollaries of
Theorem <ref>.

If $\AdvStructure$ satisfies the $\Q^{(4)}(\PartySet, \AdvStructure)$ condition, then
$\PiMPC$ UC-securely realizes $\Functionality$ in the $\FABA$-hybrid model with perfect security.
The protocol makes $\Order(|\AdvStructure| \cdot n^5)$ calls to $\FABA$
and incurs a communication of $\Order(M \cdot (|\AdvStructure|^2 \cdot n^7 \log{|\F|} + |\AdvStructure| \cdot n^9 \log{n}))$ bits, where
$M$ is the number of multiplication gates in $\ckt$.

If $\AdvStructure$ satisfies the $\Q^{(3)}(\PartySet, \AdvStructure)$ condition, then
$\PiMPC$ UC-securely realizes $\Functionality$ in the $\FABA$-hybrid model with statistical security.
If $|\F| > n^4 2^{\kappa}$ for a given statistical-security parameter $\kappa$, then the error probability of the protocol is at most $2^{-\kappa}$.
The protocol makes $\Order(n^3)$ calls to $\FABA$
and incurs a communication of
$\Order(M \cdot |\AdvStruct| \cdot n^9 \log{|\F|})$ bits, where $M$ is the
number of multiplication gates in $\ckt$.

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

[2]
Hagit Attiya and Jennifer Welch.
Distributed Computing: Fundamentals, Simulations, and Advanced
Topics, volume 19.
John Wiley & Sons, 2004.

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

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

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

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

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

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

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

[10]
R. Canetti.
Universally Composable Security.
J. ACM, 67(5):28:1–28:94, 2020.

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

[12]
A. Choudhury and N. Pappu.
Perfectly-Secure Asynchronous MPC for General Adversaries
(Extended Abstract).
In INDOCRYPT, volume 12578 of Lecture Notes in Computer
Science, pages 786–809. Springer, 2020.

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

[14]
R. Cohen.
Asynchronous Secure Multiparty Computation in Constant Time.
In PKC, volume 9615 of Lecture Notes in Computer Science,
pages 183–207. Springer, 2016.

[15]
S. Coretti, J. A. Garay, M. Hirt, and V. Zikas.
Constant-Round Asynchronous Multi-Party Computation Based on One-Way
In ASIACRYPT, volume 10032 of Lecture Notes in Computer
Science, pages 998–1021, 2016.

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

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

[18]
O. Goldreich.
The Foundations of Cryptography - Volume 2, Basic
Cambridge University Press, 2004.

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

[20]
M. Hirt, J. B. Nielsen, and B. Przydatek.
Cryptographic Asynchronous Multi-party Computation with Optimal
Resilience (Extended Abstract).
In R. Cramer, editor, Advances in Cryptology - EUROCRYPT 2005,
24th Annual International Conference on the Theory and Applications of
Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings,
volume 3494 of Lecture Notes in Computer Science, pages 322–340.
Springer, 2005.

[21]
M. Hirt, J. B. Nielsen, and B. Przydatek.
Asynchronous Multi-Party Computation with Quadratic Communication.
In ICALP, volume 5126 of Lecture Notes in Computer
Science, pages 473–485. Springer, 2008.

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

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

[24]
J. Katz, U. Maurer, B. Tackmann, and V. Zikas.
Universally Composable Synchronous Computation.
In TCC, volume 7785 of Lecture Notes in Computer Science,
pages 477–498. Springer, 2013.

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

[26]
K. Kursawe.
Distributed trust.
PhD thesis, Saarland University, 2001.

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

[28]
Nancy A Lynch.
Distributed algorithms.
Morgan Kaufmann, 1996.

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

[30]
A. Patra, A. Choudhury, and C. Pandu Rangan.
Asynchronous Byzantine Agreement with Optimal Resilience.
Distributed Computing, 27(2):111–146, 2014.

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

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

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

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

§ THE ASYNCHRONOUS UNIVERSAL COMPOSABILITY (UC) FRAMEWORK AND VARIOUS ASYNCHRONOUS FUNCTIONALITIES

In this section, we discuss the asynchronous UC framework followed in this paper. The discussion is based on the description of the framework against
threshold adversaries as provided in [14] (which is further based on [24, 15]). We adapt the framework for the case of general adversaries.
Informally, the security of a protocol is argued by “comparing" the capabilities of the adversary in two separate
In the real-world, the parties exchange messages among themselves, computed as per
a given protocol. In the ideal-world, the parties do not interact with each other, but with a trusted third-party
(an ideal functionality), which enables the parties to obtain the result of the computation based on the inputs provided by
the parties. Informally, a protocol is considered to be secure if whatever an adversary can do in the real protocol
can be also done in the ideal-world.

The Asynchronous Real-World: An execution of a protocol $\Pi$ in the real-world
consists of $n$ interactive Turing machines (ITMs) representing the parties in $\PartySet$.
Additionally, there is an ITM for representing the adversary $\Adv$.
Each ITM is initialized with its random coins and possible inputs. Additionally, $\Adv$ may have some auxiliary input $z$.
Following the convention of [8],
the protocol operates asynchronously by a sequence of activations, where at each point, a single ITM is active.
Once activated, a party can perform some local computation, write on its output tape, or send messages to other parties.
On the other hand, if the adversary is
activated,  it can send messages on the behalf of corrupt parties.
The protocol execution is complete once all honest parties obtain their respective outputs.
We let $\REAL_{\Pi, \Adv(z), Z^{\star}}(\vec{x})$
denote the random variable consisting of the output of the honest parties and the view of the adversary
$\Adv$ during the execution of a protocol $\Pi$. Here, $\Adv$ controls parties in $Z^{\star}$ during the execution of protocol $\Pi$ with inputs $\vec{x} = (x^{(1)}, \ldots, x^{(n)})$ for the parties (where party $P_i$ has input $x^{(i)}$), and auxiliary input $z$ for $\Adv$.

The Asynchronous Ideal-World:

A protocol in the ideal-world
consists of $n$ dummy parties $P_1, \ldots, P_n$, an ideal-world adversary $\Sim$ (also called simulator)
and an ideal functionality $\Functionality$.
We consider static corruptions such that the set of corrupt parties $Z^{\star}$ is fixed at the beginning of the computation
and is known to $\Sim$. The functionality $\Functionality$ receives the inputs from the respective dummy parties,
performs the desired computation $f$ on the received inputs, and sends the outputs to the respective parties.
The ideal-world adversary does not see and cannot delay the communication between the parties and
$\Functionality$. However, it can communicate with $\Functionality$ on the behalf of corrupt parties.

Since $\Functionality$ models the desired behaviour of a real-world protocol which is asynchronous,
ideal functionalities must consider some inherent limitations to model the asynchronous communication model with eventual delivery.
For example, in a real-world protocol, the adversary  can decide when each honest party learns the output since
it has full control over message scheduling. To model the notion of time in the ideal-world,
[24] uses the concept of number of activations.
Namely, once $\Functionality$ has computed the output for some party,
it does not ask “permission"  from $\Sim$ to deliver it to the respective party.
Instead, the corresponding party must “request" $\Functionality$ for the output, which
can be done only  when the concerned party is active.
Moreover, the adversary can “instruct" $\Functionality$ to delay the output for each party by ignoring the corresponding
requests, but only for a polynomial number of activations.  If a party is activated
sufficiently many times, the party will eventually receive the output from $\Functionality$
and hence, ideal computation eventually completes. That is, each honest party
eventually obtains its desired output. As in [14],
we use the term “$\Functionality$ sends a request-based delayed output to $P_i$",
to  describe the above interaction between the $\Functionality, \Sim$ and $P_i$.

Another limitation is that in a real-world AMPC protocol, the (honest) parties cannot afford for all the parties to provide their input for the computation to avoid an
endless wait, as the corrupt parties may decide not to provide their inputs. Hence, every
AMPC protocol suffers from input deprivation, where inputs of a subset of potentially honest parties (which is decided by the choice of
adversarial message scheduling) may get ignored during computation. Consequently, once a “core set" of parties $\CoreSet$ provide their inputs for
the computation, where $\PartySet \setminus \CoreSet \in \AdvStructure$, the parties have to start computing the function by assuming some default input for
the left-over parties.
To model this in the ideal-world, $\Sim$ is given the provision
to decide the set $\CoreSet$ of parties whose inputs should be taken into consideration by $\Functionality$. We stress that
$\Sim$ cannot delay sending $\CoreSet$ to $\Functionality$ indefinitely. This is because in the real-world
protocol, $\Adv$ cannot prevent the honest parties from providing their
inputs indefinitely.
The formal description of
$\Functionality$ is available in Fig <ref>.

$\Functionality$The ideal functionality for asynchronous secure multi-party computation for session id $\sid$.fig:FAMPC

$\Functionality$ proceeds as follows, running with the parties $\PartySet = \{P_1, \ldots, P_n \}$ and an adversary $\Sim$, and is parametrized by an $n$-party function
$f: \F^n \rightarrow \F$ and an adversary structure $\AdvStructure \subseteq 2^{\PartySet}$.

* For each party $P_i \in \PartySet$, initialize an input value $x^{(i)} = \bot$.

* Upon receiving a message $(\inp, \sid, v)$ from some $P_i \in \PartySet$ (or from $\Sim$ if $P_i$ is corrupt), do the following:

* Ignore the message if output has already been  computed;

* Else, set $x^{(i)} = v$ and send $(\inp, \sid, P_i)$ to $\Sim$.[If $P_i$ is corrupt, then no need to send $(\inp, \sid, P_i)$ to $\Sim$ as the input has been provided
by $\Sim$ only.]

* Upon receiving a message $(\coreset, \sid, \CoreSet)$ from $\Sim$, do the following:[$\Sim$ cannot delay sending $\CoreSet$ indefinitely; see the discussion
before the description of the functionality.]

* Ignore the message if $(\PartySet \setminus \CoreSet) \not \in \AdvStructure$ or if output has already been computed;

* Else, record $\CoreSet$ and set $x^{(i)} = 0$ for every $P_i \not \in \CoreSet$.[It is possible that for some $P_i \not \in \CoreSet$,
the input has been set to a value
different from $0$ during step 1 and $x^{(i)}$ is now reset to $0$. This models the scenario that in the real-world
protocol, even if $P_i$ is able to provide its input,
$P_i$'s inclusion to $\CoreSet$ finally depends upon message scheduling, which is under adversarial control.]

* If  $\CoreSet$ has been recorded and the value $x^{(i)}$ has been set to a value different from $\bot$ for every $P_i \in \CoreSet$, then
compute $y \defined f(x^{(1)}, \ldots, x^{(n)})$ and generate a request-based delayed output $(\out, \sid, (\CoreSet, y))$ for every $P_i \in \PartySet$.

Similar to the real-world, we let $\IDEAL_{\Functionality, \Sim(z), Z^{\star}}(\vec{x})$
denote the random variable consisting of the output of the honest parties and the view of the adversary
$\Sim$, controlling the parties in $Z^{\star}$,
with the parties having inputs $\vec{x} = (x^{(1)}, \ldots, x^{(n)})$ (where party $P_i$ has input $x_i$), and auxiliary input $z$ for $\Sim$.

We say that a real-world asynchronous protocol $\Pi$ securely realizes $\Functionality$ with
perfectly-security if and only if  for every real-world adversary $\Adv$, there exists an ideal-world adversary
$\Sim$ whose running time is polynomial in the running time of $\Adv$, such that for every possible $Z^{\star}$,
every possible $\vec{x} \in \F^n$
and every possible $z \in \{0, 1 \}^{\star}$, it holds that the random variables

\[ \Big \{ \REAL_{\Pi, \Adv(z), Z^{\star}}(\vec{x}) \Big \}  \quad  \mbox{ and }  \quad  \Big \{ \IDEAL_{\Functionality, \Sim(z), Z^{\star}}(\vec{x}) \Big \}\]

are identically distributed. That is, the random variables are perfectly-indistinguishable.

For statistically-secure AMPC, the parties and adversaries are parameterized with a statistical-security parameter $\kappa$,
and the above random variables (which are viewed as ensembles, parameterized by $\kappa$)
are required to be statistically-indistinguishable. That is, their statistical-distance should be a negligible
function in $\kappa$.

The Universal-Composability (UC) Framework:
While the real-world / ideal-world based security paradigm is used to define the security of a protocol in the “stand-alone" setting,
the more powerful UC framework [9, 10] is used to define
the security of a protocol when multiple instances of the protocol might be running in parallel, possibly along with other
protocols. Informally, the security in the UC-framework is still argued by comparing the real-world and the ideal-world. However,
now, in both worlds, the computation takes place in the presence of an additional interactive
process (modeled as an ITM) called the environment and denoted by $\Env$.
Roughly speaking, $\Env$ models the “external environment" in which
protocol execution takes place. The interaction between $\Env$ and the various entities takes place as follows
in the two worlds.

In the real-world, the environment gives inputs to the honest parties, receives their outputs, and can communicate with the adversary
at any point during the execution. During the protocol execution, the environment gets activated first. Once activated, the environment
can either activate one of the parties by providing some input, or activate $\Adv$ by sending it a message. Once a party
completes its operations upon getting activated, the control is returned to the environment. Once $\Adv$ gets activated,
it can communicate with the environment (apart from sending the messages to the honest parties).
The environment also fully controls the corrupt parties that send all the messages they receive to $\Env$,
and follow the orders of $\Env$.
The protocol execution is completed once $\Env$ stops activating
other parties, and outputs a single bit.

In the ideal-model, the environment $\Env$ gives inputs to the (dummy) honest parties, receives their outputs, and can communicate with
$\Sim$ at any point during the execution. The dummy parties act  as channels between $\Env$ and the functionality. That is, they
send the inputs received from $\Env$ to functionality and transfer the output they receive from the functionality
to $\Env$. The activation sequence in this world is similar to the one in the real-world.
The protocol execution is completed once $\Env$ stops activating
other parties and outputs a single bit.

A protocol is said to be UC-secure with perfect-security, if for every real-world adversary $\Adv$ there exists a simulator $\Sim$,
such that for any environment $\Env$, the
environment cannot distinguish the real-world from the ideal-world.
On the other hand, the protocol is said to be UC-secure with statistical-security, if the
environment cannot distinguish the real-world from the ideal-world, except with a probability which
is a negligible function in the statistical-security parameter $\kappa$.

The Hybrid Model: In a $\AcceptedParties$-hybrid model, a protocol execution proceeds as in the real-world. However, the parties have access to
an ideal functionality $\AcceptedParties$ for some specific task. During the protocol execution, the parties
communicate with $\AcceptedParties$ as in the ideal-world. The UC framework guarantees
that an ideal functionality in a hybrid model can be replaced with a protocol that UC-securely realizes $\AcceptedParties$. This is specifically due to the
following composition theorem from [9, 10].

Let $\Pi$ be a protocol that UC-securely realizes some functionality $\Fun$ in the $\AcceptedParties$-hybrid model and let $\rho$ be a protocol that UC-securely
realizes $\AcceptedParties$. Moreover, let $\Pi^{\rho}$ denote the protocol that is obtained from $\Pi$ by replacing every ideal call to $\AcceptedParties$
with the protocol $\rho$. Then $\Pi^{\rho}$ UC-securely realizes $\Fun$
in the model where the parties do not have access to the functionality $\AcceptedParties$.

§.§ The Asynchronous Reliable Broadcast (Acast) Functionality and the Protocol

The ideal functionality $\FAcast$ capturing the requirements for asynchronous reliable broadcast  is presented in Fig <ref>. The functionality,
upon receiving $m$ from the sender $P_S$, performs a request-based delayed delivery of $m$ to all the parties.
Notice that if
$P_S$ is corrupt, then the functionality may not receive any message for delivery, in which case parties obtain no output.
This models the fact that in any real-world Acast protocol, a potentially corrupt $P_S$ may not invoke the protocol.

$\FAcast$The ideal functionality for asynchronous reliable broadcast for session id $\sid$.fig:FAcast

$\FAcast$ proceeds as follows, running with the parties $\PartySet = \{P_1, \ldots, P_n \}$ and an adversary $\Sim$, and is parametrized
by an adversary structure $\AdvStructure \subseteq 2^{\PartySet}$. Let $Z^{\star}$ denote the set of corrupt parties, where
$Z^{\star}  \in \AdvStructure$.

* Upon receiving $(\Sender, \Acast, \sid, m)$ from $P_S \in \PartySet$ (or from $\Sim$ if $P_S \in Z^{\star}$), do the following:

– Send $(P_S, \Acast, \sid, m)$ to $\Sim$;[If $P_S \in Z^{\star}$, then no need to send $(P_S, \Acast, \sid, m)$ to $\Sim$, as
in this case $m$ is received from $\Sim$ itself.]

– Send a request-based delayed output
$(P_S, \Acast, \sid, m)$ to each $P_i \in \PartySet \setminus Z^{\star}$ (no need to send $m$ to the parties in $Z^{\star}$, as $\Sim$ gets $m$ on their behalf).

We next recall the Acast protocol of [27] and present it in Fig <ref>.

$(P_S, m)$The perfectly-secure Acast protocol for realizing $\FAcast$fig:A-cast

– Code for the Sender $P_S$ (with input $m \in \{0, 1 \}^{\ell}$):

* Send the message ($\inp, \sid, m$) to all the parties in $\PartySet$.

– Code for each party $P_i \in \PartySet$ (including $P_S$):

* If the message ($\inp, \sid, m$) is received from $P_S$, then send the message ($\echo, \sid, m$)
to all the parties in $\PartySet$.

* If the message ($\echo, \sid, m'$) is received from a set of parties
$\PartySet \setminus Z$ for some $Z \in \AdvStructure$, then send the message ($\Ready, \sid, m'$) to all the parties.

* If the message ($\Ready, \sid, m'$) is received from a set of parties $C$
where $C \not \in \AdvStructure$, then send the message $(\Ready, \sid, m')$ to all
the parties in $\PartySet$.

* If ($\Ready, \sid, m'$) is received from a set of parties
$\PartySet \setminus Z$ for some $Z \in \AdvStructure$, then output $m'$.

The properties of the protocol $\PiAcast$ are stated in Theorem <ref>.

If $\AdvStructure$ satisfies
the $\Q^{(3)}(\PartySet, \AdvStructure)$ condition, then protocol $\PiAcast$ UC-securely realizes $\FAcast$ with perfect security.
The protocol incurs a communication of $\Order(n^2\ell)$ bits, where $P_S$ has an input of size $\ell$ bits.

The communication complexity simply follows from the fact that in the protocol, each party needs to send $m$ to every other party.
For security, consider an arbitrary adversary $\Adv$ attacking $\PiAcast$ by corrupting a set of parties $Z^{\star} \in \AdvStructure$,
and let $\Env$ be an arbitrary environment.
We present a simulator $\SimAcast$  such  that for any set of corrupt parties $Z^{\star} \in \AdvStructure$,
the output of the honest parties and the view of the adversary in an execution of $\PiAcast$ with $\Adv$
is distributed identically to the output of the honest parties and the view of the adversary
in an execution with $\SimAcast$ involving $\FAcast$ in the ideal world.
This further implies that $\Env$ cannot distinguish between the two executions.
The simulator constructs virtual real-world honest parties and invokes $\Adv$. The simulator simulates the environment
and the honest parties towards $\Adv$ as follows: in order to simulate $\Env$, the simulator $\SimAcast$ forwards every message it receives from
$\Env$ to $\Adv$ and vice-versa. To simulate the execution of honest parties, we consider two cases, depending upon whether
$P_S$ is corrupt or not.

Case I: $P_S$ is honest.

In this case, $\SimAcast$ first interacts with $\FAcast$ and receives
the output $m$ from the functionality.
The simulator then plays the role of $P_S$ with input $m$, as well as the role of the
honest parties, and
interacts with $\Adv$ as per the steps of $\PiAcast$.

It is easy to see that that view of $\Adv$ is identical in the real execution and simulated execution. This is because
only $P_S$ has input in the protocol and in the simulated execution, $\SimAcast$ plays the role of $P_S$ as per $\PiAcast$ after
learning the input of $P_S$ from $\FAcast$. Next, conditioned on the view of $\Adv$, we show that the outputs of the honest parties are
identical in both the executions. So consider an arbitrary $\View$ of $\Adv$.
Conditioned on $\View$, all honest parties eventually obtain a  request-based delayed output  $m$
in the simulated execution, where $m$ is the input of $P_S$ as per $\View$.
We show that even in the  real execution, all honest parties eventually output $m$.
This is because all honest parties eventually  complete steps $1-4$ in the protocol, even if the corrupt parties do not send their messages, as
the messages of the honest parties $\PartySet \setminus Z^{\star}$ are eventually selected for delivery
and $\PartySet \setminus Z^{\star} \not \in \AdvStructure$; the latter holds, as otherwise $\AdvStructure$
does not satisfy the $\Q^{(2)}(\PartySet, \AdvStructure)$ condition.
$\Adv$ may send
$\echo$ and $\Ready$
messages for $m'$, where $m' \neq m$, on the behalf of corrupt parties. But since $Z^{\star} \in \AdvStructure$ and since
$\AdvStructure$ satisfies the $\Q^{(2)}(\PartySet, \AdvStructure)$ condition, it follows that
no honest party ever generates a $\Ready$ message for $m'$,  neither in step $2$, nor in step $3$.
Thus the output of the honest parties is identically distributed in both the worlds.
Consequently, in this case, we conclude that $\Big \{\REAL_{\PiAcast, \Adv(z), \Env}(m) \Big \}_{m \in \{0, 1\}^{\ell}, z \in \{0, 1 \}^{\star}}
\equiv \Big \{\IDEAL_{\FAcast, \SimAcast(z), \Env}(m) \Big\}_{m \in \{0, 1\}^{\ell}, z \in \{0, 1 \}^{\star}}$ holds, where
$\equiv$ denotes perfect indistinguishability.

Case II: $P_S$ is corrupt. In this case, $\SimAcast$ first plays the role of the honest parties and interacts with
$\Adv$, as per $\PiAcast$. If in this execution, $\SimAcast$ finds that some honest party, say
$P_h$, outputs $m^{\star}$, then $\SimAcast$ interacts with $\FAcast$
by sending $m^{\star}$ as the input to $\FAcast$, on the behalf of $P_S$.
Else, $\SimAcast$ does not provide any input to $\FAcast$ on the behalf of $P_S$.

It is easy to see that the view of $\Adv$ is identically distributed in the real and the simulated execution.
This is because only $P_S$, which is under the control of $\Adv$, has an input in the protocol,
and $\SimAcast$ plays the role of the honest parties exactly as per the protocol $\PiAcast$.
We next show that conditioned on the view of $\Adv$, the outputs of the honest parties are identically distributed
in both the executions.

Consider an arbitrary view $\View$ of $\Adv$, during an execution of $\PiAcast$.
If according to $\View$, no honest party obtains an output during the execution of $\PiAcast$, then the honest parties do not obtain any output
in the simulated execution as well. This is because in this case, $\SimAcast$ does not provide any input on the behalf of $P_S$
to $\FAcast$. On the other hand, consider the case when according to $\View$, some honest party $P_h$ outputs $m^{\star}$.
In this case, in the simulated execution, all honest parties eventually obtain an output $m^{\star}$, since $\SimAcast$ provides
$m^{\star}$ as the input to $\FAcast$ on the behalf of $P_S$. We next show that even in the real execution, all honest parties
eventually obtain the output $m^{\star}$.

Since $P_h$ obtained the output $m^{\star}$, it received $\Ready$ messages for $m^{\star}$ during step $4$ of the protocol
from a set of parties $\PartySet \setminus Z$, for some $Z \in \AdvStructure$.
Let $\Hon$ be the set of honest parties whose $\Ready$ messages are received by $P_h$ during step $4$. It is easy to see that
$\Hon \not \in \AdvStructure$, as otherwise, $\AdvStructure$ does not satisfy
the  $\Q^{(3)}(\PartySet, \AdvStructure)$ condition.
The $\Ready$ messages of the parties in $\Hon$ are eventually delivered to every honest party
and hence, each honest party (including $P_h$) eventually executes step $3$ and sends a
$\Ready$ message for $m^{\star}$.
It follows that the $\Ready$ messages of all honest parties $\PartySet \setminus Z^{\star}$
are eventually delivered
to every honest party (irrespective of whether $\Adv$ sends all the required
messages), guaranteeing that all honest parties eventually obtain some output. To complete the proof,
we show that this output is the same as $m^{\star}$.

For contradiction, let
$P_{h'} \neq P_h$ be an honest party who outputs
$m^{\star \star} \neq m^{\star}$. This implies that
$P_{h'}$ received $\Ready$ message for $m^{\star \star}$ from at least
one honest party.
From the protocol steps, it follows that an honest party generates a $\Ready$
message for some potential $m$, only if it either receives $\echo$ messages for $m$ during step 2 from a set of parties $\PartySet \setminus Z$ for some $Z \in \AdvStructure$,
or $\Ready$ messages for $m$ from a set of parties $C \not \in \AdvStructure$ during step 3.
So, in order that a subset of parties $\PartySet \setminus Z$ for some $Z \in \AdvStructure$ eventually generates
$\Ready$ messages for some potential $m$ during step 4, it must be
the case that some honest party has received $\echo$ messages for $m$ during step 1 from a set of parties $\PartySet \setminus Z'$ for some
$Z' \in \AdvStructure$ and has generated a
$\Ready$ message for $m$.

Since $P_h$ received the $\Ready$ message for $m^{\star}$ from at least one honest party, it must be the case that
some honest party has received $\echo$ messages for $m^{\star}$ from a set of parties $\PartySet \setminus Z_1$ for some $Z_1 \in \AdvStructure$.
Similarly, since $P_{h'}$ received the $\Ready$ message for $m^{\star \star}$ from at least one honest party, it must be the case that
some honest party has received $\echo$ messages for $m^{\star \star}$ from a set of parties $\PartySet \setminus Z_2$ for some $Z_2 \in \AdvStructure$.
Let ${\cal T} = (\PartySet \setminus Z_1) \cap (\PartySet \setminus Z_2)$. Since $\AdvStructure$
satisfies the $\Q^{(3)}(\PartySet, \AdvStructure)$ condition, it follows
that $\AdvStructure$
satisfies the $\Q^{(1)}({\cal T}, \AdvStructure)$ condition and hence ${\cal T}$ is guaranteed to have at least one honest party.
This further implies that there exists some honest party who generated an $\echo$ message for $m^{\star}$ as well
as $m^{\star \star}$ during step 1, which is impossible. This is because an honest party executes step 1 at most once
and hence, generates an $\echo$ message at most once.
$\Big \{\REAL_{\PiAcast, \Adv(z), \Env}(m) \Big \}_{m \in \{0, 1\}^{\ell}, z \in \{0, 1 \}^{\star}}
\equiv \Big \{\IDEAL_{\FAcast, \SimAcast(z), \Env}(m) \Big\}_{m \in \{0, 1\}^{\ell}, z \in \{0, 1 \}^{\star}}$ holds.

§.§ Asynchronous Byzantine Agreement (ABA)

In a synchronous BA protocol, each party participates with an input bit to obtain an output bit. The protocol guarantees the following three properties.

– Agreement: The output bit of all honest parties is the same.

– Validity: If all honest parties have the same input bit, then this will be the common output bit.

– Termination: All honest parties eventually complete the protocol.

In an ABA protocol, the above requirements are slightly weakened, since all (honest) parties may not be able to provide their inputs to the
protocol, as waiting for all the inputs may turn out to be an endless wait.
Hence the decision is taken based on the inputs of a subset of parties $\CoreSet$, where $\PartySet \setminus \CoreSet \in \AdvStructure$.
Moreover, since the adversary can control the schedule of message delivery,
it has full control in deciding the set $\CoreSet$.

The formal specification of an ideal ABA functionality is presented in Fig <ref>, which is obtained by generalizing the corresponding ideal functionality
against threshold adversaries, as presented in
[15]. Intuitively, it can be considered as
a special case of the ideal AMPC functionality (see Fig <ref>), which looks at the set of inputs provided by the
set of parties in $\CoreSet$, where $\CoreSet$ is decided by the ideal-world adversary. If the input bits provided by all the honest parties in
$\CoreSet$ are the same, then it is set as the output bit. Else, the output bit is set to be the input bit provided by some corrupt party
in $\CoreSet$ (for example, the first corrupt party in $\CoreSet$ according to lexicographic ordering).
In the functionality, the inputs bits provided by various parties are considered to be the “votes" of the respective parties.

$\FABA$The ideal functionality for asynchronous Byzantine agreement for session id $\sid$.fig:FABA

$\FABA$ proceeds as follows, running with the parties $\PartySet = \{P_1, \ldots, P_n \}$ and an adversary $\Sim$, and is parametrized
by an adversary-structure $\AdvStructure \subseteq 2^{\PartySet}$. Let $Z^{\star}$ denote the set of corrupt parties, where
$Z^{\star} \in \AdvStructure$ and let $\Hon = \PartySet \setminus Z^{\star}$. For each party $P_i$, initialize an input value $x^{(i)} = \bot$.

* Upon receiving a message $(\vote, \sid, b)$ from some $P_i \in \PartySet$ (or from $\Sim$ if $P_i$ is corrupt) where $b \in \{0, 1 \}$, do the following:

* Ignore the message if output has been already computed;

* Else, set $x^{(i)} = b$ and send $(\vote, \sid, P_i, b)$ to $\Sim$.[If $P_i \in Z^{\star}$, then no need to send
$(\vote, \sid, P_i, b)$ to $\Sim$ as the input has been provided
by $\Sim$ only.]

* Upon receiving a message $(\coreset, \sid, \CoreSet)$ from $\Sim$, do the following:[As in the case
of the AMPC functionality $\Functionality$, $\Sim$ cannot delay sending $\CoreSet$ indefinitely.]

* Ignore the message if $(\PartySet \setminus \CoreSet) \not \in \AdvStructure$ or if output has been already computed;

* Else, record $\CoreSet$.

* If the set $\CoreSet$ has been recorded and the value $x^{(i)}$ has been set to a value different from $\bot$ for every $P_i \in \CoreSet$, then
compute the output $y$ as follows and generate a request-based delayed output $(\decide, \sid, (\CoreSet, y))$ for every $P_i \in \PartySet$.

* If $x^{(i)} = b$ holds for all $P_i \in (\Hon \cap \CoreSet)$, then set $y = b$.

* Else, set $y = x^{(i)}$, where $P_i$ is the party with the smallest index in $\CoreSet \cap Z^{\star}$.

§ PROPERTIES OF THE PERFECTLY-SECURE PREPROCESSING PHASE

In this section, we prove the security properties of all the perfectly-secure subprotocols, followed by the perfectly-secure preprocessing phase.
We first start with the perfectly-secure VSS.

§.§ Asynchronous VSS Protocol

In this section, we recall the perfectly-secure VSS protocol $\PiPerVSS$ from [12]. The protocol is designed with respect to an adversary structure
$\AdvStructure$ and a sharing specification $\ShareSpec = (S_1, \ldots, S_h) \defined \{ \PartySet \setminus Z | Z \in \AdvStructure\}$, such that
satisfies the
$\Q^{(4)}(\PartySet, \AdvStructure)$ condition (this automatically implies that $\ShareSpec$ satisfies the
$\Q^{(3)}(\ShareSpec, \AdvStructure)$
condition). The input for the dealer $P_{\D}$ in the protocol is a vector of shares
$(s_1, \ldots, s_h)$, the goal being to ensure that the parties output a secret-sharing of $s \defined s_1 + \ldots + s_h$, such that
$[s]_q = s_q$, for each $S_q \in \ShareSpec$.
The protocol guarantees that even if $P_{\D}$ is corrupt, if some honest party completes the protocol, then every honest party eventually completes the protocol such
that there exists some value which has been secret-shared by $P_{\D}$.

The high level idea of the protocol is as follows: the dealer gives the share
$s_q$ to all the parties in the set $S_q \in \ShareSpec$. To verify whether the dealer has distributed the same share to all the parties in $S_q$, the
parties in $S_q$ perform pairwise consistency tests of the supposedly common share and publicly announce the result.
Next, the parties check if there exists a subset of “core" parties $\C_q$, where $S_q \setminus \C_q \in \AdvStructure$, who have positively confirmed the pairwise
consistency of their supposedly common share. Such a subset $\C_q$ is guaranteed for an honest dealer, as the set of honest parties in $S_q$ always
constitutes a candidate set for $\C_q$. To ensure that all honest parties have the same version of the core sets $\C_1, \ldots, \C_h$, the
dealer is assigned the task of identifying these sets based on the results of the pairwise consistency tests, and making them public.
Once the core sets are identified and verified, it is guaranteed that the
dealer has distributed some common share  to all honest parties within $\C_q$.
The next goal is to ensure that even the honest parties in $S_q \setminus \C_q$ get this common share, which is required as per the semantics of our
For this, the (honest) parties in $S_q \setminus \C_q$ “filter" out the supposedly common shares received during the pairwise consistency tests
and ensure that they obtain the common share held by the honest parties in $\C_q$.
Protocol $\PiPerVSS$ is formally presented in Fig <ref>.

$\PiPerVSS$The perfectly-secure VSS protocol for realizing $\FVSS$ in the $\FAcast$-hybrid model.
The above steps are executed by every $P_i \in \PartySet$fig:PerAVSS

* Distribution of Shares by $P_{\D}$ : If $P_i$ is the dealer $P_{\D}$, then execute the following steps.

* On having the shares
$s_1, \ldots, s_h \in \F$, send $(\dist, \sid, P_{\D}, q, [s]_q)$ to all the parties $P_i \in S_q$,
corresponding to each $S_q \in \ShareSpec$, where $s \defined s_1 + \ldots + s_h$ and $[s]_q = s_q$.

* Pairwise Consistency Tests and Public Announcement of Results : For each $S_q \in \ShareSpec$, if $P_i \in S_q$, then execute the following steps.

* Upon receiving $(\dist, \sid, P_{\D}, q, s_{qi})$ from $\D$, send $(\test, \sid, P_{\D}, q, s_{qi})$ to every party $P_j \in S_q$.

* Upon receiving $(\test, \sid, P_{\D}, q, s_{qj})$ from $P_j \in S_q$,
send $(\Sender, \Acast, \sid^{(P_{\D}, q)}_{ij}, \OK_q(i, j))$ to $\FAcast$ if
$s_{qi} = s_{qj}$, where $\sid^{(P_{\D}, q)}_{ij} = \sid || P_{\D} || q || i || j$.[The notation $\sid^{(P_{\D}, q)}_{ij}$ is used here to distinguish among the different calls to
$\FAcast$ within the session $\sid$.]

* Constructing Consistency Graph : For each $S_q \in \ShareSpec$, execute the following steps.

* Initialize $\C_q$ to $\emptyset$. Construct an undirected consistency graph $G^{(i)}_q$ with $S_q$ as the vertex set.

* For every ordered pair of parties $(P_j, P_k)$ where $P_j, P_k \in S_q$,
keep requesting for an output from $\FAcast$ with $\sid^{(P_{\D}, q)}_{jk}$, till an output is received.

* Add the edge $(P_j, P_k)$ to $G^{(i)}_q$ if
outputs $(P_j, \Acast, \sid^{(P_{\D}, q)}_{jk}, \OK_q(j, k))$ and
$(P_k, \Acast, \sid^{(P_{\D}, q)}_{kj}, \allowbreak \OK_q(k, j))$ are received from $\FAcast$ with $\sid^{(P_{\D}, q)}_{jk}$ and
$\FAcast$ with $\sid^{(P_{\D}, q)}_{kj}$ respectively.

* Identification of Core Sets and Public Announcements :  If $P_i$ is the dealer $P_{\D}$, then execute the following steps.

* For each $S_q \in \ShareSpec$, check if there exists a subset of parties $\W_q \subseteq S_q$, such that $S_q \setminus \W_q \in \AdvStructure$
and the parties in $\W_q$ form a clique in the consistency graph $G^{\D}_q$. If such a $\W_q$ exists, then assign $\C_q \coloneqq \W_q$.

* Upon computing the sets $\C_1, \ldots, \C_h$,
send $(\Sender, \Acast, \sid_{P_{\D}}, \allowbreak \{ \C_q \}_{S_q \in \ShareSpec})$ to $\FAcast$, where $\sid_{P_{\D}} = \sid || P_{\D}$.

* Share Computation : Execute the following steps.

1. For each $S_q \in \ShareSpec$ such that $P_i \in S_q$, initialize $[s]_q $ to $\bot$.

2. Keep requesting for an output from $\FAcast$ with $\sid_{P_\D}$ until an output is received.

3. Upon receiving an output $(\Sender, \Acast, \sid_{P_{\D}}, \{ \C_q \}_{S_q \in \ShareSpec})$ from $\FAcast$ with $\sid_{P_{\D}}$,
wait until the parties in $\C_q$ form a clique in $G^{(i)}_q$, for $q = 1, \ldots, h$. Then, verify if
$S_q \setminus \C_q \in \AdvStructure$, for each $q = 1, \ldots, h$.
If the verification is successful, then proceed to compute the output
as follows.

i. Corresponding to each $\C_q$ such that $P_i \in \C_q$, set $[s]_q \coloneqq s_{qi} $.

ii. Corresponding to each $\C_q$ such that $P_i \not \in \C_q$, set $[s]_q \coloneqq s_{q}$, where $(\test, \sid, P_{\D}, q, s_{q})$
is received from a set of parties $\C'_q$
such that $\C_q \setminus \C'_q \in \AdvStructure$.

4. Once $[s]_q \neq \bot$ for each $S_q \in \ShareSpec$ such that $P_i \in S_q$, output $(\Share, \sid,P_{\D}, \{[s]_q\}_{P_i \in S_q})$.

We next prove the security of the protocol $\PiPerVSS$.

Consider a static malicious adversary $\Adv$ characterized by an adversary-structure $\AdvStructure$, satisfying the $\Q^{(4)}(\PartySet, \AdvStructure)$ condition
and let  $\ShareSpec = (S_1, \ldots, S_h) \defined \{ \PartySet \setminus Z | Z \in \AdvStructure\}$ be the sharing specification.[Hence $\ShareSpec$
satisfies the $\Q^{(3)}(\ShareSpec, \AdvStructure)$ condition.]
Then protocol $\PiPerVSS$ UC-securely realizes the functionality $\FVSS$
with perfect security in the $\FAcast$-hybrid model, in the
presence of $\Adv$.

Let $\Adv$ be an arbitrary adversary corrupting a set of parties
$Z^{\star} \in \AdvStructure$. Let $\Env$ be an arbitrary environment. We show the existence of a simulator $\SimPVSS$, such that for any
$Z^{\star} \in \AdvStructure$,
the outputs of the honest parties and the view of the adversary in the
protocol $\PiPerVSS$ is indistinguishable from the outputs of the honest parties and the view of the adversary in an execution in the ideal world involving
$\SimPVSS$ and $\FVSS$. The steps of the simulator will be different depending on whether the dealer is corrupt of honest.

If the dealer is honest, then the simulator interacts with $\FVSS$ and receives the shares of the corrupt parties corresponding to the sets $S_q \in \ShareSpec$
which they are part of. With these shares, the simulator then plays the role of the dealer as well as the honest parties, as per the steps of $\PiPerVSS$, and interacts with
$\Adv$. The simulator also plays the role of $\FAcast$. If $\Adv$ queries $\FAcast$ for the result of any pairwise consistency test involving an honest party, the simulator provides the appropriate result. In addition, the simulator records the result of any test involving corrupt parties which $\Adv$  sends to $\FAcast$.
Based on the results of these pairwise consistency tests, the simulator finds the core sets for each $S_q$ and sends these to $\Adv$ upon request.

If the dealer is corrupt, the simulator plays the role of honest parties and interacts with $\Adv$, as per the
steps of  $\PiPerVSS$. This involves recording shares which $\Adv$ distributes to any
honest party (on the behalf of the dealer),
as well as performing pairwise consistency tests on their behalf. If $\Adv$ sends core sets for each $S_q \in \ShareSpec$ as input to $\FAcast$, then the simulator checks if these are valid, and accordingly, sends the shares held by honest parties in these core sets as the input shares to $\FVSS$ on the behalf
of the dealer. The simulator is presented in Figure <ref>.

$\SimPVSS$Simulator for the protocol $\PiPerVSS$ where $\Adv$ corrupts the parties in set $Z^{\star} \in \AdvStructure$fig:SimPVSS

$\SimPVSS$ constructs virtual real-world honest parties and invokes the real-world adversary $\Adv$. The simulator simulates the view of
$\Adv$, namely its communication with $\Env$, the messages sent by the honest parties and the interaction with $\FAcast$.
In order to simulate $\Env$, the simulator $\SimPVSS$ forwards every message it receives from
$\Env$ to $\Adv$ and vice-versa.  The simulator then simulates the various phases of the protocol as follows, depending upon whether the dealer is honest or corrupt.

Simulation When $P_{\D}$ is Honest

Interaction with $\FVSS$: The simulator interacts with the functionality $\FVSS$ and receives a request based delayed output
$(\Share,\sid,P_{\D},\{[s]_q\}_{S_q \cap Z^{\star} \neq \emptyset})$, on the behalf of the parties in $Z^{\star}$.

Distribution of Shares by $P_{\D}$: On the behalf of the dealer, the simulator sends $(\dist, \sid, P_{\D}, q, [s]_q)$ to $\Adv$, corresponding to
every $P_i \in Z^{\star} \cap S_q$.

Pairwise Consistency Tests: For each $S_q \in \SharingSpec$ such that $S_q \cap Z^{\star} \neq \emptyset$,
corresponding to each $P_i \in S_q \cap Z^{\star}$, the simulator does the following.

–  On the behalf of every party $P_j \in S_q \setminus Z^{\star}$, send $(\test, \sid, P_{\D}, q, s_{qj})$ to $\Adv$, where $s_{qj} = [s]_q$.

– If $\Adv$ sends $(\test, \sid, P_{\D}, q, s_{qi})$ on the behalf of $P_i$ to any $P_j \in S_q$, then record it.

Announcing Results of Consistency Tests:

– If for any $S_q \in \SharingSpec$, $\Adv$ requests an output from $\FAcast$ with $\sid^{(P_{\D}, q)}_{ij}$ corresponding to parties
$P_i \in S_q \setminus Z^{\star}$ and $P_j \in S_q$, then the simulator provides output on the behalf of $\FAcast$ as follows.

* If $P_j \in S_q \setminus Z^{\star}$, then send the output $(P_i, \Acast, \sid^{(P_{\D}, q)}_{ij}, \OK_q(i,j))$.

* If $P_j \in (S_q \cap Z^{\star})$, then send the output $(P_i, \Acast ,\sid^{(P_{\D}, q)}_{ij}, \OK_q(i,j))$, if
the message $(\test, \sid, P_{\D}, \allowbreak q, s_{qj})$ has been recorded
on the behalf of $P_j$ for party $P_i$ and
$s_{qj} = [s]_q$ holds.

– If for any $S_q \in \SharingSpec$ and any $P_i \in S_q \cap Z^{\star}$,
$\Adv$ sends $(P_i, \Acast, \sid^{(P_{\D}, q)}_{ij}, \OK_q(i,j))$ to $\FAcast$
with $\sid^{(P_{\D}, q)}_{ij}$ on the behalf of
$P_i$ for any $P_j \in S_q$, then the simulator records it.
Moreover, if $\Adv$ requests for an output from $\FAcast$ with $\sid^{(P_{\D}, q)}_{ij}$, then
the simulator sends the output $(P_i, \Acast ,\sid^{(P_{\D}, q)}_{ij}, \OK_q(i,j))$ on the behalf of $\FAcast$.

Construction of Core Sets and Public Announcement:

– For each $S_q \in \ShareSpec$, the simulator plays the role of $P_{\D}$ and adds the edge $(P_i,P_j)$ to the graph $G^{\D}_q$ over the vertex set $S_q$, if the following hold.

* $P_i,P_j \in S_q$.

* One of the following is true.

* $P_i,P_j \in S_q \setminus Z^{\star}$.

* If $P_i \in S_q \cap Z^{\star}$ and $P_j \in S_q \setminus Z^{\star}$, then the simulator has recorded
$(P_i, \Acast, \sid^{(P_{\D}, q)}_{ij}, \OK_q(i,j))$ sent by $\Adv$ on the behalf of $P_i$ to $\FAcast$ with $\sid^{(P_{\D}, q)}_{ij}$,
and recorded $(\test, \sid, P_{\D}, q, s_{qi})$ on the behalf of $P_i$ for $P_j$ such that $s_{qi} = [s]_q$.

* If $P_i, P_j \in S_q \cap Z^{\star}$, then the simulator has recorded $(P_i, \Acast, \sid^{(q)}_{ij}, \OK_q(i,j))$
and $(P_j, \Acast,  \sid^{(q)}_{ji}, \allowbreak \OK_q(j,i))$ sent by $\Adv$ on behalf $P_i$ and $P_j$ to
$\FAcast$ with $\sid^{(P_{\D}, q)}_{ij}$ and $\sid^{(P_{\D}, q)}_{ji}$ respectively.

– For each $S_q \in \ShareSpec$, the simulator finds the set $\C_q$ which forms a clique in $G^{\D}_q$, such that $S_q \setminus \C_q \in \AdvStructure$.
When $\Adv$ requests output from $\FAcast$ with $\sid_{P_{\D}}$,
the simulator sends the output $(\Sender, \Acast, \sid_{P_{\D}}, \{\C_q\}_{S_q \in \ShareSpec})$ on the behalf of $\FAcast$.

Simulation When $P_{\D}$ is Corrupt

In this case, the simulator $\SimPVSS$ interacts with $\Adv$ during the various phases of $\PiPerVSS$ as follows.

Distribution of shares by $P_{\D}$: For $q = 1, \ldots, h$, if $\Adv$ sends $(\dist, \sid, P_{\D}, q, v)$
on the behalf of $P_{\D}$ to any party $P_i \in S_q \setminus Z^{\star}$, then the simulator records it and sets $s_{qi}$ to be $v$.

Pairwise Consistency Tests: For each $S_q \in \SharingSpec$ such that
$S_q \cap Z^{\star} \neq \emptyset$, corresponding to each party $P_i \in S_q \cap Z^{\star}$ and each
$P_j \in S_q \setminus Z^{\star}$, the simulator does the following.

– If $s_{qj}$ has been set to some value, then send $(\test,\sid, P_{\D}, q, s_{qj})$ to $\Adv$ on the behalf of $P_j$.

– If $\Adv$ sends $(\test, \sid, P_{\D}, q, s_{qi})$ on the behalf of $P_i$ to $P_j$, then record it.

Announcing Results of Consistency Tests:

– If for any $S_q \in \SharingSpec$, $\Adv$ requests an output from $\FAcast$ with $\sid^{(P_{\D}, q)}_{ij}$ corresponding to
parties $P_i \in S_q \setminus Z^{\star}$ and $P_j \in S_q$, then the simulator provides the
output on the behalf of $\FAcast$ as follows, if $s_{qi}$ has been set to some value.

* If $P_j \in S_q \setminus Z^{\star}$, then send the output $(P_i,\Acast,\sid^{(P_{\D}, q)}_{ij},\OK_q(i,j))$, if
$s_{qj}$ has been set to some value and $s_{qi} = s_{qj}$ holds.

* If $P_j \in S_q \cap Z^{\star}$, then send the output $(P_i,\Acast,\sid^{(P_{\D}, q)}_{ij},\OK_q(i,j))$,
if $(\test, \sid, P_{\D}, q, s_{qj})$ sent by $\Adv$ on the behalf of $P_j$ to $P_i$ has been recorded and $s_{qj} = s_{qi}$ holds.

–  If for any $S_q \in \SharingSpec$ and any $P_i \in S_q \cap Z^{\star}$,
$\Adv$ sends $(P_i, \Acast, \sid^{(P_{\D}, q)}_{ij}, \OK_q(i,j))$ to $\FAcast$
with $\sid^{(P_{\D}, q)}_{ij}$ on the behalf of
$P_i$ for any $P_j \in S_q$, then the simulator records it.
Moreover, if $\Adv$ requests for an output from $\FAcast$ with $\sid^{(P_{\D}, q)}_{ij}$, then
the simulator sends the output $(P_i, \Acast ,\sid^{(P_{\D}, q)}_{ij}, \OK_q(i,j))$ on the behalf of $\FAcast$.

Construction of Core Sets: For each $S_q \in \ShareSpec$, the simulator plays the role of
the honest parties $P_i \in S_q \setminus Z^{\star}$ and adds the edge $(P_j,P_k)$ to the graph $G^{(i)}_q$ over vertex set $S_q$, if the following hold.

– $P_j, P_k \in S_q$.

– One of the following is true.

* If $P_j, P_k \in S_q \setminus Z^{\star}$, then the simulator has set $s_{qj}$ and $s_{qk}$ to some values, such that $s_{qj} = s_{qk}$.

* If $P_j \in S_q \cap Z^{\star}$ and $P_k \in S_q \setminus Z^{\star}$, then the simulator has recorded
$(P_j, \Acast, \sid^{(P_{\D}, q)}_{jk}, \OK_q(j, k))$ sent by $\Adv$ on the behalf of $P_j$ to $\FAcast$ with $\sid^{(P_{\D}, q)}_{jk}$,
and recorded $(\test, \sid, P_{\D}, q, s_{qj})$ on the behalf of $P_j$ for $P_k$ and has set $s_{qk}$ to a value such that $s_{qj} = s_{qk}$.

* If $P_j, P_k \in S_q \cap Z^{\star}$, then the simulator has recorded
$(P_j, \Acast, \sid^{(P_{\D}, q)}_{jk}, \OK_q(j, k))$ and $(P_k, \Acast,  \sid^{(P_{\D}, q)}_{kj}, \allowbreak \OK_q(k, j))$ sent by $\Adv$ on behalf of
$P_j$ and $P_k$ respectively to $\FAcast$ with $\sid^{(P_{\D}, q)}_{jk}$ and $\FAcast$ with $\sid^{(P_{\D}, q)}_{kj}$.

Verification of Core Sets and Interaction with $\FVSS$:

* If  $\Adv$ sends $(\Sender, \Acast, \sid_{P_{\D}}, \{\C_q\}_{S_q \in \ShareSpec})$ to $\FAcast$ with $ \sid_{P_{\D}}$ on the behalf of
$P_{\D}$, then the simulator records it. Moreover, if $\Adv$ requests an output from $\FAcast$ with $ \sid_{P_{\D}}$, then on the behalf
of $\FAcast$, the simulator sends the output $(P_{\D}, \Acast , \sid_{P_{\D}}, \{\C_q\}_{S_q \in \ShareSpec})$.

* If simulator has recorded the sets  $ \{\C_q\}_{S_q \in \ShareSpec}$, then it plays
the role of the honest parties and verifies if $\C_1, \ldots, \C_h$ are valid  by checking
if each $S_q \setminus \C_q \in \AdvStructure$ and if each $\C_q$ constitutes a clique in the graph $G^{(i)}_q$ of every party $P_i \in \PartySet \setminus Z^{\star}$.
If $\C_1, \ldots, \C_h$ are valid, then the simulator sends $(\Share, \sid, P_{\D}, \{s_q\}_{S_q \in \ShareSpec})$ to $\FVSS$, where $s_q$ is set to
$s_{qi}$ corresponding to any $P_i \in \C_q \setminus Z^{\star}$.

We now prove a series of claims which will help us prove the theorem. We start with an honest

If $P_{\D}$ is honest, then the view of $\Adv$ in the simulated execution of $\PiPerVSS$ with $\SimPVSS$ is identically distributed to the view of $\Adv$ in the real execution of $\PiPerVSS$ involving honest parties.

Let $\ShareSpec^{\star} \defined
\{S_q \in \ShareSpec \mid S_q \cap Z^{\star} \neq \emptyset \}$. Then the
view of $\Adv$ during the various executions consists of the following.

– The shares $\{[s]_q\}_{S_q \in \ShareSpec^{\star}}$ distributed by $P_{\D}$: In the real execution, $\Adv$ receives $[s]_q$ from $P_{\D}$ for each $S_q \in \ShareSpec^{\star}$. In the simulated execution, the simulator provides this to $\Adv$ on behalf of $P_{\D}$. Clearly, the distribution of the shares is identical in both the

– Corresponding to every $S_q \in \ShareSpec^{\star}$,
messages $(\test, \sid, P_{\D}, q, s_{qj})$ received from party $P_j \in S_q \setminus Z^{\star}$,
as part of pairwise consistency tests, where $s_{qj} = [s]_q$: While each $P_j$ sends this to $\Adv$ in the real execution, the simulator sends this on the behalf of $P_j$ in the simulated execution.
Clearly, the distribution of the messages is identical in both the executions.

– For every $S_q \in \ShareSpec$ and every $P_i,P_j \in S_q$, the outputs $\OK_q(P_i, \Acast, \sid^{(P_{\D}, q)}_{ij}, \OK_q(i,j))$
of the pairwise consistency tests, received as output from $\FAcast$ with $\sid^{(P_{\D}, q)}_{ij}$:
To compare the distribution of these messages in the two executions,
we consider the following cases, considering an arbitrary $S_q \in \ShareSpec$ and arbitrary $P_i, P_j \in S_q$.

– $P_i,P_j \in S_q \setminus Z^{\star}$: In both the executions,
$\Adv$ receives $\OK_q(P_i, \Acast, \sid^{(P_{\D}, q)}_{ij}, \OK_q(i,j))$ as the output from $\FAcast$ with $\sid^{(P_{\D}, q)}_{ij}$.

– $P_i \in S_q \setminus Z^{\star}, P_j \in (S_q \cap Z^{\star}) $:  In both the
executions, $\Adv$ receives $\OK_q(P_i, \Acast, \sid^{(P_{\D}, q)}_{ij}, \allowbreak \OK_q(i,j))$ as the output from $\FAcast$ with
$\sid^{(P_{\D}, q)}_{ij}$ if and only if $\Adv$ sent $(\test, \sid, P_{\D}, q, s_{qj})$ on the behalf of $P_j$ to $P_i$ such that $s_{qj} = [s]_q$ holds.

– $P_i \in (S_q \cap Z^{\star}) $:  In both the executions,
$\Adv$ receives $\OK_q(P_i, \Acast, \sid^{(q)}_{ij}, \OK_q(i,j))$ if and only if
$\Adv$ on the behalf of $P_i$ has sent $(P_i, \Acast, \sid^{(P_{\D}, q)}_{ij}, \OK_q(i,j))$ to $\FAcast$
with $\sid^{(P_{\D}, q)}_{ij}$ for $P_j$.

Clearly, irrespective of the case, the distribution of the $\OK_q$ messages is identical in both the executions.

– The core sets $\{\C_q\}_{S_q \in \ShareSpec}$: In both the
executions, the sets $\C_q$ are determined based on the $\OK_q$ messages delivered to $P_{\D}$. So the distribution of these sets is also identical.

We next claim that if the dealer is honest, then conditioned on the view of the adversary $\Adv$ (which is identically distributed in both the executions, as per the previous claim),
the outputs of the honest parties are identically distributed in both the executions.

If $P_{\D}$ is honest, then conditioned on the view of $\Adv$, the outputs of the honest parties during the execution of $\PiPerVSS$ involving $\Adv$ has the
same distribution as the outputs of the honest parties in the ideal-world involving $\SimPVSS$ and $\FVSS$.

Let $P_{\D}$ be honest and let $\View$ be an arbitrary view of $\Adv$. Moreover, let $\{s_q \}_{S_q \cap Z^{\star} \neq \emptyset}$ be the shares
of the corrupt parties, as per $\View$. Furthermore, let $\{s_q \}_{S_q \cap Z^{\star} = \emptyset}$ be the shares used by $P_{\D}$
in the simulated execution, corresponding to the set $S_q \in \ShareSpec$, such that $S_q \cap Z^{\star} = \emptyset$.
Let $s \defined \displaystyle \sum_{S_q \cap Z^{\star} \neq \emptyset} s_q + \sum_{S_q \cap Z^{\star} = \emptyset} s_q$.
Then in the simulated execution, each honest party $P_i$ obtains the output $\{[s]_q\}_{P_i \in S_q}$ from $\FVSS$, where
$[s]_q = s_q$. We now show that $P_i$ eventually obtains the
output $\{[s]_q\}_{P_i \in S_q}$ in the real execution as well, if $P_{\D}$'s inputs in the protocol $\PiPerVSS$ are
$\{s_q \}_{S_q \in \ShareSpec}$.

Since $P_{\D}$ is honest, it sends the share $s_q$ to all the parties in the set $S_q$, which is eventually delivered. Now consider
an arbitrary $S_q \in \ShareSpec$.
During the pairwise consistency tests, each honest $P_k \in S_q$ will eventually send $s_{qk} = s_q$ to
all the parties in $S_q$. Consequently, every honest $P_j \in S_q$ will eventually broadcast the message $\OK_q(j, k)$,
corresponding to every honest $P_k \in S_q$. This is because $s_{qj} = s_{qk} = s_q$ will hold.
These $\OK_q(j, k)$ messages are eventually received by every honest party, including $P_\D$.
This implies that the parties in $S_q \setminus Z^{\star}$ will eventually form a clique in the graph $G^{(i)}_q$
of every honest $P_i$. This further implies that $P_{\D}$ will eventually find a set $\C_q$ where $S_q \setminus \C_q \in \AdvStructure$
and where $\C_q$ constitutes a clique in the consistency graph of every honest party.
This is because the set $S_q \setminus Z^{\star}$ is guaranteed to eventually constitute a clique.
Hence $P_{\D}$ eventually broadcasts the sets $\{ \C_q\}_{S_q \in \ShareSpec}$, which are eventually delivered to every honest
party. Moreover, the verification of these sets will eventually be successful for every honest party.

Next, consider an arbitrary honest $P_i \in S_q$. If $P_i \in \C_q$, then it has already received the share $s_q$ from $P_{\D}$
and $s_{qi} = s_q$ holds. Hence, $P_i$ sets $[s]_q$ to $s_q$. So consider the case when $P_i \not \in \C_q$. In this case,
$P_i$ sets $[s]_q$ based on the supposedly common values $s_{qj}$ received from the parties
$P_j \in S_q$ as part of pairwise consistency tests.
Specifically, $P_i$ checks for a subset of parties $\C'_q \subseteq \C_q$, where $\C_q \setminus \C'_q \in \AdvStructure$, such that
every party $P_j \in \C'_q$ has sent the same $s_{qj}$ value to $P_i$ as part of the pairwise consistency test.
If $P_i$ finds such a set $\C'_q$, then it sets $[s]_q$ to the common $s_{qj}$.
To complete the proof, we need to show that $P_i$ will eventually find such a set $\C'_q$,
and if such a set $\C'_q$ is found by $P_i$, then the common $s_{qj}$ is the same as $s_q$.

Assuming that $P_i$ eventually finds such a $\C'_q$, the proof that the common $s_{qj}$ is the same as $s_q$
follows from the fact that $\C'_q$ is guaranteed to contain at least one honest party from $\C_q$, who would have received the share
$s_{qj} = s_q$ from $P_{\D}$ and sent to $P_i$ as part of the pairwise consistency test. This is because $\AdvStructure$
satisfies the $\Q^{(4)}(\PartySet, \AdvStructure)$ condition.
Also, since the $\Q^{(4)}(\PartySet, \AdvStructure)$ condition is satisfied, the set of honest parties in $\C_q$, namely the parties in
$\C_q \setminus Z^{\star}$, always constitute a candidate $\C'_q$ set. This is because every party $P_j \in \C_q \setminus Z^{\star}$
would have sent $s_{qj} = s_q$ to every party in $S_q$ during the pairwise consistency test, and these values are eventually delivered.

We next prove certain claims with respect to a corrupt dealer. The first claim is that the view of $\Adv$ in this
case is also identically distributed in both the real as well as simulated execution. This is simply
because in this case, the honest parties have no inputs
and the simulator simply plays the role of the honest parties exactly
as per the steps of the protocol $\PiPerVSS$ in the simulated execution.

If $P_{\D}$ is corrupt, then
the view of $\Adv$ in the simulated execution of $\PiPerVSS$ with $\SimPVSS$ is identically distributed as the view of $\Adv$ in the real execution of
$\PiPerVSS$ involving honest parties.

The proof follows from the fact that if $P_{\D}$ is corrupt, then $\SimPVSS$ participates in a full execution of the protocol
$\PiPerVSS$, by playing the role of the honest parties as per the steps of $\PiPerVSS$.
Hence, there is a one-to-one correspondence between simulated
executions and real executions.

We finally claim that if the dealer is corrupt, then conditioned on the view of the adversary (which is identical in both
the executions as per the last claim), the outputs of the honest parties are identically distributed in
both the executions.

If $\D$ is corrupt, then conditioned on the view of $\Adv$, the output of the honest parties during the execution of $\PiPerVSS$ involving $\Adv$ has the  same distribution as the output of the honest parties in the ideal-world involving $\SimPVSS$ and $\FVSS$.

Let $P_{\D}$ be corrupt and let
$\View$ be an arbitrary view of $\Adv$. We note that whether valid
core sets $\{\C_q\}_{S_q \in \ShareSpec}$ have been generated during the corresponding execution of $\PiPerVSS$ or not can be found out from $\View$. We now consider the following cases.

– No core sets $\{\C_q\}_{S_q \in \ShareSpec}$ are generated as per $\View$: In this case, the honest parties do not obtain any output in either execution.
This is because in the real execution of $\PiPerVSS$, the honest parties compute their output only when they get valid core sets $\{\C_q\}_{S_q \in \ShareSpec}$
from $P_{\D}$'s broadcast. If this is not the case, then in the simulated execution,
the simulator $\SimPVSS$ does not provide any input to $\FVSS$ on behalf of $P_\D$; hence, $\FVSS$ does not produce any output for the honest parties.

– Core sets $\{\C_q\}_{S_q \in \ShareSpec}$ generated as per $\View$ are invalid:
Again, in this case, the honest parties do not obtain any output in either execution.
This is because in the real execution of $\PiPerVSS$, even if the sets
$\{\C_q\}_{S_q \in \ShareSpec}$ are received from $P_{\D}$'s broadcast,
the honest parties compute their output only when each set $\C_q$ is found to be valid with respect to the verifications
performed by the honest parties in their own consistency graphs.
If these verifications fail (implying that the core sets are invalid), then in the simulated execution,
the simulator $\SimPVSS$ does not provide any input to $\FVSS$ on behalf of $P_\D$, implying that
$\FVSS$ does not produce any output for the honest parties.

– Valid core sets $\{\C_q\}_{S_q \in \ShareSpec}$ are generated as per $\View$:
We first note that in this case, $P_{\D}$ has distributed some common share, say $s_q$, determined by $\View$,
to all the parties in $\C_q \setminus Z^{\star}$ during the real execution of $\PiPerVSS$.
This is because all the parties in $\C_q \setminus Z^{\star}$ are honest, and form a clique
in the consistency graph of the honest parties. Hence,
each $P_j, P_k \in \C_q \setminus Z^{\star}$ has broadcasted the messages $\OK_q(j, k)$ and $\OK_q(k, j)$
after checking that $s_{qj} = s_{qk}$ holds, where $s_{qj}$ and $s_{qk}$ are the shares
received from $P_{\D}$ by $P_j$ and $P_k$ respectively.

We next show that in the real execution of $\PiPerVSS$, every party in $S_q \setminus Z^{\star}$, eventually sets
$[s]_q = s_q$. While this is true for the parties in $\C_q \setminus Z^{\star}$, we consider an arbitrary party
$P_i \in S_q \setminus (Z^{\star} \cup \C_q)$. From the protocol steps,
$P_i$ checks for a subset of parties $\C'_q \subseteq \C_q$ where $\C_q \setminus \C'_q \in \AdvStructure$, such that
every party $P_j \in \C'_q$ has sent the same $s_{qj}$ value to $P_i$ as part of the pairwise consistency test.
If $P_i$ finds such a set $\C'_q$, then it sets $[s]_q$ to the common $s_{qj}$.
We next argue that $P_i$ will eventually find such a set $\C'_q$
and if such a set $\C'_q$ is found by $P_i$, then the common $s_{qj}$ is the same as $s_q$.
The proof for this is exactly the same, as for Claim <ref>.

Thus, in the real execution, every honest party $P_i$ eventually outputs $\{[s]_q = s_q \}_{P_i \in S_q}$.
From the steps of $\SimPVSS$, the simulator sends the shares $\{s_q \}_{S_q \in \ShareSpec}$ to $\FVSS$ on the behalf of
$P_{\D}$ in the simulated execution. Consequently, in the ideal world, $\FVSS$ will eventually deliver
the shares $\{[s]_q = s_q \}_{P_i \in S_q}$ to every honest $P_i$.
Hence, the outputs of the honest parties are identical in both the worlds.

The proof of the theorem now follows
from Claims <ref>-<ref>.

Reducing the Broadcast Complexity of the Protocol $\PiPerVSS$:

Protocol $\PiPerVSS$ as presented in [12] has a broadcast complexity, which is proportional to the size of $\AdvStructure$. More specifically,
in the protocol, $P_\D$ needs to compute a core set $\C_q$ corresponding to each $S_q \in \ShareSpec$. For finding these $\C_q$ sets, every pair of (honest)
parties need to broadcast an $\OK_q$ message for each other by calling $\FAcast$. This results in the number of bits being broadcasted, proportional to $|\ShareSpec|$, where
$|\ShareSpec| = |\AdvStructure|$ in our case. A small modification to the protocol can make the broadcast complexity, independent of $|\AdvStructure|$.
The idea is to let every party broadcast a single $\OK$ message for every other party, if the pairwise consistency test with that party is successful across all
the sets $S_q$ to which both the parties belong. In a more detail, party $P_i$ sends an $\OK(i, j)$ message to $\FAcast$, only after checking whether
$s_{qi} = s_{qj}$ holds corresponding to every $S_q \in \ShareSpec$, such that $P_j \in S_q$ holds. Consequently, $P_\D$ now checks for the presence
of a single core set $\C$ where for $q = 1, \ldots, |\ShareSpec|$, the conditions $\C \subseteq S_q$ and $S_q \setminus \C \in \AdvStructure$ hold. Upon finding such a
$\C$ the dealer broadcasts it by sending it to $\FAcast$. Note that such a $\C$ is eventually obtained for an honest $P_\D$. This is because the set
of parties $(S_1 \setminus Z^{\star}) \cap \ldots \cap (S_q \setminus Z^{\star})$ constitutes a candidate $\C$ for an honest $P_\D$, where
$Z^{\star}$ is the set of corrupt parties. The rest of the protocol steps remain the same. With these modifications, the communication complexity of the
protocol $\PiPerVSS$ is computed as follows: the dealer needs to send the share $s^{(q)}$ to all the parties in $S_q$, and every party in $S_q$ has to send
the received share to every other party in $S_q$ during pairwise consistency tests. This incurs a communication of $\Order(|\AdvStructure| \cdot n^2 \log{|\F|} )$
bits, since each $|S_q| = \Order(n)$ and each share $s^{(q)}$ can be represented by $\log{|\F|}$ bits. There will be total $\Order(n^2)$ $\OK$ messages broadcasted,
where each message can be represented by $\Order(\log n)$ bits, since it represents the index of $2$ parties.
Moreover, $P_\D$ will broadcast a single core set $\C$ of size $\Order(n \log n)$ bits.
Based on this discussion, we next state the following theorem for $\PiPerVSS$.

Consider a static malicious adversary $\Adv$ characterized by an adversary-structure $\AdvStructure$, satisfying the $\Q^{(4)}(\PartySet, \AdvStructure)$ condition
and let  $\ShareSpec = (S_1, \ldots, S_h) \defined \{ \PartySet \setminus Z | Z \in \AdvStructure\}$ be the sharing specification.[Hence $\ShareSpec$
satisfies the $\Q^{(3)}(\ShareSpec, \AdvStructure)$ condition.]
Then protocol $\PiPerVSS$ UC-securely realizes the functionality $\FVSS$
with perfect security in the $\FAcast$-hybrid model, in the
presence of $\Adv$.
The protocol makes $\Order(n^2)$ calls to $\FAcast$ with $\Order(\log{n})$ bit messages, one call to $\FAcast$ with $\Order(n \log{n})$ bit message
and additionally incurs a communication of
$\Order(|\AdvStructure| \cdot n^2 \log{|\F|})$ bits.

By replacing the calls to $\FAcast$ with protocol $\PiAcast$, the protocol incurs a total communication of $\Order(|\AdvStructure| \cdot n^2 \log{|\F|} + n^4 \log{n})$

§.§ Asynchronous Reconstruction Protocols

Let $s$ be a value which is secret-shared with respect to some sharing specification $\ShareSpec = (S_1, \ldots, S_h)$, such that $\ShareSpec$ satisfies the
$\Q^{(2)}(\ShareSpec, \AdvStructure)$ condition. We first present the protocol
$\PiPerRecShare$, which allows all parties in $\PartySet$ to reconstruct a single share $[s]_q$, corresponding to a
designated set $S_q \in \ShareSpec$. In the protocol, every party in $S_q$ sends the share $[s]_q$ to all the parties outside $S_q$, who then
“filter" out the potentially incorrect versions of $[s]_q$ and output $[s]_q$.
Protocol $\PiPerRecShare$ is formally presented in Figure <ref>.

$\PiPerRecShare(q)$Perfectly-secure reconstruction protocol for session id $\sid$ to publicly
reconstruct the share $[s]_q$ corresponding to $S_q \in \ShareSpec$.
The public inputs are $\PartySet$, $\AdvStructure$ and $\ShareSpec$.
The above steps are executed by every $P_i \in \PartySet$fig:PerRecShare

* Sending Share to All Parties: If $P_i \in S_q$, then execute the following steps.

* On having $[s]_q$, send $(\Share,\sid,q,[s]_q)$ to all the parties in $\PartySet \setminus S_q$.

* Computing Output: Based on the following conditions, execute the corresponding steps.

* $P_i \in S_q$: Output $[s]_q$.

* $P_i \notin S_q$: Upon receiving $(\Share, \sid, q, v)$ from a set of parties $S'_q \subseteq S_q$ such that
$S_q \setminus S'_q \in \AdvStructure$, output $[s]_q = v$.

Let $\AdvStructure$ be an adversary structure and let $\ShareSpec = (S_1, \ldots, S_h)$ be a sharing specification, such that
$\ShareSpec$ satisfies the
$\Q^{(2)}(\ShareSpec, \AdvStructure)$ condition. Moreover, let $s$ be a value, which is secret-shared as per $\ShareSpec$.
Then for any $q \in \{1, \ldots, h \}$ and any adversary $\Adv$ corrupting a set of parties $Z^{\star} \in \AdvStructure$,
all honest parties eventually output the share $[s]_q$ in the protocol $\PiPerRecShare$.
The protocol incurs a communication of $\Order(n^2 \log{|\F|})$ bits.

Consider an arbitrary honest party $P_i \in \PartySet$. We consider two cases.

– $P_i \in S_q$: In this case, $P_i$ outputs $[s]_q$.

– $P_i \notin S_q$: In this case, $P_i$ waits for a subset of parties $S'_q \subseteq S_q$ where $S_q \setminus S'_q \in \AdvStructure$, such that
every party $P_j \in S'_q$ has sent the same share $v$ to $P_i$.
If $P_i$ finds such a set $S'_q$, then it outputs $v$.
To complete the proof, we need to show that $P_i$ will eventually find such a set $S'_q$
and if such a set $S'_q$ is found by $P_i$, then the common $v$ is the same as $[s]_q$.

Assuming that $P_i$ eventually finds such a common $S'_q$, the proof that the common $v$ is the same as $[s]_q$
follows from the fact that $S'_q$ is guaranteed to contain at least one honest party from $S_q$, who would have sent the share
$[s]_q$ to $P_i$. This is because the $\Q^{(2)}(\ShareSpec, \AdvStructure)$ condition is satisfied.
Also, since the $\Q^{(2)}(\ShareSpec, \AdvStructure)$ condition is satisfied, the set of honest parties in $S_q$, namely the parties in
$S_q \setminus Z^{\star}$, always constitute a candidate $S'_q$ set. This is because every party $P_j \in S_q \setminus Z^{\star}$
would have sent $[s]_q$ to $P_i$ and these values are eventually delivered to $P_i$.

The communication complexity follows from the protocol steps.

We now present the protocol $\PiPerRec$ (Fig <ref>), which allows all parties in $\PartySet$ to reconstruct a secret shared value $s$.
The idea is to run an instance of $\PiPerRecShare$ for each $S_q \in \ShareSpec$, and to sum up the shares obtained as the
output from each instantiation.

$\PiPerRec$Perfectly-secure reconstruction protocol for session id $\sid$ to reconstruct a shared value $s$. The public inputs of the protocol are $\PartySet, \ShareSpec$
and $\AdvStructure$. The above steps are executed by every $P_i \in \PartySet$fig:PerRec

* Reconstructing Shares: For each $S_q \in \ShareSpec$, participate
in an instance $\PiPerRecShare(q)$ with $\sid$ to obtain the output $[s]_q$.

* Output Computation: Output $s = \displaystyle \sum_{S_q \in \ShareSpec} [s]_q$.

The properties of the protocol $\PiPerRec$ are stated in Lemma <ref>, which follow from the protocol steps and Lemma <ref>.

Let $\AdvStructure$ be an adversary structure and let $\ShareSpec = (S_1, \ldots, S_h)$ be a sharing specification, such that
$\ShareSpec$ satisfies the
$\Q^{(2)}(\ShareSpec, \AdvStructure)$ condition.
Moreover, let $s$ be a value which is secret-shared as per $\ShareSpec$.
Then for every adversary $\Adv$ corrupting a set of parties $Z^{\star} \in \AdvStructure$,
all honest parties eventually output $s$ in the protocol $\PiPerRecShare$.
The protocol incurs a communication of $\Order(|\ShareSpec| \cdot n^2 \log{|\F|})$ bits, which is
$\Order(|\AdvStructure| \cdot n^2 \log{|\F|})$ bits if $|\ShareSpec| = |\AdvStructure|$.

§.§ Properties of the Optimistic Multiplication Protocol $\OptMult$

In this section, we formally prove the properties of the protocol $\OptMult$ (Fig <ref>).
While proving these properties, we will assume that  $\AdvStructure$ satisfies the $\Q^{(4)}(\PartySet, \AdvStructure)$ condition.
This further implies that the sharing specification $\ShareSpec = (S_1, \ldots, S_h) \defined \{ \PartySet \setminus Z | Z \in \AdvStructure\}$
satisfies the $\Q^{(3)}(\ShareSpec, \AdvStructure)$ condition.
Moreover, while proving these properties, we also assume that for every $\iter$,
no honest party is ever included in the set $\Discarded$ and
all honest parties are eventually removed from the $ \Waitlist^{(i)}_{\iter'}, \LocalDiscarded^{(i)}_{\iter'}$ sets of every honest $P_i$ for every
$\iter' < \iter$. Note that these conditions are guaranteed in the protocols $\MultLCE$ and $\MultGCE$ (where these sets are constructed and managed),
where  $\OptMult$ is used as a subprotocol.

For every $Z \in \AdvStructure$ and every ordered pair $(p, q) \in \{1, \ldots, h \} \times \{1, \ldots, h \}$,
the set $(S_p \cap S_q) \setminus Z$ contains at least one honest party.

From the definition of the sharing specification $\ShareSpec$, we have
$S_p = \PartySet \setminus Z_p$ and $S_q = \PartySet \setminus Z_q$, where $Z_p, Z_q \in \AdvStructure$.
Let $Z^{\star} \in \AdvStructure$ be the set of corrupt parties during the protocol $\OptMult$.
If $(S_p \cap S_q) \setminus Z$ does not contain any honest party, then it implies that
$((S_p \cap S_q) \setminus Z) \subseteq Z^{\star}$.
This further implies that   $\PartySet \subseteq Z_p \cup Z_q \cup Z \cup Z^{\star}$, implying that
$\AdvStructure$ does not satisfy the $\Q^{(4)}(\PartySet, \AdvStructure)$ condition, which is a contradiction.

For every $Z \in \AdvStructure$, if all honest parties participate during the hop number $\hop$ in the protocol $\OptMult$, then
all honest parties eventually obtain a common summand-sharing party, say $P_j$, for this hop, such that the honest parties
will eventually hold $[c^{(j)}_{(Z, \iter)}]$. Moreover, party $P_j$ will be distinct from the summand-sharing party
selected for any hop number $\hop' < \hop$.

Since all honest parties participate in hop number $\hop$, it follows that
$\Products_{(Z, \iter)} \neq \emptyset$ at the beginning of hop number $\hop$. This implies that there exists at least one ordered pair $(p, q) \in \Products_{(Z, \iter)}$.
From Claim <ref>,
there exists at least one honest party in $(S_p \cap S_q) \setminus Z$, say $P_k$, who will have both the shares
$[a]_p$ as well as $[b_q]$ (and hence the summand $[a]_p [b]_q$). We also note that $P_k$ would not have been selected as the common summand-sharing
party in any previous $\hop' < \hop$, as otherwise $P_k$ would have already included the summand $[a]_p[b]_q$ in the sum $c^{(k)}_{(Z, \iter)}$ shared
by $P_k$ during hop $\hop'$, implying that $(p, q) \not \in \Products_{(Z, \iter)}$. Now, during the hop number $\hop$, party $P_k$
will randomly secret-share the sum $c^{(k)}_{(Z, \iter)}$ by making a
call to $\FVSS$  and every honest $P_i$ will eventually receive an output
$(\Share, \sid_{\hop, k, \iter, Z}, P_k, \{ [c^{(k)}_{(Z, \iter)}]_q \}_{P_i \in S_q})$  from $\FVSS$
with $\sid_{\hop, k, \iter, Z}$.
Moreover, $P_k$ will not be present in the set $\Discarded$
and if $P_k$ is present in the sets $ \Waitlist^{(i)}_{\iter'}, \LocalDiscarded^{(i)}_{\iter'}$ of any honest $P_i$ for any
$\iter' < \iter$, then it is eventually removed from these sets.

We next claim that during the hop number $\hop$, there will at least one instance of $\FABA$ corresponding to which all honest parties
eventually receive the output $1$. For this, we consider two possible cases:

– At least one honest party participates with input $0$ in the $\FABA$ instance corresponding to $P_k$: Let
$P_i$ be an honest party, who sends $(\vote, \sid_{\hop, k, \iter, Z}, 0)$ to $\FABA$ with
$\sid_{\hop, k, \iter, Z}$. Then from the steps of $\OptMult$, it follows that there exists some $P_j \in \PartySet$, such that
$P_i$ has received
$(\decide, \sid_{\hop, j, \iter, Z}, 1)$ as the output from $\FABA$ with  $\sid_{\hop, j, \iter, Z}$. Hence, every honest party
will eventually receive the output $(\decide, \sid_{\hop, j, \iter, Z}, 1)$ as the output from $\FABA$ with  $\sid_{\hop, j, \iter, Z}$.

– No honest party participates with input $0$ in the $\FABA$ instance corresponding to $P_k$:
In this case, every honest party will eventually send $(\vote, \sid_{\hop, k, \iter, Z}, 1)$ to $\FABA$ with
$\sid_{\hop, k, \iter, Z}$ and eventually receives the output $(\decide, \sid_{\hop, k, \iter, Z}, 1)$ from $\FABA$.

Now, based on the above claim, we can further claim that
all honest parties will eventually participate with some input in all the
$n$ instances of $\FABA$ invoked during the hop number $\hop$
and hence, all the $n$ instances of $\FABA$ during the hop number $\hop$ will eventually produce an output.
Since the summand-sharing party for hop number $\hop$
corresponds to the least indexed $\FABA$ instance in which all the honest parties obtain $1$ as the output,
it follows that eventually the honest parties will select a summand-sharing party. Moreover, this summand-sharing party will be common,
as it is based on the outcome of $\FABA$ instances.

Let $P_j$ be the summand-sharing party for the hop number $\hop$.
We next show that the honest parties will eventually hold $[c^{(j)}_{(Z, \iter)}]$.
For this, we note that since $P_j$ has been selected as the summand-sharing party, at least one honest party, say
$P_i$, must have sent $(\vote, \sid_{\hop, j, \iter, Z}, 1)$ to $\FABA$ with
$\sid_{\hop, j, \iter, Z}$. If not, then $\FABA$ with $\sid_{\hop, j, \iter, Z}$ will never produce the output
$(\decide, \sid_{\hop, j, \iter, Z}, 1)$ and hence $P_j$ will not be the summand-sharing party for the hop number $\hop$.
Now since $P_i$ sent $(\vote, \sid_{\hop, j, \iter, Z}, 1)$ to $\FABA$, it follows that
$P_i$ has received an output $(\Share, \sid_{\hop, j, \iter, Z}, P_j, \{ [c^{(j)}_{(Z, \iter)}]_q \}_{P_i \in S_q})$  from $\FVSS$
with $\sid_{\hop, j, \iter, Z}$. This implies that $P_j$ must have sent the message
$(\Dealer, \sid_{\hop, j, \iter, Z}, (c^{(j)}_{{(\iter, Z)}_1}, \ldots, c^{(j)}_{{(\iter, Z)}_h}))$ to
$\FVSS$ with $\sid_{\hop, j, \iter, Z}$.
Consequently, every honest party will eventually receive their respective outputs from
$\FVSS$ with $\sid_{\hop, j, \iter, Z}$ and hence, the honest parties will eventually hold
$[c^{(j)}_{(Z, \iter)}]$.

Finally, to complete the proof of the claim, we need to show that party $P_j$ is different from the summand-sharing parties selected
during the hops $1, \ldots, \hop - 1$. If $P_j$ has been selected as a summand-sharing party for any hop number $\hop' < \hop$, then
no honest party ever sends $(\vote, \sid_{\hop, j, \iter, Z}, 1)$ to $\FABA$ with
$\sid_{\hop, j, \iter, Z}$. Consequently, $\FABA$ with $\sid_{\hop, j, \iter, Z}$ will never send the output
$(\decide, \sid_{\hop, j, \iter, Z}, 1)$ to any honest party and hence $P_j$ will not be selected as the summand-sharing party
for hop number $\hop$, which is a contradiction.

In protocol $\OptMult$, all honest parties eventually obtain an output.
The protocol makes $\Order(n^2)$ calls to $\FVSS$ and $\FABA$.

From Claim <ref> and <ref>, it follows that the number of hops in the protocol
is $\Order(n)$, as in each hop a new summand-sharing party is selected and if all honest parties are included
in the set of summand-sharing parties $\Selected_{(Z, \iter)}$, then $\Products_{(Z, \iter)}$ becomes $\emptyset$.
The proof now follows from the fact that in each hop, there are $\Order(n)$ calls to $\FVSS$ and $\FABA$.

In protocol $\OptMult$, if no party in $\PartySet \setminus Z$ behaves maliciously, then for each $P_i \in \Selected_{(Z, \iter)}$, the condition
$c^{(i)}_{(Z, \iter)} = \sum_{(p, q) \in \Products^{(i)}_{(Z, \iter)}} [a]_p[b]_q$ holds and
$c_{(Z, \iter)} = ab$.

From the protocol steps, it follows that $\Selected_{(Z, \iter)} \cap Z = \emptyset$, as no honest part ever votes for any party from $Z$ as a candidate
summand-sharing party during any hop in the protocol.
Now since $\Selected_{(Z, \iter)} \subseteq (\PartySet \setminus Z)$,
if no party in $\PartySet \setminus Z$ behaves maliciously, then it implies that every party
$P_i \in \Selected_{(Z, \iter)}$ behaves honestly and secret-shares $c^{(i)}_{(Z, \iter)}$ by calling $\FVSS$, where
$c^{(i)}_{(Z, \iter)} = \sum_{(p, q) \in \Products^{(i)}_{(Z, \iter)}} [a]_p[b]_q$.
Moreover, from the protocol steps, it follows that for every $P_j, P_k \in \Selected_{(Z, \iter)}$:

\[ \displaystyle \Products^{(j)}_{(Z, \iter)} \cap \Products^{(k)}_{(Z, \iter)} = \emptyset.  \]

To prove this, suppose $P_j$ and $P_k$ are included in $\Selected_{(Z, \iter)}$ during hop number $\hop_j$ and $\hop_k$ respectively, where
without loss of generality, $\hop_j < \hop_k$.
Then from the protocol steps, during $\hop_j$, the parties would set
$\Products^{(k)}_{(Z, \iter)} = \Products^{(k)}_{(Z, \iter)} \setminus \Products^{(j)}_{(Z, \iter)}$. This ensures that
during $\hop_k$, there exists no ordered pair $(p, q) \in \{1, \ldots, |\ShareSpec| \} \times \{1, \ldots, |\ShareSpec| \}$, such that
$(p, q) \in \Products^{(j)}_{(Z, \iter)} \cap \Products^{(k)}_{(Z, \iter)}$.

Since all the parties $P_i \in \Selected_{(Z, \iter)}$ have behaved honestly,
from the protocol steps, it also follows that :

\[ \displaystyle \bigcup_{P_i \in \Selected_{(Z, \iter)}} \Products^{(i)}_{(Z, \iter)} = \{ (p, q) \}_{p, q = 1, \ldots, |\ShareSpec|}. \]

Finally, from the protocol steps, it follows that
$\forall P_j \in \PartySet \setminus \Selected_{(Z, \iter)}$, the condition
$c^{(j)}_{(Z, \iter)} = 0$ holds. Now since $c_{(Z, \iter)} =  c^{(1)}_{(Z, \iter)} + \ldots + c^{(n)}_{(Z, \iter)}$, it follows that
if no party in $\PartySet \setminus Z$ behaves maliciously, then $c_{(Z, \iter)} = ab$ holds.

In $\OptMult$, $\Adv$ does not learn any additional information about $a$ and $b$.

Let $Z^{\star} \in \AdvStructure$ be the set of corrupt parties. To prove the claim, we argue that in the protocol, $\Adv$ does not learn any additional information about
the shares $\{[a]_p, [b]_p\}_{S_p \cap Z^{\star} = \emptyset}$. For this, consider an arbitrary summand $[a]_p [b]_q$ where $S_p \cap Z^{\star} = \emptyset$ and where
$q \in \{1, \ldots, h \}$. Clearly, the summand $[a]_p [b]_q$ will not be available with any party in $Z^{\star}$.
Let $P_j$ be the party from $\Selected_{(Z, \iter)}$, such that $(p, q) \in \Products^{(j)}_{(Z, \iter)}$; i.e. the summand
$[a]_p[b]_q$ is included by $P_j$ while computing the summand-sum $c^{(j)}_{(Z, \iter)}$.
Clearly $P_j$ is honest, since $P_j \not \in Z^{\star}$.
In the protocol, party $P_j$ randomly secret-shares the summand-sum $c^{(j)}_{(Z, \iter)}$, by supplying a random vector of shares
for $c^{(j)}_{(Z, \iter)}$ to the corresponding $\FVSS$. Now, since $\ShareSpec$ is $\AdvStructure$-private,
it follows that the shares $\{ [c^{(j)}_{(Z, \iter)}]_r \}_{S_r \cap Z^{\star} \neq \emptyset}$ learnt by $\Adv$ in the protocol
will be independent of the summand $[a]_p[b]_q$ and hence, independent of $[a]_p$. Using a similar argument, we can conclude
that the shares learnt by $\Adv$ in the protocol will be independent of the summands $[a]_q [b]_p$ (and hence independent of $[b]_p$),
where $S_p \cap Z^{\star} = \emptyset$ and where
$q \in \{1, \ldots, h \}$.

Lemma <ref>.

Let  $\AdvStructure$ satisfy the $\Q^{(4)}(\PartySet, \AdvStructure)$ condition and let
$\ShareSpec = (S_1, \ldots, S_h) = \{ \PartySet \setminus Z | Z \in \AdvStructure\}$.
Consider an arbitrary $Z \in \AdvStructure$ and $\iter$,
such that all honest parties participate in the instance $\OptMult(\PartySet,\AdvStruct,\SharingSpec,[a],[b], Z,\iter)$. Then all
honest parties eventually compute  $[c_{(Z, \iter)}]$ and $([c^{(1)}_{(Z, \iter)}], \ldots, [c^{(n)}_{(Z, \iter)}])$
where $c_{(Z, \iter)} = c^{(1)}_{(Z, \iter)} + \ldots + c^{(n)}_{(Z, \iter)}$,
provided no honest party is ever included in the $\Discarded$ and $\LocalDiscarded^{(i)}_{\iter'}$ sets
and every honest party in the $ \Waitlist^{(i)}_{\iter'}$ sets of every honest $P_i$ is eventually removed,
for every
$\iter' < \iter$. If no party in $\PartySet \setminus Z$ behaves maliciously, then
$c_{(Z, \iter)} = ab$ holds. In the protocol, $\Adv$ does not learn any additional information about $a$ and $b$.
The protocol makes $\Order(n^2)$ calls to $\FVSS$ and $\FABA$

The proof follows from Claims <ref>-<ref>.

We end this section by claiming an important property about the protocol $\OptMult$, which will be useful later when we analyze the properties of the
protocol $\MultGCE$ where $\OptMult$ is used as a sub-protocol.

For every $Z \in \AdvStructure$ and every $\iter$, all the following hold for every $P_j \in \Selected_{(Z, \iter)}$ during the instance
$\OptMult(\PartySet,\AdvStruct,\SharingSpec,[a],[b], Z,\iter)$.

– There exists at least one honest party $P_i$, such that
$P_j$ will not be present in the $\Waitlist^{(i)}_{\iter'}$ and $\LocalDiscarded^{(i)}_{\iter'}$ sets of $P_i$ for any $\iter' < \iter$.

– $P_j$ will not be present in the set $\Discarded$.

Consider an arbitrary $P_j \in \Selected_{(Z, \iter)}$, such that $P_j$ is included in $\Selected_{(Z, \iter)}$ during the hop number $\hop$
in the instance $\OptMult(\PartySet,\AdvStruct,\SharingSpec,[a],[b], Z,\iter)$.
We prove the first part of the claim through a contradiction.
Let $\Hon$ be the set of honest parties and
for every $P_i \in \Hon$, let there exist some $\iter' < \iter$, such that either $P_j \in \Waitlist^{(i)}_{\iter'}$ or
$P_j \in \LocalDiscarded^{(i)}_{\iter'}$. This implies that during
hop number $\hop$, no $P_i \in \Hon$ will send $(\vote, \sid_{\hop, j, \iter, Z}, 1)$ to $\FABA$ with
$\sid_{\hop, j, \iter, Z}$. Consequently, $\FABA$ with  $\sid_{\hop, j, \iter, Z}$ will never return the output
$(\decide, \sid_{\hop, j, \iter, Z}, 1)$ for any honest party and hence, $P_j$ will not be selected as the summand-sharing party
for hop number $\hop$, which is a contradiction.

The second part of the claim also follows using a similar argument as above. Namely, if
$P_j$ is present in the set $\Discarded$, then
no $P_i \in \Hon$ will send $(\vote, \sid_{\hop, j, \iter, Z}, 1)$ to $\FABA$ with
$\sid_{\hop, j, \iter, Z}$ and consequently,
$P_j$ will not be selected as the summand-sharing party
for hop number $\hop$, which is a contradiction.

§.§ Properties of the Multiplication Protocol $\MultLCE$ with Cheater Identification

In this section, we formally prove the properties of the protocol $\MultLCE$ (see Fig <ref> for the formal description of the protocol).
While proving these properties, we will assume that  $\AdvStructure$ satisfies the $\Q^{(4)}(\PartySet, \AdvStructure)$ condition.
This further implies that the sharing specification $\ShareSpec = (S_1, \ldots, S_h) \defined \{ \PartySet \setminus Z | Z \in \AdvStructure\}$
satisfies the $\Q^{(3)}(\ShareSpec, \AdvStructure)$ condition. Moreover, we will also assume that no honest party is ever included
in the set $\Discarded$, which will be guaranteed in the protocol $\MultGCE$ where the set $\Discarded$ is constructed and managed, and where
$\MultLCE$ is used as a sub-protocol.

We first give the definition of a successful $\MultLCE$ instance, which will be used
throughout this section and the next.

For an instance $\MultLCE(\PartySet, \AdvStruct, \SharingSpec, [a], [b], \iter)$, we define the following.

– The instance is called successful if and only if
for every $Z \in \AdvStruct$, the value $c_{(Z, \iter)} - c_{(Z', \iter)} = 0$, where $Z' \in \AdvStructure$ is the fixed
set used in the protocol.

– If the instance is not successful, then the sets $Z, Z'$ are called the conflicting-sets for the instance,
if $Z$ is the smallest indexed set from $\AdvStructure$ such that $c_{(Z, \iter)} - c_{(Z', \iter)} \neq 0$.

We first show that any instance of $\MultLCE$ will be eventually found to be either a success or a failure by the honest parties.

For every $\iter$, any instance $\MultLCE(\PartySet, \AdvStruct, \SharingSpec, [a], [b], \iter)$
will eventually be deemed to either succeed or fail by the honest parties,
provided no honest party is ever included in the $\Discarded$ and $\LocalDiscarded^{(i)}_{\iter'}$ sets,
and all honest parties are eventually removed from the $ \Waitlist^{(i)}_{\iter'}$ sets of every honest $P_i$ for every
$\iter' < \iter$.
Moreover, for a
instance, the parties output a sharing of $ab$. If the instance is not successful, then
the parties identify the  conflicting-sets $Z, Z'$ for the instance.

Let $Z^{\star} \in \AdvStructure$ be the set of corrupt parties. If the lemma conditions hold, then
it follows from
Lemma <ref>, that corresponding to every $Z \in \AdvStructure$, the instance $\OptMult(\PartySet, \AdvStruct, \SharingSpec,[a], [b], Z, \iter)$
eventually completes with honest parties obtaining the outputs $[c^{(1)}_{(Z, \iter)}] , \ldots, [c^{(n)}_{(Z, \iter)}], [c_{(Z, \iter)}]$, where
$c_{(Z, \iter)} = c^{(1)}_{(Z, \iter)} + \ldots + c^{(n)}_{(Z, \iter)}$. Moreover, in the $\OptMult$ instance corresponding to $Z^{\star}$,
the output $c_{(Z^{\star}, \iter)}$ will be the same as $ab$, since all the parties in $\PartySet \setminus Z^{\star}$ will be honest.

Since $\ShareSpec$ satisfies the $\Q^{(3)}(\ShareSpec, \AdvStructure)$ condition, it follows that with respect to the fixed
$Z' \in \AdvStruct$, the honest parties will eventually reconstruct the difference $c_{(Z, \iter)} - c_{(Z', \iter)}$, corresponding to every
$Z \in \AdvStructure$. Now there are two possibilities. If all the differences $c_{(Z, \iter)} - c_{(Z', \iter)}$ turn out to be $0$, then
the $\MultLCE$ instance will be considered to be successful by the honest parties and the honest parties will output
$[c_{(Z', \iter)}]$, which is bound to be the same as $ab$. This is because $c_{(Z', \iter)} - c_{(Z^{\star}, \iter)} = 0$ and hence
$c_{(Z', \iter)} = c_{(Z^{\star}, \iter)} = ab$ holds. The other possibility is that all the differences are not zero, in which case
the instance $\MultLCE$ will not be considered successful by the honest parties. Moreover, in this case, the parties will set
$(Z, Z')$ as the conflicting-sets for the instance, where $Z$ is the smallest indexed set from $\AdvStructure$ such that $c_{(Z, \iter)} - c_{(Z', \iter)} \neq 0$.

We next prove a series of claims regarding any $\MultLCE$ instance which is not successful.
We begin by showing that
if any instance of $\MultLCE$ is not successful, then every honest party in eventually removed from the waiting-list
of the honest parties for that instance. Moreover, no honest party will be ever included in the $\LocalDiscarded$ set of any honest party for that instance.

For every $\iter$, if the instance $\MultLCE(\PartySet, \AdvStruct, \SharingSpec, [a], [b], \iter)$ is not successful, then
every honest party from the set $\Selected_{(Z, \iter)} \cup \Selected_{(Z', \iter)}$ is eventually removed from the waiting set
$\Waitlist^{(i)}_{\iter}$ of every honest party $P_i$. Moreover, no honest party is ever included
in the $\LocalDiscarded^{(i)}_{\iter}$ set of any honest party $P_i$.

Suppose that the instance $\MultLCE(\PartySet, \AdvStruct, \SharingSpec, [a], [b], \iter)$ is not successful. This implies that the parties identify
a pair of conflicting-sets $(Z, Z')$, such that $c_{(Z, \iter)} - c_{(Z', \iter)} \neq 0$. From the protocol steps, every honest party
$P_i$ initializes $\Waitlist^{(i)}_{\iter}$ to  $\Selected_{(Z, \iter)} \cup \Selected_{(Z', \iter)}$. Let $P_j$ be an arbitrary
honest party belonging to $\Selected_{(Z, \iter)} \cup \Selected_{(Z', \iter)}$. From the protocol steps,
party $P_j$ secret-shares all the required values $d^{(jk)}_{(Z, \iter)}, e^{(jk)}_{(Z', \iter)}$ by calling appropriate instances of $\FVSS$
and eventually these values are secret-shared, with every honest $P_i$ receiving the appropriate shares
from corresponding $\FVSS$ instances. Consequently, $P_j$ will eventually be removed from the set $\Waitlist^{(i)}_{\iter}$.
Moreover, since $P_j$ is an honest party, the $d^{(jk)}_{(Z, \iter)}, e^{(jk)}_{(Z', \iter)}$ values shared
by $P_j$ will be correct and consequently, the conditions for including $P_j$ to the $\LocalDiscarded^{(i)}_{\iter}$
set of any honest party $P_i$ will fail. That is, if $P_j \in \Selected_{(Z, \iter)}$, then the parties will find that
$\displaystyle c^{(j)}_{(Z, \iter)} - \sum_{P_k \in \Selected_{(Z', \iter)}} d^{(jk)}_{(Z, \iter)} = 0$.
On the other hand, if $P_j \in \Selected_{(Z', \iter)}$, then the parties will find that
$\displaystyle c^{(j)}_{(Z', \iter)} - \sum_{P_k \in \Selected_{(Z, \iter)}} e^{(jk)}_{(Z', \iter)} = 0$.
Moreover, if there exists any $P_k \in \Selected_{(Z, \iter)} \cup \Selected_{(Z', \iter)}$ such that
either $d^{(jk)}_{(Z, \iter)} \neq e^{(kj)}_{(Z', \iter)}$ or $d^{(kj)}_{(Z, \iter)} \neq e^{(jk)}_{(Z', \iter)}$,
then after reconstructing the values shared by $P_j$ and the shares held by $P_j$, the parties
will find that $P_j$ has behaved honestly and hence, $P_j$ will not be included to the
$\LocalDiscarded^{(i)}_{\iter}$ set of any honest $P_i$.

We next give the definition of a conflicting-pair of parties, which is defined based on the partitions of the summand-sum shared by the summand-sharing parties.

Let $\MultLCE(\PartySet, \AdvStruct, \SharingSpec, [a], [b], \iter)$ be an instance of $\MultLCE$ which  is not successful and let $Z, Z'$ be the corresponding conflicting-sets for the instance. A pair of parties $(P_j,P_k)$ is said to be a
conflicting-pair of parties for this $\MultLCE$ instance if all the following hold:

– $P_j \in \Selected_{(Z,\iter)}, P_k \in \Selected_{(Z',\iter)}$;

– $d^{(jk)}_{(Z, \iter)} \neq e^{(kj)}_{(Z', \iter)}$.

We next show that if an instance of $\MultLCE$ is not successful,
then certain conditions hold with respect to the summand-sums and the respective partitions shared by the
summand-sharing parties during the underlying instances of $\OptMult$ and the
phase of the $\MultLCE$ instance.

Let $\MultLCE(\PartySet, \AdvStruct, \SharingSpec, [a], [b], \iter)$ be an instance of $\MultLCE$ which is not successful and let $Z, Z'$ be the corresponding conflicting-sets for the instance. Moreover, let $Z^{\star}$ be the set of corrupt parties.
Then, one of the following must hold true for some $P_j \in Z^{\star}$.

i. $P_j \in \Selected_{(Z, \iter)}$ and
$\displaystyle c^{(j)}_{(Z, \iter)} - \sum_{P_k \in \Selected_{(Z', \iter)}} d^{(jk)}_{(Z, \iter)} \neq 0$.

ii. $P_j \in \Selected_{(Z', \iter)}$ and
$\displaystyle c^{(j)}_{(Z', \iter)} - \sum_{P_k \in \Selected_{(Z, \iter)}} e^{(jk)}_{(Z', \iter)} \neq 0$.

iii. There is some $P_k \in \Selected_{(Z, \iter)} \cup \Selected_{(Z', \iter)}$ such that
either $(P_j,P_k)$ or $(P_k,P_j)$ constitutes a conflicting-pair of parties.

Since the instance of $\MultLCE$ is not successful and $Z, Z'$ constitute
conflicting-sets, it follows that
$c_{(Z,\iter)} \neq c_{(Z',\iter)}$. Assume for the sake of contradiction that the none of the conditions
in the claim is true. Then, we can infer the following.

\begin{align*}
\displaystyle c_{(Z,\iter)} &= \sum_{P_j \in \Selected_{(Z,\iter)}}c^{(j)}_{(Z,\iter)} \\
&= \sum_{P_j \in \Selected_{(Z,\iter)}} \sum_{P_k \in \Selected_{(Z',\iter)}} d^{(jk)}_{(Z,\iter)} \\
&= \sum_{P_j \in \Selected_{(Z,\iter)}} \sum_{P_k \in \Selected_{(Z',\iter)}} e^{(kj)}_{(Z',\iter)} \\
&= \sum_{P_k \in \Selected_{(Z',\iter)}} \sum_{P_j \in \Selected_{(Z,\iter)}} e^{(kj)}_{(Z',\iter)} \\
&= \sum_{P_k \in \Selected_{(Z',\iter)}} c^{(k)}_{(Z',\iter)} \\
&= c_{(Z',\iter)},
\end{align*}

where the first equation follows from the definition of $c_{(Z,\iter)}$, the
second equation holds because, as per our assumption, $\displaystyle c^{(j)}_{(Z, \iter)} - \sum_{P_k \in \Selected_{(Z', \iter)}} d^{(jk)}_{(Z, \iter)} = 0$ for every
$P_j \in \Selected_{(Z, \iter)}$,
the third equation holds because, as per our assumption, there is no conflicting-pair of parties, the fifth equation holds because as per our assumption
$\displaystyle c^{(k)}_{(Z', \iter)} - \sum_{P_j \in \Selected_{(Z, \iter)}} e^{(kj)}_{(Z', \iter)} = 0$ for every
$P_k \in \Selected_{(Z', \iter)}$ and the last equation follows from the definition of $c_{(Z',\iter)}$. However,  $c_{(Z,\iter)} = c_{(Z',\iter)}$ is a contradiction.

We next define a characteristic function with respect to the partitions of the summands-sum shared by the summand-sharing parties,
to “characterize" instances of $\MultLCE$ which are not successful. Looking ahead, this will be helpful to upper bound the number of
failed $\MultLCE$ instances in the protocol $\MultGCE$.

Let $\MultLCE(\PartySet, \AdvStruct, \SharingSpec, [a], [b], \iter)$ be an instance of $\MultLCE$
which is not successful and let $Z, Z'$ be the corresponding conflicting-sets for the instance. Then
the characteristic function $f_{\Char}$ for this instance is defined as follows.

– If there is some
$P_j \in \Selected_{(Z,\iter)}$ such that $\displaystyle c^{(j)}_{(Z, \iter)} - \sum_{P_k \in \Selected_{(Z', \iter)}} d^{(jk)}_{(Z, \iter)} \neq 0$, then $f_{\Char}(\iter) \defined (P_j, P_k)$,
where $P_k$ is the smallest-indexed party from $\PartySet \setminus \{P_j \}$.[If there are multiple parties $P_j$ satisfying this condition, then we consider
the $P_j$ with the smallest index.]

– Else, if there is some
$P_j \in \Selected_{(Z',\iter)}$ such that $\displaystyle c^{(j)}_{(Z', \iter)} - \sum_{P_k \in \Selected_{(Z, \iter)}} e^{(jk)}_{(Z', \iter)} \neq 0$, then $f_{\Char}(\iter) = (P_k, P_j)$,
where $P_k$ is the smallest-indexed party from $\PartySet \setminus \{P_j \}$.[If there are multiple parties $P_j$ satisfying this condition, then we consider
the $P_j$ with the smallest index.]

– Else, $f_{\Char}(\iter) \defined (P_j, P_k)$, where $(P_j,P_k)$ is a conflicting-pair of parties, corresponding to the $\MultLCE$ instance.[If there are multiple
conflicting-pairs, then we consider the one having parties with the smallest indices.]

Before we proceed, we would like to stress that if $f_{\Char}$ is defined either with respect to the first or the second condition, then party $P_k$ in the pair
$(P_j, P_k)$ serves as
a “dummy" party. This is just for notational convenience to ensure uniformity so that $f_{\Char}$ is always a pair of parties irrespective of whether
it is defined with respect to the first, second or third condition.

From the definition, it is easy to see that if $f_\Char(\iter) = (P_j, P_k)$, then at least one party among $P_j, P_k$ is
maliciously-corrupt. We next claim that the characteristic function is well defined.

Let $\MultLCE(\PartySet, \AdvStruct, \SharingSpec, [a], [b], \iter)$ be an instance of $\MultLCE$
which is not successful and let $Z, Z'$ be the corresponding conflicting-sets for the instance. Then $f_\Char(\iter)$ is well defined.

Proof follows from Claim <ref>.

We next prove an important property by showing that if $f_\Char(\iter) = (P_j, P_k)$ for some instance
of $\MultLCE$ which is not successful, and if both $P_j$ and $P_k$
have been removed from the waiting-list of some honest party for that instance,
then the corrupt party(ies) among $P_j, P_k$ will eventually be discarded by all honest parties.

Let $\MultLCE(\PartySet, \AdvStruct, \SharingSpec, [a], [b], \iter)$ be an instance of $\MultLCE$  which  is not successful and let
$Z, Z'$ be the corresponding conflicting-sets for the instance. Moreover. let $f_\Char(\iter) = (P_j, P_k)$. If both
$P_j$ and $P_k$ are removed from the set $\Waitlist^{(h)}_{\iter}$ of any honest party $P_h$, then
the corrupt party(ies) among $P_j, P_k$ will eventually be included
in the set $\LocalDiscarded^{(i)}_{\iter}$ of every honest $P_i$.

Let $f_\Char(\iter) = (P_j, P_k)$, where without loss of generality,
$P_j \in \Selected_{(Z,\iter)}$ and $P_k \in \Selected_{(Z',\iter)}$.
From the definition of characteristic function (Def <ref>), one of the following holds for $P_j$ and $P_k$:

– $(P_j, P_k)$ constitutes a conflicting-pair: In this case, $d^{(jk)}_{(Z,\iter)} \neq e^{(kj)}_{(Z',\iter)}$.
Since the honest $P_h$ has removed both $P_j$ and $P_k$ from $\Waitlist^{(h)}_\iter$, from the protocol steps,
the outputs $(\Share, \sid_{j, k, \iter, Z},P_j, \allowbreak \{[d^{(jk)}_{(Z,\iter)}]_q\}_{P_h \in S_q})$ and
$(\Share, \sid_{k, j, \iter, Z'}, P_k,\{[e^{(kj)}_{(Z',\iter)}]_q\}_{P_h \in S_q})$ have been obtained by $P_h$ from
$\FVSS$ with $\sid_{j, k, \iter, Z}$ and $\sid_{k, j, \iter, Z'}$ respectively.
Consequently, each honest party will eventually receive its respective share corresponding to
$[d^{(jk)}_{(Z,\iter)}]$ and $[e^{(kj)}_{(Z',\iter)}]$ from the corresponding $\FVSS$ instances.
Hence, each honest  party will be able to locally compute its share of $d^{(jk)}_{(Z,\iter)} - e^{(kj)}_{(Z',\iter)}$ and
participate in the instance of $\PiPerRec$ to reconstruct the difference. Since $\ShareSpec$ satisfies the $\Q^{(3)}(\ShareSpec, \AdvStructure)$
condition, all honest parties will eventually reconstruct $d^{(jk)}_{(Z,\iter)} - e^{(kj)}_{(Z',\iter)}$ and find that the difference is not $0$.
Consequently, the honest parties will
participate in appropriate instances of $\PiPerRec$ to reconstruct the values
$d^{(jk)}_{(Z,\iter)}$, $e^{(kj)}_{(Z',\iter)}$, and instances of $\PiPerRecShare$ to reconstruct
the shares $[a]_p$ and $[b]_q$, such that
$(p,q) \in \Products^{(j)}_{(Z,\iter)} \cap \Products^{(k)}_{(Z',\iter)}$. Now,
either $d^{(jk)}_{(Z,\iter)}$ or $e^{(kj)}_{(Z',\iter)}$ will not be equal to $\displaystyle \sum_{(p, q) \in \Products^{(j)}_{(Z, \iter)} \cap \Products^{(k)}_{(Z', \iter)}} [a]_p [b]_q$,
as otherwise $d^{(jk)}_{(Z,\iter)} = e^{(kj)}_{(Z',\iter)}$ will hold, which is a contradiction.
Consequently, every honest party $P_i$ will eventually add the corrupt party(ies) among $P_j, P_k$ to $\LocalDiscarded^{(i)}_{\iter}$.

– The condition $\displaystyle c^{(j)}_{(Z, \iter)} - \sum_{P_k \in \Selected_{(Z', \iter)}} d^{(jk)}_{(Z, \iter)} \neq 0$ holds:
Since the honest $P_h$ has removed $P_j$  from $\Waitlist^{(h)}_\iter$, then from the protocol steps, corresponding to every
$P_k \in \Selected_{(Z', \iter)}$, party $P_h$ has received the output
$(\Share, \sid_{j, k, \iter, Z},P_j,  \{[d^{(jk)}_{(Z,\iter)}]_q\}_{P_h \in S_q})$ from  $\FVSS$ with $\sid_{j, k, \iter, Z}$.
Consequently, for every $P_k \in \Selected_{(Z', \iter)}$,
all honest parties eventually receive their respective shares corresponding to $[d^{(jk)}_{(Z,\iter)}]$ from the respective $\FVSS$ instances.
In the protocol, all honest parties participate in an instance of $\PiPerRec$ with their respective shares corresponding to
$\displaystyle [c^{(j)}_{(Z, \iter)}] - \sum_{P_k \in \Selected_{(Z', \iter)}} [d^{(jk)}_{(Z, \iter)}]$ to reconstruct the difference
$\displaystyle c^{(j)}_{(Z, \iter)} - \sum_{P_k \in \Selected_{(Z', \iter)}} d^{(jk)}_{(Z, \iter)}$. Now since the difference is not $0$,
each honest $P_i$ will eventually include the corrupt $P_j$ to $\LocalDiscarded^{(i)}_{\iter}$.

– The condition $\displaystyle c^{(k)}_{(Z', \iter)} - \sum_{P_j \in \Selected_{(Z, \iter)}} e^{(kj)}_{(Z', \iter)} \neq 0$ holds:
This case is symmetric to the previous case and using a similar argument as above, we can conclude that
each honest $P_i$ will eventually include the corrupt $P_k$ to $\LocalDiscarded^{(i)}_{\iter}$.

We next claim that the adversary does not learn anything additional about $a$ and $b$ in the protocol.

In $\MultLCE$, $\Adv$ does not not learn any additional information about $a$ and $b$.

From Claim <ref>, $\Adv$ does not learn any additional information about $a$ and $b$ from the instances of $\OptMult$ executed in
$\MultLCE$. Corresponding to every $Z \in \AdvStructure$, $\Adv$ learns the difference  $c_{(Z, \iter)} - c_{(Z', \iter)}$ which are all $0$,
unless the adversary cheats. In case of cheating, the reconstructed differences $c_{(Z, \iter)} - c_{(Z', \iter)}$
depend completely upon
the inputs of the adversary and hence learning these differences does not add anything additional about $a$ and $b$ to the adversary's view.
Next, corresponding to every honest $P_j \in \Selected_{(Z, \iter)} \cup \Selected_{(Z', \iter)}$, the shares corresponding to
$d^{(jk)}_{(Z,\iter)}$ or $e^{(kj)}_{(Z',\iter)}$ learnt by $\Adv$ will be distributed uniformly, since $\ShareSpec$ is $\AdvStructure$-private
and hence, these shares do not add anything additional about $a$ and $b$ to the adversary's view.
Moreover, for every honest $P_j \in \Selected_{(Z, \iter)} \cup \Selected_{(Z', \iter)}$,
$\Adv$ will know beforehand that the differences
$\displaystyle c^{(j)}_{(Z, \iter)} - \sum_{P_k \in \Selected_{(Z', \iter)}} d^{(jk)}_{(Z, \iter)}$ as well as
$\displaystyle c^{(j)}_{(Z', \iter)} - \sum_{P_k \in \Selected_{(Z, \iter)}} e^{(jk)}_{(Z', \iter)}$ will be $0$ and hence, learning these differences does not add anything
additional about $a$ and $b$ to adversary's view.
On the other hand, for every corrupt $P_j \in \Selected_{(Z, \iter)} \cup \Selected_{(Z', \iter)}$, the above differences
completely depend upon the adversary's inputs and hence, reveal no additional information. Finally, if for any ordered pair of parties $(P_j, P_k)$,
the condition $d^{(jk)}_{(Z, \iter)} \neq e^{(kj)}_{(Z', \iter)}$ holds, then at least one among $P_j$ and $P_k$ is corrupt.
Consequently, the shares $[a]_p$ and $[b]_q$ where $(p, q) \in \Products^{(j)}_{(Z, \iter)} \cap \Products^{(k)}_{(Z', \iter)}$
reconstructed in this case are already known to the adversary, and do not add anything new to the view of the adversary regarding $a$
and $b$.

Protocol $\MultLCE$  needs $\Order(|\AdvStructure| \cdot n^2)$ calls to $\FVSS$ and $\FABA$ and incurs an additional communication of
$\Order(|\AdvStructure|^2 \cdot n^2 \log{|\F|} + |\AdvStructure| \cdot n^4 \log{|\F|})$ bits.

In the protocol, corresponding to each $Z \in \AdvStructure$, an instance of $\OptMult$ is executed. From Lemma <ref>, this will require
$\Order(|\AdvStructure| \cdot n^2)$ calls to $\FVSS$ and $\FABA$. There are $\Order(|\AdvStructure|)$ instances of $\PiPerRec$ to reconstruct
$\Order(|\AdvStructure|)$ difference values for checking whether the instance is successful or not, incurring a communication of
$\Order(|\AdvStructure|^2 \cdot n^2 \log{|\F|})$ bits. If the instance is not successful, then there are $\Order(n^2)$ calls to $\FVSS$ to share
various summand-sum partitions. To check whether the correct partitions are shared, $\Order(n^2)$ values need to be publicly reconstructed through
these many instances of $\PiPerRec$, which incurs a communication of $\Order(|\AdvStructure| \cdot n^4 \log{|\F|})$ bits.

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

Lemma <ref>.