To leverage amortization, the send phase of $\jsend$ alone is executed on the fly and verify is performed once for multiple instances of $\jsend$. Further, observe that $P_1,P_2$ possess the required shares in the online phase to compute the entire circuit.  Hence, $P_3$ can come in only during verify of $\jsend$ towards $P_1, P_2$, which can be deferred towards the end. Hence, the $\jsend$ to $P_3$ (as part of $\prot{\JSh}$ by $P_1, P_2$ during the online) can be performed once, towards the end, thereby requiring a single round for multiple instances of $\prot{\JSh}$. Following this, the verify of $\jsend$ towards $P_3$ is performed first, followed by  performing the verify of $\jsend$ towards $P_1, P_2$ in parallel.

As mentioned above, parties should obtain a $\sgr{\cdot}$-sharing of $(\gm{\vl{ab}}{} - \vl{r})$ from the preprocessing. The $\sgr{\cdot}$-shares for a random $\vl{r} \in \Z{\ell}$ can be generated non-interactively using the key setup $\Func[Setup]$ (<ref>). To compute $\sgr{\gm{\vl{ab}}{}}$, we rely on a 3-party multiplication protocol, say $\prot{\MultPre}$, abstracted in a functionality $\Func[\MultPre]$ (fig:FMultPre3pcM). The security of $\prot{\MultPre}$ depends on the security required in our framework. For instance, instantiating $\Func[\MultPre]$ with the protocols of <cit.> and <cit.> will result in abort or fairness guarantees whereas using the robust 3 party protocol of <cit.> will result in a multiplication protocol with robustness. In $\Tthis$, we use the protocol of <cit.>  in a black-box manner resulting in a communication of $3\ell$ bits (amortized) for $\prot{\MultPre}$. This leaves room for further improvements in the overall efficiency of our multiplication, which can be obtained by instantiating the black-box with efficient protocols.

$\Func[\MultPre]$Ideal functionality for $\prot{\MultPre}$ in $\Tthis$.fig:FMultPre3pcM
$\Func[\MultPre]$ interacts with the parties in $\Partyset$ and the adversary $\Sim$. $\Func[\MultPre]$ receives $\sgr{\cdot}$-shares of $\vl{d}, \vl{e}$ from the parties. Let $P^{\star}$ denotes the party corrupted by $\Sim$. $\Func[\MultPre]$ receives $(\vl{f}_i, \vl{f}_j)$ from $\Sim$ as its share for $\sgr{\vl{f}}$ where $\vl{f} = \vl{d} \vl{e}$. $\Func[\MultPre]$ proceeds as follows:

* Reconstructs $\vl{d}, \vl{e}$ using the shares received from honest parties and compute $\vl{f} = \vl{d} \vl{e}$.

* Computes the third share $\vl{f}_k = \vl{f} - \vl{f}_i -\vl{f}_j$ and sets $\sgr{\vl{f}}_1 = (\vl{f}_1, \vl{f}_3), \sgr{\vl{f}}_2 = (\vl{f}_2, \vl{f}_3),  \sgr{\vl{f}}_3 = (\vl{f}_1, \vl{f}_2)$.

* Send $(\OUTPUT, \sgr{\vl{f}}_s)$ to $P_s \in \Partyset$.

Protocol $\prot{\Mult}$ (fig:piMult3pcM) without truncation (in $\Tthis$) requires $3 \ell$ bits of communication in the preprocessing, and $1$ round and $3 \ell$ bits of communication in the online phase.

During preprocessing, sampling of the shares for $\sgr{\vl{r}}$ is performed non-interactively using $\Func[Setup]$. The $\prot{\MultPre}$ protocol, instantiated using the protocol of <cit.> requires a communication of $3\ell$ bits in the preprocessing.
During online, two instances of $\prot{\jsend}$ are executed in parallel resulting in a communication of $2\ell$ bits and 1 round. This is followed by a joint sharing by $P_1,P_2$ for which an additional communication of $\ell$ bits are required. However, in joint sharing, the communication is from $P_1$ to $P_3$ and the same can be deferred till the verification stage. Thus the online round is retained as $1$ in an amortized sense.

§.§.§ Truncation

To incorporate truncation, the multiplication protocol is modified such that $P_1, P_2$ execute joint sharing on the truncated value of $(\vl{z - r})$ in the online phase. To complete the protocol, the $\shr{\cdot}$-shares of the truncated $\vl{r}$, denoted by $\vl{r}^t$, is needed. For this, we use $\prot{\trgen}$ (fig:trgen3pcM) protocol in the preprocessing that generates a pair of the form $(\sgr{\vl{r}}, \shr{\vl{r}^{\vl{t}}})$. More details on $\prot{\trgen}$ are provided in <ref>. Parties locally compute $\shr{\vl{z}^{\vl{t}}} = \shr{(\vl{z-r})^{\vl{t}}} + \shr{\vl{r}^{\vl{t}}}$.

§.§.§ Multiplication with constant

Multiplication by a constant in MPC is typically local. Given constant $\alpha$ and $\shr{\vl{v}}$, the $\shr{\cdot}$-shares of the product $\vl{y} = \alpha\vl{v}$ can be locally computed as per (<ref>).

\begin{equation}\label{eq:mutconst3pcM}
\mk{\vl{y}} = \alpha \mk{\vl{u}},~~~\pad{\vl{y}}{1} = \alpha \pad{\vl{v}}{1},~~~\pad{\vl{y}}{2} = \alpha \pad{\vl{v}}{2},~~~\pad{\vl{y}}{3} = \alpha \pad{\vl{v}}{3}
\end{equation}

In FPA, parties should obtain truncated $\vl{y}$ as both $\alpha$ and $\vl{v}$ are decimal values. For this, parties invoke $\prot{\trgen}$ (fig:trgen3pcM) in the preprocessing to generate $(\sgr{\vl{r}}, \shr{\vl{r}^{\vl{t}}})$ for a random $\vl{r} \in \Z{\ell}$. The $\shr{\cdot}$-shares of $\vl{r}$ are locally computed from $\sgr{\vl{r}}$ locally similar to $\prot{\Mult}$ (fig:piMult3pcM). During online, parties locally compute $\shr{\vl{v-r}}$ and reconstructs $\vl{z} = \vl{v-r}$ using $\prot{\Rec}$ (fig:piRec3pcM). Parties locally compute  $\shr{\vl{z}^{\vl{t}}}$ by setting $\mk{{\vl{z}^{\vl{t}}}} = \vl{z}^{\vl{t}}$ and $\pad{{\vl{z}^{\vl{t}}}}{1} = \pad{{\vl{z}^{\vl{t}}}}{2} = \pad{{\vl{z}^{\vl{t}}}}{3} = 0$. Lastly, parties locally compute  $\shr{\vl{v}^{\vl{t}}} - \shr{\vl{z}^{\vl{t}}} + \shr{\vl{r}^{\vl{t}}}$.

§.§ Reconstruction

Protocol $\prot{\Rec}(\Partyset, \vl{v})$ (fig:piRec3pcM) enables parties to compute $\vl{v}$, given its $\shr{\cdot}$-share and achieves security with abort. Note that each party misses one share to reconstruct the output, and the other two parties hold this share. They will $\jsend$ (abort variant) the missing share to the party that lacks it. Reconstruction towards a single party can be viewed as a special case.

$\prot{\Rec}(\Partyset, \shr{\vl{v}})$Reconstruction (with abort security) of value $\vl{v}$ among $\Partyset$ in $\Tthis$.fig:piRec3pcM

Input(s): $\shr{\vl{v}}$,  Output: $\vl{v}$.

* $P_1, P_3$ $\jsend$ $\pad{\vl{v}}{1}$ to $P_2$;   $P_2, P_3$ $\jsend$ $\pad{\vl{v}}{2}$ to $P_1$; $P_1, P_2$ $\jsend$ $\pad{\vl{v}}{3}$ to $P_3$.

* Parties compute $\vl{v} = \mk{\vl{v}} - \pad{\vl{v}}{1} - \pad{\vl{v}}{2} - \pad{\vl{v}}{3}$.

Protocol $\prot{\Rec}$ (abort security, fig:piRec3pcM) requires an amortized communication of $3\ell$ bits and $1$ round.

The protocol involves three invocations of $\prot{\jsend}$ protocol and the cost follows from Lemma <ref>.

$\prot{\Rec}(\Partyset, \shr{\vl{v}})$Fair Reconstruction of value $\vl{v}$ among $\Partyset$ in $\Tthis$.fig:piRecfair3pcM

Input(s): $\shr{\vl{v}}$,  Output: $\vl{v}$.

* Parties locally compute the commitments on the $\pad{\vl{v}}{}$ shares as:

\begin{equation*}
P_1, P_3: \Commit{\pad{\vl{v}}{1}},~~P_2, P_3: \Commit{\pad{\vl{v}}{2}},~~P_1, P_2: \Commit{\pad{\vl{v}}{3}}
\end{equation*}

* $P_1, P_3$ $\jsend$ $\Commit{\pad{\vl{v}}{1}}$ to $P_2$;   $P_2, P_3$ $\jsend$ $\Commit{\pad{\vl{v}}{2}}$ to $P_1$; $P_1, P_2$ $\jsend$ $\Commit{\pad{\vl{v}}{3}}$ to $P_3$

Online: Parties set their aliveness bit $\bitb = \continue$, if the verification phase is successful. Else $\bitb = \abort$.

* Party $P_s \in \Partyset$ broadcasts $\bitb_s$ and parties accept the value that forms the majority.

* If the accepted value is $\abort$, parties abort. Else $P_1, P_3$ open $\Commit{\pad{\vl{v}}{1}}$ towards $P_2$; $P_2, P_3$ open $\Commit{\pad{\vl{v}}{2}}$ towards $P_1$; $P_1, P_2$ open $\Commit{\pad{\vl{v}}{3}}$ towards $P_3$. Parties use the correct opening to obtain their missing share.

* Parties compute $\vl{v} = \mk{\vl{v}} - \pad{\vl{v}}{1} - \pad{\vl{v}}{2} - \pad{\vl{v}}{3}$.

§.§.§ Achieving Fairness

Here, we show how to extend the security of $\Tthis$ from abort to fairness by modifying the reconstruction protocol. During preprocessing, each pair of parties together prepare a commitment on the $\pad{\vl{v}}{}$ share missing at the third party. The commitments are then communicated via $\jsend$ (abort variant), and the privacy is guaranteed by the hiding property of the underlying commitment scheme (cf. <ref>).

Before proceeding with the output reconstruction in the online phase, we need to ensure that all the honest parties are alive after the verification phase. For this, all the parties maintain an aliveness bit, say $\bitb$, which is initialized to $\continue$. If the verification phase is not successful for a party, it sets $\bitb = \abort$. In the first round of reconstruction, the parties broadcast their $\bitb$ bit and accept the value that forms the majority.  If $\bitb = \continue$, then a pair of parties open the commitment (communicated in the preprocessing) towards the third party. This method is fair because at least one honest party would have provided the correct opening to allow the third party to obtain its missing share. The formal protocol appears in fig:piRecfair3pcM.

§.§ Achieving Robustness

To elevate the security of $\Tthis$ to robustness, we use the robust variant of $\jsend$ in all the protocols. Moreover, for reconstruction, we use the fair reconstruction protocol in fig:piRecfair3pcM except that the aliveness check (Online, Step 1) is no longer required. This is because the verification in robust $\jsend$ guarantees identification of a $\TTP$ in case of any inconsistency, and the parties wouldn't have executed the reconstruction protocol.

§.§ Multi-input Multiplication

3-input multiplication

To compute $\shr{\cdot}$-shares of $\vl{z} = \vl{abc}$, note that

\begin{align}\label{eq:3pcMmultT}
\vl{z} - \vl{r} &= \vl{abc} - \vl{r} = (\mk{\vl{a}} - \pd{\vl{a}})(\mk{\vl{b}} - \pd{\vl{b}})(\mk{\vl{c}} - \pd{\vl{c}}) - \vl{r} \nonumber\\
&= \mk{\vl{abc}} - \mk{\vl{ac}}\pd{\vl{b}} - \mk{\vl{bc}}\pd{\vl{a}} - \mk{\vl{ab}}\pd{\vl{c}} + \mk{\vl{a}}\gm{\vl{bc}}{} + \mk{\vl{b}}\gm{\vl{ac}}{} + \mk{\vl{c}}\gm{\vl{ab}}{} - \gm{\vl{abc}}{} - \vl{r}
~~\text{\footnotesize{(cf. notation~\ref{notation:3pcMconcise})}}
\end{align}

Similar to $\prot{\Mult}$, for $\vl{y} = (\vl{z - r}) - \mk{\vl{abc}}$, let $\vl{y} = \vl{y}_1 + \vl{y}_2 + \vl{y}_3$.

\begin{align}\label{eq:3pcMmultTy}
P_1, P_3: \vl{y}_1 &= - \pad{\vl{a}}{1} \mk{\vl{bc}} - \pad{\vl{b}}{1} \mk{\vl{ac}} - \pad{\vl{c}}{1} \mk{\vl{ab}} + \gm{\vl{ab}}{1} \mk{\vl{c}} + \gm{\vl{ac}}{1} \mk{\vl{b}} + \gm{\vl{bc}}{1} \mk{\vl{a}} - {(\gm{\vl{abc}}{} + \vl{r})}^1 \nonumber\\
P_2, P_3: \vl{y}_2 &= - \pad{\vl{a}}{2} \mk{\vl{bc}} - \pad{\vl{b}}{2} \mk{\vl{ac}} - \pad{\vl{c}}{2} \mk{\vl{ab}} + \gm{\vl{ab}}{2} \mk{\vl{c}} + \gm{\vl{ac}}{2} \mk{\vl{b}} + \gm{\vl{bc}}{2} \mk{\vl{a}} - {(\gm{\vl{abc}}{} + \vl{r})}^2 \nonumber\\
P_1, P_2: \vl{y}_3 &= - \pad{\vl{a}}{3} \mk{\vl{bc}} - \pad{\vl{b}}{3} \mk{\vl{ac}} - \pad{\vl{c}}{3} \mk{\vl{ab}} + \gm{\vl{ab}}{3} \mk{\vl{c}} + \gm{\vl{ac}}{3} \mk{\vl{b}} + \gm{\vl{bc}}{3} \mk{\vl{a}} - {(\gm{\vl{abc}}{} + \vl{r})}^3
\end{align}

To generate $\sgr{\vl{x}}$ for $\vl{x} \in \{\gm{\vl{ab}}{}, \gm{\vl{ac}}{}, \gm{\vl{bc}}{}\}$, parties rely on $\prot{\MultPre}$ protocol. Parties then use another instance of $\prot{\MultPre}$ on the inputs $\gm{\vl{ab}}{}$ and $\pad{\vl{c}}{}$ to generate $\sgr{\gm{\vl{abc}}{}}$.
The generation of $\sgr{\gm{\vl{abc}}{} + \vl{r}}$ and the rest of the steps follow similar to that of 2-input multiplication protocol $\prot{\Mult}$ in <ref>. The formal protocol appears in fig:piMultT3pcM.

$\prot{\Mult}(\vl{a}, \vl{b}, \isTr)$Three-input Multiplication with / without truncation in $\Tthis$.fig:piMultT3pcM
$\isTr$ is a bit denoting whether truncation is required ($\isTr =1$) or not ($\isTr=0$).

Input(s): $\shr{\vl{a}}, \shr{\vl{b}}, \shr{\vl{c}}$.

Output: $\shr{\vl{o}}$ where $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{o} = \vl{z}$ if $\isTr = 0$ and $\vl{z} = \vl{abc}$.

* Invoke $\Func[\MultPre]$ on the $\sgr{\cdot}$-shares of $(\pad{\vl{a}}{}, \pad{\vl{b}}{})$, $(\pad{\vl{a}}{}, \pad{\vl{c}}{})$, and $(\pad{\vl{b}}{}, \pad{\vl{c}}{})$ to obtain $\sgr{\gm{\vl{ab}}{}}, \sgr{\gm{\vl{ac}}{}}, \sgr{\gm{\vl{bc}}{}}$ respectively.

* Invoke $\Func[\MultPre]$ on the $\sgr{\cdot}$-shares of $\gm{\vl{ab}}{}$ and $\pad{\vl{c}}{}$ to obtain  $\sgr{\gm{\vl{abc}}{}}$.

* If $\isTr = 0$:

* Local computation of $\sgr{\vl{r}}$: $\Partyset \setminus \{P_2\} \leftarrow_R {\vl{r}}^1$;   $\Partyset \setminus \{P_1\} \leftarrow_R {\vl{r}}^2$;   $\Partyset \setminus \{P_3\} \leftarrow_R {\vl{r}}^3$.

* Local computation of $\shr{\vl{r}}$: $\pad{\vl{r}}{1} = - {\vl{r}}^1$,  $\pad{\vl{r}}{2} = - {\vl{r}}^2$,  $\pad{\vl{r}}{3} = - {\vl{r}}^3$,  $\mk{\vl{r}} = 0$. Set $\shr{\vl{q}} = \shr{\vl{r}}$.

* If $\isTr = 1$, invoke $\prot{\trgen}$ (fig:trgen3pcM) to generate $(\sgr{\vl{r}}, \shr{\vl{r}^{\vl{t}}})$. Set $\shr{\vl{q}} =  \shr{\vl{r}^{\vl{t}}}$.

* Locally compute $\sgr{(\gm{\vl{abc}}{} + \vl{r})} = \sgr{\gm{\vl{abc}}{}} + \sgr{\vl{r}}$.

Online: Let $\vl{y} = (\vl{z} - \vl{r}) - \mk{\vl{abc}}$.

* Parties locally compute the following:

\begin{align*}
P_1, P_3: \vl{y}_1 &= - \pad{\vl{a}}{1} \mk{\vl{bc}} - \pad{\vl{b}}{1} \mk{\vl{ac}} - \pad{\vl{c}}{1} \mk{\vl{ab}} + \gm{\vl{ab}}{1} \mk{\vl{c}} + \gm{\vl{ac}}{1} \mk{\vl{b}} + \gm{\vl{bc}}{1} \mk{\vl{a}} - {(\gm{\vl{abc}}{} + \vl{r})}^1 \nonumber\\
P_2, P_3: \vl{y}_2 &= - \pad{\vl{a}}{2} \mk{\vl{bc}} - \pad{\vl{b}}{2} \mk{\vl{ac}} - \pad{\vl{c}}{2} \mk{\vl{ab}} + \gm{\vl{ab}}{2} \mk{\vl{c}} + \gm{\vl{ac}}{2} \mk{\vl{b}} + \gm{\vl{bc}}{2} \mk{\vl{a}} - {(\gm{\vl{abc}}{} + \vl{r})}^2 \nonumber\\
P_1, P_2: \vl{y}_3 &= - \pad{\vl{a}}{3} \mk{\vl{bc}} - \pad{\vl{b}}{3} \mk{\vl{ac}} - \pad{\vl{c}}{3} \mk{\vl{ab}} + \gm{\vl{ab}}{3} \mk{\vl{c}} + \gm{\vl{ac}}{3} \mk{\vl{b}} + \gm{\vl{bc}}{3} \mk{\vl{a}} - {(\gm{\vl{abc}}{} + \vl{r})}^3
\end{align*}

* $P_1, P_3$ $\jsend$ $\vl{y}_1$ to $P_2$, while $P_2, P_3$ $\jsend$ $\vl{y}_2$ to $P_1$. They locally compute $\vl{z} - \vl{r} = (\vl{y}_1 + \vl{y}_2 + \vl{y}_3) + \mk{\vl{abc}}$.

* $P_1, P_2$: If $\isTr = 1$, set $\vl{p} = (\vl{z} - \vl{r})^{\vl{t}}$, else $\vl{p} = \vl{z} - \vl{r}$. Execute $\prot{\JSh}(P_1, P_2, \vl{p})$ to generate $\shr{\vl{p}}$.

* Compute $\shr{\vl{o}} = \shr{\vl{p}} + \shr{\vl{q}}$. Here $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{z}$ otherwise.

Protocol $\prot{\MultT}$ (fig:piMultT3pcM) (in $\Tthis$) requires $12\ell$ bits of communication in the preprocessing, and $1$ round and $3 \ell$ bits of communication in the online phase.

During preprocessing, sampling of the shares for $\sgr{\vl{r}}$ is performed non-interactively using $\Func[Setup]$. Also, four instances of $\prot{\MultPre}$ protocol are executed in the preprocessing. Instantiating $\prot{\MultPre}$ using <cit.> requires a communication of $3\ell$ bits for each of the instances.

The online phase is similar to that of $\prot{\Mult}$ and the costs follow from Lemma <ref>.

4-input multiplication

For the case of 4-input multiplication with $\vl{z} = \vl{abcd}$, note that

\begin{align}\label{eq:3pcMmultF}
\vl{z} - \vl{r} &= \vl{abcd} - \vl{r} = (\mk{\vl{a}} - \pd{\vl{a}})(\mk{\vl{b}} - \pd{\vl{b}})(\mk{\vl{c}} - \pd{\vl{c}})(\mk{\vl{d}} - \pd{\vl{d}}) - \vl{r} \nonumber\\
&= \mk{\vl{abcd}} - \mk{\vl{abc}}\pd{\vl{d}} - \mk{\vl{abd}}\pd{\vl{c}} - \mk{\vl{acd}}\pd{\vl{b}} - \mk{\vl{bcd}}\pd{\vl{a}}
+ \mk{\vl{ab}}\gm{\vl{cd}}{} + \mk{\vl{ac}}\gm{\vl{bd}}{} + \mk{\vl{ad}}\gm{\vl{bc}}{} + \mk{\vl{bc}}\gm{\vl{ad}}{} \nonumber\\
&~~~+ \mk{\vl{bd}}\gm{\vl{ac}}{} + \mk{\vl{cd}}\gm{\vl{ab}}{}
- \mk{\vl{a}}\gm{\vl{bcd}}{} - \mk{\vl{b}}\gm{\vl{acd}}{} - \mk{\vl{c}}\gm{\vl{abd}}{} - \mk{\vl{d}}\gm{\vl{abc}}{} + \gm{\vl{abcd}}{} - \vl{r}
~~\text{\footnotesize{(cf. notation~\ref{notation:3pcMconcise})}}
\end{align}

