The communication complexity and the number of calls to $\FVSS$ and $\FABA$ simply follows from the communication complexity of $\RandMultLCE$
and the fact that there might be $\Order(n)$ instances of $\RandMultLCE$ in the protocol.
This is because from Lemma <ref>, if any instance of $\RandMultLCE$ fails,
then at least one new corrupt party is globally discarded and included in $\Discarded$. Once all the corrupt parties are included in $\Discarded$, then
from Claim <ref>, the next instance of $\RandMultLCE$ is bound to give the correct output.

We next prove the security. For the ease of explanation, we consider the case where
only one multiplication-triple is generated in $\PiStatTriples$; i.e. $M = 1$. The proof can easily be  modified for any general $M$.

Let $\Adv$ be an arbitrary adversary, attacking the protocol $\PiStatTriples$ by corrupting a set of parties
$Z^{\star} \in \AdvStructure$, and let $\Env$ be an arbitrary environment. We show the existence of a simulator $\SimStatTriples$ (Fig <ref>),
such that for any
$Z^{\star} \in \AdvStructure$,
the outputs of the honest parties and the view of the adversary in the
protocol $\PiStatTriples$ is indistinguishable from the outputs of the honest parties and the view of the adversary in an execution in the ideal world involving
$\SimStatTriples$ and $\FTriples$, except with probability at most $\frac{n}{|\F|}$.

The high level idea of the simulator is very similar to that of the simulator for the protocol $\PiPerTriples$ (see the proof of Theorem <ref>).
Throughout the simulation,
the simulator itself performs the role of the ideal functionalities $\FVSS$ and
$\FABA$ whenever required and performs the role of the honest parties, exactly as per the steps of the protocol.
In each iteration, the simulator
simulates the actions of honest parties during the underlying instance of $\RandMultLCE$ by playing the role of the honest parties with random inputs.
Once the simulator finds any iteration of $\RandMultLCE$ to be successful, the simulator learns the secret-sharing of the output triple of that iteration
and sends the shares of this triple, corresponding to the corrupt parties to $\FTriples$, on the behalf of $\Adv$.

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

$\SimStatTriples$ 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 $\FVSS$ and $\FABA$.
In order to simulate $\Env$, the simulator $\SimStatTriples$ forwards every message it receives from
$\Env$ to $\Adv$ and vice-versa.  The simulator then simulates the various stages of the protocol as follows.

– Initialization: On behalf of the honest parties, the simulator initializes $\Discarded$ to $\emptyset$ and $\iter$ to $1$.

– Detectable Triple Generation: The simulator plays the role of the honest parties as per the protocol and interacts with $\Adv$ for an instance
$\RandMultLCE(\PartySet,\AdvStruct,\SharingSpec, \Discarded, \iter)$.
During this instance, the simulator simulates the interface for $\FABA$ and $\FVSS$ for $\Adv$ during the underlying instances of
$\BasicMult$, by itself performing the role of $\FABA$ and $\FVSS$. Next, based on whether the instance is successful or not,
simulator does the following.

* If during the instance $\RandMultLCE(\PartySet,\AdvStruct,\SharingSpec, \Discarded, \iter)$,
simulator has set $\flag^{(i)}_\iter=0$, corresponding to any $P_i \not \in Z^{\star}$:
In this case, let $([\sima_\iter], [\simb_\iter], [\simc_\iter])$ be the output of the honest parties from the instance of $\RandMultLCE$.
The simulator then sets $\{ [\sima_\iter]_q, [\simb_\iter]_q, [\simc_\iter]_q \}_{S_q \cap Z^{\star} \neq \emptyset}$
to be the shares corresponding to the parties in $Z^{\star}$ and goes to the step labelled Interaction with $\FTriples$.

* If during the instance $\RandMultLCE(\PartySet,\AdvStruct,\SharingSpec, \Discarded, \iter)$,
simulator has set $\flag^{(i)}_\iter=1$, corresponding to any $P_i \not \in Z^{\star}$:
In this case, the simulator sets $\iter = \iter+1$ and goes to step labelled Detectable Triple Generation.

– Interaction with $\FTriples$:
Let $\{[\widetilde{a}]_q,[\widetilde{b}]_q,[\widetilde{c}]_q\}_{S_q \cap Z^{\star} \neq \emptyset}$ be the shares set by the simulator
corresponding to the parties in $Z^{\star}$. The simulator sends
$(\shares,\sid, \{[\widetilde{a}]_q, [\widetilde{b}]_q, [\widetilde{c}]_q\}_{S_q \cap Z^{\star} \neq \emptyset})$ to $\FTriples$,  on the behalf of $\Adv$.

We now prove a series of claims which will help us to finally prove the theorem. We first show that the view generated by $\SimStatTriples$ for $\Adv$ is identically distributed to $\Adv$'s view during the real execution of $\PiStatTriples$.

The view of $\Adv$ in the simulated execution with $\SimPerTriples$ is identically distributed as the view of $\Adv$ in the real execution of

In both the real as well as simulated execution, the parties run an instance of $\RandMultLCE$ for each iteration $\iter$, where in the simulated execution, the role
of the honest parties is played by the simulator, including the role of $\FVSS$ and $\FABA$.
Now, in either execution, if $\flag^{(i)}_\iter$ is set to $0$ during some iteration $\iter$  corresponding to any honest $P_i$,
then from Lemma <ref>,
the view of $\Adv$ will be independent of the underlying triple and hence, will be
identically distributed in both the executions. Else, in both executions,
at least one new corrupt party gets discarded and the parties
proceed to the next iteration. Hence, the view of $\Adv$ in both executions is identically distributed.

We now show that conditioned on the view of $\Adv$, the output of honest parties is identically distributed in the real execution of $\PiStatTriples$ involving $\Adv$, as well as in the ideal execution involving $\SimStatTriples$ and $\FTriples$.

Conditioned on the view of $\Adv$, the output of the honest parties is identically distributed in the real execution of $\PiStatTriples$ involving $\Adv$ and in the ideal execution involving $\SimStatTriples$ and $\FTriples$, except with probability at most $\frac{n}{|\F|}$.

Consider an arbitrary view $\View$ of $\Adv$, generated as per some execution of $\PiStatTriples$. From Lemma <ref>,
in the real execution of $\PiStatTriples$, during each iteration,
all honest parties either obtain shares of a random multiplication triple,
or discard a new maliciously-corrupt party.
Since $|Z^{\star}| < n$, it will take less than $n$ iterations to discard all the maliciously-corrupt parties.
Furthermore, once all parties in $Z^{\star}$ are discarded, from Claim <ref>, the
next instance of $\RandMultLCE$ will output a secret-shared multiplication-triple for the honest parties.
Consequently, within $n$ iterations, there will be some iteration $\iter$, such that all honest parties $P_i$ eventually set
$\flag_\iter^{(i)}$ to $0$ and output a secret-shared triple $([a_{\iter}], [b_{\iter}], [c_{\iter}])$. Moreover, from
the union bound, it follows that except with probability at most $\frac{n}{|\F|}$, the triple $(a_\iter, b_\iter, c_\iter)$ will be a multiplication-triple.
Furthermore, from Lemma <ref>, the triple will be randomly distributed over $\F$.

To complete the proof, we show that conditioned on the shares $\{([a_{\iter}]_q, [b_{\iter}]_q, [c_{\iter}]_q) \}_{S_q \cap Z^{\star} \neq \emptyset}$ (which are determined by
$\View$), the honest
parties output a secret-sharing
of some random multiplication-triple in the simulated execution, which is consistent with
the shares  $\{([a_{\iter}]_q, [b_{\iter}]_q, [c_{\iter}]_q) \}_{S_q \cap Z^{\star} \neq \emptyset}$.
However, this simply follows from the fact that in the simulated execution,
$\SimStatTriples$ sends the shares $\{([a_{\iter}]_q, [b_{\iter}]_q, [c_{\iter}]_q) \}_{S_q \cap Z^{\star} \neq \emptyset}$
to $\FTriples$ on the behalf of the parties in $Z^{\star}$, and as an output, $\FTriples$ generates a random secret-sharing of some random multiplication-triple consistent with these shares.

Since all honest parties participate in hop number $\hop$, it follows that
$\Products_\iter \neq \emptyset$ at the beginning of hop number $\hop$. This implies that there exists at least one ordered pair $(p, q) \in \Products_\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)}_\iter$ shared
by $P_k$ during hop $\hop'$, implying that $(p, q) \not \in \Products_\iter$. Now during the hop number $\hop$, party $P_k$
will randomly secret-share the sum $c^{(k)}_\iter$ by making a
call to $\FVSS$  and every honest $\mathsf{I}$ will eventually receive an output
$(\Share, \sid_{\hop, k}, P_k, \{ [c^{(k)}_\iter]_q \}_{\mathsf{I} \in S_q})$  from $\FVSS$
with $\sid_{\hop, k, \iter, Z}$.
Moreover, $P_k$ will not be present in the set $\Discarded$.

We next claim that during the hop number $\hop$, there will be 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
$\mathsf{I}$ be an honest party, who sends $(\vote, \sid_{\hop, k}, 0)$ to $\FABA$ with
$\sid_{\hop, k}$. Then from the steps of $\BasicMult$, it follows that there exists some $P_j \in \PartySet$, such that
$\mathsf{I}$ has received
$(\decide, \sid_{\hop, j}, 1)$ as the output from $\FABA$ with  $\sid_{\hop, j}$. Hence, every honest party
will eventually receive the output $(\decide, \sid_{\hop, j}, 1)$ as the output from $\FABA$ with  $\sid_{\hop, j}$.