Here the parties first generate $\sgr{\cdot}$-shares of $\gm{\vl{ab}}{},\gm{\vl{ac}}{},\gm{\vl{ad}}{},\gm{\vl{bc}}{},\gm{\vl{bd}}{}$, and $\gm{\vl{cd}}{}$ using $\prot{\MultPre}$ on the respective inputs. In the next round, parties make use of these shares and $\prot{\MultPre}$ to generate $\gm{\vl{abc}}{},\gm{\vl{abd}}{},\gm{\vl{acd}}{},\gm{\vl{bcd}}{}$ and $\gm{\vl{abcd}}{}$. Thus, the preprocessing involves a total of eleven instances of $\prot{\MultPre}$ protocol.

Protocol $\prot{\MultF}$ (in $\Tthis$) requires $33\ell$ bits of communication in the preprocessing, and $1$ round and $3 \ell$ bits of communication in the online phase.

During preprocessing, 11 instances of $\prot{\MultPre}$ protocol are executed. This results in communication of $33\ell$ bits when the $\prot{\MultPre}$ protocol is instantiated with <cit.>.

The online phase is similar to that of $\prot{\Mult}$, and the costs follow from Lemma <ref>.

§ GARBLED WORLD

Similar to $\TSthis$, we have two variants – $\TthisT$ requiring communication of 2 GCs and one online round, and $\TthisC$ requiring 1 GC and two rounds.

The 2 GC variant has two parallel executions, each comprising of 2 garblers and 1 evaluator. $P_1, P_2$ act as evaluators in two independent executions and the parties in $\PlSet{1} = \{P_2, P_3\}$, $\PlSet{2} = \{P_1, P_3\}$ act as garblers, respectively. The 1 GC variant comprises of a single execution with $\PlSet{1}$ acting as garblers and $P_1$ as the evaluator.

§.§ 2 GC Variant

Input Phase

Here, the boolean values $(\mk{\vl{x}}, \pad{\vl{x}}{1}, \pad{\vl{x}}{2}, \pad{\vl{x}}{3})$ act as the new inputs for the garbled computation.  The semantics of $\shrB{\cdot}$-sharing ensures that each of these shares is available with at least two parties (including evalator) in each garbling instance. Thus, the goal of our input phase is to create the compound sharing, $\shrC{\vl{x}} = (\shrG{\mk{\vl{x}}}, \shrG{\pad{\vl{x}}{1}}, \shrG{\pad{\vl{x}}{2}}, \shrG{\pad{\vl{x}}{2}})$ for every input $\vl{x}$ to the function to be evaluated via the GC.

Consider the garbling instance with $P_1$ as the evaluator. The number of input keys for this instance can be further reduced by treating $(\mk{\vl{x}} \xor \pad{\vl{x}}{2})$ as a single input. For the case of arithmetic values, the input changes to $(\mk{\vl{x}} - \pad{\vl{x}}{2})$. Similarly, the other instance with $P_2$ as evaluator uses $(\mk{\vl{x}} \xor \pad{\vl{x}}{1})$ as input.

We first discuss the semantics for $\shrG{\cdot}$-sharing followed by steps for generating $\shrC{\cdot}$-sharing.

Garbled sharing semantics

A value $\vl{v} \in \Z{}$  is $\shrG{\cdot}$-shared (garbled shared) amongst  $\Partyset$ if $P_3$ holds $\shrG{\vl{v}}_{i}= (\key{{\vl{v}}}{0,1}, \key{{\vl{v}}}{0,2})$, $P_1$ holds $\shrG{\vl{v}}_{1} = (\key{{\vl{v}}}{\vl{v},1}, \key{{\vl{v}}}{0,2})$ and $P_2$ holds $\shrG{\vl{v}}_{2} = (\key{{\vl{v}}}{0,1}, \key{{\vl{v}}}{\vl{v},2})$. Here, $\key{{\vl{v}}}{\vl{v}, j} = \key{{\vl{v}}}{0, j} \xor \vl{v} \Delta^{j}$ for $j \in \{1, 2\}$, and $\Delta^{j}$, which is known only to the garblers in $\PlSet{j}$, denotes the global offset with its least significant bit set to $1$ and is same for every wire in the circuit.

A value $\vl{x} \in \Z{}$ is said to be $\shrC{\cdot}$-shared (compound shared) if each value from $(\mk{\vl{x}}, \pad{\vl{x}}{1}, \pad{\vl{x}}{2}, \pad{\vl{x}}{3})$ is $\shrG{\cdot}$-shared. We write $\shrC{\vl{x}} = (\shrG{\mk{\vl{x}}}, \shrG{\pad{\vl{x}}{1}}, \shrG{\pad{\vl{x}}{2}}, \shrG{\pad{\vl{x}}{2}})$.

Generation of $\shrG{\vl{v}}$ and $\shrC{\vl{x}}$

Protocol $\pigsh(\Partyset, \vl{v})$ (fig:pigsh3pcM) enables generation of $\shrG{\vl{v}}$ where two garblers in each garbling instance hold $\vl{v}$, and proceeds as follows. Consider the first garbling instance with evaluator $P_1$ and garblers $P_s, P_t$. Garblers in $\PlSet{1}$ generate $\{\key{{{\vl{v}}}}{\bitb, 1}\}_{\bitb \in \{0, 1\}}$ which denotes the key for value $\bitb$ on wire $\vl{v}$, following the free-XOR technique <cit.>. If the value $\vl{v}$ is known to both $P_s, P_t$, they $\jsend$ the respective key to $P_1$. Else, w.l.o.g. let $P_s \in \PlSet{j}$ be the garbler that knows $\vl{v}$. To ensure the correct key delivery towards $P_1$, we make garblers $P_s, P_t$ commit to both the keys to $P_1$ via $\jsend$. $P_s$ then sends the opening for commitment of $\key{\vl{v}}{\vl{v}, j}$ to $P_1$. If the decommitment fails, $P_1$ abort for the case of secuirty with abort or fairness. For robustness it accuses $P_s$ and $P_t$ is chosen as the $\TTP$.

Similar steps carried out with respect to the second garbling instance, at the end of which, garblers in $\PlSet{2}$ possess $\{\key{\vl{v}}{\bitb, 2}\}_{\bitb \in \{0,1\}}$ while the evaluator $P_2$ holds $\key{\vl{v}}{\vl{v}, 2}$. Following this, the shares $\shrG{\vl{v}}_s$ held by $P_s \in \Partyset$ are defined as $\shrG{\vl{v}}_0 = (\key{\vl{v}}{0, 1}, \key{\vl{v}}{0, 2})$, $\shrG{\vl{v}}_1 = (\key{\vl{v}}{\vl{v}, 1}, \key{\vl{v}}{0, 2})$, $\shrG{\vl{v}}_2 = (\key{\vl{v}}{0, 1}, \key{\vl{v}}{\vl{v}, 2})$.

To generate $\shrC{\vl{x}}$, $\pigsh$ is invoked for each of $\mk{\vl{x}}, \pad{\vl{x}}{1}, \pad{\vl{x}}{2}$, and $\pad{\vl{x}}{3}$ .

$\pigsh(\Partyset, \vl{v})$Generation of $\shrG{\vl{v}}$ in $\Tthis$.fig:pigsh3pcM

Input(s): $\vl{v}$,  Output: $\shrG{\vl{v}}$.

Let $P_s \in \PlSet{j}$ be the garbler that knows $\vl{v}$ in clear where $j \in \{1, 2\}$ and $P_t$ be the co-garbler in $\PlSet{j}$.

* Garblers in $\PlSet{j}$ generate keys $\key{{\vl{v}}}{0, j}, \key{{\vl{v}}}{1, j}$ for wire $\vl{v}$, using free-XOR technique.

* If both $P_s$ and $P_t$ know $\vl{v}$ in clear, $P_s, P_t$ $\jsend$ $\key{\vl{v}}{\vl{v}, j}$ to evaluator $P_j$.

* Else, parties proceed as follows:

* $P_s, P_t$ prepare commitment on both the keys as $\Commit{\key{{\vl{v}}}{0, j}}, \Commit{\key{{\vl{v}}}{1, j}}$ and communicates to evaluator $P_j$ in a random permuted order using $\jsend$.

* $P_s$ sends the opening for commitment of $\key{\vl{v}}{\vl{v}, j}$ to $P_j$.

* If the decommitment using the opening fails, $P_j$ $\abort$ for the case of security with abort or fairness. For robustness, $P_j$ broadcasts "" and $P_t$ is chosen as the $\TTP$.

* $P_0$ sets $\shrG{\vl{v}}_0 = (\key{{\vl{v}}}{0,1}, \key{{\vl{v}}}{0,2})$, $P_1$ sets $\shrG{\vl{v}}_{1} = (\key{{\vl{v}}}{\vl{v},1}, \key{{\vl{v}}}{0,2})$ and $P_2$ sets $\shrG{\vl{v}}_{2} = (\key{{\vl{v}}}{0,1}, \key{{\vl{v}}}{\vl{v},2})$.

Let $f(\vl{x})$ be the function to be evaluated. At this point, the function input is $\shrC{\cdot}$-shared. This renders $\shrG{\cdot}$-sharing for the input of the GC that corresponds to the function $f'\big(\mk{\vl{x}}, \pad{\vl{x}}{1}, \pad{\vl{x}}{2}, \pad{\vl{x}}{3} \big)$ which first combines the given boolean-shares to compute the actual input and then applies $f$ on it. Let $\GC_j$ denote the garbled circuit to be sent to $P_j \in \{P_1, P_2\}$ by garblers in $\PlSet{j}$. Sending of $\GC_j$ is overlapped  with the key transfer (during generation of $\shrC{\vl{x}}$), to save rounds, where garblers $\jsend$ $\GC_j$ to $P_j$. On receiving the $\GC$, evaluators evaluate their respective GCs and obtain the key corresponding to the output, say $\vl{z}$. This generates $\shrG{\vl{z}}$.

Output phase

The goal of output computation is to compute the output $\vl{z}$ from $\shrG{\vl{z}}$.
To reconstruct $\vl{z}$ towards $P_j \in \{P_1, P_2\}$, garblers in $\PlSet{j}$ $\jsend$ the least significant bit $\vl{p}^j$ of $\key{\vl{z}}{0, j}$, referred to as the decoding information, to $P_j$. $P_j$ uses the received $\vl{p}^j$ to reconstruct $\vl{z}$ as $\vl{z} = \vl{p}^j \xor \vl{q}^j$, where $\vl{q}^j$ denotes the least significant bit of $\key{\vl{z}}{\vl{z}, j}$. $P_1, P_2$ then $\jsend$ $\vl{z}$ to $P_3$ completing the protocol. Reconstruction is lightweight and requires a single round towards $P_3$ while reconstruction towards $P_1, P_2$ can be overlapped with key transfer and does not incur extra rounds. The protocol appears in fig:pirec3pcM.

$\pigrec(\Partyset, \shrG{\vl{z}})$Output computation: reconstruction of $\vl{z}$ in $\Tthis$.fig:pirec3pcM

Input(s): $\shrG{\vl{z}}$,  Output: $\vl{z}$.

* For an output wire $\vl{z}$, let $\vl{p}^j$ denote the least significant bit of $\key{{\vl{z}}}{0,j}$ and $\vl{q}^j$ denote the least significant bit of $\key{{\vl{z}}}{\vl{z},j}$ for $j \in \{1, 2\}$.

* Reconstruction towards $P_j$: Parties in $\PlSet{j}$ $\jsend$ $\vl{p}^j$ to $P_j$ who reconstructs $\vl{z} = \vl{p}^j \xor \vl{q}^j$.

* Reconstruction towards $P_3$: $P_1, P_2$ $\jsend$ $\vl{z}$ to $P_3$.

Optimizations when deployed in mixed framework

Working in the preprocessing model enables transfer of the (communication-intensive) GC and generating $\shrG{\cdot}$-shares of the input-independent shares of $\vl{x}$ (i.e. $\pad{\vl{x}}{}$) in the preprocessing. Thus, the online phase is very light and only requires one round to generate $\shrG{\cdot}$-shares  for the input-dependent data (i.e. ${\mk{\vl{x}}}$). Since evaluation is local, evaluators obtain $\shrG{\cdot}$-sharing of the GC output at the end of $1$ round. Moreover, we require the garbled output to be reconstructed towards both $P_1$ and $P_2$ in clear. Thus, the steps for reconstruction towards $P_3$ can be avoided in $\pigrec$ protocol (fig:pirec3pcM).

§.§ 1 GC Variant

The garbling scheme here is similar to the 2GC variant except that now there exists only a single garbling instance. Parties in $\PlSet{1} = \{P_2, P_3\}$ act as the garblers while $P_1$ act as the evaluator. Looking ahead, in the mixed protocol framework, the output has to be reconstructed towards $P_1, P_2$. Reconstruction towards $P_1$ does not incur additional rounds since sending of decoding information can be overlapped with the key transfer. To reconstruct towards $P_2$, $P_1$ sends the least significant bit of $\key{{\vl{z}}}{\vl{z},1}$, denoted by $\vl{q}^1$, along with a hash of $\key{{\vl{z}}}{\vl{z},j}$ to $P_2$. Party $P_2$ accepts $\vl{q}^1$ if the hash is consistent with the respective key. This is fine since a corrupt $P_1$ cannot send an incorrect key due to the authenticity of the garbling scheme <cit.>. On the other hand, if the hash is inconsistent, $P_2$ aborts for the case of security with abort or fairness. For robustness it accuses $P_1$ and $P_3$ is chosen as the $\TTP$.

§ SECURITY PROOFS

Without loss of generality, we prove the security of our robust framework. The case for fairness follows similarly, and we omit its details. We provide proofs in the $\{\FSETUP, \Func[\MultPre], \Func[\jsend]\}$-hybrid model, where $\FSETUP$ (<ref>), $\Func[\MultPre]$ (fig:FMultPre3pcM) and $\Func[\jsend]$ (fig:JsendFunc) denote the ideal functionality for the shared-key setup, preprocessing of multiplication ($\prot{\MultPre}$) and $\jsend$, respectively.

The strategy for simulating the computation of function $f$ (represented by a circuit $\Ckt$) is as follows. The simulation begins with the simulator emulating the shared-key setup ($\FSETUP$) functionality and giving the respective keys to the adversary. This is followed by the input sharing phase in which $\Sim$ computes the input of $\Adv$, using the known keys, and sets the honest parties' inputs to be used in the simulation to $0$. $\Sim$ invokes the ideal functionality $\Func[GOD]$ on behalf of $\Adv$ using the extracted input and obtains the output $\vl{y}$. $\Sim$ now knows the inputs of $\Adv$ and can compute all the intermediate values for each building block. $\Sim$ proceeds with simulating each of the building blocks in the topological order. We provide the simulation for the case for corrupt $P_1$ and $P_3$. The case for corrupt $P_2$ is similar to that of $P_1$.

For modularity, we provide the simulation steps for each building block separately. Carrying out these blocks in the topological order yields the simulation for the entire computation. If a $\TTP$ is identified during the simulation, the simulator stops and returns the function output to the adversary on behalf of the $\TTP$ as per $\Func[\jsend]$.

Ideal $\jsend$ Functionality

The ideal $\jsend$ functionality for fairness security appears in fig:JsendFFunc3pcM and that for the robust setting appears in fig:Funcjsend3pcM.

$\Func[\jsend]$ (for fair security)Ideal functionality for $\jsend$ in $\Tthis$fig:JsendFFunc3pcM
$\Func[\jsend]$ interacts with the parties in $\Partyset$ and the adversary $\Sim$.

Step 1: $\Func[\jsend]$ receives $(\INPUT,\vl{v}_s)$ from senders $P_s$ for $s \in \{i,j\}$, $(\INPUT,\bot)$ from receiver $P_k$. While sending the inputs, the adversary is also allowed to send a special $\abort$ command.

Step 2: Set $\msg_i = \msg_j = \msg_l = \bot$.

Step 3: If $\vl{v}_i = \vl{v}_j$, set $\msg_k = \vl{v}_i$. Else, set $\msg_k = \abort$.

Step 4: Send $(\OUTPUT, \msg_s)$ to $P_s$ for $s \in \{1,2, 3\}$.

Sharing Protocol ($\prot{\Sh}$, fig:piSh3pcM)

During the preprocessing, $\Sim_{\prot{\Sh}}^{P_1}$ emulates $\FSETUP$ and gives the respective keys to $\Adv$. The values commonly held with $\Adv$ are sampled using the respective keys, while others are sampled randomly. The details for the online phase are provided next. We omit the simulation for corrupt $P_3$ as it is similar to that of $P_1$.

$\Sim_{\prot{\Sh}}^{P_1}$Simulator $\Sim_{\prot{\Sh}}^{P_1}$ for corrupt $P_1$ fig:ShFSim13pcM

– If dealer is $\Adv$, $\Sim_{\prot{\Sh}}^{P_1}$ receives $\mk{\vl{v}}$ from $\Adv$ on behalf of $P_2$. $\Sim_{\prot{\Sh}}^{P_1}$ computes $\Adv$'s input $\vl{v}$ as $\vl{v} = \mk{\vl{v}} - \sqr{\pd{\vl{v}}}_1 - \sqr{\pd{\vl{v}}}_2 - \sqr{\pd{\vl{v}}}_3$. It invokes $\Func[GOD]$ on input $(\INPUT, \vl{v})$ to obtain the function output $\vl{y}$.

– If dealer is $P_2$ or $P_3$, $\Sim_{\prot{\Sh}}^{P_1}$ sets $\vl{v} = 0$ and performs the protocol steps honestly.

Shares unknown to $\Adv$ are sampled randomly in the simulation, whereas in the real protocol, they are sampled using the pseudorandom function (PRF). The indistinguishability of the simulation thus follows by a reduction to the security of the PRF. The same holds for the rest of the blocks.

The simulation for the joint sharing protocol ($\prot{\JSh}$) is similar to that of the sharing protocol. The protocol's design is such that the simulator will always know the value to be sent as part of the joint sharing protocol. The communication is constituted by $\jsend$ calls and is emulated according to the simulation of $\Func[\jsend]$.

Multiplication Protocol ($\prot{\Mult}$ fig:piMult3pcM)

$\Sim_{\prot{\Mult}}^{P_1}$Simulator $\Sim_{\prot{\Mult}}^{P_1}$ for corrupt $P_1$ fig:MulFSim13pcM

–  $\Sim_{\prot{\Mult}}^{P_1}$ emulates $\Func[\MultPre]$ for a corrupt $P_1$ and obtains $\gm{\vl{a}\vl{b}}{1}, \gm{\vl{a}\vl{b}}{2}$, and $\gm{\vl{a}\vl{b}}{3}$.

– Computes $\vl{y}_1, \vl{y}_2, \vl{y}_3$ honestly.

– Emulates two instances of $\Func[\jsend]$ – i) $\Adv$ as sender to send $\vl{y}_1$ to $P_2$, and ii) $\Adv$ as receiver to obtain $\vl{y}_2$ from $P_2$.

– Simulates joint sharing for a corrupt sender as discussed earlier.

$\Sim_{\prot{\Mult}}^{P_3}$Simulator $\Sim_{\prot{\Mult}}^{P_3}$ for corrupt $P_3$ fig:MulFSim33pcM

–  $\Sim_{\prot{\Mult}}^{P_3}$ emulates $\Func[\MultPre]$ for a corrupt $P_3$ and obtains $\gm{\vl{a}\vl{b}}{1}, \gm{\vl{a}\vl{b}}{2}$, and $\gm{\vl{a}\vl{b}}{3}$.

– Computes $\vl{y}_1, \vl{y}_2, \vl{y}_3$ honestly.

– Emulates two instances of $\Func[\jsend]$ with $\Adv$ as sender to send $\vl{y}_1$ to $P_2$ and $\vl{y}_2$ to $P_1$.

– Simulates joint sharing for a corrupt receiver as discussed earlier.

Reconstruction Protocol ($\prot{\Rec}$, fig:piRec3pcM)

Using the input of $\Adv$ obtained during simulation of sharing protocol, $\Sim_{\prot{\Rec}}$ invokes $\Func[GOD]$ on behalf of $\Adv$ and obtains the function output $\vl{y}$ in clear. $\Sim_{\prot{\Rec}}$ calculates the missing share of $\Adv$ using $\vl{y}$ and the other shares. The missing share is then communicated to $\Adv$ by emulating the $\Func[\jsend]$ functionality.

CHAPTER: $\FTHIS$: 4PC FAIR AND ROBUST PROTOCOLS

This chapter provides details for the Layer I blocks of our 4PC framework $\Fthis$.

Some of the results in this chapter resulted in publications at NDSS'20 <cit.> and NDSS'22 <cit.>.

Depending on the sensitivity of the application and the underlying data, we may want different levels of security. For this, we propose multiple variants of the framework, covering fairness ($\Fthis$) and robustness ($\FthisA$, $\FthisB$) guarantees. Comparison of $\Fthis$ with actively secure 4PC PPML frameworks, in terms of the communication for multiplication, is presented in 4pcCost.

§ PRELIMINARIES AND DEFINITIONS

We consider $4$ parties denoted by $\Partyset = \{ P_0, P_1, P_2, P_3 \}$ that are connected by pair-wise private and authentic channels in a synchronous network, and a static, active adversary that can corrupt at most 1 party.

§.§ Sharing Semantics

For the arithmetic and boolean sharing, we follow  a $(4, 1)$ replicated secret sharing (RSS) <cit.>, where a value $\vl{v} \in \Z{\ell}$ is split into four shares. To leverage the benefits of the preprocessing paradigm, we associate meaning to the shares and demarcate the parties in terms of their roles.  Three of the shares of a $(4, 1)$ RSS can be generated in the preprocessing phase independent of the value to be shared, and their sum can be interpreted as a mask. The fourth share, dependent on $\vl{v}$,  can be computed in the online phase and can be treated as the masked value. We denote the three preprocessed shares as $\pad{\vl{v}}{1}, \pad{\vl{v}}{2}, \pad{\vl{v}}{3}$ and the mask as $\pad{\vl{v}}{} =  \pad{\vl{v}}{1} + \pad{\vl{v}}{2} + \pad{\vl{v}}{3}$. The masked value is denoted as $\mk{\vl{v}}$, and $\mk{\vl{v}}= \vl{v} +\pad{\vl{v}}{}$.

r r r r r[notes/para]
Type      $P_0$     $P_1$     $P_2$     $P_3$

$-$          ${\vl{v}}^1$         ${\vl{v}}^2$        $-$

${\vl{v}}^2$        ${\vl{v}}^3$

$\sgr{\cdot}$-sharing$\vl{v} = \vl{v}^1 + \vl{v}^2 + \vl{v}^3$
$-$         $({\vl{v}}^1, {\vl{v}}^3)$
$({\vl{v}}^2, {\vl{v}}^3)$         $({\vl{v}}^1, {\vl{v}}^2)$

$\shr{\cdot}$-sharing$\pad{\vl{v}}{} = \pad{\vl{v}}{1} + \pad{\vl{v}}{2}  + \pad{\vl{v}}{3}$, $\mk{\vl{v}} = \vl{v} + \pad{\vl{v}}{}$
$(\pad{\vl{v}}{1}, \pad{\vl{v}}{2}, \pad{\vl{v}}{3})$
$(\mk{\vl{v}}, \pad{\vl{v}}{1}, \pad{\vl{v}}{3})$
$(\mk{\vl{v}}, \pad{\vl{v}}{2}, \pad{\vl{v}}{3})$
$(\mk{\vl{v}}, \pad{\vl{v}}{1}, \pad{\vl{v}}{2})$

Sharing semantics for a value $\vl{v} \in \Z{\ell}$ in .

Next, we distinguish the four parties into two sets; the eval set $\SetE = \{P_1,P_2\}$ which is assigned the task of carrying out the computation, and is active throughout the online phase. The helper set $\SetD = \{P_0, P_3\}$, is used to assist $\SetE$ in verification, and so it is only active towards the end of the computation. Complying with the roles and RSS format, the distribution is done as follows: $P_0: \{\pad{\vl{v}}{1}, \pad{\vl{v}}{2},  \pad{\vl{v}}{3}\}, P_1: \{\pad{\vl{v}}{1},  \pad{\vl{v}}{3},  \mk{\vl{v}}\}, P_2: \{\pad{\vl{v}}{2},  \pad{\vl{v}}{3},  \mk{\vl{v}}\}$, and $P_3: \{\pad{\vl{v}}{1}, \pad{\vl{v}}{2}, \mk{\vl{v}}\}$.

The shares are distributed among $\SetD$ such that $P_3$ gets $\mk{\vl{v}}$ whereas $P_0$ gets all the shares of $\pad{\vl{v}}{}$. In the preprocessing phase, $P_0$ computes a part of the data needed for verification (cf. fig:piMultiplication) using its input independent shares, which is communicated to $P_3$. This enables a verification in the online, without $P_0$, for the fair protocols.

The RSS sharing semantics is presented in 4pcsharing, denoted by $\shr{\cdot}$, in a modular way with the help of three intermediate sharing semantics $\sqr{\cdot}, \spr{\cdot}$ and $\sgr{\cdot}$. All the sharings used are linear i.e. given sharings of values $\vl{v}_1,\ldots, \vl{v}_m$ and public constants $c_1,\ldots,c_m$, sharing of $\sum_{i=1}^m c_i \vl{v}_i$ can be computed non-interactively for an integer $m$.

(a) For the $\shr{\cdot}$-shares of $n$ values $\vl{a}_1,\ldots,\vl{a}_n$, $\gm{\vl{a}_1 \ldots \vl{a}_n}{} = \prod\limits_{i=1}^{n} \pad{\vl{a}_i}{}$ and $\mk{\vl{a}_1 \ldots \vl{a}_n}{} = \prod\limits_{i=1}^{n} \mk{\vl{a}_i}{}$ (b) We use superscripts ${\bf B}$, and ${\bf G}$ to denote sharing semantics in boolean, and garbled world, respectively– $\shrB{\cdot}$,  $\shrG{\cdot}$. We omit the superscript for arithmetic world.

Sharing semantics for boolean sharing over $\Z{}$ is similar to arithmetic sharing except that addition is replaced with XOR. The semantics for garbled sharing are described in <ref> with the relevant context.

§.§.§ $\FZero$ - Generating additive shares of zero

In $\Fthis$, we make use of a functionality $\FZero$ to enable parties $P_0, P_i$ obtain $Z_i$ for $i \in \{1,2,3\}$ such that $Z_1 + Z_2 + Z_3 = 0$. We observe that the functionality can be instantiated non-interactively using the pre-shared keys (cf. <ref>). For this, parties in $\Partyset \setminus \{P_j\}$ sample random value $\vl{r}_j$ for $j \in \{1,2,3\}$. The shares are then defined as $Z_1 = \vl{r}_3 - \vl{r}_2, Z_2 = \vl{r}_1 - \vl{r}_3$ and $Z_3 = \vl{r}_2 - \vl{r}_1$.

§.§ Joint-Send ($\jsend$) Primitive

The Joint-Send ($\jsend$) primitive, for the case of security with fairness, allows to parties $P_i, P_j$ to relay a message $\vl{v}$ to a third party $P_k$ ensuring either the delivery of the message or $\abort$ in case of inconsistency. Towards this, $P_i$ sends $\vl{v}$ to $P_k$, while $P_j$ sends a hash of the same ($\Hash(\vl{v})$) to $P_k$. Party $P_k$ accepts the message if the hash values are consistent and $\abort$ otherwise. Note that the communication of the hash can be clubbed together for several instances and be deferred to the end of the protocol, amortizing the cost.

Joint-Send ($\jsend$) for robust protocols

The $\jsend$ primitive (fig:4pcjsendrobust), for the case of robustness, allows two senders $P_i, P_j$ to relay a common message, $\vl{v} \in \Z{\ell}$, to recipient $P_k$, either by ensuring successful delivery of $\vl{v}$, or by establishing a Trusted Third Party ($\TTP$) among the parties. The instantiation of $\jsend$ can be viewed as consisting of two phases (send, verify), where the send phase consists of $P_i$ sending $\vl{v}$ to $P_k$ and the rest of the protocol steps go to verify phase (which ensures correct send or $\TTP$ identification). This requires $1$ round of interaction and $\ell$ bits of communication. To leverage amortization, verify will be executed only once, at the end the computation, requiring $2$ rounds.

Note that the appropriate instantiation of $\jsend$ is used depending on the security guarantee. For simplicity, protocols where the fair and robust variants only differ in the instantiation of $\jsend$ used, we give a common construction for both.

Protocol $\prot{\jsend}$ denotes the instantiation of Joint-Send ($\jsend$) primitive. We say that $P_i, P_j$ $\jsend$ $\vl{v}$ to $P_k$ when they invoke $\prot{\jsend}(P_i, P_j, \vl{v}, P_k)$.

$\prot{\jsend}(P_i, P_j,\vl{v},P_k)$Joint-Send for robust protocols in $\Fthis$.fig:4pcjsendrobust

Input(s): $P_i, P_j : \vl{v}$, $P_k : \bot$,  Output: $P_i, P_j : \bot / \TTP$, $P_k : \vl{v} / \TTP$.

$P_s \in \Partyset$ initializes an inconsistency bit $\bitb_s = 0$. If $P_s$ remains silent instead of sending $\bitb_s$ in any of the following rounds, the recipient sets $\bitb_s$ to $1$.

– Send:  $P_i$ sends $\vl{v}$ to $P_k$.

– Verify:

–  $P_j$ sends $\Hash(\vl{v})$ to $P_k$.
$P_k$ sets $\bitb_k = 1$ if the received values are inconsistent or if the value is not received.

– $P_k$ sends $\bitb_k$ to all parties. $P_s$ for $s \in \{i, j, l\}$ sets $\bitb_s = \bitb_k$.

– $P_s$ for $s \in \{i, j, l\}$ mutually exchange their bits. $P_s$ resets $\bitb_s = \bitb^{\prime}$ where $\bitb^{\prime}$ denotes the bit which appears in majority among $\bitb_i, \bitb_j, \bitb_l$.

– All parties set $\TTP = P_l$ if $\bitb^{\prime} = 1$, terminate otherwise.

Protocol $\prot{\jsend}$ (fig:4pcjsendrobust) requires an amortized communication of $\ell$ bits and $1$ round.

In the protocol $\prot{\jsend}(P_i, P_j,\vl{v},P_k)$ for the fair variant, $P_i$ communicates $\vl{v}$ to $P_k$ requiring communication of $\ell$ bits and one round. The hash value communication from $P_j$ to $P_k$ can be clubbed for multiple instances with the same set of parties and hence the cost gets amortized. The analysis is similar for the robust case as well. Here, though the verification consists of multiple steps, the cost gets amortized over multiple instances.

§ ARITHMETIC / BOOLEAN 4PC

This section covers the details of our 4PC protocol $\Fthis$ over an arithmetic ring $\Z{\ell}$. We begin by explaining the sharing protocol in share4pcM, multiplication with abort in mult4pcM, and the reconstruction in rec4pcM. Lastly, the details on elevating the security to fairness are presented in recfair4pcM and to robustness in robust4pc.

§.§ Sharing

Protocol $\prot{\Sh}$ (fig:piSh) enables $P_i$ to generate $\shr{\cdot}$-share of a value $\vl{v}$. During the preprocessing phase, $\pd{}$-shares are sampled non-interactively using the pre-shared keys (cf. <ref>) in a way that $P_i$ will get the entire mask $\pd{\vl{v}}$. During the online phase, $P_i$ computes $\mk{\vl{v}} = \vl{v} + \pd{\vl{v}}$ and sends to $P_1, P_2, P_3$, which exchange the hash values to check for consistency. Parties abort in the fair protocol in case of inconsistency, whereas for robust security, parties proceed with a default value.

$\prot{\Sh}(P_i, \vl{v})$$\shr{\cdot}$-sharing of a value $\vl{v}$ by party $P_i$ in $\Fthis$.fig:piSh

Input(s): $P_i : \vl{v}$,  Output: $\shr{\vl{v}}$.

Preprocessing: Sample as follows:
$P_i, P_0, P_1, P_3: \pad{\vl{v}}{1}~~\Big|~~P_i, P_0, P_2, P_3: \pad{\vl{v}}{2}~~\Big|~~P_i, P_0, P_1, P_2: \pad{\vl{v}}{3}$

* $P_i$ computes $\mk{\vl{v}} = \vl{v} + \pd{\vl{v}}$ and sends to $P_1, P_2, P_3$.

* $P_1, P_2, P_3$ mutually exchange $\Hash(\mk{\vl{v}})$ and accept the sharing if there exists a majority. Else parties $\abort$ for the case of fairness and accepts a default value for the case of robust security.

Protocol $\prot{\Sh}$ (fig:piSh) requires an amortized communication of at most $3\ell$ bits and $1$ round in the online phase.

The preprocessing of $\prot{\Sh}$ is non-interactive as the parties sample non interactively using key setup $\Func[Setup]$ (<ref>). in the online phase, $P_i$ sends $\mk{\vl{v}}$ to $P_1, P_2, P_3$ resulting in 1 round and communication of at most $3\ell$ bits ($P_i = P_0$). The next round of hash exchange can be clubbed for several instances and the cost gets amortized over multiple instances.

§.§.§ Joint Sharing

Protocol $\prot{\JSh}$ enables parties $P_i, P_j$ to generate $\shr{\cdot}$-share of a value $\vl{v}$. The protocol is similar to $\prot{\Sh}$ except that $P_j$ ensures the correctness of the sharing performed by $P_i$. During the preprocessing, $\pd{}$-shares are sampled such that both $P_i, P_j$ will get the entire mask $\pd{\vl{v}}$. During the online phase, $P_i, P_j$ compute and $\jsend$ $\mk{\vl{v}} = \vl{v} + \pd{\vl{v}}$ to parties $P_1, P_2, P_3$.

For joint-sharing a value $\vl{v}$ possessed by $P_0$ along with another party in the preprocessing, the communication can be optimized further. The protocol steps based on the $(P_i, P_j)$ pair are summarised below:

– $(P_0, P_1): \Partyset \setminus \{P_2\}$ sample $\pad{\vl{v}}{1} \in_R \Z{\ell}$; Parties set $\pad{\vl{v}}{2} = \mk{\vl{v}} = 0$; $P_0, P_1$ $\jsend$ $\pad{\vl{v}}{3} = - \vl{v} - \pad{\vl{v}}{1}$ to $P_2$.

– $(P_0, P_2): \Partyset \setminus \{P_3\}$ sample $\pad{\vl{v}}{3} \in_R \Z{\ell}$; Parties set $\pad{\vl{v}}{1} = \mk{\vl{v}} = 0$; $P_0, P_2$ $\jsend$ $\pad{\vl{v}}{2} = - \vl{v} - \pad{\vl{v}}{3}$ to $P_3$.

– $(P_0, P_3): \Partyset \setminus \{P_1\}$ sample $\pad{\vl{v}}{2} \in_R \Z{\ell}$; Parties set $\pad{\vl{v}}{3} = \mk{\vl{v}} = 0$; $P_0, P_3$ $\jsend$ $\pad{\vl{v}}{1} = - \vl{v} - \pad{\vl{v}}{1}$ to $P_1$.

§.§ Multiplication

Given the shares of $\vl{a}, \vl{b}$, the goal of the multiplication protocol is to generate shares of $\vl{z} = \vl{ab}$. The protocol is designed such that parties $P_1, P_2$ obtain a masked version of the output $\vl{z}$, say $\vl{z} - \vl{r}$ in the online phase, and $P_0, P_3$ obtain the mask $\vl{r}$ in the preprocessing phase. Parties then generate $\shr{\cdot}$-sharing of these values by executing $\prot{\JSh}$, and locally compute $\shr{\vl{z} - \vl{r}} + \shr{\vl{r}}$ to obtain the final output.

Note that,

\begin{align}\label{eq:z+r}
\vl{z} - \vl{r} &= \vl{a}\vl{b} - \vl{r} = (\mk{\vl{a}} - \pd{\vl{a}})(\mk{\vl{b}} - \pd{\vl{b}}) - \vl{r} \nonumber\\
&= \mk{\vl{ab}} - \mk{\vl{a}}\pd{\vl{b}} - \mk{\vl{b}}\pd{\vl{a}} + \gm{\vl{a}\vl{b}}{} - \vl{r}
~~\text{\footnotesize{(cf. notation~\ref{notation:4pcconcise})}}
\end{align}

In Eq <ref>, $P_1, P_2$ can compute $\mk{\vl{ab}}$ locally, and hence we are interested in computing $\vl{y} = (\vl{z - r}) - \mk{\vl{ab}}$. Let us view $\vl{y}$ as $\vl{y} = \vl{y}_1 + \vl{y}_2 + \vl{y}_3$, where $\vl{y}_1$ and $\vl{y}_2$ can be computed respectively by $P_1$ and $P_2$, and $\vl{y}_3$ consists of terms that can be computed by both $P_1, P_2$.

\begin{align}\label{eq:y}
P_1: \vl{y}_1 &= - \pad{\vl{a}}{1} \mk{\vl{b}} - \pad{\vl{b}}{1} \mk{\vl{a}} + \sqr{\gm{\vl{a}\vl{b}}{} - \vl{r}}_1 \nonumber\\
P_2: \vl{y}_2 &= - \pad{\vl{a}}{2} \mk{\vl{b}} - \pad{\vl{b}}{2} \mk{\vl{a}} + \sqr{\gm{\vl{a}\vl{b}}{} - \vl{r}}_2 \nonumber\\
P_1, P_2: \vl{y}_3 &= - \pad{\vl{a}}{3} \mk{\vl{b}} - \pad{\vl{b}}{3} \mk{\vl{a}}
\end{align}

The preprocessing is set up such that $P_1, P_2$ receive an additive sharing ($\sqr{\cdot}$) of $\gm{\vl{a}\vl{b}}{} - \vl{r}$. Parties $P_1, P_2$ mutually exchange the missing share to reconstruct $\vl{y}$ and subsequently $\vl{z - r}$.

$\prot{\Mult}(\vl{a}, \vl{b}, \isTr)$Multiplication with / without truncation in $\Fthis$.fig:piMultiplication
$\isTr$ is a bit denoting whether truncation is required ($\isTr =1$) or not ($\isTr=0$).

Input(s): $\shr{\vl{a}}, \shr{\vl{b}}$.

Output: $\shr{\vl{o}}$ where $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{o} = \vl{z}$ if $\isTr = 0$ and $\vl{z} = \vl{ab}$.

* Locally compute the following:

\begin{align*}
P_0, P_1: \gm{\vl{a}\vl{b}}{1} &= \pad{\vl{a}}{1} \pad{\vl{b}}{3} + \pad{\vl{a}}{3} \pad{\vl{b}}{1} + \pad{\vl{a}}{3} \pad{\vl{b}}{3} \\
P_0, P_2: \gm{\vl{a}\vl{b}}{2} &= \pad{\vl{a}}{2} \pad{\vl{b}}{3} + \pad{\vl{a}}{3} \pad{\vl{b}}{2} + \pad{\vl{a}}{2} \pad{\vl{b}}{2}\\
P_0, P_3: \gm{\vl{a}\vl{b}}{3} &= \pad{\vl{a}}{1} \pad{\vl{b}}{2} + \pad{\vl{a}}{2} \pad{\vl{b}}{1} + \pad{\vl{a}}{1} \pad{\vl{b}}{1}
\end{align*}

* $P_0, P_3$ and $P_j$ sample random ${\vl{u}}^j \in_R \Z{\ell}$ for $j \in \{1,2\}$. Let ${\vl{u}^1} + \vl{u}^2 = \gm{\vl{a}\vl{b}}{3} - \vl{r}$ for a random $\vl{r} \in_R \Z{\ell}$.

* $P_0, P_3$ compute $\vl{r} = \gm{\vl{a}\vl{b}}{3} - {\vl{u}^1} - \vl{u}^2$ and set $\vl{q} = \vl{r}^{\vl{t}}$  if $\isTr = 1$, else set $\vl{q} = \vl{r}$. $P_0, P_3$ execute $\prot{\JSh}(P_0, P_3, \vl{q})$ to generate $\shr{\vl{q}}$.

* $P_0, P_1, P_2$ sample random ${\vl{s}}_1, {\vl{s}}_2 \in_R \Z{\ell}$ and set ${\vl{s}} = {\vl{s}}_1 + {\vl{s}} _2$[For the fair protocol, it is enough for $P_0, P_1, P_2$ to sample ${\vl{s}}$ directly.].
$P_0$ sends $\vl{w} = \gm{\vl{a}\vl{b}}{1} + \gm{\vl{a}\vl{b}}{2} + {\vl{s}}$ to $P_3$.

Online: Let $\vl{y} = (\vl{z} - \vl{r}) - \mk{\vl{a}} \mk{\vl{b}}$.

* Locally compute the following:

\begin{align*}
P_1: \vl{y}_1 &= - \pad{\vl{a}}{1} \mk{\vl{b}} - \pad{\vl{b}}{1} \mk{\vl{a}} + \gm{\vl{a}\vl{b}}{1} + {\vl{u}}^1 \\
P_2: \vl{y}_2 &= - \pad{\vl{a}}{2} \mk{\vl{b}} - \pad{\vl{b}}{2} \mk{\vl{a}} + \gm{\vl{a}\vl{b}}{2} + {\vl{u}}^2 \\
P_1, P_2: \vl{y}_3 &= - \pad{\vl{a}}{3} \mk{\vl{b}} - \pad{\vl{b}}{3} \mk{\vl{a}}
\end{align*}

* $P_1$ sends $\vl{y}_1$ to $P_2$, while $P_2$ sends $\vl{y}_2$ to $P_1$, and they locally compute $\vl{z} - \vl{r} = (\vl{y}_1 + \vl{y}_2 + \vl{y}_3) + \mk{\vl{a}} \mk{\vl{b}}$.

* If $\isTr = 1$, $P_1, P_2$ set $\vl{p} = (\vl{z} - \vl{r})^{\vl{t}}$, else $\vl{p} = \vl{z} - \vl{r}$. $P_1, P_2$ execute $\prot{\JSh}(P_1, P_2, \vl{p})$ to generate $\shr{\vl{p}}$.