– 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}, 1)$ to $\FABA$ with
$\sid_{\hop, k}$ and eventually receives the output $(\decide, \sid_{\hop, k}, 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 thus 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)}_\iter]$.
For this, we note that since $P_j$ has been selected as the summand-sharing party, at least one honest party, say
$\mathsf{I}$, must have sent $(\vote, \sid_{\hop, j}, 1)$ to $\FABA$ with
$\sid_{\hop, j}$. If not, then $\FABA$ with $\sid_{\hop, j}$ will never produce the output
$(\decide, \sid_{\hop, j}, 1)$ and hence $P_j$ will not be the summand-sharing party for the hop number $\hop$.
Now since $\mathsf{I}$ sent $(\vote, \sid_{\hop, j}, 1)$ to $\FABA$, it follows that
$\mathsf{I}$ has received an output $(\Share, \sid_{\hop, j}, P_j, \{ [c^{(j)}_\iter]_q \}_{\mathsf{I} \in S_q})$  from $\FVSS$
with $\sid_{\hop, j}$. This implies that $P_j$ must have sent the message
$(\Dealer, \sid_{\hop, j}, (c^{(j)}_{\iter,1}, \ldots, c^{(j)}_{\iter,h}))$ to
$\FVSS$ with $\sid_{\hop, j}$.
Consequently, every honest party will eventually receive their respective outputs from
$\FVSS$ with $\sid_{\hop, j}$ and hence the honest parties will eventually hold

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}, 1)$ to $\FABA$ with
$\sid_{\hop, j}$. Consequently, $\FABA$ with $\sid_{\hop, j}$ will never send the output
$(\decide, \sid_{\hop, j}, 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.

shares corresponding to a random multiplication triple.

Consider an instance of $\RandMultLCE$ invoked during iteration $\iter$. If no party in $\PartySet \setminus \Discarded$ behaves maliciously, then each honest party $\mathsf{I}$ sets $\flag^{(i)}_\iter=0$ and outputs shares $\{([a_\iter]_q,[b_\iter]_q,[c_\iter]_q)\}_{\mathsf{I} \in S_q}$, such that $c_\iter = a_\iter b_\iter$ holds.

From Lemma <ref>, if no party behaves maliciously, then for all parties $P_j \in \Selected_\iter$, it holds that $c^{(j)}_\iter = \sum_{(p,q) \in \Products^{(j)}_{(\iter,c)}}$, and that $c'^{(j)}_\iter = \sum_{(p,q) \in \Products^{(j)}_{(\iter,c')}}a_pb'_q$. For every $P_j \in \Selected_\iter$, it then holds that $r_\iter c^{(j)}_\iter + c'^{(j)}_\iter \neq r_\iter \sum_{(p,q) \in \Products^{(j)}_{(\iter,c)}} a_pb_q + \sum_{(p,q) \in \Products^{(j)}_{(\iter,c')}}a_pb'_q$. Then, we can infer the following.

$$\displaystyle \sum_{P_j \in \Selected_\iter} r^{(j)_\iter}_\iter c^{(j)}_\iter + c'^{(j)}_\iter = \sum_{P_j \in \Selected_\iter} r^{(j)} \sum_{(p,q) \in \Products^{(j)}_{(\iter,c)}} a_pb_q + \sum_{(p,q) \in \Products^{(j)}_{(\iter,c')}}a_pb'_q$$

By summing over the parties $P_j \in \Selected$, the following holds, based on how $r^{(\iter)}, a^{(\iter)}, b^{(\iter)}$ and $b'^{(\iter)}$ are defined.

$$r_\iter c_\iter + c'_\iter = r_\iter a_\iter b_\iter + a_\iter b'_\iter$$

But since $e_\iter = r_\iter b_\iter + b'_\iter$,

$$r_\iter c_\iter + c'_\iter = e_\iter a_\iter \implies e_\iter a_\iter - c_\iter - c'_\iter = 0 \implies d_\iter = 0$$

Hence, the reconstructed value of $d_\iter$ is $0$, and each party $\mathsf{I}$ outputs $\{([a_\iter]_q,[b_\iter]_q,[c_\iter]_q)\}_{\mathsf{I} \in S_q}$ along with $\Success$. From Lemma <ref>, it holds that $c_\iter = a_\iter b_\iter$.

We next show that if the protocol $\RandMultLCE$ succeeds, then with high probability, each honest party obtains shares corresponding to a random multiplication triple as output.

We next claim that if the protocol $\RandMultLCE$ fails, then each honest party discards at least one corrupt party which was not discarded in an earlier iteration.

Consider an instance of $\RandMultLCE$ invoked during iteration $\iter$. Consider an honest party $\mathsf{I}$. If $\mathsf{I}$ sets $\flag^{(i)}_\iter=1$, then at least one corrupt party $P_j$ is added by every honest party $\mathsf{I}$ to $\Discarded$. Furhtermore, $P_j$ will be different from any party added to $\Discarded$ during any previous iteration $\iter' < \iter$.