* Parties locally compute $\shr{\vl{o}} = \shr{\vl{p}} + \shr{\vl{q}}$. Here $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{z}$ otherwise.

* Verification: $P_3$ computes $\vl{v} = - (\pad{\vl{a}}{1} + \pad{\vl{a}}{2}) \mk{\vl{b}} - (\pad{\vl{b}}{1} + \pad{\vl{b}}{2}) \mk{\vl{a}} + {\vl{u}^1} + \vl{u}^2 + \vl{w}$ and sends $\Hash(\vl{v})$ to $P_1$ and $P_2$. Parties $P_1, P_2$ $\abort$ iff $\Hash(\vl{v}) \ne \Hash(\vl{y}_1 + \vl{y}_2 + {\vl{s}})$.

To ensure the correctness of the values exchanged, we use the assistance of $P_3$. Concretely, $P_3$ obtains $\vl{y}_1 + \vl{y}_2 + \vl{s}$, where $\vl{s}$ is a random mask known to $P_0, P_1, P_2$. For this $P_3$ needs $\gm{\vl{a}\vl{b}}{} + \vl{s}$, which it obtains from the preprocessing phase. The mask $\vl{s}$ is used to prevent the leakage from $\gm{\vl{a}\vl{b}}{}$ to $P_3$. $P_3$ computes a hash of $\vl{y}_1 + \vl{y}_2 + \vl{s}$ and sends it to $P_1, P_2$, which $\abort$ if it is inconsistent.

Parties should obtain the following values from the preprocessing phase:

\begin{equation*}
{\sf i)}~~P_1, P_2: \sqr{\gm{\vl{ab}}{} - \vl{r}}~~\Big|~~
{\sf ii)}~~P_0, P_3: \vl{r}~~\Big|~~
{\sf iii)}~~P_3: \gm{\vl{a}\vl{b}}{} + \vl{s}
\end{equation*}

For ${\sf i)}$ and ${\sf ii)}$, let $\gm{\vl{ab}}{} = \gm{\vl{ab}}{1} + \gm{\vl{ab}}{2} + \gm{\vl{ab}}{3}$, where $P_0$ along with $P_i$ can compute $\gm{\vl{ab}}{i}$ for $i \in \{1, 2, 3\}$. For $P_1, P_2$, to form an additive sharing of $(\gm{\vl{ab}}{} - r)$, it suffices for them to define their share as $\gm{\vl{ab}}{i} + \sqr{\gm{\vl{ab}}{3} - r}$.

Instead of sampling a random $\vl{r}$, $P_0, P_3$, along with $P_i$, sample the share for $\gm{\vl{ab}}{3} - \vl{r}$ as $\vl{u}^i$ for $i \in \{1, 2\}$.  $P_0, P_3$ compute $\vl{r}$ as $\gm{\vl{ab}}{3} - \vl{u}^1 - \vl{u}^2$.

For ${\sf iii)}$, $P_3$ needs $\vl{w} = \gm{\vl{ab}}{1} + \gm{\vl{ab}}{2} + \vl{s}$. To tackle this, $P_0, P_1, P_2$ sample $\vl{s}_1, \vl{s}_2$, and set $\vl{s} = \vl{s}_1 + \vl{s}_2$. $P_0, P_i$, for $i \in \{1, 2\}$, $\jsend$ $\gm{\vl{ab}}{i} + \vl{s}_i$ to $P_3$. This requires a communication of 2 elements.

As an optimization, $P_0$ sends $\vl{w}$ to $P_3$. If $P_0$ is malicious, it might send a wrong value to $P_3$. However, in this case, every party in the online phase would be honest. And since $P_1, P_2$ do not use $\vl{w}$ in their computation, any error in $\vl{w}$ is bound to get caught in the verification phase.

Protocol $\prot{\Mult}$ (fig:piMultiplication) (in $\Fthis$) requires $2 \ell$ bits of communication in the preprocessing phase, and $1$ round and $3 \ell$ bits of communication in the online phase.

During preprocessing, sampling of values ${\vl{u}}^1, {\vl{u}}^2$ are performed non-interactively using $\Func[Setup]$. A communication of $\ell$ bits is required for the joint sharing of $\vl{q}$ by $P_0, P_3$ as explained in <ref>. In addition, $P_0$ communicates $\vl{w}$ to $P_3$ requiring additional $\ell$ bits.
During online, two instances of $\prot{\jsend}$ are executed in parallel resulting in a communication of $2\ell$ bits and 1 round. This is followed by a joint sharing by $P_1,P_2$ for which an additional communication of $\ell$ bits are required. However, in joint sharing, the communication is from $P_1$ to $P_3$ and the same can be deferred till the verification stage. Thus the online round is retained as $1$ in an amortized sense.

§.§.§ Truncation

To accommodate truncation, the multiplication protocol is modified as follows. $P_1, P_2$ locally truncate $(\vl{z - r})$ and generate $\shr{\cdot}$-shares of it in the online phase. Similarly, $P_0, P_3$ truncate $\vl{r}$ in the preprocessing phase and generate its $\shr{\cdot}$-shares. Parties locally compute $\shr{\vl{z}^{\vl{t}}} = \shr{(\vl{z-r})^{\vl{t}}} + \shr{\vl{r}^{\vl{t}}}$.

§.§.§ Multiplication with constant

Multiplication by a constant in MPC is typically local. Given constant $\alpha$ and $\shr{\vl{v}}$, the $\shr{\cdot}$-shares of the product $\vl{y} = \alpha\vl{v}$ can be locally computed as per (<ref>).

\begin{equation}\label{eq:mutconst4pcM}
\mk{\vl{y}} = \alpha \mk{\vl{u}},~~~\pad{\vl{y}}{1} = \alpha \pad{\vl{v}}{1},~~~\pad{\vl{y}}{2} = \alpha \pad{\vl{v}}{2},~~~\pad{\vl{y}}{3} = \alpha \pad{\vl{v}}{3}
\end{equation}

However, in FPA, we need to perform a truncation on the output. For this, note that the product can be written as $\alpha\vl{v} = \beta^1 + \beta^2$ where $\beta^1 = \alpha.(\mk{\vl{v}} - \pad{\vl{v}}{3})$ and $\beta^2 = \alpha.(- \pad{\vl{v}}{1} - \pad{\vl{v}}{2})$.
$P_1, P_2$ locally truncate $\beta^{1}$ and execute $\prot{\JSh}$, while $P_0, P_3$ do the same with $\beta^{2}$.

§.§.§ Special multiplication protocol $\prot{\MultS}$

Given the $\sgr{\cdot}$-shares of values $\vl{a}, \vl{b}$ with $P_0$ knowing the entire shares of both $\sgr{\vl{a}}$ and $\sgr{\vl{b}}$, protocol $\prot{\MultS}$ (fig:piMultS) computes $\sgr{\vl{z}}$ for $\vl{z} = \vl{ab}$.

$\prot{\MultS}(\sgr{\vl{a}}, \sgr{\vl{b}})$Special multiplication of $\sgr{\cdot}$-shares in $\Fthis$.fig:piMultS

Input(s): $\sgr{\vl{a}}, \sgr{\vl{b}}$,   Output: $\sgr{\vl{z}}$ where $\vl{z} = \vl{ab}$.

* Parties invoke $\FZero$ (4pcMFZero) to enable $P_0, P_j$ obtain $Z_j$ for $j \in \{1,2,3\}$ such that $Z_1 + Z_2 + Z_3 = 0$. Then,

\begin{align*}
P_0, P_1 &~\jsend~\vl{(ab)}^{1}  = \vl{a}^1 \vl{b}^3 + \vl{a}^3 \vl{b}^1 + \vl{a}^3 \vl{b}^3 + Z_1~\text{to } P_2.\\
P_0, P_2 &~\jsend~\vl{(ab)}^{2} = \vl{a}^2 \vl{b}^3 + \vl{a}^3 \vl{b}^2 + \vl{a}^2 \vl{b}^2 + Z_2~\text{to } P_3.\\
P_0, P_3 &~\jsend~\vl{(ab)}^{3} = \vl{a}^1 \vl{b}^2 + \vl{a}^2 \vl{b}^1 + \vl{a}^1 \vl{b}^1 +  Z_3~\text{to } P_1.
\end{align*}

–  Set $\sgr{\vl{z}}$ as $\sgr{\vl{z}}^1 = \vl{(ab)}^{3},~~\sgr{\vl{z}}^2 = \vl{(ab)}^{2},~~\sgr{\vl{z}}^3 = \vl{(ab)}^{1}$.

§.§ Reconstruction

Protocol $\prot{\Rec}(\Partyset, \vl{v})$ (fig:piRec) enables parties in $\Partyset$ to compute $\vl{v}$, given its $\shr{\cdot}$-share and achieves security with abort. Note that each party misses one share to reconstruct the output, and the other 3 parties hold this share. 2 out of the 3 parties will $\jsend$ the missing share to the party that lacks it. Reconstruction towards a single party can be viewed as a special case.

$\prot{\Rec}(\Partyset, \shr{\vl{v}})$Reconstruction (with abort security) of value $\vl{v}$ among $\Partyset$ in $\Fthis$.fig:piRec

Input(s): $\shr{\vl{v}}$,  Output: $\vl{v}$.

* $P_1, P_0$ $\jsend$ $\pad{\vl{v}}{1}$ to $P_2$;   $P_2, P_0$ $\jsend$ $\pad{\vl{v}}{3}$ to $P_3$;$P_3, P_0$ $\jsend$ $\pad{\vl{v}}{2}$ to $P_1$;   $P_1, P_2$ $\jsend$ $\mk{\vl{v}}$ to $P_0$.

* Parties compute $\vl{v} = \mk{\vl{v}} - \pad{\vl{v}}{1} - \pad{\vl{v}}{2} - \pad{\vl{v}}{3}$.

Protocol $\prot{\Rec}$ (fig:piRec) requires an amortized communication of $4\ell$ bits and $1$ round in the online phase.

The protocol involves 4 invocations of $\prot{\jsend}$ protocol and the communication follows from Lemma <ref>.

§.§.§ Achieving Fairness

Here, we show how to extend the security of $\Fthis$ from abort to fairness. Before proceeding with the output reconstruction, we must ensure that all the honest parties are alive after the verification phase. For this, all the parties maintain an aliveness bit, say $\bitb$, which is initialized to $\continue$. If the verification phase is not successful for a party, it sets $\bitb = \abort$. In the first round of reconstruction, the parties mutually exchange their $\bitb$ bit and accept the value that forms the majority. Since we have only one corruption, it is guaranteed that all the honest parties will agree on $\bitb$. If $\bitb = \continue$, the parties exchange their missing shares and accept the majority. As per the sharing semantics, every missing share is possessed by three parties, out of which there can be at most one corruption. As an optimization, for instances where many values are reconstructed, two out of the three parties can send the share while the third can send a hash of the same.

Looking ahead, a similar reconstruction will be used for the robust variants as well. However, there is no need to perform an explicit aliveness check as it will be taken care of by the verification of $\jsend$ instances.

§.§ Achieving Robustness

In this section, we show how to extend the security of $\Fthis$ to robustness. We provide two variants with different trade-offs in the communication for multiplication – i) $\FthisA$: It has the same amortized communication complexity as that of $\Fthis$ but requires verification in the preprocessing phase, and ii) $\FthisB$: It avoids the verification in $\FthisA$ but incurs a communication overhead of $1$ element in the preprocessing phase over $\Fthis$.

§.§.§ $\FthisA$

On a high level, we make two modifications to the multiplication protocol $\prot{\Mult}$ (fig:piMultiplication). In the preprocessing, communication comes from a $\prot{\JSh}$ in step 3 of the protocol, and the value $\vl{w}$ sent by $P_0$ to $P_3$, in step 4. To get robustness, the robust variant of $\prot{\JSh}$ is used. To ensure the correctness of $\vl{w}$, we introduce $\piVrfyP$ (fig:piVrfyP0). If $\piVrfyP$ fails, parties identify a $\TTP$ in the preprocessing phase itself. The second modification is in the online phase, which proceeds as that of $\prot{\Mult}$. If any $\abort$ happens, $P_0$ is assigned as the $\TTP$. Since $P_0$ does not participate in the online phase of the multiplication, and its communication in the preprocessing has been verified via $\piVrfyP$, this assignment is safe.

Verifying the communication by $P_0$:

In $\prot{\Mult}$ (fig:piMultiplication) protocol, $P_0$ computes and sends $\vl{w} = \gm{\vl{a}\vl{b}}{1} + \gm{\vl{a}\vl{b}}{2} + {\vl{s}}_1 + {\vl{s}}_2$ to $P_3$ with $P_0, P_1, P_2$ knowing ${\vl{s}}_1, {\vl{s}}_2$ in clear. Note that $\vl{w} = \vl{w}^1 + \vl{w}^2$ for $\vl{w}^1 = \gm{\vl{a}\vl{b}}{1} + {\vl{s}}_1$ and $\vl{w}^2 = \gm{\vl{a}\vl{b}}{2} + {\vl{s}}_2$. Also, $P_0$ along with $P_1, P_2$ and $P_3$ possess the values $\vl{w}^1, \vl{w}^2$ and $\vl{w}$ respectively. Checking the correctness of $\vl{w}$ reduces to verifying $\vl{w} = \vl{w}^1 + \vl{w}^2$.

To verify this relation for all $M$ multiplication gates in the circuit, i.e. $\{\vl{w}_j \iseq \vl{w}_j^1 + \vl{w}_j^2\}_{j \in [M]}$, one approach is to compute a random linear combination and verify the relation on the sum.

While working over a field $\F_p$, this solution has an error probability $1/|\F_p|$, where $|\F_p|$ denotes the size of $\F_p$. However, this solution does not work naively over rings since not every element in the ring has an inverse, unlike fields. Concretely, the check can still pass with a probability of at most $1/2$ <cit.>. To reduce the cheating probability, the check is repeated $\csec$ times, thereby bounding the cheating probability by $1/2^{\csec}$. As an optimization, it is sufficient to choose the random combiners from $\{0,1\}$. Thus, parties need to sample only a binary string of $M$ bits using the shared key for one check. The formal verification protocol appears in fig:piVrfyP0A.

$\piVrfyP(\{\sqr{{\vl{w}}_j}\}_{j=1}^{M})$Verifying $P_0$'s communication in the multiplication protocol of $\FthisA$: Approach 1fig:piVrfyP0A

Input(s): $P_0, P_1: {\vl{w}}_j^1~~\Big|~~P_0, P_2: {\vl{w}}_j^2~~\Big|~~P_0, P_3: {\vl{w}}_j~~\Big|~$, for $j = 1, \ldots, M$.

Output: Whether ${\vl{w}}_j = {\vl{w}}_j^1 + {\vl{w}}_j^2$ or not, for $j = 1, \ldots, M$.

Repeat the following $\csec$ times, in parallel.

* Sample random values $\tau_1,\ldots, \tau_M \in \Z{\ell}$.

* Locally compute: $P_0, P_1: \vl{e}^1 = \sum_{j=1}^{M} \tau_j \vl{w}_j^1$; $P_0, P_2: \vl{e}^2 = \sum_{j=1}^{M} \tau_j \vl{w}_j^2$; $P_0, P_3: \vl{e} = \sum_{j=1}^{M} \tau_j \vl{w}_j$.

* $(P_0,P_1)$, $(P_0,P_2)$ and $(P_0,P_3)$ generate $\shr{\cdot}$-shares of $ \vl{e}^1,  \vl{e}^2$ and  $\vl{e}$ respectively using $\prot{\JSh}$.

* Locally compute $\shr{\vl{g}} = \shr{\vl{e}} - \shr{\vl{e}^1} - \shr{\vl{e}^2}$.

* Robustly reconstruct $\vl{g}$ and check if $\vl{g} \iseq 0$.

If for all $\csec$ repetitions, $\vl{g} = 0$, then continue with rest of the computation. Else, $P_0$ is identified to be corrupt and $\TTP = P_1$.

Another approach, that avoids the repetition in the $\piVrfyP$ protocol above, is to perform a similar check over a Galois ring <cit.>. To carry out the verification, the extended ring $\Z{\ell}/f(x)$ is used, which is the ring of all polynomials with coefficients in $\Z{\ell}$ modulo an irreducible polynomial $f$ of degree $d$ over $\Z{}$. Here, each element in $\Z{\ell}$ is lifted to a $d$-degree polynomial in $\Z{\ell}[x]/f(x)$ (which results in blowing up the communication by a factor $d$). Given this, to verify the $M$ values, further packing is performed. More concretely, assume that $d$ divides $M$ and $M = d \cdot q$. For $j = 1, \ldots, q $, public polynomial $g_j$ and shared polynomials $g^1_j$ and $g^2_j$ are defined for each set of $d$ values $\{\vl{w}, \vl{w}^1, \vl{w}^2\}$, all of which are then combined to check whether $\{\vl{w}_j \iseq \vl{w}_j^1 + \vl{w}_j^2\}_{j \in [M]}$. We describe the polynomial with respect to $j=1$ below.

\begin{align*}
g_1 = \vl{w}_{1} + X \cdot \vl{w}_{2} + \ldots + X^{d-1} \cdot \vl{w}_{d} \\
g_1^1 = \vl{w}^1_{1} + X \cdot \vl{w}^1_{2} + \ldots + X^{d-1} \cdot \vl{w}^1_{d} \\
g_1^2 = \vl{w}^2_{1} + X \cdot \vl{w}^2_{2} + \ldots + X^{d-1} \cdot \vl{w}^2_{d}
\end{align*}

Now, parties sample random values $\vl{r}_1, \ldots, \vl{r}_{q} \in \Z{\ell}/f(x)$ and compute $g = \sum_{j=1}^{q} \vl{r}_j g_j $, $g^1 = \sum_{j=1}^{q} \vl{r}_j g^1_j$ and $g^2 = \sum_{j=1}^{q} \vl{r}_j g^2_j $. This is followed by robustly reconstructing $g - g^1 - g^2$ and verifying if this value is $0$. If not, $P_0$ is identified to be a corrupt and computation is carried out by a $\TTP$. The formal verification protocol appears in fig:piVrfyP0.

$\piVrfyP(\{\sqr{{\vl{w}}_j}\}_{j=1}^{M})$Verifying $P_0$'s communication in the multiplication protocol of $\FthisA$: Approach 2fig:piVrfyP0

Input(s): $P_0, P_1: {\vl{w}}_j^1~~\Big|~~P_0, P_2: {\vl{w}}_j^2~~\Big|~~P_0, P_3: {\vl{w}}_j~~\Big|~$, for $j = 1, \ldots, M$.

Output: Whether ${\vl{w}}_j = {\vl{w}}_j^1 + {\vl{w}}_j^2$ or not, for $j = 1, \ldots, M$.

* Define the following polynomials over $\Z{\ell}/f(x)$ for $j \in [q]$ .

\begin{align*}
g_j = \vl{w}_{1 + (j-1)d} + X \cdot \vl{w}_{2 + (j-1)d} + \ldots + X^{d-1} \cdot \vl{w}_{d + (j-1)d} \\
g^1_j = \vl{w}^1_{1 + (j-1)d} + X \cdot \vl{w}^1_{2 + (j-1)d} + \ldots + X^{d-1} \cdot \vl{w}^1_{d + (j-1)d} \\
g^2_j = \vl{w}^2_{1 + (j-1)d} + X \cdot \vl{w}^2_{2 + (j-1)d} + \ldots + X^{d-1} \cdot \vl{w}^2_{d + (j-1)d}
\end{align*}

* Parties generate random values $\vl{r}_1, \ldots, \vl{r}_q \in \Z{\ell}/f(x)$, and compute $g = \sum_{j=1}^{q} \vl{r}_j g_j $, $g^1 = \sum_{j=1}^{q} \vl{r}_j g^1_j$ and $g^2 = \sum_{j=1}^{q} \vl{r}_j g^2_j $.

* Parties execute $\prot{\JSh}(P_0, P_1, g^1)$, $\prot{\JSh}(P_0, P_2, g^2)$ and $\prot{\JSh}(P_0, P_3, g)$ to generate $\shr{g^1}, \shr{g^2}$ and $\shr{g}$, respectively.

* Parties robustly reconstruct $g - g^1 - g^2$ and check equality to $0$. If it is $0$, then parties continue with rest of the computation. Else, $P_0$ is identified to be corrupt and $\TTP = P_1$.

§.§.§ $\FthisB$

This variant (fig:piMultGOD) avoids the verification of $P_0$ at the cost of communicating 1 extra ring element in the preprocessing, compared to $\FthisA$. Note that the communication cost of this protocol is similar to that of the one in SWIFT <cit.>. We were unable to extend the latter's efficiently to support multi-input multiplication.

Hence, we design $\FthisB$ that has the same communication complexity as SWIFT but also supports multi-input multiplication, as well as truncation without any overhead. In order to get rid of $\piVrfyP$, the communication of $\vl{w}$ from $P_0$ to $P_3$ is split into 2 parts. ($P_0, P_1$) and ($P_0, P_2$) compute $\vl{w}$ in parts, and send them to $P_3$ using $\jsend$.

This modification allows $P_3$ to compute $\vl{y}_1 + \vl{s}_1$ and $\vl{y}_2 + \vl{s}_2$ separately in the online phase. In addition, to enable $P_2$ to obtain $\vl{y}_1$, $P_1, P_3$ can $\jsend$ $\vl{y}_1 + \vl{s}_1$ to $P_2$. $P_1$ obtains $\vl{y}_2 + \vl{s}_2$ similarly.