From Claim <ref>, the parties will be able to reconstruct a value $d_\iter$. From Lemma <ref>, the parties will be able to reconstruct  $a_\iter,b_\iter,b'_\iter,c^{(1)}_\iter,\ldots,c^{(n)}_\iter,c'^{(1)}_\iter,\ldots,c'^{(n)}_\iter$. We claim that for at least one player $P_j \in \Selected_\iter$, it must hold that $r_\iter c^{(j)}_\iter + c'^{(j)}_\iter \neq r\sum_{(p,q) \in \Products^{(j)}_{(\iter,c)}} a_pb_q + \sum_{(p,q) \in \Products^{(j)}_{(\iter,c')}}a_pb'_q$. Otherwise, from Claim <ref>, the reconstructed value of $d_\iter$ is $0$. Now, since $P_j \in \Selected_\iter$, from the protocol steps of $\BasicMult$, $P_j \notin \Discarded$. This is because if $P_j$ was added to $\Discarded$ in a previous iteration, then no honest party will send $(\vote,\sid_{\hop,j},1)$ to $\FABA$ in $\BasicMult$ during iteration $\iter$, and hence, no honest party will obtain $(\decide,\sid_{\hop,j},1)$ from $\FABA$. Hence, at least one corrupt party $P_j$ different from any party added to $\Discarded$ in previous iterations will be added by all honest parties $\mathsf{I}$ to $\Discarded$ during iteration $\iter$.

the values $((\alpha_1,v_1,m_1),\ldots,(\alpha_{t'},v_{t'},m_{t'}))$. However, since $F(\cdot)$ is of degree $t+L$, for every candidate $s = (s^{(1)},\ldots,s^{(L)}) \in \F^{(L)}$, $|\F|^{t-t'}$ possible candidate polynomials for $F(\cdot)$ which are consistent with $v_1 ,\ldots,v_{t'}$ can be defined. $\Adv$ also learns the value of $d$, $B(x) = dF(x) + M(x)$ and the set $\R$ of supporting verifiers. However, since $M(\cdot)$ is chosen uniformly at random, for every possible polynomial $M(x)$ which is consistent with $m_1,\ldots,m_{t'}$, there is a unique $F(x) = d^{-1}\cdot(B(x) - M(x))$ of degree $L+t$, which is consistent with $v_1,\ldots,v_{t'}$. Furthermore, from the proof of Claim <ref>, $\mathsf{S}$ sends an $\OK$ message to $\FAcast$, since $B(\alpha_j) = dv_j + m_j$ for all verifiers $P_j \in \PartySet$. During $\Reveal$, $\Adv$ does not learn anything new, since the verification points and signing polynomials are sent privately to $\mathsf{R}$.

Let $\mathsf{S}$ and $\mathsf{R}$ be honest, and suppose corrupt $\mathsf{I}$ reveals
$\ICSig^{(\ell)}(\mathsf{S} \rightarrow \mathsf{I} \rightarrow \mathsf{R}, \vec{S'^{(\ell)}})$ during $\ell = 1,\ldots,M$ instances of $(\Auth^{(\ell)},\Reveal^{(\ell)})$.
If $\mathsf{R}$ outputs $\vec{S'^{(\ell)}}$ during $\Reveal^{(\ell)}$, then irrespective of the value of $M$, except with probability at most $\frac{L+t}{|\F| - L}$, the condition
$\vec{S'^{(\ell)}} = \vec{S^{(\ell)}}$ holds.

From the pro

as part of the protocol $\Reveal^{(\ell)}$

We fix a value of $\ell \in \{1,\ldots,M\}$ for which $\mathsf{R}$ has obtained output in $\Reveal^{(\ell)}$. Since $\mathsf{R}$ has obtained an output as part of the protocol $\Reveal^{(\ell)}$, $\mathsf{R}$ has received some polynomial $F'(x)$ of degree $t+L$ from $\mathsf{I}$, and has set $\authCompleted^{(\sid_\ell,R)}_{\mathsf{S},\mathsf{I},\mathsf{R}}$ to $1$ during $\Auth^{(\ell)}$. Furthermore, $\mathsf{I} \notin \LocalDiscarded^{(\ell,R)}$. There are now two cases.

– $\mathsf{R}$ received $\NOK$ along with $\vec{S'^{(\ell)}}$ as output from $\FAcast$ : In this case, since $\mathsf{S}$ is honest, $\vec{S'^{(\ell)}} = \vec{S^{(\ell)}}$.

– $\mathsf{R}$ received $\OK$ along with $(d,B(x),\R)$ as output from $\FAcast$ : This means that $B(\alpha_i) = dv_i + m_i$ for all honest verifiers $\mathsf{I} \in \R$. Suppose that during $\Reveal^{(\ell)}$, $\mathsf{I}$ sent $F'(x) \neq F(x)$ to $\mathsf{R}$. We show that in this case, except with probability $\frac{L+t}{|\F| - L}$, $\mathsf{R}$ will add $\mathsf{I}$ to $\LocalDiscarded^{(\ell,R)}$. To prove this, we show that except with probability $\frac{L+t}{|\F| - L}$, the verification point of each honest verifier is rejected. Suppose that $\mathsf{R}$ receives a point $(\alpha_i,v_i,m_i)$ from an honest verifier $\mathsf{I} \in \Hon \cap \R$. This point can be accepted in the following two cases.

* $v_i = F'(\alpha_i)$ : This is possible with probability at most $\frac{L+t}{|\F| - L}$. This is because $F'(x)$ and $F(x)$, being distinct polynomials of degree $L+t$, can have  at most $L+t$ points in common.

* $dv_i + m_i \neq B(\alpha_i)$ : This is impossible, since $\mathsf{S}$ has verified that $B(\alpha_i) = dv_i + m_i$ for all verifiers $\mathsf{I} \in \R$.

Since $\Hon \cap \R = \R \setminus Z^{\star}$, $\mathsf{R}$ will eventually receive points from a set of parties $R' \subset \R$, such that $\R' = \R \setminus Z$ for some $Z \in \AdvStructure$, such that each point received is rejected. Also, the set of corrupt parties in $\R$ cannot form a candidate set for $\R'$. This is because since $\AdvStructure$ satisfies the $\Q^{(3)}(\PartySet,\AdvStructure)$ condition,  it satisfies the $\Q^{(2)}(\R,\AdvStructure)$ condition, and thereby, the $\Q^{(1)}(\R',\AdvStructure)$ condition. Hence, any candidate set of parties for $\R'$ must contain at least one honest party.

We further note that once $\mathsf{I}$ is added to $\LocalDiscarded^{(\ell,R)}$, $\mathsf{R}$ will not obtain any output from $\mathsf{I}$ as part of any later instance of $\Reveal$. Hence, irrespective of the value of $M$, except with probability $\frac{L+t}{|\F| - L}$, $\vec{S'^{(\ell)}} = \vec{S^{(\ell)}}$ for all instances of $\Reveal^{(\ell)}$ where $\mathsf{R}$ obtains an output.

We next show that if an honest $\mathsf{I}$ completes the authentication phase and tries to reveal a vector of secrets to an honest $\mathsf{R}$, then with high probability, $\mathsf{R}$ will accept this vector of secrets.

Let $\mathsf{S}$ be corrupt and $\mathsf{I}, \mathsf{R}$ be honest. Suppose that during $\ell = 1,\ldots,M$ instances of $(\Auth^{(\ell)},\Reveal^{(\ell)})$, $\mathsf{S}$ gives $\ICSig(\sid_\ell,\mathsf{S} \rightarrow \mathsf{I} \rightarrow \mathsf{R}, \vec{S'^{(\ell)}})$ to $\mathsf{I}$. Suppose that $\mathsf{I}$ sets $\authCompleted^{(\sid_\ell,I)}_{\mathsf{S},\mathsf{I},\mathsf{R}}$ to $1$ during $\Auth^{(\ell)}$, for some $\ell \in \{1,\ldots,M\}$, and  $\mathsf{I}$ reveals
$\ICSig^{(\ell)}(\mathsf{S} \rightarrow \mathsf{I} \rightarrow \mathsf{R}, \vec{S'^{(\ell)}})$ to $\mathsf{R}$. Then, irrespective of the value of $M$, except with probability at most $\frac{n}{|\F|-1}$, $\mathsf{R}$ outputs $\vec{S'^{(\ell)}}$ during $\Reveal^{(\ell)}$.

Let $\Hon$ be the set of honest parties in $\PartySet$. We fix a value of $\ell \in \{1,\ldots,M\}$ for which $\mathsf{I}$ has set $\authCompleted^{(\sid_\ell,I)}_{\mathsf{S},\mathsf{I},\mathsf{R}}$ to $1$ during $\Auth^{(\ell)}$. Suppose that $\mathsf{I}$ reveals
$\ICSig^{(\ell)}(\mathsf{S} \rightarrow \mathsf{I} \rightarrow \mathsf{R}, \vec{S'^{(\ell)}})$ to $\mathsf{R}$. Then, we show that except with probability at most $\frac{n}{|\F|-1}$, $\mathsf{R}$ outputs $\vec{S'^{(\ell)}}$ during $\Reveal^{(\ell)}$. Since $\mathsf{I}$ has set $\authCompleted^{(\sid_\ell,I)}_{\mathsf{S},\mathsf{I},\mathsf{R}}$ to $1$, $\mathsf{I}$ has received $(d,B(x),\R)$ from $\FAcast$, which means that $\mathsf{R}$ will also eventually receive this from $\FAcast$. There are now two cases.

– $\mathsf{I}$ received $\NOK$ along with $\vec{S''^{(\ell)}}$ as output from $\FAcast$ : In this case, $\mathsf{R}$ will also eventually receive $\NOK$ along with $\vec{S''^{(\ell)}}$ as output from $\FAcast$. Hence, $\mathsf{R}$ will set $\authCompleted^{(\sid_\ell,R)}_{\mathsf{S},\mathsf{I},\mathsf{R}}$ to $1$ and output $\vec{S'^{(\ell)}}$ during $\Reveal^{(\ell)}$.

– $\mathsf{I}$ received $\OK$ along with $(d,B(x),\R)$ as output from $\FAcast$ : Eventually, $\mathsf{R}$ will also receive the message $\OK$ from $\FAcast$, and set $\authCompleted^{(\sid_\ell,R)}_{\mathsf{S},\mathsf{I},\mathsf{R}}$ to $1$. Suppose that $\mathsf{R}$ receives signing polynomial $F'(x)$ from $\mathsf{S}$ during $\Auth^{(\ell)}$. We show that except with probability at most $\frac{n}{|\F|-1}$, the verification point $(\alpha_i,v_i,m_i)$ of each party $\mathsf{I}$ in $\Hon \cap \R$ is accepted by $\mathsf{R}$. To show this, we consider two cases.

* $v_i = F'(\alpha_i)$ : In this case, according to the protocol steps, $(\alpha_i,v_i,m_i)$ is accepted.

* $v_i \neq F'(\alpha_i)$ : In this case, we claim that $dv_i + m_i = B(\alpha_i)$ with a probability of at most $\frac{1}{|\F|-1}$. This is because this will be possible only when $\mathsf{I}$ chooses $d$ such that $d = (M'(\alpha_i) - m_i)\cdot(v_i - F'(\alpha_i))^{-1}$, where $M'(\alpha_i)$ is the masking polynomial $\mathsf{I}$ received from $\mathsf{S}$ during $\Auth^{(\ell)}$. Since $d$ is chosen uniformly at random from $F \setminus \{0\}$, this happens with a probability of at most $\frac{1}{|\F|-1}$. Hence, except with a probability of at most $\frac{1}{|\F|-1}$, $(\alpha_i,v_i,m_i)$ will be accepted. Furthermore, in this case, from the protocol steps, $\mathsf{I}$ adds $\mathsf{S}$ to $\LocalDiscarded^{(i)}$ during $\Auth^{(\ell)}$.

It now follows from the union bound that the verification point of every honest party in $\R$ is accepted, except with a probability of at most $\frac{n}{|\F|-1}$. Since $\Hon \cap \R = \R \setminus Z^{\star}$, $\mathsf{R}$ will eventually receive points from a set of parties $\R' = \R \setminus Z$, which are accepted except with a probability of $\frac{n}{|\F|-1}$, for some $Z \in \AdvStructure$. Hence, $\mathsf{R}$ will output $\vec{S'^{(\ell)}}$.

We further note that once $\mathsf{S}$ is added to $\LocalDiscarded^{(i)}$ for some verifier $\mathsf{I} \in \PartySet$ in an instance $\Auth^{(\ell)}$, then $\mathsf{I}$ will  not be a part of the set of supporting verifiers for any later instance $\Auth^{(\ell')}$. Hence, $\mathsf{S}$ can give each verifier an “inconsistent" point only once, except with a probability of at most $\frac{1}{|\F|-1}$. By the union bound, it will follows that except with a probability of at most $\frac{n}{|\F|-1}$, $\mathsf{S}$ will be added to $\LocalDiscarded^{(i)}$ for every honest verifier $\mathsf{I}$ which has received an inconsistent verification point during any of the $M$ instances of $\Auth$. We now claim that irrespective of the value of $M$, except with a probability of at most $\frac{n}{|\F|-1}$, $\mathsf{S}$ can “cheat" a maximum of $n$ times, once with respect to each verifier. To prove this, for any instance of $\Auth$, we consider the set $\R$ of supporting verifiers. Since $\AdvStructure$ satisfies the $\Q^{(3)}(\PartySet,\AdvStructure)$ condition, and since $\R = \PartySet \setminus Z$ for some $Z \in \AdvStructure$, $\AdvStructure$ must satisfy the $\Q^{(2)}(\R,\AdvStructure)$ condition. This implies that $\R$ has to include at least one honest party. However, once a verifier $\mathsf{I}$ adds $\mathsf{S}$ to $\LocalDiscarded^{(i)}$, according to the protocol steps, it does not send the message $(\Received,i)$ to $\mathsf{I}$, and cannot be included into the set $\R$. Thus, $\Auth$ will not complete for an honest $\mathsf{I}$ after every honest verifier has discarded $\mathsf{S}$. Hence, irrespective of the value of $M$, $\mathsf{R}$ outputs  $\vec{S'^{(\ell)}}$ revealed by honest $\mathsf{I}$ during $\Reveal^{(\ell)}$, except with a probability of at most $\frac{n}{|\F|-1}$.

§ MPC PROTOCOL IN THE PRE-PROCESSING MODEL

The perfectly-secure AMPC protocol $\PiMPC$ in the $(\FTriples, \FVSS, \FABA)$-hybrid model is presented in Fig <ref>. The high level idea behind the protocol
is already discussed in Section <ref>.
The protocol has a pre-processing phase where secret-shared random multiplication triples are generated, an
input phase where each party verifiably generates a secret-sharing of its input for the function $f$ and a common subset of input-providers
is selected, and a circuit-evaluation phase where the circuit is securely evaluated and the function output is publicly reconstructed.

In the protocol, all honest parties may not be reconstructing the function-output at the same “time" and
different parties may be at different phases of the protocol, as the protocol is executed asynchronously. Consequently, a party upon reconstructing the function-output,
cannot afford to terminate immediately, as its presence and participation might be needed for the completion of various phases of the protocol by other honest parties.
A standard trick to get around this problem in the AMPC protocols [20, 21, 14]
is to have an additional termination phase, whose code is executed concurrently throughout the protocol to check if a party can “safely" terminate the protocol with
the function output.

$\PiMPC$The perfectly-secure AMPC protocol in the $(\FTriples, \FVSS, \FABA)$-hybrid model. The public inputs of
the protocol are $\PartySet, \ckt$ and $\AdvStructure$. The above steps are executed by every
$P_i \in \PartySet$fig:PerAMPC

Set the sharing specification as $\ShareSpec = (S_1, \ldots, S_h)
\defined \{ \PartySet \setminus Z | Z \in \AdvStructure\}$, where $\AdvStructure$ is the adversary structure.[Thus $\ShareSpec$ is

Pre-Processing Phase

1. Send $(\triples, \sid, P_i)$ to the functionality $\FTriples$.

2. Request output from $\FTriples$ until an output
$(\tripleshares, \sid, \{[a^{(\ell)}]_q, [b^{(\ell)}]_q, [c^{(\ell)}]_q) \}_{\ell \in \{1, \ldots, M\}, P_i \in S_q})$ is received from $\FTriples$.

Input Phase

Once the output from $\FTriples$ is received, then proceed as follows.

* Secret-sharing of the Inputs and Collecting Shares of Other Inputs:

* Upon having the input $x^{(i)}$ for the function $f$, randomly select the shares $x^{(i)}_1, \ldots, x^{(i)}_h \in \F$, subject to the condition that
$x^{(i)} = x^{(i)}_1 + \ldots + x^{(i)}_h$.
Send $(\Dealer, \sid_i, P_i, (x^{(i)}_1, \ldots, x^{(i)}_h))$ to $\FVSS$, where
$\sid_i \defined \sid || i$.[The notation $\sid_i$ is used here to distinguish among the $n$ different calls to

* For $j = 1, \ldots, n$,
request for output from $\FVSS$ with $\sid_j$ corresponding to the dealer $P_j$,  until
an output is received.

* Selecting Common Input-Providers:

1.  If $(\Share, \sid_j, P_j, \{[x^{(j)}]_q \}_{P_i \in S_q})$ is received from $\FVSS$ with $\sid_j$, then  send
$(\vote, \sid_j, 1)$ to $\FABA$ with $\sid_j$,
where $\sid_j \defined \sid || j$.[The notation $\sid_j$ is used here to distinguish among the $n$ different calls to

2. For $j = 1, \ldots, n$, keep requesting for output from $\FABA$ with $\sid_j$ until an output is received.

3. If there exists a set of parties $\GlobalProv_i$, such that $\PartySet \setminus \GlobalProv_i \in \AdvStructure$
and $(\decide, \sid_j, 1)$ is received from $\FABA$ with $\sid_j$ corresponding to each $P_j \in \GlobalProv_i$,
then send
$(\vote, \sid_j, 0)$ to every $\FABA$ with $\sid_j$ for which no input has been provided yet.

4. Once $(\decide, \sid_j, v_j)$ is received from $\FABA$ with $\sid_j$ for every $j \in \{1, \ldots, n \}$, set
$\CoreSet = \{P_j: v_j = 1\}$.

5. Wait until $(\Share, \sid_j, P_j, \{[x^{(j)}]_q \}_{P_i \in S_q})$ is received from $\FVSS$ for every $P_j \in \CoreSet$.
For every $P_j \not \in \CoreSet$, participate in an instance of the protocol $\PiPerDefaultShare$ with public input $0$ to generate a default secret-sharing of $0$.

Circuit-Evaluation Phase

Evaluate each gate $g$ in the circuit
according to the topological ordering as follows, depending upon the type of $g$.

* Addition Gate: If $g$ is an addition gate with inputs $x, y$ and output $z$, then corresponding to every $S_q$ such that
$P_i \in S_q$, set $[z]_q = [x]_q + [y]_q$ as the share
corresponding to $z$. Here $\{[x]_q\}_{P_i \in S_q}$ and $\{[y]_q\}_{P_i \in S_q}$ are $P_i$'s shares
corresponding to gate-inputs $x$ and $y$ respectively.

* Multiplication Gate: If $g$ is the $\ell^{th}$ multiplication gate with inputs $x, y$ and output $z$, where $\ell \in \{1, \ldots, M \}$, then do the following:

1. Corresponding to every $S_q$ such that $P_i \in S_q$, set
$[d^{(\ell)}]_q \defined [x]_q - [a^{(\ell)}]_q$ and $[e^{(\ell)}]_q \defined [y]_q - [b^{(\ell)}]_q$, where $\{[x]_q\}_{P_i \in S_q}$ and $\{[y]_q\}_{P_i \in S_q}$ are
$P_i$'s shares corresponding to gate-inputs $x$ and $y$ respectively and $\{([a^{(\ell)}]_q, [b^{(\ell)}]_q, [c^{(\ell)}]_q)\}_{P_i \in S_q}$
are $P_i$'s shares corresponding to the $\ell^{th}$ multiplication-triple.

2. Participate in instances of $\PiPerRec$ with shares $\{[d^{(\ell)}]_q \}_{P_i \in S_q}$ and $\{[e^{(\ell)}]_q \}_{P_i \in S_q}$ to publicly reconstruct
$d^{(\ell)}$ and $e^{(\ell)}$, where $d^{(\ell)} \defined x - a^{(\ell)}$ and $e^{(\ell)} \defined y - b^{(\ell)}$.

4. Upon reconstructing $d^{(\ell)}$ and $e^{(\ell)}$, corresponding to every $S_q$ such that $P_i \in S_q$, set
$[z]_q \defined d^{(\ell)} \cdot e^{(\ell)} + d^{(\ell)} \cdot [b^{(\ell)}]_q + e^{(\ell)} \cdot [a^{(\ell)}]_q + [c^{(\ell)}]_q$.
Set $\{[z]_q \}_{P_i \in S_q}$ as the shares corresponding to $z$.

* Output Gate: If $g$ is the output gate with output $y$, then participate in an instance of $\PiPerRec$ with shares $\{[y]_q \}_{P_i \in S_q}$ to publicly
reconstruct $y$.

Termination Phase

Concurrently execute the following steps during the protocol:

1. If the circuit-output $y$ is computed, then send $(\Ready, \sid, P_i, y)$ to every party in $\PartySet$.

2. If the message $(\Ready, \sid, P_j, y)$ is received from a set of parties ${\cal A}$ such that $\AdvStructure$ satisfies  $\Q^{(1)}({\cal A}, \AdvStructure)$ condition, then
send $(\Ready, \sid, P_i, y)$  to every party in $\PartySet$.

3. If the message $(\Ready, \sid, P_j, y)$ is received from a set of parties $\W$ such that $\PartySet \setminus \W \in \AdvStructure$,
then output $y$ and terminate.

Intuitively, protocol $\PiMPC$ eventually terminates as the set $\CoreSet$ is eventually decided. This is because even if the corrupt parties do not secret-share their inputs,
the inputs of all honest parties are eventually secret-shared. Once $\CoreSet$ is decided, the evaluation of each gate will be eventually completed:
while the addition gates are evaluated non-interactively, the evaluation of multiplication gates requires reconstructing the corresponding masked gate-inputs
which is eventually completed due to the reconstruction protocols.
The privacy of the inputs of the honest parties in $\CoreSet$ will be maintained as the sharing specification $\ShareSpec$ is $\AdvStructure$-private.
Moreover, the inputs of the corrupt parties in $\CoreSet$ will be independent of the inputs of the honest parties in $\CoreSet$, as inputs are secret-shared
via calls to $\FVSS$. Finally, correctness holds since each gate is evaluated correctly.
We next rigorously formalize this intuition by giving a formal security proof
and show that the protocol $\PiMPC$ is perfectly-secure, if the parties have access to ideal functionalities
$\FTriples, \FVSS$ and $\FABA$.

Theorem <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$.

The communication complexity in the $(\FTriples, \FVSS, \FABA)$-hybrid model follows from the fact that for evaluating each multiplication gate, the
parties need to run $2$ instances of the reconstruction protocol $\PiPerRec$.

For security, let $\Adv$ be an arbitrary real-world adversary  corrupting the set of parties $Z^{\star} \in \AdvStructure$
and let $\Env$ be an arbitrary environment. We  show  the  existence  of  a  simulator $\SimPerAMPC$, such  that
the output of honest parties and the view of the adversary in an execution of the real protocol with $\Adv$
is identical to the output in an execution with $\SimPerAMPC$ involving $\Functionality$ in the ideal model.
This further implies that $\Env$ cannot distinguish between the two executions.
The steps of the simulator are  given in
Fig <ref>.

The high level idea of the simulator is as follows. During the simulated execution, the simulator itself performs the role of the ideal functionalities $\FTriples, \FVSS$
and $\FABA$ whenever required. Performing the role of $\FTriples$ allows the simulator to learn the secret-sharing
of all the multiplication-triples.
During the input phase, whenever $\Adv$ secret-shares any value through $\FVSS$
on the behalf of a corrupt party, the simulator
records this on the behalf of the corrupt party. This allows the simulator to learn the function-input of the corresponding
corrupt party. On the other hand, for the honest parties, the simulator picks arbitrary values as their
function-inputs and simulates the secret-sharing of those input values using random shares, as per $\FVSS$.
To select the common input-providers during the simulated execution, the simulator
itself performs the role of $\FABA$ and simulates the honest parties as per the steps of the protocol and $\FABA$. This allows the simulator
to learn the
common subset of input-providers $\CoreSet$, which the simulator passes to the functionality $\Functionality$. Notice that
the function-inputs for each corrupt party in $\CoreSet$ will be available with the simulator.
This is because for every corrupt party $P_j$ which is added to $\CoreSet$, at least one honest party $P_i$ should participate with input $1$ in the corresponding call to
$\FABA$. This implies that the honest party $P_i$ must have received the shares $P_j$ sent to $\FVSS$ from $\FVSS$. Since in the simulation, the role of $\FVSS$ is played by the simulator, it implies that the full vector of shares provided by
$P_j$ to $\FVSS$ will be known to the simulator.
Hence, along with $\CoreSet$, the simulator can send the corresponding function-inputs of the corrupt parties in $\CoreSet$ to $\Functionality$.
Upon receiving the function-output, the simulator simulates the steps of the honest parties for the gate evaluations as per the
protocol. Finally, for the output gate, the simulator arbitrarily computes a secret-sharing of the function-output $y$ received from $\Functionality$, which is consistent
with the shares which corrupt parties hold for the output-gate sharing. Then, on the behalf of the honest parties, the simulator sends the shares corresponding to
the above sharing of $y$ during the public reconstruction of $y$. This ensures that in the simulated execution, $\Adv$ learns the function-output $y$. For the termination phase,
the simulator sends $y$ on the behalf of honest parties.

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

$\SimPerAMPC$ 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 various functionalities.
In order to simulate $\Env$, the simulator $\SimPerAMPC$ forwards every message it receives from
$\Env$ to $\Adv$ and vice-versa.  The simulator then simulates the various phases of the protocol as follows.

Pre-Processing Phase

Simulating the call to $\FTriples$: The simulator simulates the steps of $\FTriples$ by itself playing the role of $\FTriples$.
Namely, it receives the shares corresponding to the parties in $Z^{\star}$ for each multiplication-triple from $\Adv$ and then
randomly generates secret-sharing of $M$ random multiplication-triples $\{(\sima^{(\ell)}, \simb^{(\ell)}, \simc^{(\ell)})\}_{\ell = 1, \ldots, M}$
consistent with the provided shares.
At the end of simulation of this phase, the simulator will know the entire vector of shares corresponding to the secret-sharing of all

Input Phase

* The simulator simulates the operations of the honest parties during the input phase, by randomly picking $\simx^{(j)}$ as the input, for
every $P_j \not \in Z^{\star}$, selecting random shares $\simx^{(j)}_1, \ldots, \simx^{(j)}_h$ such that
$\simx^{(j)} = \simx^{(j)}_1 + \ldots + \simx^{(j)}_h$, and setting $[\simx^{(j)}]_q = \simx^{(j)}_q$, for $q = 1, \ldots, h$.
When $\Adv$ requests output from $\FVSS$ with $\sid_j$ on the behalf of any party $P_i \in Z^{\star}$,
then the simulator  responds with an output
$(\Share, \sid_j, P_j, \{[\simx^{(j)}]_q \}_{P_i \in S_q})$
on the behalf of $\FVSS$.

* Whenever $\Adv$ sends $(\Dealer, \sid_i, P_i, (x^{(i)}_1, \ldots, x^{(i)}_h))$
to $\FVSS$ on the behalf of any $P_i \in Z^{\star}$, the simulator
records the input $x^{(i)} \defined x^{(i)}_1 + \ldots + x^{(i)}_h$ on the behalf of $P_i$ and sets
$[x^{(i}] = (x^{(i)}_1, \ldots, x^{(i)}_h)$.

* When the simulation reaches the “Selecting Common Input-Providers" stage, the simulator simulates the interface of $\FABA$ to $\Adv$ by itself
performing the role of $\FABA$.
When the first honest party completes the simulated input phase, $\SimPerAMPC$ learns the set $\CoreSet$.

Interaction with $\Functionality$:  Once the simulator learns $\CoreSet$, it sends
the input values $x^{(i)}$ that it has recorded on the behalf of each
$P_i \in (Z^{\star} \cap \CoreSet)$, and the set of input-providers $\CoreSet$ to $\Functionality$. Upon receiving the
output $y$ from $\Functionality$, the simulator starts the simulation of circuit-evaluation phase.

Circuit-Evaluation Phase

The simulator simulates the evaluation of each gate $g$ in the circuit in topological order as follows:

* Addition Gate: Since this step involves local computation, the simulator does not have to simulate any messages on the behalf of the
honest parties. The simulator locally adds the secret-sharings corresponding to the gate-inputs and obtains the
secret-sharing corresponding to the gate-output.

* Multiplication Gate: If $g$ is the $\ell^{th}$ multiplication gate in the circuit, then the simulator takes the complete secret-sharing of the
$\ell^{th}$ multiplication triple $(\sima^{(\ell)}, \simb^{(\ell)}, \simc^{(\ell)})$ and computes the messages of the honest parties as per the
steps of the protocol (by considering the secret-sharing of the above multiplication-triple and the secret-sharing of the gate-inputs),
and sends them to $\Adv$ on the behalf of the honest parties as part of the instances of $\PiPerRec$ protocol.
Once the simulation of the circuit-evaluation phase is done, the simulator will know the secret-sharing corresponding to the gate-output.

* Output Gate: Let $[\simy] = (\simy_1, \ldots, \simy_h)$ be the secret-sharing corresponding to the output gate, available with $\SimPerAMPC$
during the simulated circuit-evaluation. The simulator then randomly selects shares $\simby_1, \ldots, \simby_h$ such that
$\simby_1+  \ldots +  \simby_h = y$ and $\simby_q = \simy_q$ corresponding to every $S_q \in \ShareSpec$ where
$S_q \cap Z^{\star} \neq \emptyset$. Then, as part of the instance of $\PiPerRec$ protocol to reconstruct the function output,
the simulator sends the shares $\{\simby_q \}_{S_q \in \ShareSpec}$ to $\Adv$ on the behalf of the honest parties.

Termination Phase

The simulator sends a $\Ready$ message for $y$ to $\Adv$ on the behalf of $P_i \not \in Z^{\star}$,
if in the simulated execution, $P_i$ has computed $y$.

We next prove a sequence of claims, which helps us to show that the joint distribution of the honest parties
and the view of $\Adv$ is identical in both the real, as well as the ideal-world.
We first claim that in  any execution of $\PiMPC$, a set $\CoreSet$ is eventually generated. This automatically implies that
the honest parties eventually possess a secret-sharing of $M$ random multiplication-triples generated by $\FTriples$, as well as
a secret-sharing of the inputs of the parties in $\CoreSet$.

In any execution of $\PiMPC$, a set $\CoreSet$ is eventually generated, such that for every $P_j \in \CoreSet$, there exists some $x^{(j)}$ held by $P_j$
which is eventually secret-shared.

As the proof of this claim is similar to the proof of Claim <ref>, we skip the formal proof.

We next show that the view generated by $\SimPerAMPC$ for $\Adv$ is identically distributed to $\Adv$'s view during the real execution of $\PiMPC$.

The view of $\Adv$ in the simulated execution with $\SimPerAMPC$ is identically distributed to the view of $\Adv$ in the real execution of

It is easy to see that the view of $\Adv$ during the pre-processing phase is identically distributed in both the executions. This is because in both the executions,
$\Adv$ receives no messages from the honest parties and the steps of $\FTriples$ are executed by the simulator itself in the simulated execution.
Namely, in both the executions, $\Adv$'s view consists of the shares of $M$ random multiplication-triples corresponding to the parties in $Z^{\star}$.
So, let us fix these shares. Conditioned on these shares,
during the input phase, $\Adv$ learns the shares $\{[x^{(j)}]_q \}_{P_j \not \in Z^{\star}, (S_q \cap Z^{\star}) \neq \emptyset}$ during the real execution
corresponding to the
parties $P_j \not \in Z^{\star}$. In the simulated execution, it learns the shares
$\{[\simx^{(j)}]_q \}_{P_j \not \in Z^{\star}, (S_q \cap Z^{\star}) \neq \emptyset}$. Since the sharing specification $\ShareSpec$
is $\AdvStructure$-private and the vector of shares $(x^{(j)}_1, \ldots, x^{(j)}_h)$ as well as
$(\simx^{(j)}_1, \ldots, \simx^{(j)}_h)$ are randomly chosen, it follows that
the distribution of  the shares $\{[x^{(j)}]_q \}_{P_j \not \in Z^{\star}, (S_q \cap Z^{\star}) \neq \emptyset}$
as well as $\{[\simx^{(j)}]_q \}_{P_j \not \in Z^{\star}, (S_q \cap Z^{\star}) \neq \emptyset}$ is identical and
independent of both $x^{(j)}$ as well as $\simx^{(j)}$,
so let us fix these shares. Since the role of $\FABA$ is played by the simulator itself, it follows easily that the view of $\Adv$ during the selection of the set $\CoreSet$
is identically distributed in both the real as well as the simulated execution.

During the evaluation of linear gates, no communication is involved. During the evaluation of multiplication gates, in the simulated execution,
the simulator will know the secret-sharing associated with gate-inputs and also the secret-sharing of the associated
multiplication-triple. Hence, the simulator correctly sends the shares corresponding to the values $d^{(\ell)}$ and $e^{(\ell)}$ as per the protocol
on the behalf of the honest parties. Moreover, the values $d^{(\ell)}$ and $e^{(\ell)}$ will be randomly distributed for $\Adv$ in both the executions, since
the underlying multiplication-triple is randomly distributed, conditioned on the shares of the corrupt parties.
Thus, $\Adv$'s view during the evaluation of multiplications gates is identically distributed
in both the executions.

For the output gate, the shares received by $\Adv$ in the real execution from the honest parties correspond to a secret-sharing
of the function-output $y$. From the steps of $\SimPerAMPC$, it is easy to see that the same holds even in the simulated execution,
as $\SimPerAMPC$ sends to $\Adv$ shares corresponding to a secret-sharing of $y$, which are consistent with the shares
held by $\Adv$. Hence, $\Adv$'s view is identically distributed in both the executions during the evaluation of output gate.
Finally, it is easy to see that $\Adv$'s view is identically distributed in both the executions during the termination phase. This is because
in both the executions, every honest party who has obtained the function output $y$, sends a $\Ready$ message for $y$.

We next claim that conditioned on the view of $\Adv$ (which is identically distributed in both the executions from the last claim),
the output of the honest parties is identically distributed in both the worlds.

Conditioned on the view of $\Adv$, the output of the honest parties is
identically distributed in the real execution of $\PiMPC$ involving $\Adv$, as well as in the ideal execution
involving $\SimPerAMPC$ and $\Functionality$.

Let $\View$ be an arbitrary view of $\Adv$, and let $\CoreSet$ be the set of input-providers determined by $\View$
(from Claim <ref>, such a set $\CoreSet$ is bound to exist).
Moreover, according to $\View$,  for every $P_i \in \CoreSet$, there exists some input $x^{(i)}$ such that the parties hold a
secret-sharing of $x^{(i)}$. Furthermore, from Claim <ref>,
if $P_i \in Z^{\star}$ then the corresponding secret-sharing is included in $\View$. For $P_i \not \in Z^{\star}$,
the corresponding $x^{(i)}$ is uniformly distributed conditioned on the shares of $x^{(i)}$ available with $\Adv$ as determined by
$\View$. Let us fix the $x^{(i)}$ values corresponding to the parties in $\CoreSet$
and denote the vector of values $x^{(i)}$, where $x^{(i)} = 0$ if $P_i \not \in \CoreSet$, by $\vec{x}$.

It is easy to see that in the ideal-world, the output of the honest parties is $y$, where $y \defined f(\vec{x})$.
This is because $\SimPerAMPC$ provides the identity of $\CoreSet$ along with the inputs $x^{(i)}$ corresponding to $P_i \in (\CoreSet \cap Z^{\star})$ to
$\Functionality$. We now show that the honest parties eventually output $y$ even in the real-world. For this, we argue
that all the values during the circuit-evaluation phase of the protocol are correctly secret-shared.
Since the evaluation of linear gates needs only local computation, it follows
that the output of the linear gates will be correctly secret-shared. During the evaluation of a multiplication gate, the honest parties will hold a
secret-sharing of the corresponding $d^{(\ell)}$ and $e^{(\ell)}$ values, as during the pre-processing phase,
all the multiplication-triples are generated in a secret-shared fashion, since they are computed
and distributed by $\FTriples$. Since $\ShareSpec$ satisfies the $\Q^{(2)}(\ShareSpec, \AdvStructure)$ condition,
the honest parties eventually get $d^{(\ell)}$ and $e^{(\ell)}$ through the instances of $\PiPerRec$.
This automatically implies that the honest parties eventually hold a secret-sharing of $y$ and reconstruct it correctly, as
$y$ is reconstructed through an instance of $\PiPerRec$.
Hence, during the termination phase, every honest party will eventually send a $\Ready$ message for $y$, while the parties in $Z^{\star}$
may send a $\Ready$ message for $y' \neq y$. Since $Z^{\star} \in \AdvStructure$, it follows that
no honest party ever sends a $\Ready$ message for $y'$. Hence no honest party ever outputs $y'$, as it will never receive
the required number of $\Ready$ messages for $y'$.
Since the $\Ready$ messages of the honest
parties for $y$ are eventually delivered to every honest party, it follows that eventually, all honest parties
receive sufficiently many $\Ready$ messages to obtain some output, even if the corrupt parties does not send the required messages.

Now let $P_i$ be the first honest party to terminate the protocol with some output. From the above arguments, the output has to be $y$.
This implies that $P_i$ receives $\Ready$ messages for $y$
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_i$. 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_i$) eventually executes step $2$ of the termination phase and sends a
$\Ready$ message for $y$.
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 the output $y$.

The theorem now follows from Claims <ref>-<ref>.


August 29, 2024

On the exclusion limits in $t\overline{t}+$DM searches at the LHC

Jonathan Hermann111Work supported by German Research Foundation (DFG)
Collaborative Research Centre/Transregio project CRC/TRR 257:P3H - Particle
Physics Phenomenology after the Higgs Discovery, by the Research Training
Group GRK $2497$: The physics of the heaviest particles at the Large Hadron
Collider and by a grant of the Bundesministerium für Bildung und Forschung
(BMBF).

Institute for Theoretical Particle Physics and Cosmology
RWTH Aachen University
D-52056 Aachen, Germany

> In these proceedings we discuss the importance of higher-order corrections
> and off-shell effects for the calculation of signal strength exclusion
> limits in $t\overline{t}+$DM searches at the Large Hadron Collider. We
> present limits for the spin-0 s-channel mediator model using state-of-the-
> art NLO QCD predictions with full off-shell effects for the relevant
> $t\overline{t}$ and $t\overline{t}Z$ background processes. These are then
> compared to less sophisticated predictions using either the narrow-width
> approximation or LO calculations in order to asses the respective effects.

> PRESENTED AT
>
>
>
>
> $14^{\mathrm{th}}$ International Workshop on Top Quark Physics
> Michigan, US (videoconference), 13–17 September, 2021

Preprint numbers

TTK-22-03 $\,\cdot\,$ P3H-22-003

##  1 Introduction

Even though the existence of Dark Matter (DM) has been well established, the
discovery of a suitable Dark Matter candidate has proven to be a difficult
task. At the forefront of current DM searches are collider searches by the CMS
and ATLAS collaborations. These analyses cover a wide range DM models which
result in various signatures and final states. The unifying characteristic of
all of these models is that they result in an excess of missing transverse
momentum $p_{T,\text{miss}}$ which might be observable at the LHC. However, in
order to distinguish any sort of signal from the SM background, one requires
accurate and precise predictions for the Standard Model (SM) background. This
is particularly true for distribution tails, e.g. for $p_{T,\text{miss}}$, as
both next-to-leading (NLO) QCD corrections and off-shell effects are most
prominent in these tails. NLO QCD corrections have by now become the norm for
(associated) top-quark pair production but decays are often still modelled at
leading order (LO), like e.g. in MadGraph5_aMC@NLO [1], and off-shell effects
are often ignored or only partly taken into account. As full off-shell NLO QCD
predictions have become available over past few years (see e.g. Refs [2, 3]),
we want to asses the importance of both higher-order corrections and off-shell
effects and evaluate whether the added complexity is actually necessary for DM
searches at the LHC. The discussion is based on the results presented in Ref.
[4].

##  2 Setup

For our analysis we consider top-quark pair associated DM production with
leptonic top decays, i.e. $pp\to
b\overline{b}e^{+}\mu^{-}\nu_{e}\overline{\nu}_{\mu}\chi\overline{\chi}$
production. The DM particle pair production is described by the spin-0
s-channel mediator model which extends the SM by a (pseudo-)scalar mediator
$Y$ and a fermionc DM particle $\chi$. Adhering to the Minimal Flavor
Violation (MFV) hypothesis, the coupling between the mediator and SM quarks is
proportional to the Yukawa coupling $y_{q}$. We fix the DM particle mass to
$m_{\chi}=1$ TeV and the couplings to $g_{q}=g_{\chi}=1$, in line with the
recommendations outlined in Ref. [5]. The mediator mass is varied between
$m_{Y}=10$ GeV and $1$ TeV. The $t\overline{t}\chi\overline{\chi}$ signal
predictions are calculated with MadGraph5_aMC@NLO at NLO in QCD using the
DMsimp [6] implementation.

The dominant SM background processes for the $t\overline{t}+$DM signal are
$t\overline{t}$ and $t\overline{t}Z,\,Z\to\nu\overline{\nu}$ production with
leptonically decaying top quarks. Cross-sections and distributions for these
processes are calculated using Helac-NLO [7, 8]. Integrated fiducial cross-
sections with inclusive cuts are presented in Table 1 as
$\sigma_{\text{uncut}}$.

Table 1: Comparison of LO and NLO integrated cross sections for the two background processes in the NWA (top) and the FOST (bottom) before and after applying the additional cuts. The numbers of events are given for an integrated luminosity of $L=300\,\text{ fb}^{-1}$ and include the lepton flavour factors ($4$ for the DM signal and $t\overline{t}$, and $12$ for $t\overline{t}Z$). Process | Order |  $\sigma_{\text{uncut}}$ [fb] |  $\sigma_{\text{cut}}$ [fb] |  $\sigma_{\text{cut}}/\sigma_{\text{uncut}}$ | Events
---|---|---|---|---|---
$t\overline{t}$ NWA | LO | $1061$ | $0$ |  $0.0\%$ | $0$
NLO | $1097$ | $0$ |  $0.0\%$ | $0$
NLO with LO decays | $1271$ | $0$ |  $0.0\%$ | $0$
$t\overline{t}Z$ NWA | LO | $0.1223$ | $0.0130$ |  $11\%$ | $47$
NLO | $0.1226$ | $0.0130$ |  $11\%$ | $47$
NLO with LO decays | $0.1364$ | $0.0140$ |  $10\%$ | $50$
$t\overline{t}$ Off-shell | LO | $1067$ | $0.0144$ |  $0.0013\%$ | $17$
NLO | $1101$ | $0.0156$ |  $0.0014\%$ | $19$
$t\overline{t}Z$ Off-shell | LO | $0.1262$ | $0.0135$ |  $11\%$ | $49$
NLO | $0.1269$ | $0.0134$ |  $11\%$ | $48$

For the actual analysis we impose an additional, more exclusive cut selection
based on Ref. [9]. Here, we also require $p_{T,\text{miss}}>150$ GeV,
$M_{T2,W}>90$ GeV and $C_{em,W}>130$ GeV where $M_{T2,W}$ is the stransverse
$W$-mass and $C_{em,W}$ is defined as $C_{em,W}=M_{T2,W}-0.2\cdot(200\text{
GeV}-p_{T,\text{miss}})$. The corresponding integrated fiducial cross-sections
are listed in Table 1 under $\sigma_{\text{cut}}$ along with the fraction of
events that pass the cuts and the expected number of background events for an
integrated luminosity of $L=300\,\text{fb}^{-1}$.

It turns out that despite the initially overwhelming size of the
$t\overline{t}$ cross-section, the $t\overline{t}Z$ process is actually the
dominant SM background with between $47$ and $50$ expected events depending on
the modeling, compared to up to $19$ for $t\overline{t}$. However, the most
important observation is that in the narrow-width approximation (NWA), no
$t\overline{t}$ events pass the exclusive cuts which is not the case in the
full off-shell treatment (FOST). This is a result of the cut on $M_{T2,W}$
since for $t\overline{t}$ in the NWA, we have $M_{T2,W}\leq m_{W}$. However,
single- and non-resonant contributions still appear above this threshold so
that in the FOST there are still $t\overline{t}$ events passing the cuts. This
means that around a quarter of the background events is missing when using the
NWA instead of the FOST which significantly affects the exclusion limits.

Figure 1: Comparison of signal strength exclusion limits computed with
different background predictions for the pseudoscalar mediator scenarios with
a luminosity of $L=3000\text{ fb}^{-1}$. In the lower panels we present the
ratios to the limits obtained using the NLO${}_{\text{Off-shell}}$ background
predictions.

##  3 Exclusion Limits

In Figure 1 we compare the signal strength exclusion limits
$\mu^{95\%\,\text{CL}}$ calculated at $95\%$ confidence level (CL) for various
different SM background predictions. All limits were computed using the
HistFitter [10] implementation of the $CL_{s}$-method [11]. For this specific
comparison we chose
$\cos(\theta^{*}_{ll})=\tanh(|\eta_{l_{1}}-\eta_{l_{2}}|/2)$ as our
observable. An explicit comparison between the integrated fiducial cross-
section $\sigma_{\text{tot}}$, $p_{T,\text{miss}}$, $\cos(\theta^{*}_{ll})$,
the azimuthal angle between the missing transverse momentum and the closest
lepton $\Delta\phi_{l,\text{miss}}$ and the stransverse top mass $M_{T2,t}$
showed that $\cos(\theta^{*}_{ll})$ yields the most stringent limits for
almost all considered mediators. Solely for light scalar mediators, $M_{T2,t}$
provides better limits. The results shown here were obtained using the
pseudoscalar mediator scenario but they are comparable for the scalar case. We
use an integrated luminnosity of $L=3000\,\text{fb}^{-1}$ for this specific
comparison but the main observations are independent of this value. However,
the differences are more striking for larger luminosities as statistical
uncertainties play less of a role.

One can clearly observe from the left plot in Figure 1 that the off-shell NLO
(red) background predictions lead to significantly better limits than if one
uses LO predictions (blue). We also find that it is insufficient to only model
the $t\overline{t}$ process at NLO as the
$t\overline{t}^{NLO}+t\overline{t}Z^{LO}$ background (green) leads to limits
that are almost as far off the full NLO results as the pure LO results. This
is not surprising as we have already seen that $t\overline{t}Z$ is the
dominant background, so reducing the scale uncertainties is more important for
this process than for $t\overline{t}$.

Turning to the off-shell effects, we observe that the NWA predictions lead to
underestimated limits (purple) compared to the full prediction. The main
reason are the missing $t\overline{t}$ events in the NWA which we mentioned
previously. This hypothesis is underlined by the comparison on the right side
of Figure 1 where we replaced the $t\overline{t}$ NWA predictions by their
off-shell counterpart whilst keeping $t\overline{t}Z$ in the NWA. As this
substantially reduces the difference to the NLO off-shell limits, we conclude
that off-shell effects in $t\overline{t}Z$ only play a minor role here.

We also considered NLO predictions with LO decays (brown) in this comparison.
Since the size of their scale uncertainties falls in between those for the LO
and NLO predictions, the exclusion limits do the same. As these limits are
considerably worse than those for the full NLO, we can conclude that it is
important to also include NLO corrections to the decays.

In order to disentangle the effects of reduced scale uncertainties and shape
distortions between LO and NLO, we also include a so-called LO’ prediction on
the right plot (green) which corresponds to LO predictions with NLO
uncertainites. The corresponding limits essentially coincide with the full NLO
results, so the main difference between LO and NLO is the reduction in scale
uncertainties while shape distortions only play a minor role. Let us mention
that in principle the integrated cross-section can also change significantly
between LO and NLO but due to our scale choice this effect is minimized.

In addition to the above described comparison, we also considered the effect
that the choice of the central scale has on the exclusion limits. It turns out
that for some observables, in particular $M_{T2,t}$, this is even relevant at
NLO. As a fixed scale setting leads to larger scale uncertainties than the
dynamical ones, the corresponding limits are also worse. Hence, it is
important to use a dynamical scale. In contrast, the difference between the
tested dynamical scale settings is rather small.

We also investigated the effects of different integrated luminosities on the
exclusion limits. As one might expect, the limits improve when increasing the
luminosity since statistical uncertainties are proportional to $1/\sqrt{L}$.
These effects are larger the more precise the background prediction is because
statistical uncertainties make up a larger proportion of the total uncertainty
for more precise backgrounds.

For further details on all of the described comparisons we refer to Ref. [4].

##  4 Conclusions

In these proceedings we have discussed various different inputs for the
calculation of exclusion limits and outlined the impact that changing these
has on the limits. We have demonstrated that NLO QCD corrections are vital for
this type of analysis. Off-shell effects also need to be taken into account
for the $t\overline{t}$ process but seem to be unnecessary for
$t\overline{t}Z$. In addition, we found that the central scale choice is
important even at NLO and that one should refrain from using a fixed scale.
Similar to higher-order corrections, an increased luminosity reduces the
uncertainties and thus also improves the limits considerably. Finally, we
investigated which observable yields the most stringent limits and identified
$\cos(\theta^{*}_{ll})$ as the most promising observable.

## References

  * [1] J. Alwall, et al., JHEP 07 (2014) 079.
  * [2] G. Bevilacqua, M. Czakon, A. van Hameren, C.G. Papadopoulos, M. Worek, JHEP 02 (2011) 083.
  * [3] G. Bevilacqua, H.B. Hartanto, M. Kraus, T. Weber, M. Worek, JHEP 11 (2019) 001.
  * [4] J. Hermann, M. Worek, Eur. Phys. J. C 81 (2021) 1029.
  * [5] D. Abercrombie, et al., Phys. Dark Univ. 27 (2020) 100371.
  * [6] M. Backović, M. Krämer, F. Maltoni, A. Martini, K. Mawatari, M. Pellen, Eur. Phys. J. C 75 (2015) 482.
  * [7] G. Bevilacqua, M. Czakon, M.V. Garzelli, A. van Hameren, A. Kardos, C.G. Papadopoulos, R. Pittau, M. Worek, Comput. Phys. Commun. 184 (2013) 986.
  * [8] G. Bevilacqua, H.B. Hartanto, M. Kraus, T. Weber, M. Worek, JHEP 03 (2020) 154.
  * [9] U. Haisch, P. Pani, G. Polesello, JHEP 02 (2017) 131.
  * [10] M. Baak, G.J. Besjes, D. Côte, A. Koutsman, J. Lorenz, D. Short, Eur. Phys. J. C 75 (2015) 153.
  * [11] A.L. Read, J. Phys. G: Nucl. Part. Phys. 28 (2002) 2693.


# Fake News and Hate Speech: Language in Common
††thanks: This work was partially supported by European Commission under
project IBERIFIER (CEF-TC-2020-2, European Digital Media Observatory) with
reference 2020-EU-IA-0252 and partially supported by a María Zambrano grant of
the Spanish Ministerio de Universidades and the European Union
NextGenerationEU/PRTR.
First author is also a member of Social Psychology Department at the
Universitat de València

Berta Chulvi  PRLHT Research Center
Universitat Politècnica de València
Valencia, Spain
berta.chulvi@upv  Alejandro H. Toselli  PRLHT Research Center
Universitat Politècnica de València
Valencia, Spain
<EMAIL_ADDRESS>Paolo Rosso  PRLHT Research Center
Universitat Politècnica de València
Valencia, Spain
<EMAIL_ADDRESS>
###### Abstract

In this paper we raise the research question of whether fake news and hate
speech spreaders share common patterns in language. We compute a novel index,
the ingroup vs outgroup index, in three different datasets and we show that
both phenomena share an ”us vs them” narrative.

###### Index Terms:

Fake news, hate speech, NLP

##  I Introduction

Language use is central to the spread of fake news and hate speech. Both
phenomena are part of information disorders according to the Council of Europe
[1]. To stress the links between them some authors have used also the concept
of harmful information [2]. Recently some studies have characterised the
language used to disseminate fake news at the psycholinguistic level [3].
Other research has analyzed which psycholinguistic features are most present
in the dissemination of online hate speech [4]. However, to the best of our
knowledge, there is no empirical research showing that the two phenomena share
linguistic patterns.

This research is based on the idea that hate speech and fake news are both at
the service of online extremism. Conceptually, extremism involves hostility
towards an apparent ”foreign” group based on an opposing characteristic or
ideology[5]. Following this line of reasoning, fake news and hate speech
spreaders could share certain linguistic patterns if their deep goal was
similar, that is to say, to divide the social arena between two groups (us vs
them) focusing especially on the construction of otherness (them).

It is well known that personal pronouns in language provide valuable
information about subjects and their social environment [6]. It has been shown
a higher occurrence of first and third-person plural pronouns in Extremist
Alt-Right Subreddit forums [7]. Also, the use of third-person plural pronouns
has been identified as a mark of extremism [8]. But all these research
computed the frequency of first-person and third-person plural words
independently, and none of them used a relational index to measure the
relative emphasis placed on the ingroup or the outgroup. In Section III, we
explain how we have created an index to measure this relative emphasis.

##  II Datasets

In the present research, we use three different datasets.

###  II-A Check-worthiness tweets in CheckThat!2022

The dataset was presented in CheckThat! lab in CLEF-2022 to determine whether
a claim in a tweet is worth fact-checking. For Spanish, it was provided a
corpus of 14,000+ posts from Twitter published by 310 politicians. This corpus
was annotated by professional fact-checkers from
Newtral111https://www.newtral.es. They assigned the label 1 when considering
that the tweet contains content that should be verified and 0 in the opposite
case. For the present research, we identify in the training and development
part of this dataset (7,489 tweets) the authors of each tweet, and we select
the tweets of 209 politicians that have tweets annotated in classes 0 (4,983
tweets) and 1 (2,184 tweets). See [9] for details about the corpus.

###  II-B Fake news spreaders in PAN2020

The dataset was provided in the PAN Lab in CLEF-2020. The objective of this
task was to determine whether or not the author of a Twitter feed is keen to
spread fake news. In Spanish, a corpus with Twitter data was provided with 500
user feeds. For the present research, we use only the Spanish training dataset
composed of 300 user feeds. We select the user feeds with have between 90 and
150 tweets, discarding users with an anomalous number of tweets. The result is
a dataset that contains a total of 31,652 tweets from 284 user feeds: 146
users are considered fake news spreaders because they had shared at least once
a piece of fake news and 138 users were labeled as non-fake news spreaders
because they have not shared any fake news. See [10] for details about the
corpus.

###  II-C Hate speech spreaders in PAN2021

The dataset was created for PAN Lab in CLEF-2021 focusing on hate speech. The
objective of the task was to determine whether or not the author of a Twitter
feed is keen to spread hate speech, mainly against women and immigrants. In
Spanish, a corpus of 300 user feeds (200 for training, and 100 for test)
composed of the 200 last tweets of each user was provided. Users with more
than ten hateful tweets were annotated as keen to spread hate speech and users
that do not fit this condition as the opposite class. For the present
research, we use only the Spanish training dataset composed of 200 users and a
total of 40,000 tweets. Among them, 100 users are hate speech spreaders, and
100 are not. See [11] for details about the corpus.

##  III Methodology and hypothesis

###  III-A Text representation

Using the morphology information provided by the tagger
spaCy222https://spacy.io v3.0 we identified in the three datasets how many
verbs and pronouns in first, second, and third person are contained in each
tweet. We calculated the percentage of each person category with respect to
the total of person tags present in each tweet. For each user, the scores of
all tweets in each category were added and divided by the number of tweets of
the user. In the CheckThat!2022 dataset we did this last operation twice
considering two separate subsets of data for each user: (1) the tweets that
should be reviewed and (2) the tweets that lack interest in being reviewed. As
result, each Spanish politician included has two scores, one corresponding to
the use of personal tags in tweets that should be checked and the other
corresponding to the use of personal tags in tweets that are not interesting
for being checked. Once we have this information for each user, we calculate
the ingroup vs outgroup index as a subtraction between the use of the first
person and the use of the third person in texts. If the score in this index is
positive, it means that the user talks more about his group or about his own
position (ingroup). Otherwise, if it is negative, it means that the user
focuses their attention more on others (outgroup).

###  III-B Hypothesis

In CheckThat!2022 our hypothesis is that tweets considered relevant for being
checked will present a more negative score in the ingroup vs outgroup index
than irrelevant tweets ($H_{1}$). In PAN2020 dataset we expect that users with
spread fake news present a more negative score in the ingroup vs outgroup
index than users who do not ($H_{2}$). The same is expected In PAN2021: the
hypothesis is that users who spread hate speech present a more negative score
in the ingroup vs outgroup index than users who do not ($H_{3}$).

##  IV Results

The scores of the ingroup vs outgroup index are not normally distributed
according to the Kolmogorov-Smirnov test (p¡.001 in the three datasets).
Therefore, we performed a Wilcoxon signed-rank test for matched samples in the
CheckThat!2022 dataset to test ($H_{1}$) and a Mann-Whitney test in PAN2020
and PAN2021 datasets to test ($H_{2}$) and ($H_{3}$). Descriptive statistics
are summarized in Table 1.

In the CheckThat!2022 dataset, the Wilcoxon signed-rank test for matched
samples indicates that the ingroup vs outgroup index is statistically
significantly lower in relevant tweets than in irrelevant tweets (Z=-8,995;
p$<$.001). In PAN2020, the ingroup vs outgroup index is statistically
significantly lower in users who spread fake news than in those who do not
(U=7,648; p$<$.001). In PAN2021, the ingroup vs outgroup index is
statistically significantly lower in users who spread hate speech than in
those who do not (U=2,133; p$<$.001).

TABLE I: Ingroup vs outgroup index Data Collection | Indp. Var. | Users | Tweets | Mdn | Rank
---|---|---|---|---|---
CheckThat! | irrelevant | 209 | 4,983 | -4.14 | 105.34
| relevant | 209 | 2,184 | -16.45 | 99.23
PAN2020 | Fake news | 146 | 15,736 | -0.63 | 1.22
| Not fake news | 138 | 15,916 | -0.51 | 0.96
PAN2021 | Hate | 100 | 20,000 | -0.24 | 0.38
| Not hate | 100 | 20,000 | -0.11 | 0.45

##  V Conclusion

To the best of our knowledge, our study is the first that compares linguistic
patterns used by fake news and hate speech spreaders. In our opinion, this
research shows the usefulness of NLP for a deeper understanding of harmful
information. As it has been shown, a vision of the social arena in terms of
group conflict is underlying both phenomena. Empirical verification of these
“us vs them” narratives could provide a mechanism to demand accountability
from politicians and opinion leaders. For future work, we plan to check if it
improves the explainability and performance of the classifiers used to detect
automatically fake news and hate speech.

## References

  * [1] Wardle, C. and Derakhshan, H. Information disorder: Toward an interdisciplinary framework for research and policy making Information Disorder. Council of Europe Report DGI (2017)09
  * [2] Giachanou, A.; Rosso, P. (2020). The battle against online harmful information: The cases of fake news and hate speech. Association for Computing Machinery (ACM). 3503-3504.
  * [3] Giachanou, A.; Ghanem, B.; Ríssola, E.A.; Rosso, P.; Crestani, F.; Oberski, D. (2022) The impact of psycholinguistic patterns in discriminating between fake news spreaders and fact checkers. Data Knowl. Eng., 138.
  * [4] Caetano Da Silva, S., Castro Ferreira, T., Silva Ramos, R.M. and Paraboni, I. (2020) Data driven and psycholinguistics motivated approaches to hate speech detection. Computación y Sistemas 24.
  * [5] Kinnvall, C. and Capelos, T. (2021) The psychology of extremist Identification. European Psychologist 26, 1–5.. doi:10.1027/1016-9040/a000439
  * [6] Pennebaker, J. W., Mehl, M. R., and Niederhoffer, K. (2003) Psychological aspects of natural language use: Our words, our selves.Annual Review of Psychology, 54, 547–577.
  * [7] Grover, T. and Mark, G. (2019) Detecting potential warning behaviours of ideological radicalization in an Alt-Right Subreddit. Proc. of the 30 Int. AAAI Conf. on Web and Social Media (ICWSM 2019).
  * [8] Kaati, L, Shrestha, A and Cohen, K. (2016), ”Linguistic analysis of lone offender manifestos,” 2016 IEEE Int. Conf. on Cybercrime and Computer Forensic (ICCCF), pp. 1-8.
  * [9] Nakov,P., Barrón-Cedeño, A., Da San Martino, G.Alam, F., Míguez, R., Caselli, T., Kutlu, M, Zaghouani, W., Li, Ch, Shaar, S., Mubarak, H. Nikolov, A. and Kartal, Y.S (2022). Overview of the CLEF-2022 CheckThat! Lab Task 1 on identifying relevant claims in tweets. In Proc. of the CLEF 2022: Conference and Labs of the Evaluation Forum.
  * [10] Rangel F., De La Peña G., Chulvi B., Fersini E., Rosso P. Profiling Hate Speech Spreaders on Twitter Task at PAN 2021. In: Faggioli, G., Ferro, N., Joly, A., Maistro, M., Piroi, F. (eds.) CLEF 2021 Labs and Workshops, Notebook Papers, CEUR-WS.org, vol. 2936, pp. 1772-1789.
  * [11] Rangel F., De La Peña G., Chulvi B., Fersini E., Rosso P. Profiling Hate Speech Spreaders on Twitter Task at PAN 2021. In: Faggioli, G., Ferro, N., Joly, A., Maistro, M., Piroi, F. (eds.) CLEF 2021 Labs and Workshops, Notebook Papers. vol. 2936, pp. 1772-1789