The formal protocol for the robust multiplication in $\FthisB$, $\piMultR$, appears in fig:piMultGOD. The primary difference from the fair counterpart is that the communication of $\vl{w}$ from $P_0$ to $P_3$ in the preprocessing is now split into two parts.  $(P_0, P_1), (P_0, P_2)$ communicates $\vl{w}_1, \vl{w}_2$  respectively to $P_3$ via $\jsend$.

$\piMultR(\vl{a}, \vl{b}, \isTr)$Robust multiplication in $\FthisB$.fig:piMultGOD
$\isTr$ is a bit denoting whether truncation is required ($\isTr =1$) or not ($\isTr=0$).

Input(s): $\shr{\vl{a}}, \shr{\vl{b}}$.

Output: $\shr{\vl{o}}$ where $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{o} = \vl{z}$ if $\isTr = 0$ and $\vl{z} = \vl{ab}$.

* Parties locally compute the following:

\begin{align*}
P_0, P_1: \gm{\vl{a}\vl{b}}{1} &= \pad{\vl{a}}{1} \pad{\vl{b}}{3} + \pad{\vl{a}}{3} \pad{\vl{b}}{1} + \pad{\vl{a}}{3} \pad{\vl{b}}{3} \\
P_0, P_2: \gm{\vl{a}\vl{b}}{2} &= \pad{\vl{a}}{2} \pad{\vl{b}}{3} + \pad{\vl{a}}{3} \pad{\vl{b}}{2} + \pad{\vl{a}}{2} \pad{\vl{b}}{2} \\
P_0, P_3: \gm{\vl{a}\vl{b}}{3} &= \pad{\vl{a}}{1} \pad{\vl{b}}{2} + \pad{\vl{a}}{2} \pad{\vl{b}}{1} + \pad{\vl{a}}{1} \pad{\vl{b}}{1}
\end{align*}

* $P_0, P_3$ and $P_j$ sample random ${\vl{u}}^j \in_R \Z{\ell}$ for $j \in \{1,2\}$. Let ${\vl{u}^1} + \vl{u}^2 = \gm{\vl{a}\vl{b}}{3} - \vl{r}$ for a random $\vl{r} \in_R \Z{\ell}$.

* $P_0, P_3$ compute $\vl{r} =  \gm{\vl{a}\vl{b}}{3} - {\vl{u}^1} - \vl{u}^2$ and set $\vl{q} = \vl{r}^{\vl{t}}$  if $\isTr = 1$, else set $\vl{q} = \vl{r}$. $P_0, P_3$ execute $\prot{\JSh}(P_0, P_3, \vl{q})$ to generate $\shr{\vl{q}}$.

* $P_0, P_1, P_2$ sample random ${\vl{s}}_1, {\vl{s}}_2 \in_R \Z{\ell}$. $P_0, P_j$ $\jsend$ $\vl{w}_j = \gm{\vl{a}\vl{b}}{j} + {\vl{s}}_j$ to $P_3$  for $j \in \{1,2\}$.

Online: Let $\vl{y} = (\vl{z} - \vl{r}) - \mk{\vl{a}} \mk{\vl{b}} + \vl{s}_1 + \vl{s}_2$ .

* Parties locally compute the following:

\begin{align*}
P_1, P_3: \vl{y}_1 + \vl{s}_1   &=  - \pad{\vl{a}}{1} \mk{\vl{b}} - \pad{\vl{b}}{1} \mk{\vl{a}} + {\vl{u}}^1 + {\vl{w}}_1 \\
P_2, P_3: \vl{y}_2 + \vl{s}_2 &=  - \pad{\vl{a}}{2} \mk{\vl{b}} - \pad{\vl{b}}{2} \mk{\vl{a}} + {\vl{u}}^2 + {\vl{w}}_2 \\
P_1, P_2: \vl{y}_3  &= - \pad{\vl{a}}{3} \mk{\vl{b}} - \pad{\vl{b}}{3} \mk{\vl{a}}
\end{align*}

* $P_1, P_3$ $\jsend$ $\vl{y}_1 + \vl{s}_1$ to $P_2$, while $P_1, P_3$ $\jsend$ $\vl{y}_2 + \vl{s}_2$ to $P_1$.

* $P_1, P_2$ locally compute $\vl{z} - \vl{r} = (\vl{y}_1 + \vl{y}_2 + \vl{y}_3) + \mk{\vl{a}} \mk{\vl{b}} - \vl{s}_1 - \vl{s}_2$.

* If $\isTr = 1$, $P_1, P_2$ locally set $\vl{p} = (\vl{z} - \vl{r})^{\vl{t}}$, else $\vl{p} = \vl{z} - \vl{r}$. $P_1, P_2$ execute $\prot{\JSh}(P_1, P_2, \vl{p})$ to generate $\shr{\vl{p}}$.

* Parties locally compute $\shr{\vl{o}} = \shr{\vl{p}} + \shr{\vl{q}}$. Here $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{z}$ otherwise.

Protocol $\piMultR$ (fig:piMultGOD) (in $\FthisB$) requires $3 \ell$ bits of communication in the preprocessing phase, and $1$ round and $3 \ell$ bits of communication in the online phase.

During preprocessing, the sampling of values ${\vl{u}}^1, {\vl{u}}^2$ are performed non-interactively using $\Func[Setup]$. A communication of $\ell$ bits is required for the joint sharing of $\vl{q}$ by $P_0, P_3$ as explained in <ref>. In addition, $P_0, P_j$ for $j \in \{1,2\}$ communicates $\vl{w}_j$ to $P_3$ via $\jsend$ requiring additional $2\ell$ bits.
The online phase is similar to the fair multiplication protocol ($\prot{\Mult}$) and the costs follow from Lemma <ref>.

§.§ Multi-input Multiplication

The goal of 3-input multiplication is to generate $\shr{\cdot}$-sharing of $\vl{z} = \vl{a} \vl{b} \vl{c}$ given $\shr{\vl{a}}, \shr{\vl{b}}, \shr{\vl{c}}$. For this parties proceed similar to the multiplication protocol (see <ref>), where they compute $\shr{\vl{z}} = \shr{\vl{z} - \vl{r}} + \shr{\vl{r}}$. Observe that

\begin{align*}
\vl{z} - \vl{r}
&= \vl{a} \vl{b} \vl{c} - \vl{r} = (\mk{\vl{a}} - \pd{\vl{a}})(\mk{\vl{b}} - \pd{\vl{b}})(\mk{\vl{c}} - \pd{\vl{c}}) - \vl{r} \\
&= \mk{\vl{a}\vl{b}\vl{c}} - \mk{\vl{a}\vl{c}} \pd{\vl{b}} - \mk{\vl{b}\vl{c}} \pd{\vl{a}} - \mk{\vl{a}\vl{b}} \pd{\vl{c}} + \mk{\vl{a}} \gm{\vl{b} \vl{c}}{} +  \mk{\vl{b}} \gm{\vl{a} \vl{c}}{} + \mk{\vl{c}} \gm{\vl{a} \vl{b}}{} - \gm{\vl{a} \vl{b} \vl{c}}{} - \vl{r}
\end{align*}

Similar to the 2-input fair multiplication $\prot{\Mult}$ (fig:piMultiplication), the goal of the preprocessing phase is to generate additive shares of $\gm{\vl{ab}}{}, \gm{\vl{ac}}{}, \gm{\vl{bc}}{},  \gm{\vl{abc}}{} + \vl{r}$ among $P_1, P_2$.

Informally, the terms that $P_1, P_2$ cannot compute locally for the aforementioned $\gm{}{}$ values, can be computed by $P_0, P_3$, as evident from our sharing semantics. $P_0, P_3$ compute the missing terms and share them among $P_1, P_2$ in the preprocessing phase. $P_1, P_2$ proceed with online phase similar to $\prot{\Mult}$, to compute $\vl{z} - \vl{r}$. Thus the online complexity is retained as that of $\prot{\Mult}$ while the preprocessing communication is increased to 9 elements. The protocol appears in fig:piMultT.

$\prot{\MultT}(\vl{a}, \vl{b}, \vl{c}, \isTr)$3-input fair multiplication in $\Fthis$.fig:piMultT
$\isTr$ is a bit denoting whether truncation is required ($\isTr =1$) or not ($\isTr=0$).

Input(s): $\shr{\vl{a}}, \shr{\vl{b}}, \shr{\vl{c}}$.

Output: $\shr{\vl{o}}$ where $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{o} = \vl{z}$ if $\isTr = 0$ and $\vl{z} = \vl{abc}$.

* Computation for $\gm{\vl{ab}}{}$: Invoke $\prot{\MultS}$ (fig:piMultS) on $\sgr{\padR{\vl{a}}}$ and $\sgr{\padR{\vl{b}}}$ to generate $\sgr{\gm{\vl{ab}}{}}$.

* Computation for $\gm{\vl{ac}}{}$:

– Parties locally compute the following:

\begin{align*}
P_0, P_1: \gm{\vl{ac}}{1}  &= \pad{\vl{a}}{1} \pad{\vl{c}}{3} + \pad{\vl{a}}{3} \pad{\vl{c}}{1} + \pad{\vl{a}}{3} \pad{\vl{c}}{3}\\
P_0, P_2: \gm{\vl{ac}}{2} &= \pad{\vl{a}}{2} \pad{\vl{c}}{3} + \pad{\vl{a}}{3} \pad{\vl{c}}{2} + \pad{\vl{a}}{2} \pad{\vl{c}}{2}\\
P_0, P_3: \gm{\vl{ac}}{3} &= \pad{\vl{a}}{1} \pad{\vl{c}}{2} + \pad{\vl{a}}{2} \pad{\vl{c}}{1} + \pad{\vl{a}}{1} \pad{\vl{c}}{1}
\end{align*}

– $P_0, P_3$ and $P_1$ sample random ${\vl{u}}_{\vl{ac}}^1 \in_R \Z{\ell}$. $P_0, P_3$ compute and $\jsend$ ${\vl{u}}_{\vl{ac}}^2 = \gm{\vl{ac}}{3} - {\vl{u}}_{\vl{ac}}^1$ to $P_2$.

–  $P_0, P_1, P_2$ sample random ${\vl{s}}_{\vl{ac}} \in_R \Z{\ell}$. $P_0$ sends ${\vl{w}}_{\vl{ac}} = \gm{\vl{ac}}{1} + \gm{\vl{ac}}{2} + {\vl{s}}_{\vl{ac}}$ to $P_3$.

* Computation for $\gm{\vl{bc}}{}$: Similar to Step 2 (for $\gm{\vl{ac}}{}$). $P_1, P_2$ obtain ${\vl{u}}_{\vl{bc}}^1, {\vl{u}}_{\vl{bc}}^2$ respectively such that ${\vl{u}}_{\vl{bc}}^1 + {\vl{u}}_{\vl{bc}}^2 = \gm{\vl{bc}}{3}$ . $P_3$ obtains ${\vl{w}}_{\vl{bc}}  = \gm{\vl{bc}}{1} + \gm{\vl{bc}}{2} + {\vl{s}}_{\vl{bc}}$.

* Computation for $\gm{\vl{abc}}{}$:

– Using $\gm{\vl{ab}}{}$ (Step 1), $\pad{\vl{c}}{}$, compute the following:

\begin{align*}
P_0, P_1: \gm{\vl{abc}}{1}  &= \gm{\vl{ab}}{1} \pad{\vl{c}}{3} + \gm{\vl{ab}}{3} \pad{\vl{c}}{1} + \gm{\vl{ab}}{3} \pad{\vl{c}}{3}\\
P_0, P_2: \gm{\vl{abc}}{2} &= \gm{\vl{ab}}{2} \pad{\vl{c}}{3} + \gm{\vl{ab}}{3} \pad{\vl{c}}{2} + \gm{\vl{ab}}{2} \pad{\vl{c}}{2}\\
P_0, P_3: \gm{\vl{abc}}{3} &= \gm{\vl{ab}}{1} \pad{\vl{c}}{2} + \gm{\vl{ab}}{2} \pad{\vl{c}}{1} + \gm{\vl{ab}}{1} \pad{\vl{c}}{1}
\end{align*}

– $P_0, P_3$ and $P_j$ sample random ${\vl{u}}_{\vl{abc}}^j \in_R \Z{\ell}$ for $j \in \{1,2\}$. Let ${\vl{u}}_{\vl{abc}}^1 + {\vl{u}}_{\vl{abc}}^2 = \gm{\vl{abc}}{3} + \vl{r}$ for $\vl{r} \in_R \Z{\ell}$.

–  $P_0, P_1, P_2$ sample random ${\vl{s}} \in_R \Z{\ell}$. $P_0$ sends ${\vl{w}}_{\vl{abc}} = \gm{\vl{abc}}{1} + \gm{\vl{abc}}{2} + {\vl{s}}$ to $P_3$.

* $P_0, P_3$ compute $\vl{r} = {\vl{u}}_{\vl{abc}}^1 + {\vl{u}}_{\vl{abc}}^2 - \gm{\vl{abc}}{3}$ and set $\vl{q} = \vl{r}^{\vl{t}}$  if $\isTr = 1$, else set $\vl{q} = \vl{r}$. Execute $\prot{\JSh}(P_0, P_3, \vl{q})$ to generate $\shr{\vl{q}}$.

Online: Let $\vl{y} = (\vl{z} - \vl{r}) - \mk{\vl{abc}}$.

* Parties locally compute the following:

\begin{align*}
P_1: \vl{y}_1 &= - \pad{\vl{a}}{1} \mk{\vl{bc}} - \pad{\vl{b}}{1} \mk{\vl{ac}} - \pad{\vl{c}}{1} \mk{\vl{ab}}
+ \gm{\vl{ab}}{1} \mk{\vl{c}} + (\gm{\vl{ac}}{1} + {\vl{u}}_{\vl{ac}}^1) \mk{\vl{b}} + (\gm{\vl{bc}}{1} + {\vl{u}}_{\vl{bc}}^1) \mk{\vl{a}} - (\gm{\vl{a}\vl{bc}}{1} + {\vl{u}}_{\vl{a}\vl{bc}}^1)\\
P_2: \vl{y}_2 &= - \pad{\vl{a}}{2} \mk{\vl{bc}} - \pad{\vl{b}}{2} \mk{\vl{ac}} - \pad{\vl{c}}{2} \mk{\vl{ab}}
+ \gm{\vl{ab}}{2} \mk{\vl{c}} + (\gm{\vl{ac}}{2} + {\vl{u}}_{\vl{ac}}^2) \mk{\vl{b}} - (\gm{\vl{bc}}{2} + {\vl{u}}_{\vl{bc}}^2) \mk{\vl{a}} - (\gm{\vl{a}\vl{bc}}{2} + {\vl{u}}_{\vl{a}\vl{bc}}^2)\\
P_1, P_2: \vl{y}_3 &= - \pad{\vl{a}}{3} \mk{\vl{bc}} - \pad{\vl{b}}{3} \mk{\vl{ac}} - \pad{\vl{c}}{3} \mk{\vl{ab}} + \gm{\vl{ab}}{3} \mk{\vl{c}}
\end{align*}

* $P_1$ sends $\vl{y}_2$ to $P_2$, while $P_2$ sends $\vl{y}_1$ to $P_1$, and they locally compute $\vl{z} - \vl{r} = (\vl{y}_1 + \vl{y}_2 + \vl{y}_3) + \mk{\vl{abc}}$.

* If $\isTr = 1$, $P_1, P_2$ locally set $\vl{p} = (\vl{z} - \vl{r})^{\vl{t}}$, else $\vl{p} = \vl{z} - \vl{r}$. Execute $\prot{\JSh}(P_1, P_2, \vl{p})$ to generate $\shr{\vl{p}}$.

* Parties locally compute $\shr{\vl{o}} = \shr{\vl{p}} + \shr{\vl{q}}$. Here $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{z}$ otherwise.

* Verification:

– Parties locally compute the following:

\begin{align*}
P_3: \vl{v} &= - (\pad{\vl{a}}{1} + \pad{\vl{a}}{2})\mk{\vl{bc}} - (\pad{\vl{b}}{1} + \pad{\vl{b}}{2} )\mk{\vl{ac}} - (\pad{\vl{c}}{1} + \pad{\vl{c}}{2}) \mk{\vl{ab}} +(\gm{\vl{ab}}{1} + \gm{\vl{ab}}{2})\mk{\vl{c}} + ({\vl{w}}_{\vl{ac}} + \gm{\vl{ac}}{3}) \mk{\vl{b}} \\
&~~~+ ({\vl{w}}_{\vl{bc}} + \gm{\vl{bc}}{3}) \mk{\vl{a}} - ({\vl{w}}_{\vl{abc}} + \gm{\vl{abc}}{3} + \vl{r})\\
P_1, P_2: \vl{v}' &=  \vl{y}_1 + \vl{y}_2 + {\vl{s}}_{\vl{ac}} \mk{\vl{b}} + {\vl{s}}_{\vl{bc}} \mk{\vl{a}} - {\vl{s}}
\end{align*}

– $P_3$ sends $\Hash(\vl{v})$ to $P_1, P_2$, who $\abort$ iff $\Hash(\vl{v}) \ne \Hash(\vl{v}')$.

Protocol $\prot{\MultT}$ (fig:piMultT) (in $\Fthis$) requires $9 \ell$ bits of communication in preprocessing, and $1$ round and $3 \ell$ bits of communication in the online phase.

In the preprocessing, computation of $\gm{\vl{ab}}{}$ involves three instances of $\jsend$. Each of the computation of $\gm{\vl{ac}}{}, \gm{\vl{bc}}{}$ involves one instance of $\jsend$ and a communication from $P_0$ to $P_3$. The computation of $\gm{\vl{abc}}{}$ is similar to the preprocessing of fair multiplication protocol (fig:piMultiplication). The communication pattern of the online phase is similar to that of the fair multiplication protocol. The costs follow from Lemma <ref> and Lemma <ref>.

Analogously, $\piMultRT$ can be extended to support 3-input multiplication while costing $12$ elements communication in preprocessing. The protocol appears in fig:piMultTrobust.

$\piMultRT(\vl{a}, \vl{b}, \vl{c}, \isTr)$3-input robust multiplication in $\FthisB$.fig:piMultTrobust
$\isTr$ is a bit denoting whether truncation is required ($\isTr =1$) or not ($\isTr=0$).

Input(s): $\shr{\vl{a}}, \shr{\vl{b}}, \shr{\vl{c}}$.

Output: $\shr{\vl{o}}$ where $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{o} = \vl{z}$ if $\isTr = 0$ and $\vl{z} = \vl{abc}$.

* Computation for $\gm{\vl{ab}}{}$: Invoke $\prot{\MultS}$ (fig:piMultS) on $\sgr{\padR{\vl{a}}}$ and $\sgr{\padR{\vl{b}}}$ to generate $\sgr{\gm{\vl{ab}}{}}$.

* Computation for $\gm{\vl{ac}}{}, \gm{\vl{bc}}{}$: Similar to Step 1 (for $\gm{\vl{ab}}{}$).

* Computation for $\gm{\vl{abc}}{}$:

– Using $\gm{\vl{ab}}{}$ (Step 1), $\pad{\vl{c}}{}$, compute the following:

\begin{align*}
P_0, P_1: \gm{\vl{abc}}{1}  &= \gm{\vl{ab}}{1} \pad{\vl{c}}{3} + \gm{\vl{ab}}{3} \pad{\vl{c}}{1} + \gm{\vl{ab}}{3} \pad{\vl{c}}{3}\\
P_0, P_2: \gm{\vl{abc}}{2} &= \gm{\vl{ab}}{2} \pad{\vl{c}}{3} + \gm{\vl{ab}}{3} \pad{\vl{c}}{2} + \gm{\vl{ab}}{2} \pad{\vl{c}}{2}\\
P_0, P_3: \gm{\vl{abc}}{3} &= \gm{\vl{ab}}{1} \pad{\vl{c}}{2} + \gm{\vl{ab}}{2} \pad{\vl{c}}{1} + \gm{\vl{ab}}{1} \pad{\vl{c}}{1}
\end{align*}

– $P_0, P_3$ and $P_j$ sample random ${\vl{u}}_{\vl{abc}}^j \in_R \Z{\ell}$ for $j \in \{1,2\}$. Let ${\vl{u}}_{\vl{abc}}^1 + {\vl{u}}_{\vl{abc}}^2 = \gm{\vl{abc}}{3} + \vl{r}$ for $\vl{r} \in_R \Z{\ell}$.

–  $P_0, P_1, P_2$ sample random ${\vl{s}}_1, {\vl{s}}_2 \in_R \Z{\ell}$. $P_0, P_j$ $\jsend$ $\vl{w}^j = \gm{\vl{abc}}{j} + {\vl{s}}_j$ to $P_3$  for $j \in \{1,2\}$.

* $P_0, P_3$ compute $\vl{r} = {\vl{u}}_{\vl{abc}}^1 + {\vl{u}}_{\vl{abc}}^2 - \gm{\vl{abc}}{3}$ and set $\vl{q} = \vl{r}^{\vl{t}}$  if $\isTr = 1$, else set $\vl{q} = \vl{r}$. Execute $\prot{\JSh}(P_0, P_3, \vl{q})$ to generate $\shr{\vl{q}}$.

Online: Let $\vl{y} = (\vl{z} - \vl{r}) - \mk{\vl{abc}} - \vl{s}_1 - \vl{s}_2$.

* Parties locally compute the following:

\begin{align*}
P_0, P_1: \vl{y}_1 &= - \pad{\vl{a}}{1} \mk{\vl{bc}} - \pad{\vl{b}}{1} \mk{\vl{ac}} - \pad{\vl{c}}{1} \mk{\vl{ab}}
+ \gm{\vl{ab}}{1} \mk{\vl{c}} + \gm{\vl{ac}}{1} \mk{\vl{b}} + \gm{\vl{bc}}{1} \mk{\vl{a}} - ({\vl{u}}_{\vl{abc}}^1 + \vl{w}^1)\\
P_0, P_2: \vl{y}_2 &= - \pad{\vl{a}}{2} \mk{\vl{bc}} - \pad{\vl{b}}{2} \mk{\vl{ac}} - \pad{\vl{c}}{2} \mk{\vl{ab}}
+ \gm{\vl{ab}}{2} \mk{\vl{c}} + \gm{\vl{ac}}{2} \mk{\vl{b}} + \gm{\vl{bc}}{2} \mk{\vl{a}}  - ({\vl{u}}_{\vl{abc}}^2 + \vl{w}^2)\\
P_1, P_2: \vl{y}_3 &= - \pad{\vl{a}}{3} \mk{\vl{bc}} - \pad{\vl{b}}{3} \mk{\vl{ac}} - \pad{\vl{c}}{3} \mk{\vl{ab}} + \gm{\vl{ab}}{3} \mk{\vl{c}} + \gm{\vl{ac}}{3} \mk{\vl{b}} + \gm{\vl{bc}}{3} \mk{\vl{a}}
\end{align*}

* $P_1, P_3$ $\jsend$ $\vl{y}_1$ to $P_2$, while $P_2, P_3$ $\jsend$ $\vl{y}_2$ to $P_1$. $P_1, P_2$ locally compute $\vl{z} - \vl{r} = (\vl{y}_1 + \vl{y}_2 + \vl{y}_3) + \mk{\vl{abc}} + \vl{s}_1 + \vl{s}_2$.

* If $\isTr = 1$, $P_1, P_2$ set $\vl{p} = (\vl{z} - \vl{r})^{\vl{t}}$, else $\vl{p} = \vl{z} - \vl{r}$. Execute $\prot{\JSh}(P_1, P_2, \vl{p})$ to generate $\shr{\vl{p}}$.

* Parties locally compute $\shr{\vl{o}} = \shr{\vl{p}} + \shr{\vl{q}}$. Here $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{z}$ otherwise.

Protocol $\piMultRT$ (fig:piMultTrobust) (in $\FthisB$) requires $12 \ell$ bits of communication in preprocessing, and $1$ round and $3 \ell$ bits of communication in the online phase.

In the preprocessing, computation of each of $\gm{\vl{ab}}{}, \gm{\vl{ac}}{}, \gm{\vl{bc}}{}$ involves three instances of $\jsend$. The computation of $\gm{\vl{abc}}{}$ is similar to the preprocessing of robust multiplication protocol (fig:piMultGOD). The communication pattern of the online phase is similar to that of the robust multiplication protocol. The costs follow from Lemma <ref> and Lemma <ref>.

To obtain $\shr{\cdot}$-sharing of $\vl{z}= \vl{a} \vl{b} \vl{c} \vl{d}$ given the $\shr{\cdot}$-sharing of $\vl{a}, \vl{b}, \vl{c}, \vl{d}$, we can write $\vl{z} - \vl{r}$ as

\begin{align}\label{eq:4pcMmultF}
\vl{z} - \vl{r} &= \vl{abcd} - \vl{r} = (\mk{\vl{a}} - \pd{\vl{a}})(\mk{\vl{b}} - \pd{\vl{b}})(\mk{\vl{c}} - \pd{\vl{c}})(\mk{\vl{d}} - \pd{\vl{d}}) - \vl{r} \nonumber\\
&= \mk{\vl{abcd}} - \mk{\vl{abc}}\pd{\vl{d}} - \mk{\vl{abd}}\pd{\vl{c}} - \mk{\vl{acd}}\pd{\vl{b}} - \mk{\vl{bcd}}\pd{\vl{a}}
+ \mk{\vl{ab}}\gm{\vl{cd}}{} + \mk{\vl{ac}}\gm{\vl{bd}}{} + \mk{\vl{ad}}\gm{\vl{bc}}{} + \mk{\vl{bc}}\gm{\vl{ad}}{} \nonumber\\
&~~~+ \mk{\vl{bd}}\gm{\vl{ac}}{} + \mk{\vl{cd}}\gm{\vl{ab}}{}
- \mk{\vl{a}}\gm{\vl{bcd}}{} - \mk{\vl{b}}\gm{\vl{acd}}{} - \mk{\vl{c}}\gm{\vl{abd}}{} - \mk{\vl{d}}\gm{\vl{abc}}{} + \gm{\vl{abcd}}{} - \vl{r}
~~\text{\footnotesize{(cf. notation~\ref{notation:4pcconcise})}}
\end{align}

While the online phase proceeds similarly to the 2 and 3-input multiplication, in the preprocessing phase, the parties need to generate the additive shares of $\gm{\vl{ab}}{}$,$\gm{\vl{ac}}{}$,$\gm{\vl{ad}}{}$,$\gm{\vl{bc}}{}$,$\gm{\vl{bd}}{}$,$\gm{\vl{cd}}{}$,$\gm{\vl{abc}}{}$,$\gm{\vl{abd}}{}$,$\gm{\vl{acd}}{}$,$\gm{\vl{bcd}}{}$ and $\gm{\vl{abcd}}{} - \vl{r}$. This is computed similarly as in the case of 3-input multiplication as follows.

Parties generate shares of $\gm{\vl{ac}}{}, \gm{\vl{ad}}{}, \gm{\vl{bc}}{}, \gm{\vl{bd}}{}$ similar to the generation of shares of $\gm{\vl{ac}}{}$ in the 3-input multiplication. For $\gm{\vl{ab}}{}, \gm{\vl{cd}}{}$, parties proceed similar to generation of shares of $\gm{\vl{ab}}{}$ in the 3-input multiplication, where the respective $\sgr{\cdot}$-shares are generated. This is followed by generation of shares of $\gm{\vl{abc}}{}, \gm{\vl{abd}}{}, \gm{\vl{acd}}{}, \gm{\vl{bcd}}{}, \gm{\vl{abcd}}{}$ following steps similar to the ones involved in generating $\gm{\vl{abcc}}{}$ in the 3-input multiplication. Since the protocol is very similar to the 3-input protocol, we omit the formal details.

§.§ Supporting on-demand computations

For on-demand applications where the underlying function to be computed is not known in advance, the preprocessing model is not desirable. We observe that the $\Fthis$ protocol can be modified by executing the preprocessing phase in the online phase itself, keeping the same overall communication cost. The formal protocol appears in fig:piMultNoPre.

We provide the fair multiplication, $\piMultO$, for function-independent preprocessing in fig:piMultNoPre. The protocol incurs no overhead over the fair multiplication ($\prot{\Mult}$) in $\Fthis$. This is due to the design of $\prot{\Mult}$ where values ${\vl{u}}^1, {\vl{u}}^2$ are sampled non-interactively in the preprocessing. Thus the joint-sharing by $P_0, P_3$ (Step 5 (a) in fig:piMultNoPre) can be performed along with the communication among $P_1, P_2$ (Step 4 in fig:piMultNoPre) in the online. Moreover, the rest of the communication can be deferred till the verification stage and thus, the online round complexity is retained. The protocol for robust setting is similar.

$\piMultO(\vl{a}, \vl{b}, \isTr)$Fair multiplication without preprocessing in $\Fthis$.fig:piMultNoPre
$\isTr$ is a bit denoting whether truncation is required ($\isTr =1$) or not ($\isTr=0$).

Input(s): $\shr{\vl{a}}, \shr{\vl{b}}$.

Output: $\shr{\vl{o}}$ where $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{o} = \vl{z}$ if $\isTr = 0$ and $\vl{z} = \vl{ab}$.

* Parties locally compute the following:

\begin{align*}
P_0, P_1: \gm{\vl{a}\vl{b}}{1} &= \pad{\vl{a}}{1} \pad{\vl{b}}{3} + \pad{\vl{a}}{3} \pad{\vl{b}}{1} + \pad{\vl{a}}{3} \pad{\vl{b}}{3} \\
P_0, P_2: \gm{\vl{a}\vl{b}}{2} &= \pad{\vl{a}}{2} \pad{\vl{b}}{3} + \pad{\vl{a}}{3} \pad{\vl{b}}{2} + \pad{\vl{a}}{2} \pad{\vl{b}}{2} \\
P_0, P_3: \gm{\vl{a}\vl{b}}{3} &= \pad{\vl{a}}{1} \pad{\vl{b}}{2} + \pad{\vl{a}}{2} \pad{\vl{b}}{1} + \pad{\vl{a}}{1} \pad{\vl{b}}{1}
\end{align*}

* $P_0, P_3$ and $P_j$ sample random ${\vl{u}}^j \in_R \Z{\ell}$ for $j \in \{1,2\}$. Let ${\vl{u}^1} + \vl{u}^2 = \gm{\vl{a}\vl{b}}{3} - \vl{r}$ for a random $\vl{r} \in_R \Z{\ell}$.

* Let $\vl{y} = (\vl{z} - \vl{r}) - \mk{\vl{a}} \mk{\vl{b}}$. Parties locally compute the following:

\begin{align*}
P_1: \vl{y}_1 &= - \pad{\vl{a}}{1} \mk{\vl{b}} - \pad{\vl{b}}{1} \mk{\vl{a}} + \gm{\vl{a}\vl{b}}{1} + {\vl{u}}^1 \\
P_2: \vl{y}_2 &= - \pad{\vl{a}}{2} \mk{\vl{b}} - \pad{\vl{b}}{2} \mk{\vl{a}} + \gm{\vl{a}\vl{b}}{2} + {\vl{u}}^2 \\
P_1, P_2: \vl{y}_3 &= - \pad{\vl{a}}{3} \mk{\vl{b}} - \pad{\vl{b}}{3} \mk{\vl{a}}
\end{align*}

* $P_1$ sends $\vl{y}_1$ to $P_2$, while $P_2$ sends $\vl{y}_2$ to $P_1$.

* Parties proceed as follows:

* $P_0, P_3$: $\vl{r} = \gm{\vl{a}\vl{b}}{3} - {\vl{u}^1} - \vl{u}^2$; $\vl{q} = \vl{r}^{\vl{t}}$  if $\isTr = 1$, else $\vl{q} = \vl{r}$; Execute $\prot{\JSh}(P_0, P_3, \vl{q})$.

* $P_1, P_2$: $\vl{z} - \vl{r} = (\vl{y}_1 + \vl{y}_2 + \vl{y}_3) + \mk{\vl{a}} \mk{\vl{b}}$; $\vl{p} = (\vl{z} - \vl{r})^{\vl{t}}$ if $\isTr = 1$, else $\vl{p} = \vl{z} - \vl{r}$; Execute $\prot{\JSh}(P_1, P_2, \vl{p})$.

* Parties locally compute $\shr{\vl{o}} = \shr{\vl{p}} + \shr{\vl{q}}$. Here $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{z}$ otherwise.

* $P_0, P_1, P_2$ sample random ${\vl{s}} \in_R \Z{\ell}$. $P_0$ sends $\vl{w} = \gm{\vl{a}\vl{b}}{1} + \gm{\vl{a}\vl{b}}{2} + {\vl{s}}$ to $P_3$.

* $P_3$ computes $\vl{v} = - (\pad{\vl{a}}{1} + \pad{\vl{a}}{2}) \mk{\vl{b}} - (\pad{\vl{b}}{1} + \pad{\vl{b}}{2}) \mk{\vl{a}} + {\vl{u}^1} + \vl{u}^2 + \vl{w}$ and sends $\Hash(\vl{v})$ to $P_1$ and $P_2$. Parties $P_1, P_2$ $\abort$ iff $\Hash(\vl{v}) \ne \Hash(\vl{y}_1 + \vl{y}_2 + {\vl{s}})$.

§.§.§ Comparison with  Fantastic Four <cit.>

We analyse the performance of Fantastic Four <cit.> where execution proceeds in segments (cf. 6.4, <cit.>). Elaborately, computation is carried out optimistically for each segment, followed by a verification phase before proceeding to the next segment. If verification fails, the current segment is recomputed via an active 3PC protocol. Subsequent segments also proceed with a 3PC execution until the verification fails again. In this case, a semi-honest 2PC with a helper is carried out for the current and rest of the segments. For analysis, we consider their best and worst-case execution cost.

r r r c

2-1Work     2cDot Product w/ Truncation
Preprocessing     Online

Fantastic Four: Case I        $\ell$      $9\ell$      4

Fantastic Four: Case II       $76(\ell+\kappa)+54x + 12$      $9\ell + 6\kappa$      3

(on-demand)           -            $5\ell$      3

(on-demand)           -            $6\ell$      3

Comparison with Fantastic Four <cit.>

Observe that the best case happens when the verification is always successful, which we call as Case I. In this case, the communication cost is that of the 4PC execution. Note that an adversary can always make the verification fail in the first segment itself. This results in executing the entire protocol (all segments) with their active 3PC, which accounts for their worst-case cost. We denote this as Case II. Their 3PC protocols are designed to work over the extended ring of size $\ell + \kappa$ bits. As evident from Tables 2, 3 of their paper, their 3PC is at least $10 \times$ more expensive than their 4PC in terms of both runtime and communication. Thus, the higher cost of 3PC defeats the purpose of having an additional honest party in the system.

Observe that their protocols are designed to work with a function-independent preprocessing. Thus, for a fair comparison, we compare both cases against the on-demand variants of our robust protocols (, ). The results are summarised in compFour. We remark that the values for their cases are obtained from Table 1 of their paper <cit.>.

§ GARBLED WORLD

In the applications we consider, the garbled circuit is used as an intermediary to evaluate certain functions where the input to the function as well as the output are in $\shr{\cdot}$-shared (or $\shrB{\cdot}$-shared) form.

Instantiating the garbled world using existing 4PC GC-based protocols <cit.> turn out to be overkill, as they are standalone protocols. For instance, <cit.> provides robust protocols by communicating $12$ GCs while <cit.> requires generating and exchanging commitments on the inputs to ensure input consistency. On the other hand, the inputs to our protocol are consistent (due to $\shr{\cdot}$-sharing), and we do not need an explicit reconstruction, making it lighter overall.

Towards this, we propose 2 GC protocols – $\FthisT$ requiring communication of 2 GC evaluations and 1 online round, and $\FthisC$ requiring 1 GC and 2 rounds. Moreover, these protocols leverage the benefit of amortization which comes from using $\jsend$.

The 2 GC variant has two parallel executions, each comprising of 3 garblers and 1 evaluator. $P_1, P_2$ act as evaluators in two independent executions and the parties in $\PlSet{1} = \{P_0, P_2, P_3\}$, $\PlSet{2} = \{P_0, P_1 ,P_3\}$ act as garblers, respectively. The 1 GC variant comprises of a single execution with $\PlSet{1}$ acting as garblers and $P_1$ as the evaluator.

Leveraging an honest majority among the garblers and using $\jsend$, we only need semi-honest GC computation to get active security.

§.§ 2 GC Variant

Input Phase

Given that the function  input $\vl{x}$ is already available as $\shrB{\vl{x}}$, the boolean values $\mk{\vl{x}}, \av{\vl{x}}, \pad{\vl{x}}{3}$, where $\av{\vl{x}} = \pad{\vl{x}}{1} \xor \pad{\vl{x}}{2}$ and $\vl{x} = \mk{\vl{x}} \xor \av{\vl{x}} \xor \pad{\vl{x}}{3}$, act as the new inputs for the garbled computation, and garbled sharing ($\shrG{\cdot}$) is generated for each of these values. The semantics of $\shrB{\cdot}$-sharing ensures that each of these shares ($\mk{\vl{x}}, \av{\vl{x}}, \pad{\vl{x}}{3}$) is available with two garblers in each garbling instance. The keys for the shares can either be sent (using $\jsend$) correctly to the evaluators or the inconsistency is detected. This key delivery essentially generates  $\shrG{\cdot}$-sharing for each of these three values  which enables GC evaluation. Thus, the goal of our input phase is to create the compound sharing, $\shrC{\vl{x}} = (\shrG{\mk{\vl{x}}}, \shrG{\av{\vl{x}}}, \shrG{\pad{\vl{x}}{3}})$ for every input $\vl{x}$ to the function to be evaluated via the GC. We first discuss the semantics for $\shrG{\cdot}$-sharing followed by steps for generating $\shrC{\cdot}$-sharing.

Garbled sharing semantics

A value $\vl{v} \in \Z{}$  is $\shrG{\cdot}$-shared (garbled shared) amongst  $\Partyset$ if $P_i \in \{P_0, P_3\}$ holds $\shrG{\vl{v}}_{i}= (\key{{\vl{v}}}{0,1}, \key{{\vl{v}}}{0,2})$, $P_1$ holds $\shrG{\vl{v}}_{1} = (\key{{\vl{v}}}{\vl{v},1}, \key{{\vl{v}}}{0,2})$ and $P_2$ holds $\shrG{\vl{v}}_{2} = (\key{{\vl{v}}}{0,1}, \key{{\vl{v}}}{\vl{v},2})$. Here, $\key{{\vl{v}}}{\vl{v}, j} = \key{{\vl{v}}}{0, j} \xor \vl{v} \Delta^{j}$ for $j \in \{1, 2\}$, and $\Delta^{j}$, which is known only to the garblers in $\PlSet{j}$, denotes the global offset with its least significant bit set to $1$ and is same for every wire in the circuit.

A value $\vl{x} \in \Z{}$ is said to be $\shrC{\cdot}$-shared (compound shared) if each value  from $(\mk{\vl{x}}, \av{\vl{x}}, \pad{\vl{x}}{3})$, which are as defined above, is $\shrG{\cdot}$-shared. We write $\shrC{\vl{x}} = (\shrG{\mk{\vl{x}}},\shrG{\av{\vl{x}}},\shrG{\pad{\vl{x}}{3}})$.

Generation of $\shrG{\vl{v}}$ and $\shrC{\vl{x}}$

Protocol $\pigsh(\Partyset, \vl{v})$ (fig:pigsh4pc) enables generation of $\shrG{\vl{v}}$ where two garblers in each garbling instance hold $\vl{v}$, and proceeds as follows. Consider the first garbling instance with evaluator $P_1$ where garblers $P_k, P_l$ hold $\vl{v}$. Garblers in $\PlSet{1}$ generate $\{\key{{{\vl{v}}}}{\bitb, 1}\}_{\bitb \in \{0, 1\}}$ which denotes the key for value $\bitb$ on wire $\vl{v}$, following the free-XOR technique <cit.>.
$P_k, P_l$ $\jsend$ $\key{{{\vl{v}}}}{\vl{v}, 1}$ to evaluator $P_1$. Similar steps carried out with respect to the second garbling instance, at the end of which, garblers in $\PlSet{2}$ possess $\{\key{\vl{v}}{\bitb, 2}\}_{\bitb \in \{0,1\}}$ while the evaluator $P_2$ holds $\key{\vl{v}}{\vl{v}, 2}$. Following this, the shares $\shrG{\vl{v}}_s$ held by $P_s \in \Partyset$ are defined as $\shrG{\vl{v}}_0 = \shrG{\vl{v}}_3 = (\key{\vl{v}}{0, 1}, \key{\vl{v}}{0, 2})$, $\shrG{\vl{v}}_1 = (\key{\vl{v}}{\vl{v}, 1}, \key{\vl{v}}{0, 2})$, $\shrG{\vl{v}}_2 = (\key{\vl{v}}{0, 1}, \key{\vl{v}}{\vl{v}, 2})$.

$\pigsh(\Partyset, \vl{v})$Generation of $\shrG{\vl{v}}$fig:pigsh4pc

* Garblers in $\PlSet{j}$ for $j \in \{1, 2\}$ generate keys $\key{{\vl{v}}}{0, j}, \key{{\vl{v}}}{1, j}$ for wire $\vl{v}$, using free-XOR technique.

* Let $P_k^j, P_l^j$ denote the garblers in the $j^{\text{th}}$ garbling instance, for $j \in \{1, 2\}$, who hold $\vl{v} \in \Z{}$. $P_k^j, P_l^j$ $\jsend$ $\key{\vl{v}}{\vl{v}, j}$ to evaluator $P_j$.

* $P_i \in \{P_0, P_3\}$ sets $\shrG{\vl{v}}_i = (\key{{\vl{v}}}{0,1}, \key{{\vl{v}}}{0,2})$, $P_1$ sets $\shrG{\vl{v}}_{1} = (\key{{\vl{v}}}{\vl{v},1}, \key{{\vl{v}}}{0,2})$ and $P_2$ sets $\shrG{\vl{v}}_{2} = (\key{{\vl{v}}}{0,1}, \key{{\vl{v}}}{\vl{v},2})$.

To generate $\shrC{\vl{x}}$, we need a way to generate  $(\shrG{\mk{\vl{x}}}, \shrG{\av{\vl{x}}}, \shrG{\pad{\vl{x}}{3}})$, given $\shrB{\vl{x}}$. For this, $\pigsh$ is invoked for each of $\mk{\vl{x}}, \av{\vl{x}}, \pad{\vl{x}}{3}$.

Let $f(\vl{x})$ be the function to be evaluated. At this point, the function input is $\shrC{\cdot}$-shared. This renders $\shrG{\cdot}$-sharing for the input of the GC that corresponds to the function $f'\big({\mk{\vl{x}}}, {\av{\vl{x}}}, {\pad{\vl{x}}{3}} \big)$ which first combines the given boolean-shares to compute the actual input and then applies $f$ on it. Let $\GC_j$ denote the garbled circuit to be sent to $P_j \in \{P_1, P_2\}$ by garblers in $\PlSet{j}$. Sending of $\GC_j$ is overlapped  with the key transfer (during generation of $\shrC{\vl{x}}$), to save rounds, where garblers in $\{P_0, P_3\}$ $\jsend$ $\GC_j$ to $P_j$. On receiving the $\GC$, evaluators evaluate their respective GCs and obtain the key corresponding to the output, say $\vl{z}$. This generates $\shrG{\vl{z}}$.

Output phase

The goal of output computation is to compute the output $\vl{z}$ from $\shrG{\vl{z}}$.
To reconstruct $\vl{z}$ towards $P_j \in \{P_1, P_2\}$, two garblers in $\PlSet{j}$ send the least significant bit $\vl{p}^j$ of $\key{\vl{z}}{0, j}$, referred to as the decoding information, to $P_j$. If the received values are consistent, $P_j$ uses the received $\vl{p}^j$ to reconstruct $\vl{z}$ as $\vl{z} = \vl{p}^j \xor \vl{q}^j$, where $\vl{q}^j$ denotes the least significant bit of $\key{\vl{z}}{\vl{z}, j}$; else $P_j$ aborts.

To reconstruct $\vl{z}$ towards the garblers $P_g \in \{P_0, P_3\}$, one evaluator, say $P_1$ sends the least significant bit, $\vl{q}^1$, of $\key{{\vl{z}}}{\vl{z}, 1}$ along with $\h = \Hash(\key{{\vl{z}}}{\vl{z}, 1})$ to $P_g$, where $\Hash$ is a collision-resistant hash function. If a garbler received a consistent $(\vl{q}^1, \h)$ pair from $P_1$ such that there exists a $K \in \{\key{{\vl{z}}}{{0, 1}}, \key{{\vl{z}}}{{1, 1}}\}$ whose least significant bit is $\vl{q}^1$ and $\Hash(K) = \h$, then it uses $\vl{q}^1$ for reconstructing $\vl{z}$; else the garbler aborts the computation.
Note that a corrupt evaluator $P_1$ cannot create confusion among garblers in $\{P_0, P_3\}$ by sending the key that was not output by the GC owing to the authenticity of the garbling scheme. Reconstruction is lightweight and requires a single round for garblers while reconstruction towards evaluators can be overlapped with key transfer and does not incur extra rounds.
The protocol appears in fig:pirec.

$\pigrec(\Partyset, \shrG{\vl{z}})$Output computation: reconstruction of $\vl{z}$fig:pirec

- For an output wire $\vl{z}$, let $\vl{p}^j$ denote the least significant bit of $\key{{\vl{z}}}{0,j}$ and $\vl{q}^j$ denote the least significant bit of $\key{{\vl{z}}}{\vl{z},j}$for $j \in \{1, 2\}$.

- Reconstruction towards $P_j \in \{P_1, P_2\}$: Garblers $P_0, P_3$ in $\PlSet{j}$ $\jsend$ $\vl{p}^j$ to $P_j$. If $P_j$ received consistent values from $P_0, P_3$, it reconstructs $\vl{z}$ as $\vl{z} = \vl{p}^j \xor \vl{q}^j$.

- Reconstruction towards $P_g \in \{P_0, P_3\}$: $P_1$ sends $\vl{q}^1$ and $\h = \Hash(\key{{\vl{z}}}{\vl{z},1})$ to $P_g$, where $\Hash$ is a collision-resistant hash function.
$P_g$ uses the $\vl{q}^1$ received from $P_1$ for reconstructing $\vl{z}$ as $\vl{z} = \vl{p}^1 \xor \vl{q}^1$ if there exists a $K \in \{\key{{\vl{z}}}{{0,1}}, \key{{\vl{z}}}{{1,1}}\}$ whose least significant bit is $\vl{q}^1$ and $\Hash(K) = \h$.

Optimizations when deployed in mixed framework

Working in the preprocessing model enables transfer of the (communication-intensive) GC and generating $\shrG{\cdot}$-shares of the input-independent shares of $\vl{x}$ (i.e. $ {\av{\vl{x}}}, {\pad{\vl{x}}{3}}$) in the preprocessing phase. Thus, the online phase is very light and only requires one round to generate $\shrG{\cdot}$-shares  for the input-dependent data (i.e. ${\mk{\vl{x}}}$). Since evaluation is local, evaluators obtain $\shrG{\cdot}$-sharing of the GC output at the end of $1$ round.

Achieving fairness and robustness

To ensure fairness, we require a fair reconstruction protocol that proceeds as follows. As described in <ref>, parties first ensure that all parties are alive.
If so, they proceed similar to the protocol in fig:pirec, except with the following differences. For reconstruction towards evaluators, all three respective garblers send it the decoding information. The evaluator selects the value appearing in the majority for reconstruction. For reconstruction towards garblers $P_0, P_3$, both the evaluators send the least significant bit of the output key together with its hash to the garbler. The presence of at least one honest evaluator guarantees that both garblers will be on the same page.
The protocol appears in fig:pifrec.

$\pigfrec(\Partyset, \shrG{\vl{z}})$Fair output computation: fair reconstruction of $\vl{z}$fig:pifrec

- Parties perform a bit exchange as described in <ref> to ensure that all parties are alive. If all parties are alive, they proceed as follows.

- For an output wire $\vl{z}$, let $\vl{p}^j$ denote the least significant bit of $\key{{\vl{z}}}{0,j}$ and $\vl{q}^j$ denote the least significant bit of $\key{{\vl{z}}}{\vl{z},j}$for $j \in \{1, 2\}$.

- Reconstruction towards $P_j \in \{P_1, P_2\}$: Garblers in $\PlSet{j}$ send $\vl{p}^j$ to $P_j$. $P_j$ selects the value forming majority among these and reconstructs $\vl{z}$ as $\vl{z} = \vl{p}^j \xor \vl{q}^j$.

- Reconstruction towards $P_g \in \{P_0, P_3\}$: $P_j \in \{P_1, P_2\}$ sends $\vl{q}^j$ and $\h^j = \Hash(\key{{\vl{z}}}{\vl{z},j})$ to $P_g$, where $\Hash$ is a collision-resistant hash function.
$P_g$ uses the $\vl{q}^1$ received from $P_1$ for reconstructing $\vl{z}$ as $\vl{z} = \vl{p}^1 \xor \vl{q}^1$ if there exists a $K \in \{\key{{\vl{z}}}{{0,1}}, \key{{\vl{z}}}{{1,1}}\}$ whose least significant bit is $\vl{q}^1$ and $\Hash(K) = \h^1$. Else, it computes $\vl{z} = \vl{p}^2 \xor \vl{q}^2$.

The main difference from its fair counterpart is the use of a robust $\jsend$ primitive to achieve robustness. This guarantees that a $\TTP$ is identified if misbehaviour is detected, taking the computation to completion and delivering the output to all.

§.§ 1 GC Variant

The input $\vl{x} = \vl{x}_1 \xor \vl{x}_2$ for this variant consists of two shares, $\vl{x}_1 = \mk{\vl{x}} \xor \pad{\vl{x}}{2}$ and $\vl{x}_2 = \pad{\vl{x}}{1} \xor \pad{\vl{x}}{3}$, where $\mk{\vl{x}}, \pad{\vl{x}}{1}, \pad{\vl{x}}{2}, \pad{\vl{x}}{3}$ are as defined in $\shrB{\vl{x}}$. To ensure correct key transfer for the value $\vl{x}_2$ held by garbler $P_0$ and evaluator $P_1$, garblers $P_0, P_3$ commit to both keys for $\vl{x}_2$ towards $P_1$, while $P_0$ sends the opening to the key for $\vl{x}_2$. Then, $P_1$ verifies the consistency of the received commitments and the opening, as it possesses $\vl{x}_2$. The protocol appears in fig:pigsh1.

$\pigsh(P_i, P_j, \vl{v})$Generation of $\shrG{\vl{v}}$fig:pigsh1

* Garblers in $\PlSet{1}$ generate keys $\key{{\vl{v}}}{0}, \key{{\vl{v}}}{1}$ using free-XOR technique.

* If $(P_i, P_j) = (P_2, P_3) $: $P_i, P_j$ $\jsend$ $\key{\vl{v}}{\vl{v}}$ to $P_1$.

* If $(P_i, P_j) = (P_0, P_1)$:

- $P_0, P_3$ compute commitments on $\key{{\vl{v}}}{0}, \key{{\vl{v}}}{1}$, and $\jsend$ the commitment to $P_1$.

- $P_0$ sends the opening of the commitment for $\key{{\vl{v}}}{\vl{v}}$ to $P_1$.

- $P_1$ verifies if the received opening information correctly decommits the commitment on $\key{\vl{v}}{\vl{v}}$, where $\vl{v}$ is held by $P_1$. Else it $\aborts$.

* Party $P_s \in \PlSet{1}$ sets $\shrG{\vl{v}}_s = \key{\vl{v}}{0}$, while $P_1$ sets $\shrG{\vl{v}}_1 = \key{\vl{v}}{\vl{v}}$.

The evaluation and output phases are similar to the 2GC variant, except there is only a single garbling instance now. Looking ahead, in the mixed protocol framework, the output has to be reconstructed towards $P_1, P_2$. Reconstruction towards $P_1$ does not incur additional rounds since sending of decoding information can be overlapped with the key transfer. However, unlike in the 2GC variant where reconstruction towards $P_2$ can be done similar to reconstruction towards $P_1$, in the 1GC variant, an additional round is required as $P_2$ is no longer an evaluator. This incurs one extra round as opposed to the 2GC variant.

Achieving fairness

To ensure fair reconstruction, as in <ref>, parties first perform an aliveness check. Following this, they proceed towards a fair reconstruction of $\vl{z}$ from $\shrG{\vl{z}}$ as follows.
First, reconstruction of $\vl{z}$ is carried out towards the garblers $P_g \in \PlSet{1}$. For this, $P_1$ sends $\vl{q}$ (least significant bit of zz) and $\h = \Hash(\key{{\vl{z}}}{\vl{z}})$ to $P_g$ as before. Now, if a garbler received a consistent $(\vl{q}, \h)$ pair from $P_1$ such that there exists a $K \in \{\key{{\vl{z}}}{{0}}, \key{{\vl{z}}}{{1}}\}$ whose least significant bit is $\vl{q}$ and $\Hash(K) = \h$, then it uses $\vl{q}$ for reconstructing $\vl{z}$, and sends $\vl{z}$ to its co-garblers. Else, a garbler accepts a $\vl{z}$ received from a co-garbler as the output. Thus, further dissemination of the output by garblers ensures that all parties are on the same page.
If garblers receive the output, reconstruction of $\vl{z}$ is carried out towards $P_1$. For this, all garblers (who received the output) send the decoding information to $P_1$, who selects the majority value to reconstruct $\vl{z}$.

$\pigfrec(\shrG{\vl{z}})$Fair reconstruction of $\vl{z}$ from $\shrG{\vl{z}}$fig:pifrec1

- Parties perform a bit exchange as described in <ref> to ensure that all parties are alive. If all parties are alive, they proceed as follows.

- Let $\vl{p}, \vl{q}$ denote the least significant bit of $\key{\vl{z}}{0}, \key{\vl{z}}{\vl{z}}$, respectively.

- Reconstruction towards garblers $P_g \in \PlSet{1}$: $P_1$ sends $\vl{q}$ and $\h = \Hash(\key{{\vl{z}}}{\vl{z}})$ to $P_g \in \PlSet{1}$, where $\Hash$ is a collision-resistant hash function. $P_g$ does the following to reconstruct $\vl{z}$.

- If $P_g$ received $(\vl{q}, \h)$ from $P_1$ such that there exists a $K \in \{\key{{\vl{z}}}{{0}}, \key{{\vl{z}}}{{1}}\}$ whose least significant bit is $\vl{q}$ and $\Hash(K) = \h$, set $\vl{z} = \vl{p} \xor \vl{q}$. $P_g$ sends $\vl{z}$ to its co-garblers.

- Else, if $P_g$ did not receive a consistent  $(\vl{q}, \h)$-pair from $P_1$ but received a $\vl{z}$ from its co-garbler in the following round, then accept $\vl{z}$ as the output.

- Reconstruction towards $P_1$: If garblers obtained the output, then they send $\vl{p}$ to $P_1$. $P_1$ selects the value forming majority among these and reconstructs $\vl{z}$ as $\vl{z} = \vl{p} \xor \vl{q}$.

Achieving robustness

To attain robustness, we list below the differences from the fair protocol that must be carried out. The first difference is the use of a robust variant of $\jsend$. Second, in input sharing protocol, where $\vl{x}_1$ is held by only garbler $P_0$, a corrupt $P_0$ may refrain from providing $P_1$ with the correct key (sent as the opening information for the commitment). To ensure robustness, if $P_1$ fails to receive the correct key from $P_0$, we let $P_1$ complain to all parties about this inconsistency by sending an inconsistency bit. All parties exchange this inconsistency bit among themselves and agree on the majority value. If all parties agree on the presence of inconsistency, then $P_0, P_1$ are identified to be in conflict, and $\TTP = P_2$ is set to carry out the rest of the computation.
Finally, to ensure a robust reconstruction, the following approach is taken. Observe that the fair reconstruction provides robustness as long as evaluator $P_1$ is honest. When none of the garblers obtains the output in the fair protocol, it is guaranteed that evaluator $P_1$ is corrupt. Thus, in such a scenario, all parties take $P_1$ to be corrupt and proceed with $P_0$ as the $\TTP$.

§ SECURITY PROOFS

Without loss of generality, we prove the security of our robust framework. The case for fairness follows similarly, and we omit its details. We provide proofs in the $\FSETUP, \Func[\jsend]$-hybrid model, where $\FSETUP$ (<ref>), $\Func[\jsend]$ (fig:JsendFunc) denote the ideal functionality for the shared-key setup and $\jsend$, respectively.

The strategy for simulating the computation of function $f$ (represented by a circuit $\Ckt$) is as follows: Simulation begins with the simulator emulating the shared-key setup ($\FSETUP$) functionality and giving the respective keys to the adversary. This is followed by the input sharing phase in which $\Sim$ computes the input of $\Adv$, using the known keys, and sets the honest parties' inputs to be used in the simulation to $0$. $\Sim$ invokes the ideal functionality $\Func[GOD]$ on behalf of $\Adv$ using the extracted input and obtains the output $\vl{y}$. $\Sim$ now knows the inputs of $\Adv$ and can compute all the intermediate values for each building block. $\Sim$ proceeds with simulating each of the building blocks in the topological order. We provide the simulation for the case for corrupt $P_0, P_1$ and $P_3$. The case for corrupt $P_2$ is similar to that of $P_1$.

For modularity, we provide the simulation steps for each building block separately. Carrying out these blocks in the topological order yields the simulation for the entire computation. If a $\TTP$ is identified during the simulation, the simulator stops and returns the function output to the adversary on behalf of the $\TTP$ as per $\Func[\jsend]$.

Ideal $\jsend$ Functionality

The ideal $\jsend$ functionality for fairness security appears in fig:JsendFFunc and that for the robust setting appears in fig:JsendFunc.

$\Func[\jsend]$ (for fair security)Ideal functionality for $\jsend$ in $\Fthis$fig:JsendFFunc
$\Func[\jsend]$ interacts with the parties in $\Partyset$ and the adversary $\Sim$.

Step 1: $\Func[\jsend]$ receives $(\INPUT,\vl{v}_s)$ from senders $P_s$ for $s \in \{i,j\}$, $(\INPUT,\bot)$ from receiver $P_k$ and fourth party $P_l$. While sending the inputs, the adversary is also allowed to send a special $\abort$ command.

Step 2: Set $\msg_i = \msg_j = \msg_l = \bot$.

Step 3: If $\vl{v}_i = \vl{v}_j$, set $\msg_k = \vl{v}_i$. Else, set $\msg_k = \abort$.

Step 4: Send $(\OUTPUT, \msg_s)$ to $P_s$ for $s \in \{0,1,2, 3\}$.

$\Func[\jsend]$ (for robust security)Ideal functionality for robust $\jsend$ in $\Fthis$.fig:JsendFunc
$\Func[\jsend]$ interacts with the parties in $\Partyset$ and the adversary $\Sim$.

Step 1: $\Func[\jsend]$ receives $(\INPUT,\vl{v}_s)$ from senders $P_s$ for $s \in \{i,j\}$, $(\INPUT,\bot)$ from receiver $P_k$ and fourth party $P_l$, while it receives $(\SELECT,\ttp)$ from $\Sim$. Here $\ttp$ is a boolean value, with a $1$ indicating that $\TTP = P_l$ should be established.

Step 2: If $\vl{v}_i =\vl{v}_j$ and $\ttp = 0$, or  if $\Sim$ has corrupted $P_l$[This condition is used to capture the fact that a corrupt $P_l$ cannot create an inconsistency in $\Func[\jsend]$ since the parties actively involved in $\Func[\jsend]$ would be honest], set $\msg_i = \msg_j = \msg_l = \bot, \msg_k = \vl{v}_i$ and go to Step 4.

Step 3: Else, set $\msg_i = \msg_j = \msg_k = \msg_l = P_l$.

Step 4: Send $(\OUTPUT, \msg_s)$ to $P_s$ for $s \in \{0,1,2, 3\}$.

Sharing Protocol ($\prot{\Sh}$, fig:piSh)

During the preprocessing, $\Sim_{\prot{\Sh}}^{P_0}$ emulates $\FSETUP$ and gives the respective keys to $\Adv$. The values commonly held with $\Adv$ are sampled using the respective keys, while others are sampled randomly. The details for the online phase are provided next. We omit the simulation for corrupt $P_3$ as it is similar to that of $P_1,P_2$.

$\Sim_{\prot{\Sh}}^{P_0}$Simulator $\Sim_{\prot{\Sh}}^{P_0}$ for corrupt $P_0$ fig:ShFSim0

– If dealer is $\Adv$, $\Sim_{\prot{\Sh}}^{P_0}$ receives $\mk{\vl{v}}$ from $\Adv$ on behalf of $P_1, P_2, P_3$. If the received values are consistent, $\Sim_{\prot{\Sh}}^{P_0}$ computes $\Adv$'s input $\vl{v}$ as $\vl{v} = \mk{\vl{v}} - \sqr{\pd{\vl{v}}}_1 - \sqr{\pd{\vl{v}}}_2 - \sqr{\pd{\vl{v}}}_3$, else sets $\vl{v}$ as the default value. It invokes $\Func[GOD]$ on input $(\INPUT, \vl{v})$ to obtain the function output $\vl{y}$.

– If dealer is $P_1, P_2$ or $P_3$, nothing to simulate as $P_0$ doesn't receive any value during the protocol.

$\Sim_{\prot{\Sh}}^{P_1}$Simulator $\Sim_{\prot{\Sh}}^{P_1}$ for corrupt $P_1$ fig:ShFSim1

– If dealer is $\Adv$, $\Sim_{\prot{\Sh}}^{P_1}$ receives $\mk{\vl{v}}$ from $\Adv$ on behalf of $P_2, P_3$. If the received values are consistent, $\Sim_{\prot{\Sh}}^{P_1}$ computes $\Adv$'s input $\vl{v}$ as $\vl{v} = \mk{\vl{v}} - \sqr{\pd{\vl{v}}}_1 - \sqr{\pd{\vl{v}}}_2 - \sqr{\pd{\vl{v}}}_3$, else sets $\vl{v}$ as the default value. It invokes $\Func[GOD]$ on input $(\INPUT, \vl{v})$ to obtain the function output $\vl{y}$.

– If dealer is $P_0, P_2$ or $P_3$, $\Sim_{\prot{\Sh}}^{P_1}$ sets $\vl{v} = 0$ and performs the protocol steps honestly.

Shares unknown to $\Adv$ are sampled randomly in the simulation, whereas in the real protocol, they are sampled using the pseudorandom function (PRF). The indistinguishability of the simulation thus follows by a reduction to the security of the PRF. The same holds for the rest of the blocks.

The simulation for the joint sharing protocol ($\prot{\JSh}$) is similar to that of the sharing protocol. The protocol's design is such that the simulator will always know the value to be sent as part of the joint sharing protocol. The communication is constituted by $\jsend$ calls and is emulated according to the simulation of $\Func[\jsend]$.

Multiplication Protocol ($\prot{\Mult}$  in $\FthisB$)

$\Sim_{\prot{\Mult}}^{P_0}$Simulator $\Sim_{\prot{\Mult}}^{P_0}$ for corrupt $P_0$ fig:MulFSim0

–  Computes $\gm{\vl{a}\vl{b}}{1}, \gm{\vl{a}\vl{b}}{2}$, and $\gm{\vl{a}\vl{b}}{3}$ on behalf of $P_1, P_2, P_3$.

– Samples $\vl{u}^1, \vl{u}^2$ using the respective keys with $\Adv$ and computes $\vl{r}$. The joint sharing of $\vl{q}$ is simulated as discussed earlier.

– Receives $\vl{w}$ from $\Adv$ on behalf of $P_3$.

– Simulating $\piVrfyP$: Joint sharing of $\vl{e_1}, \vl{e_2}, \vl{e}$ is simulated as discussed earlier. The rest of the steps are simulated honestly. This is possible since $\Sim_{\prot{\Mult}}^{P_0}$ knows the randomness and inputs that should be used by $\Adv$.

$P_0$ has no communication in the online phase except the $\jsend$ instances which are emulated by $\Sim_{\prot{\Mult}}^{P_0}$.

$\Sim_{\prot{\Mult}}^{P_1}$Simulator $\Sim_{\prot{\Mult}}^{P_1}$ for corrupt $P_1$ fig:MulFSim1

–  Computes $\gm{\vl{a}\vl{b}}{1}, \gm{\vl{a}\vl{b}}{2}$, and $\gm{\vl{a}\vl{b}}{3}$ on behalf of $P_0, P_2, P_3$.

– Samples $\vl{u}^1$ using the respective keys with $\Adv$. Samples a random $\vl{u}^2$ and computes $\vl{r}$. The joint sharing of $\vl{q}$ is simulated as discussed earlier.

– Simulate the steps of $\piVrfyP$ honestly.

– Computes $\vl{y}_1 + \vl{s}_1, \vl{y}_2 + \vl{s}_2, \vl{y}_3$ honestly.

– Emulates two instances of $\Func[\jsend]$ – i) $\Adv$ as sender to send $\vl{y}_1 + \vl{s}_1$ to $P_2$, and ii) $\Adv$ as receiver to obtain $\vl{y}_2 + \vl{s}_2$ from $P_2$.

– Simulates joint sharing as discussed earlier.

$\Sim_{\prot{\Mult}}^{P_3}$Simulator $\Sim_{\prot{\Mult}}^{P_3}$ for corrupt $P_3$ fig:MulFSim3

–  Computes $\gm{\vl{a}\vl{b}}{1}, \gm{\vl{a}\vl{b}}{2}$, and $\gm{\vl{a}\vl{b}}{3}$ on behalf of $P_0, P_1, P_2$.

– Samples $\vl{u}^1, \vl{u}^2$ using the respective keys with $\Adv$ and computes $\vl{r}$. The joint sharing of $\vl{q}$ is simulated as discussed earlier.

– Computes and sends $\vl{w}$ to $\Adv$ and simulate the steps of $\piVrfyP$ honestly.

– Computes $\vl{y}_1 + \vl{s}_1, \vl{y}_2 + \vl{s}_2, \vl{y}_3$ honestly.

– Emulates two instances of $\Func[\jsend]$ with $\Adv$ as sender to exchange $\vl{y}_1 + \vl{s}_1, \vl{y}_2 + \vl{s}_2$ among $P_1, P_2$.

– Simulates joint sharing as discussed earlier.

Reconstruction Protocol ($\prot{\Rec}$, fig:piRec)

Using the input of $\Adv$ obtained during simulation of sharing protocol, $\Sim_{\prot{\Rec}}$ invokes $\Func[GOD]$ on behalf of $\Adv$ and obtains the function output $\vl{y}$ in clear. $\Sim_{\prot{\Rec}}$ calculates the missing share of $\Adv$ using $\vl{y}$ and the other shares. The missing share is then communicated to $\Adv$ by emulating the $\Func[\jsend]$ functionality.

CHAPTER: $\TWTHIS$: 2PC SEMI-HONEST PROTOCOLS

This chapter provides details for the Layer I blocks of our 2PC framework $\TWthis$. Some of the results in this chapter resulted in a publication at USENIX Security'21 <cit.>[This is joint work with Thomas Schneider and Hossein Yalame of TU Darmstadt. All co-authors contributed to the fruitful discussions that resulted in this publication. Ajith Suresh designed the new sharing scheme for two-party computation, provided new conversions between different MPC protocols, and benchmarked the protocols. Hossein Yalame designed the new circuits for parallel-prefix adder, comparison, and equality test based on multi-input AND gates and provided the depth-optimized variant of AES.].

Comparison of $\TWthis$ with passively secure 2PC PPML framework of <cit.>, in terms of the communication for multiplication,  is presented in 2pcSCost.

§ PRELIMINARIES AND DEFINITIONS

In our framework, we have two parties $\Partyset = \{P_1, P_2 \}$ who are connected by a bidirectional synchronous channel (e.g. instantiated via TLS over TCP/IP), and a static, semi-honest adversary that can corrupt at most one party. This framework is similar to that of the three-party framework $\TSthis$ except for the absence of helper party $P_0$.

§.§ Sharing Semantics

For the arithmetic and boolean sharing, we follow  masked evaluation technique, where a value $\vl{v} \in \Z{\ell}$ is split into three shares. Two of the shares ($\pad{\vl{v}}{1}, \pad{\vl{v}}{2})$ can be generated in the preprocessing phase independent of the value to be shared, and their sum can be interpreted as a mask ($\pad{\vl{v}}{}$). The third share, dependent on $\vl{v}$,  can be computed in the online phase and can be treated as the masked value $\mk{\vl{v}}= \vl{v} +\pad{\vl{v}}{}$.

r r r[notes/para]
Sharing Type      $P_1$     $P_2$

$\sqr{\cdot}$-sharing$\vl{v} = \vl{v}^1 + \vl{v}^2$
${\vl{v}}^1$         ${\vl{v}}^2$

$\shr{\cdot}$-sharing$\pad{\vl{v}}{} = \pad{\vl{v}}{1} + \pad{\vl{v}}{2}$, $\mk{\vl{v}} = \vl{v} + \pad{\vl{v}}{}$
$(\mk{\vl{v}}, \pad{\vl{v}}{1})$
$(\mk{\vl{v}}, \pad{\vl{v}}{2})$

Semantics for $\vl{v} \in \Z{\ell}$ in .

The sharing semantics is presented in 2pcSsharing, denoted by $\shr{\cdot}$, along with the semantics for $\sqr{\cdot}$-sharing. Both the sharings used are linear i.e. given sharings of $\vl{v}_1,\ldots, \vl{v}_m$ and public constants $c_1,\ldots,c_m$, sharing of $\sum_{i=1}^m c_i \vl{v}_i$ can be computed non-interactively for an integer $m$.

(a) For the $\shr{\cdot}$-shares of $n$ values $\vl{a}_1,\ldots,\vl{a}_n$, $\gm{\vl{a}_1 \ldots \vl{a}_n}{} = \prod\limits_{i=1}^{n} \pad{\vl{a}_i}{}$ and $\mk{\vl{a}_1 \ldots \vl{a}_n}{} = \prod\limits_{i=1}^{n} \mk{\vl{a}_i}{}$ (b) We use superscripts ${\bf B}$, and ${\bf G}$ to denote sharing semantics in boolean, and garbled world, respectively– $\shrB{\cdot}$,  $\shrG{\cdot}$. We omit the superscript for arithmetic world.

Sharing semantics for boolean sharing over $\Z{}$ is similar to arithmetic sharing except that addition is replaced with XOR. The semantics for garbled sharing are described in <ref> with the relevant context.

§.§ Oblivious Transfer (OT)

In a 1-out-of-$n$ Oblivious Transfer <cit.> (OT) over $\ell$-bit messages, the sender $S$ inputs $n$ messages $(x_1, \ldots, x_n)$ each of length $\ell$ bits, while the receiver $R$ inputs the choice $c \in \{1,\ldots,n\}$. $R$ receives $x_c$ as output while $S$ receives $\bot$ as output. The privacy guarantee is that $S$ learns nothing about $c$, while $R$ learns nothing about the inputs of $S$ other than $x_c$. We use $\OTN{m}{\ell}{n}$ to denote $m$ instances of 1-out-of-$n$ OT on $\ell$ bit inputs.

OT is a fundamental building block for MPC <cit.> and requires expensive public-key cryptography <cit.>. The technique of OT Extension <cit.> allows us to generate many OTs from a small number (equal to the security parameter) of base OTs at the expense of symmetric-key operations alone. This reduces the cost of OT mainly to highly efficient symmetric-key primitives. Concretely, the OT Extension of <cit.> generates around 1 million $\OTN{1}{\ell}{2}$ per second with passive security. An orthogonal line of work considered pre-computation of OT <cit.>, where all the cryptographic operations can be shifted to a setup phase, independent of the function to be evaluated. This technique enables a very efficient online phase for protocols that use OT. In the semi-honest setting, the state-of-the-art solution for OT extension <cit.> has communication $\csec + 2\ell$ bits per OT for $\OTN{1}{\ell}{2}$ where $\kappa$ denotes the computational security parameter.

A correlated OT ($\COT{}{}$) <cit.> is a variant of the traditional OT  where the sender's input messages are correlated. In a $\COT{}{}$, the sender inputs a correlation function $f()$ and obtains the message pair ($x_0 \in_R \{0,1\}^\ell, x_1 = f(x_0)$) as the output. The receiver, on the other hand, inputs her choice $c$ and obtains $x_c$ as output. We use $\COT{m}{\ell}$ to denote $m$ instances of 1-out-of-2 correlated OT on $\ell$ bit inputs. In the semi-honest setting, $\COT{1}{\ell}$ has communication $\csec + \ell$ bits <cit.>.

§.§ Homomorphic Encryption (HE)

The homomorphic property allows us to compute a ciphertext from a set of ciphertexts such that the plaintext underlying the former is a function of the underlying plaintexts of the latter. Towards this, one party called client generates a key-pair $(\mathsf{pk}, \mathsf{sk})$ for the HE scheme and sends $\mathsf{pk}$ to the other party called server. To perform a secure computation operation, the client encrypts its data using $\mathsf{pk}$ and sends this to the server. Now the server can locally compute the ciphertext corresponding to the operation and return the encrypted result to the client. The client can now decrypt the received ciphertext using her private key $\mathsf{sk}$. An additively HE allows us to generate the ciphertext corresponding to the sum of the underlying plaintexts by doing operations on the ciphertexts. Prominent examples of additively HE schemes are Paillier <cit.>, DGK <cit.> and RLWE-AHE <cit.>. On the other hand, fully homomorphic encryption schemes allow arbitrary computations under the encryption but are less efficient. See <cit.> for a more detailed description.

§ ARITHMETIC / BOOLEAN 2PC

This section covers the details of our 2PC semi-honest protocol $\TWthis$ over an arithmetic ring $\Z{\ell}$. The protocol primarily consists of the following primitives – i) Sharing (share2pcS), ii) Multiplication (mult2pcS), and iii) Reconstruction (rec2pcS).

§.§ Sharing

Protocol $\prot{\Sh}$ (fig:piSh2pcS) enables $P_i$ to generate $\shr{\cdot}$-share of a value $\vl{v}$. During the preprocessing phase, $\pd{}$-shares are sampled non-interactively using the pre-shared keys (cf. <ref>) in a way that $P_i$ will get the entire mask $\pd{\vl{v}}$. During the online phase, $P_i$ computes $\mk{\vl{v}} = \vl{v} + \pd{\vl{v}}$ and sends to $P_1, P_2$.

For the special case when parties want to generate $\shr{\vl{v}}$ in the preprocessing, the protocol can be made non-interactive. W.l.o.g. consider the case when $P_i = P_1$. Parties set $\mk{\vl{v}} = 0$. $P_1, P_2$ sample $\pad{\vl{v}}{2}$ non-interactively while $P_1$ sets $\pad{\vl{v}}{1} = - (\vl{v} + \pad{\vl{v}}{2})$. The case for $P_i = P_2$ is similar.

$\prot{\Sh}(P_i, \vl{v})$$\shr{\cdot}$-sharing of a value $\vl{v}$ by party $P_i$ in $\TWthis$.fig:piSh2pcS

Input(s): $P_i : \vl{v}$,  Output: $\shr{\vl{v}}$.

Sample as follows: $P_i, P_1: \pad{\vl{v}}{1}$,  $P_i, P_2: \pad{\vl{v}}{2}$.

Online: $P_i$ computes $\mk{\vl{v}} = \vl{v} + \pd{\vl{v}}$ and sends to $P_1, P_2$.

Protocol $\prot{\Sh}$ (fig:piSh2pcS) requires a communication of at most $\ell$ bits and $1$ round in the online phase.

The preprocessing of $\prot{\Sh}$ is non-interactive as the parties sample non interactively using key setup $\Func[Key]$ (<ref>). In the online phase, $P_i$ sends $\mk{\vl{v}}$ to either $P_1$ or $P_2$ (depending upon $P_i$) resulting in 1 round and communication of $\ell$ bits.

§.§.§ Joint Sharing

Protocol $\prot{\JSh}$ enables parties $P_1,P_2$ to generate $\shr{\cdot}$-share of a value $\vl{v}$ known to both of them non-interactively. For this, parties set $\pad{\vl{v}}{1} = \pad{\vl{v}}{2} = 0$ and $\mk{\vl{v}} = \vl{v}$.

§.§ Multiplication

Given the shares of $\vl{a}, \vl{b}$, the goal of the multiplication protocol is to generate shares of $\vl{z} = \vl{ab}$. The protocol is designed such that $P_i$ for $i \in \{1,2\}$ obtain $\vl{z}^i$ in the online phase such that $\vl{z} = \vl{z}^1 + \vl{z}^2$. Parties then compute $\shr{\vl{z}}$ as $\shr{\vl{z}^1} + \shr{\vl{z}^2}$ to obtain the final output.

Note that,

\begin{align}\label{eq:2pcSmult}
\vl{z} = \vl{ab} = (\mk{\vl{a}} - \pd{\vl{a}})(\mk{\vl{b}} - \pd{\vl{b}})
= \mk{\vl{ab}} - \mk{\vl{a}}\pd{\vl{b}} - \mk{\vl{b}}\pd{\vl{a}} + \gm{\vl{ab}}{}
~~\text{\footnotesize{(cf. notation~\ref{notation:2pcSconcise})}}
\end{align}

Let $\vl{z} = \vl{z}_1 + \vl{z}_2$, where $\vl{z}_1$ and $\vl{z}_2$ can be computed respectively by $P_1$ and $P_2$.

\begin{align}\label{eq:2pcSmulty}
P_1: \vl{z}_1 &= \mk{\vl{ab}} - \pad{\vl{a}}{1} \mk{\vl{b}} - \pad{\vl{b}}{1} \mk{\vl{a}} + \sqr{\gm{\vl{ab}}{}}_1 \nonumber\\
P_2: \vl{z}_2 &= ~~~~~~- \pad{\vl{a}}{2} \mk{\vl{b}} - \pad{\vl{b}}{2} \mk{\vl{a}} + \sqr{\gm{\vl{ab}}{}}_2
\end{align}

During preprocessing, parties rely on $\prot{\MultPre}$ to generate an additive sharing ($\sqr{\cdot}$) of $\gm{\vl{ab}}{}$. We note that Turbospeedz <cit.> achieves same online cost as that of ours, but with a more expensive preprocessing. We provide more details in <ref>.

$\prot{\Mult}(\vl{a}, \vl{b}, \isTr)$Multiplication with / without truncation in $\TWthis$.fig:piMult2pcS
$\isTr$ is a bit denoting whether truncation is required ($\isTr =1$) or not ($\isTr=0$).

Input(s): $\shr{\vl{a}}, \shr{\vl{b}}$.

Output: $\shr{\vl{o}}$ where $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{o} = \vl{z}$ if $\isTr = 0$ and $\vl{z} = \vl{ab}$.

Preprocessing: Execute $\prot{\MultPre}$ on $\sqr{\pad{\vl{a}}{}}$ and $\sqr{\pad{\vl{b}}{}}$ to generate $\sqr{\gm{\vl{ab}}{}}$.

* Compute: $P_1: \vl{z}_1 = \mk{\vl{ab}} - \pad{\vl{a}}{1} \mk{\vl{b}} - \pad{\vl{b}}{1} \mk{\vl{a}} + \sqr{\gm{\vl{ab}}{}}_1,~~
P_2: \vl{z}_2 = - \pad{\vl{a}}{2} \mk{\vl{b}} - \pad{\vl{b}}{2} \mk{\vl{a}} + \sqr{\gm{\vl{ab}}{}}_2$

* If $\isTr = 1$, $P_i$ sets $\vl{p}_i = \vl{z}_i^{\vl{t}}$, else $\vl{p}_i = \vl{z}_i$ where $i \in \{1,2\}$.
Execute $\prot{\Sh}(P_i, \vl{p}_i)$ to generate $\shr{\vl{p}_i}$.

* Compute $\shr{\vl{o}} = \shr{\vl{p}_1} + \shr{\vl{p}_2}$. Here $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{z}$ otherwise.

We now provide the details for instantiating $\prot{\MultPre}$ using two of the well-known primitives: i) Oblivious Transfer (OT) as used in <cit.> and ii) Homomorphic Encryption (HE) as used in <cit.>. These two approaches have been rallied against each other in terms of practical efficiency in the past, and fair competition is still going on. In our work, we make only black-box access to these primitives, and hence any improvement in any of them will directly impact the overall efficiency of the setup phase of our protocols.

Note that $\gm{\vl{ab}}{} = (\pad{\vl{a}}{1} + \pad{\vl{a}}{2})(\pad{\vl{b}}{1} + \pad{\vl{b}}{2}) = \pad{\vl{a}}{1}\pad{\vl{b}}{1} + \pad{\vl{a}}{1}\pad{\vl{b}}{2} + \pad{\vl{a}}{2}\pad{\vl{b}}{1} + \pad{\vl{a}}{2}\pad{\vl{b}}{2}$. Here $P_i$ for $i \in \{1,2\}$ can locally compute $\pad{\vl{a}}{i}\pad{\vl{b}}{i}$ and hence the problem reduces to computing $\pad{\vl{a}}{1}\pad{\vl{b}}{2}$ and  $\pad{\vl{a}}{2}\pad{\vl{b}}{1}$.

OT based $\prot{\MultPre}$:

In our OT-based approach, we use Correlated OTs ($\COT{}{}$) <cit.> where the sender inputs a correlation function $f(\cdot)$ to $\COT{}{}$ and obtains $(m_0, m_1)$, where $m_0$ is a random element and $m_1 = f(m_0)$. We use $\COT{n}{\ell}$ to represent $n$ parallel instances of 1-out-of-2 Correlated OTs on $\ell$ bit input strings.

To compute $\sqr{\pad{\vl{a}}{1}\pad{\vl{b}}{2}}$, the parties execute $\COT{\ell}{\ell}$ with $P_1$ being the sender and $P_2$ being the receiver. For the $j$-th instance of $\COT{}{}$ where $j \in \{0,\ldots,\ell-1\}$, $P_1$ inputs the correlation $f_j(x) = x + 2^j \pad{\vl{a}}{1}$ and obtains $(m_{j,0} = r_j, m_{j,1} = r_j + 2^j \pad{\vl{a}}{1})$. $P_2$ inputs choice bit $b_j$ as the $j$-th bit of $\pad{\vl{b}}{2}$ and obtains $m_{j,b_j}$ as output. Now the $\sqr{\cdot}$-shares are defined as $\sqr{\pad{\vl{a}}{1}\pad{\vl{b}}{2}}_1 = \sum_{j=0}^{\ell-1} (-r_j)$ and $\sqr{\pad{\vl{a}}{1}\pad{\vl{b}}{2}}_2 = \sum_{j=0}^{\ell-1} m_{j,b_j}$. Computation of $\pad{\vl{a}}{2}\pad{\vl{b}}{1}$ proceeds similarly with the role of the parties reversed.

In the OT-based approach <cit.>, the technique of OT extension <cit.> can be used. One instance of $\prot{\MultPre}$ requires two instances of $\COT{\ell}{\ell}$ where each instance has communication $\ell (\csec + \ell)$ bits. Over a $64$-bit ring, this corresponds to $3072$ bytes.

Recently, <cit.> came up with a very efficient OT extension technique named Silent OT Extension which claims to outperform state-of-the-art solutions for performing $\prot{\MultPre}$. Since our protocol makes black-box calls to $\prot{\MultPre}$, it can directly benefit from the performance improvements of <cit.>.

HE-based $\prot{\MultPre}$:

In a HE based solution, $P_1$, using its public key $\mathsf{pk_1}$, encrypts its messages $\pad{\vl{a}}{1}, \pad{\vl{b}}{1}$ in independent ciphertexts and sends the ciphertexts to $P_2$. In parallel, $P_2$ computes the ciphertexts corresponding to $\pad{\vl{a}}{2}, \pad{\vl{b}}{2}$ and a random element $\vl{r} \in_R \Z{\ell}$ using $\mathsf{pk_1}$. Upon receiving the ciphertexts from $P_1$, $P_2$ computes the ciphertext corresponding to $\vl{v} = \pad{\vl{a}}{1}\pad{\vl{b}}{2} + \pad{\vl{a}}{2}\pad{\vl{b}}{1} - \vl{r}$ using the homomorphic property of the underlying HE. $P_2$ then sends encryption of $\vl{v}$ to $P_1$ who then decrypts it using its secret key $\mathsf{sk_1}$. Note that ($\vl{v}$, $\vl{r}$) forms an additive sharing of the desired value: $\pad{\vl{a}}{1}\pad{\vl{b}}{2} + \pad{\vl{a}}{2}\pad{\vl{b}}{1} = \vl{v} + \vl{r}$.

Recently, Ring LWE-based AHE <cit.> was shown to outperform the solutions based on OT for generating multiplication triples. The authors observed that the plaintext space is much larger than the range of the values being encrypted. Thus they used the technique of ciphertext packing, using Microsoft SEAL library, where ciphertexts corresponding to multiple plaintexts are packed into a single ciphertext. This optimizes the number of ciphertexts being sent back and the number of decryptions on $P_1$'s side. In <cit.>, the amortized communication cost for performing one instance of $\prot{\MultPre}$ over a $64$-bit ring with a security level of 128 bits is $448$ bytes, which is a $7\times$ improvement over the best OT-based solutions <cit.> available at that time.