MPClan: Protocol Suite for Privacy-Conscious Computations

Nishat Koti1,
Shravani Patil1,
Arpita Patra1,
Ajith Suresh2,

1Indian Institute of Science, Bangalore, Email: {kotis, shravanip<EMAIL_ADDRESS>2Technical University of Darmstadt, Germany, Email<EMAIL_ADDRESS>
The growing volumes of data being collected and its analysis to provide better services are creating worries about digital privacy. To address privacy concerns and give practical solutions, the literature has relied on secure multiparty computation. However, recent research has mostly focused on the small-party honest-majority setting of up to four parties, noting efficiency concerns. In this work, we extend the strategies to support a larger number of participants in an honest-majority setting with efficiency at the center stage.

Cast in the preprocessing paradigm, our semi-honest protocol improves the online complexity of the decade-old state-of-the-art protocol of Damgård and Nielson (CRYPTO'07). In addition to having an improved online communication cost, we can shut down almost half of the parties in the online phase, thereby saving up to 50$\%$ in the system's operational costs. Our maliciously secure protocol also enjoys similar benefits and requires only half of the parties, except for one-time verification, towards the end.

To showcase the practicality of the designed protocols, we benchmark popular applications such as deep neural networks, graph neural networks, genome sequence matching, and biometric matching using prototype implementations. Our improved protocols aid in bringing up to 60-80$\%$ savings in monetary cost over prior work.

§ INTRODUCTION

Today's world is seeing a visible transition from offline services to a heavy dependency on online platforms for banking, socializing, healthcare, etc. This is leading to an increased user presence online, which leaves a trail of online activity and personal data over the Internet.
The availability of such user-specific data opens up possibilities for its misuse. For instance, there has been a lot of concern raised regarding advertisement service providers such as Google, Facebook breaching user privacy for targeted advertisement services [34]. In the process of providing enhanced targeted advertisement services, service providers are allegedly learning more information about their users than they are entitled to (e.g., user's shopping activity, browsing history) from various data collection entities. These entities collect user data via website cookies, loyalty cards, etc. [65]. While such targeted advertisements offer a personalized online experience, they may come at the cost of revealing unauthorized user data to these service providers. Such a challenge is also encountered in the healthcare sector. Collaborative analysis among healthcare institutes over patient data is known to facilitate better diagnosis and improved treatment. However, laws such as GDPR, which prevent sharing of patient records, hinder such collaborations, thereby re-emphasizing the need for mechanisms that enable privacy-preserving computations.

Such mechanisms that ensure privacy-preserving computations can be facilitated
via several privacy-enhancing technologies such as homomorphic encryption [16, 41], differential privacy [36], secure multiparty computation [89, 11, 43], to name a few. We focus on secure multiparty computation (MPC) as it has been the cornerstone of research lately, showcasing its effectiveness in various applications such as privacy-preserving machine learning [56, 68, 85], secure collaborative analytics [75], secure genome matching [79, 5], etc.  Essentially, it offers a solution to the potential privacy issues which may arise in collaborative computation scenarios such as targeted advertisements described earlier.

MPC allows mutually distrusting parties to perform computations on their private inputs such that they learn nothing beyond the output of the computation. The distrust among the parties is captured by the notion of a centralized adversary, which is said to corrupt up to $t$ out of the $n$ participating parties. Depending on its behaviour, the adversary can be categorized as either semi-honest or malicious [42]. Semi-honest adversary models the corruption scenario where the corrupt parties are restricted to follow the protocol and cannot deviate arbitrarily, as in the stronger notion of malicious corruption.

MPC with honest majority, where only a minority of the parties are corrupt, enables construction of efficient protocols for multiple parties [13, 31, 1, 48, 12, 75]. The recent concretely efficient protocols have only considered small number of parties [56, 74, 22, 85, 68, 28, 66, 84], which restricts the number of corruptions to at most one ($t = 1$). Although the small-party setting has found application in the outsourced computation paradigm too, the generic multiparty setting is a better fit for real-world deployments due to its resiliency to a higher number of corruptions ($t < n/2$). Thus, for larger $n$, the number of corruptions that can be tolerated is also higher, thereby increasing the trust in the system. Moreover, multiparty setting allows for privacy-conscious computations even in a non-outsourced deployment scenario, such as in providing targeted advertisement services (described in fig:usecase and elaborated below), when outsourcing the computation is not feasible/preferable. Hence, to design efficient protocols, we focus on honest majority multiparty computation.

Use Case Consider the scenario of targeted advertisement services depicted in fig:usecase(a). Typically, data collection entities track a user's online activities via website cookies while browsing the Internet (1). Also known as cookie profiling, such data collection allows the entities to create a “profile” for each user, which may contain information such as browsing habits, gender, marital status, and age, to name a few, as shown in 2. These profiles can facilitate targeted advertisements via specialized algorithms (4), which is leveraged by the advertisement service providers such as Google and Facebook. While such services offer a personalized experience, it comes at the expense of users' private data being revealed to the service providers, as indicated in 3. A feasible solution (fig:usecase(b)) instead is to place a solution box at the interface between these service providers and the data collection entities such that it provides mechanisms to ensure the privacy of user data while also facilitating the required computations over the same (to provide targeted advertisement services). MPC being a technology that supports privacy-preserving computations, lends itself well to such tasks. Instead of the data collection entities directly revealing the user data to the advertisement service providers, they can engage in an instance of MPC protocol (3) which securely runs the required algorithm on the user data while maintaining its privacy. Moreover, such a computation does not require the data collection entities to reveal their data to each other, thus offering a viable solution. Furthermore, as studied in [49], the effectiveness of targeted advertisements can greatly benefit from the use of machine learning algorithms. In particular, neural networks, and more recently graph neural networks [24, 72, 90, 62, 88] have shown the potential to better analyse the data available via user profiles, in turn allowing for a refined personalized experience. We thus focus on protocols for securely evaluating the standard neural networks such as VGG16 [82] (deep neural network) and graph neural network, and provide benchmarks for the same in Section <ref>.

§.§ Related work

We restrict related work to MPC protocols in honest-majority setting.

Despite the interest in MPC for small population [4, 3, 39, 23, 1, 21, 74, 22, 18, 56, 85, 28], MPC protocols for arbitrary number of parties have been studied largely [38, 31, 48, 6, 8, 10, 15, 13, 17, 78, 2, 19, 12, 45]. In the honest majority ($t<n/2$) semi-honest setting, [31, 40] forms the state of the art MPC protocols over fields in the information theoretic setting.  This was further optimized in the computational setting in [13] using a one-time setup for correlated randomness.
We will often refer to this optimized honest-majority semi-honest protocol of [31] as DN07. In the information-theoretic setting, the work of [46], improves upon the communication and round complexity of [31].

The work of  [38] recently demonstrates MPC protocols in the honest majority setting in the preprocessing model with malicious security, which requires communicating $3t$ field elements in the online as well as the preprocessing phase. We observe that the semi-honest protocol derived from this requires communicating $2t$ elements in the online and $3t$ elements in the preprocessing phase.

The recent work of [12, 6] provides semi-honest MPC protocols which require each party to communicate roughly $t$ elements per multiplication gate, resulting in quadratic communication in the number of parties.
DN07 has served as the basis for obtaining malicious security for free (i.e. amortized communication cost of $3t$ elements per multiplication gate) in the computational setting [13, 15] as well as in the information-theoretic setting [48, 46]. Both [48] and [15] follow the approach of executing a semi-honest protocol, followed by a verification phase to check the correctness of multiplication which involves heavy polynomial interpolation operations.

As mentioned earlier, the recent work of [38] focuses on maliciously secure protocols for honest-majority setting in the preprocessing model. Their protocol relies on an instantiation of [48] in the preprocessing phase that requires communicating $3t$ elements while requiring another $3t$ element communication in the online phase. However, their protocol is inefficient due to a consistency check required after each level of multiplication and introduces depth-dependent overhead in communication complexity. The absence of this check results in a privacy breach as described in [47] and is elaborated in <ref>.

§.§ Towards practically efficient protocols

Before stating our contributions, we elaborate on the choices made in designing a practically efficient protocol.

1. Preprocessing paradigm. With the goal of attaining as fast a response time as possible, the protocols are cast in the preprocessing paradigm [33, 30, 54, 52, 7, 32, 25, 76, 53, 74, 22]. Here, expensive data-independent computations are carried out in a preprocessing phase, thereby making way for a fast and efficient data-dependent online phase. We thus focus on improving the online phase without hampering the overall protocol complexity.

2. Algebraic structure. To further enhance efficiency by utilizing the underlying CPU architecture, several protocols work over rings [68, 56, 22, 85, 57, 66]. We follow this approach and design MPC protocols operating over the ring $\Z{\ell}$ and rely on replicated secret sharing (RSS). Note that usage of RSS inherently results in exponential blow-up in the number of shares for an arbitrary number of parties. Hence, it is well-suited for the practically-oriented scenarios comprising of a constant number of parties [13, 15], which we restrict to for benchmarking our protocols.

3. Masked evaluation.  To make our protocols efficient in the preprocessing paradigm, we use the masked evaluation paradigm, a variant of the replicated secret sharing scheme. The secret data is masked using a masking value in this case, and the mask is RSS shared. The computation is done on the publicly available masked values and the shared masks. This technique was first introduced in the context of circuit garbling schemes (see [64, 87]), and was then adapted to secret sharing-based protocols in dishonest majority (see [51, 9]). It was later applied to small-population honest-majority settings such as [44, 21, 74, 28, 56] and [57] to aid in the development of practically efficient protocols.

4. Adversarial strategy. Based on the deployment scenario, different levels of security may be desired. While semi-honest security suffices for several applications as shown in [4, 59, 21, 70, 5, 79, 20, 83], malicious security is always desirable. Thus, to cater to different scenarios, our protocols are designed to provide semi-honest and malicious security, where each security goal has its merit.

5. Monetary cost. To reduce the operational costs in the online phase, several recent works [74, 56, 22, 57] reduce the number of (online) computing parties. This is useful in long computations such as those involved in privacy-preserving machine learning (PPML) applications, which span several days or even weeks. Reducing the number of online parties is especially advantageous for protocols deployed in the secure outsourced computation (SOC) setting since one has to pay for the up-time of every hired server. Shutting down even a single server significantly helps in reducing the monetary cost [67, 57] of the system. We thus focus on ensuring the participation of a minimal number of parties during the online computation in our protocols. This is achieved for the first time in generic $n$-party protocols
[A recent work [38] also claims to achieve this reduction in online parties. However, their protocol suffers from a privacy breach as explained in <ref>.]. Specifically, all the protocols for the semi-honest setting in our framework benefit from using only $t+1$ parties in the online phase. The protocols in the malicious setting also enjoy this benefit except that the remainder $t$ parties are required to come online for a short verification phase at the end. The reduction in online parties aids in improving the operational cost of the framework by almost 50$\%$. This is unlike prior works [31, 13, 15, 48, 46] which require active participation from all parties throughout the computation.

§.§ Our Contributions

We begin with a quick overview of the contributions of this work, followed by the details.

* We construct an $n$-party semi-honest protocol in the preprocessing paradigm which offers an improved online phase than the decade-old state-of-the-art protocol of [31], without inflating its total cost. Moreover, our protocol reduces the number of active parties in the online phase, thereby improving the system's operational cost when deployed in SOC setting.

* We extend our semi-honest protocol to the malicious setting, while retaining the benefits of requiring reduced number of parties in online phase for majority of the computation. Our offer over state-of-the-art protocol of [38] is a stronger security guarantee of fairness, and $\Order(d)$ improvement in round complexity. Here, $d$ denotes depth of the circuit to be evaluated.

* We provide support for $3$ and $4$ input multiplication, at the same online complexity as that of the $2$ input multiplication. In addition to improving the communication cost over the approach of sequential multiplications, multi-input multiplication offers a $2\times$ improvement in the round complexity which is beneficial for high latency networks.

* We design building blocks for a range of applications such as deep neural networks, graph neural networks, genome sequence matching and biometric matching. When the applications are benchmarked, our semi-honest protocol witnesses a saving of up to $69\%$ in monetary cost, and has $3.5\times$ to $4.6\times$ improvements in online run time and throughput over [31]. Interestingly, our maliciously secure protocols outperforms the semi-honest protocol of [31] in terms of online run time and throughput for the applications under consideration, achieving the goal of fast online phase.

We now elaborate on the contributions and highlight the technical details and novelty of our work.

Hierarchy of primitives in our 3-tier framework

Our protocol suite follows a 3-tier architecture (fig:architecture) to attain the final goal of privacy-conscious computations. The first tier comprises fundamental primitives such as input sharing, reconstruction, multiplication (with truncation), and multi-input multiplication. The second tier includes building blocks such as dot product, matrix multiplication, conversion between Boolean and arithmetic worlds, comparison, equality, non-linear activation functions, to name a few, as required in the applications considered. Finally, the third tier is applications. Our main contribution lies in Tier I and is detailed below.

§.§.§ Tier I - MPC protocols

Our goal is to design protocols with a fast online phase. Thus, working over $\Z{\ell}$ and relying on RSS, we design a semi-honest MPC protocol in the computational setting assuming a one-time shared-key setup for correlated randomness.

Note that the straightforward extension of semi-honest multiplication protocol of [31] to the preprocessing model, which can also be derived from the recent work of [38], incurs a communication of $3t$ elements in the preprocessing phase while communicating $2t$ elements in the online. This amounts to a $1.6\times$ overhead in the total cost over [31].

Our contribution lies in ensuring a fast online phase, without inflating the total communication cost of the protocol. Specifically, our protocol requires communicating only $2t$ ring elements in the online phase and $t$ in the preprocessing, for a multiplication gate. We are the first to achieve a communication cost of $2t$ in the online phase (unlike $3t$ in the prior works [31, 40]), without incurring any overhead in the total cost, i.e., our total cost still matches that of the best known (optimized) semi-honest honest-majority protocol [31, 40].

We extend our protocol to provide malicious security with fairness[Guarantees either all parties receive the output or none do.] at the cost of additionally communicating $t$ elements in the online phase and $2t$ in the preprocessing phase.

Although (abort[Honest parties may not receive the output while corrupt parties do.]) protocol of [38] has the same communication as our maliciously secure protocol, we achieve a stronger security notion of fairness. Moreover, [38] requires an additional round of communication for consistency checks after each level, the absence of which results in a privacy breach (described in [47] and elaborated in <ref>), and necessitates participation from all parties. However, by relying on a variant of RSS, our protocol avoids the consistency check after each level of circuit evaluation and ensures privacy. Notably, we only require participation from all parties for a one-time verification at the end of evaluation, thus reducing the number of rounds by $d$ ($d$ denotes circuit depth).

*3 and 4 input multiplications

Following [73, 71, 57], to reduce the online communication cost and round complexity, we design protocols to enable the multiplication of 3 and 4 inputs in a single shot. Compared to the naive approach of performing sequential multiplications to multiply 3/4 inputs, the multi-input multiplication protocol enjoys the benefit of having the same online phase complexity as that of the 2-input multiplication protocol. This brings in a $2\times$ improvement in the online round complexity and improves the online communication cost. Support for multi-input multiplication enables usage of optimized adder circuits [73] for secure comparison and Boolean addition, thereby resulting in a faster online phase.

The recent work of [46] also proposes a method to improve the round complexity of circuit evaluation by evaluating all gates in two consecutive layers in a circuit in parallel. We observe that their method can be viewed as a variant of multi-input multiplication with 3 and 4 inputs. Thus, our protocols need not be limited to facilitate faster comparison and Boolean additions alone (as described above), but can be used to reduce the round and communication complexity of any general circuit evaluation. Note that [46] only improves the round complexity (2$\times$) without inflating the communication cost when compared to [31]. However, we focus on improving round complexity (2$ \times$) as well as communication of the online phase by trading off an increase in the preprocessing.

§.§.§ Tier II - Building Blocks

We design efficient protocols for several building blocks in semi-honest and malicious settings, which are stepping stones for Tier III applications. These are extensions from the small party setting [68, 74, 56, 73], and hence we defer the details to <ref> (semi-honest) and <ref> (malicious).

§.§.§ Tier III - Applications

To showcase the practicality of our framework and improvements of our protocols, we benchmark a range of applications such as neural networks (NN), which also includes the popular deep NN called VGG16 [82], graph neural network, genome sequence matching, and biometric matching, and are considered for the first time in the $n$-party honest-majority setting. We benchmark the applications in the WAN setting using Google Cloud instances. As mentioned, owing to the inherent restrictions of RSS and keeping the focus on practical scenarios, we showcase the performance of our protocols for $n = 5, 7$, and $9$ and compare with the state-of-the-art semi-honest protocol of [31].

1. Deep neural networks. We benchmark inference phases of deep neural networks such as LeNet [60] and VGG16 [82]. We observe savings of up to $69\%$ in monetary cost, and improvements of up to $4.3\times$ in online run-time
and throughput, in comparison to [31].

2. Graph neural network. We benchmark the inference phase of graph neural network [35, 81] on MNIST [61] data set. In comparison to [31], our protocol improves up to $3.5\times$ in online run-time, and sees up to $15\%$ savings in monetary cost.

3. Genome sequence matching. We demonstrate an efficient protocol for similar sequence queries (SSQ), which can be used to perform secure genome matching. Our protocol is based on the protocol of  [79] which works for $2$ parties and uses an edit distance approximation [5]. We extend and optimize the protocol for the multiparty setting. In comparison to [31], we witness improvements of up to $4\times$ in online run-time and throughput, and savings of $66\%$ in monetary cost.

4. Biometric matching. We propose efficient protocols for computing Euclidean distance (ED), which forms the basis for performing biometric matching. Continuing the trend, we witness a $4.6\times$ improvement in online run-time and throughput compared to [31], and savings of up to $85\%$ in monetary cost.

§ PRELIMINARIES

We cast our protocols in the (function-dependent) preprocessing paradigm to enable a fast online phase. Parties rely on a one-time shared key setup (see <ref>) [74, 22, 56, 68, 4, 18] to enable generation of correlated randomness, non-interactively.
Our protocols are designed for rings ($\Z{\ell}$).
We use fixed-point arithmetic (FPA) [70, 68, 21, 22, 74, 56] representation to operate over decimal values. Here, a decimal value is represented as an $\ell$-bit integer in signed 2's complement representation. The most significant bit ($\MSB$) represents the sign bit, and $d$ least significant bits are reserved for the fractional part. The $\ell$-bit integer is then treated as an element of $\Z{\ell}$, and operations are performed modulo $2^{\ell}$. We let $\ell = 64$, $d = 13$, with $\ell - d - 1$ bits for the integer part.

This work considers both semi-honest and malicious adversarial models with static and at most $t<n/2$ corruptions. The security of constructions is proved using the real-world/ ideal-world simulation paradigm [63], and the details are provided in <ref>.

Let $\Partyset = \{P_1, P_2, \ldots, P_n\}$ denote the set of $n$ parties which are connected by pair-wise private and authentic channels in a synchronous network.
Set $\Evlset = \{P_1, P_2, \ldots, P_{t+1}\}$, termed as the evaluator set, comprises parties that are active during the online phase. Set $\Hlpset = \{P_{t+2}, P_{t+3}, \ldots, P_n\}$, termed as the helper set, comprises parties which help in the preprocessing phase, and in the online verification in the malicious setting.
Parties agree on a $\Pking \in \Evlset$. Without loss of generality, let $\Pking = P_{t+1}$.

Sharing semantics

We use the following sharing semantics, based on RSS & additive sharing schemes, which facilitate a fast online phase.

* $\sqr{\cdot}$-sharing: This denotes the replicated secret sharing (RSS) of a value with threshold $t$.

A value $\va \in \Z{\ell}$ is said to be RSS-shared with threshold $t$ if for every subset $\T \subset \Partyset$ of $n-t$ parties there exists $\sqr{\va}_{\T} \in \Z{\ell}$ possessed by all $P_i \in \T$ such that $\va = \sum_{\T} \sqr{\va}_{\T}$.

Alternatively, for every set of $t$ parties, the residual $h = n-t$ parties forming the set $\T$, hold the share $\sqr{\va}_{\T}$.

Let $\T_1, \T_2, \ldots, \T_{\h} \subset \Partyset$ be the distinct subsets of size $h$, where $\h = \binom n {h}$ represents the total number of shares.

Since $P_i$ belongs to $\binom{n-1}{h-1}$ such sets, the tuple of shares $\{\sqr{\va}_{\T}\}$ that it possesses are denoted as $\sqr{\va}_i$.

* $\sgr{\cdot}$-sharing: A value $\va \in \Z{\ell}$ is said to be $\sgr{\cdot}$-shared (additively shared) among parties in $\Partyset$ if $P_i \in \Partyset$ possesses $\sgr{\va}_i \in \Z{\ell}$ such that $\va  = \sgr{\va}_1 + \sgr{\va}_2 + \ldots + \sgr{\va}_n$.

* $\tsgra{\cdot}{\T}$-sharing: A value $\va \in \Z{\ell}$ is said to be $\tsgra{\cdot}{\T}$-shared among $t+1$ parties in $\T$,
if each $P_i \in \T$ holds $\tsgra{\va}{\T}_i$ such that $\va  = \sum_{P_i \in \T} \tsgra{\va}{\T}_{i}$. We refer to this sharing scheme as $(t+1)$-additive sharing, and use $\tsgr{\va}$ to denote such a sharing among parties in $\Evlset$.

* $\shr{\cdot}$-sharing: A value $\va \in \Z{\ell}$ is said to be $\shr{\cdot}$-shared in the semi-honest setting if there exist values $\lv{\va}, \mv{\va} \in \Z{\ell}$ such that $\mv{\va} = \va + \lv{\va}$ where $\lv{\va}$ is $\sqr{\cdot}$-shared among $\Partyset$ and every $P_i \in \Evlset$ holds $\mv{\va}$. We denote the shares of $P_i \in \Hlpset$ by $\shr{\va}_{i} = \sqr{\lv{\va}}_{i}$ and that of $P_i \in \Evlset$ as  $\shr{\va}_{i} = (\mv{\va}, \sqr{\lv{\va}}_{i})$.
In the malicious setting, $\mv{\va}$ is held by all parties, and $\shr{\va}_{i} = (\mv{\va}, \sqr{\lv{\va}}_{i})$ for all $P_i \in \Partyset$.

It is trivial to see that all the sharing schemes mentioned above are linear. This allows parties to compute linear operations such as addition and multiplication with constants locally.

The Boolean world operates over $\Z{}$, and we denote the corresponding Boolean sharing with a superscript B. Notations are summarized in notations.

Helper primitives

We use the primitives described in helper from literature [13, 15, 74, 26] in our protocols, and their details are deferred to <ref>. The Boolean variants of corresponding primitives are denoted with a superscript B.

§ MPCLAN PROTOCOL

This section details the semi-honest MPC protocol execution performed over the ring $\Z{\ell}$ that comprises three phases– input sharing, evaluation (linear operations and multiplication), and output reconstruction.

Input sharing and Output Reconstruction

To enable $P_s \in \Partyset$ to $\shr{\cdot}$-share a value $\val \in \Z{\ell}$, parties first non-interactively sample $\sqr{\cdot}$-shares of $\lv{\val}$, relying on the shared-key setup, such that $P_s$ learns all these shares on clear (via $\PiRandRP$). This enables $P_s$ to compute and send $\mv{\val} = \val + \lv{\val}$ to parties in $\Evlset$, thereby generating $\shr{\val}$.

To reconstruct $\val$ towards all parties given $\shr{\val}$, parties in $\Evlset$ non-interactively generate its additive shares, $\tsgr{\val}$, among themselves (via $\Pictashr$). These parties send their additive shares to $\Pking$, who computes and sends $\val$ to all parties. Reconstruction towards a single party, say $P_s$, proceeds similarly except that the protocol terminates after parties in $\Evlset$ send their additive shares of $\val$ to $\Pking = P_s$, who then computes $\val$.

Evaluation comprises linear operations of addition and multiplication with public constant, and non-linear operations such as multiplication. Parties can non-interactively compute linear operations owing to the linearity of the $\shr{\cdot}$-sharing. Concretely, given $\shr{\va}, \shr{\vb}$ and public constants $\vc_1, \vc_2$, parties can non-interactively compute $\shr{\vc_1 \va + \vc_2 \vb}$ as $\vc_1 \shr{\va} + \vc_2 \shr{\vb}$.

To compute $\shr{\cdot}$-shares for non-linear operations such as multiplication, say $\vz = \va \vb$ given $\shr{\va}, \shr{\vb}$, parties proceed as follows. At a high-level, the approach is to enable generation of $\shr{\vz - \vr}$ and $\shr{\vr}$ for a random $\vr \in \Z{\ell}$, which enables parties to non-interactively compute $\shr{\vz} = \shr{\vz - \vr} + \shr{\vr}$. Observe that $\shr{\vr}$ can be generated non-interactively by locally sampling each of its shares.
To generate $\shr{\vz - \vr}$, we let parties in $\Evlset$ obtain $\vz - \vr$, following which $\shr{\vz - \vr}$ can be generated non-interactively (this is achieved via $\Piptosh$ where all parties set their shares of $\sqr{\lv{\vz - \vr}}$ as 0, and parties in $\Evlset$ set $\mv{\vz - \vr} = \vz - \vr$). Observe that $\vz$ remains private while revealing $\vz - \vr$ to parties in $\Evlset$ since $\vr$ is a random mask not known to adversary.

To enable parties in $\Evlset$ to obtain $\vz - \vr$, we let $\vz - \vr = \D + \E$, where $\D$ is additively shared among parties in $\Hlpset$ while $\E$ is additively shared among parties in $\Evlset$ ($\D, \E$ are defined in the following paragraphs). Thus, to reconstruct $\vz - \vr$ towards parties in $\Evlset$, parties send their respective additive shares of $\D$ or $\E$ towards $\Pking \in \Partyset$. $\Pking$ reconstructs $\D, \E$, and sends $\vz - \vr = \D + \E$ to parties in $\Evlset$.

Elaborately, as seen in [21, 57], $\vz - \vr$ can be computed as

\begin{align}
\vz - \vr &=  \va \vb - \vr = \left( \mv{\va} - \lv{\va} \right) \left( \mv{\vb} - \lv{\vb} \right) - \vr \nonumber \\
&= \cmv{\va \vb} -\mv{\va} \lv{\vb} - \mv{\vb} \lv{\va} + \clv{\va \vb} - \vr \label{maskedVz} \\
&= \underbrace{\cmv{\va \vb} -\mv{\va} \lv{\vb} - \mv{\vb} \lv{\va} + (\clv{\va \vb} - \vr)_{\Evlset}}_{\E} + \underbrace{(\clv{\va \vb} -  \vr)_{\Hlpset}}_{\D}  \nonumber
\end{align}

where $\clv{\va \vb} - \vr = (\clv{\va \vb} - \vr)_{\Hlpset} + (\clv{\va \vb} - \vr)_{\Evlset}$.

We next detail the steps in the multiplication protocol, and its schematic representation is provided in figure:multsemi.

$\blacktriangleright$ Step 1:  Parties non-interactively generate $\sqr{\vr}$ by locally sampling each of its shares (via $\PiRandR$). Parties locally compute $\sgr{\vr}$ and $\shr{\vr}$ from $\sqr{\vr}$ using $\Pictaf$ and $\Pisqtosh$, respectively. Looking ahead, $\sgr{\vr}$ aids in generating additive shares of $\D, \E$, while $\shr{\vr}$ aids in computing $\shr{\vz}$ from $\shr{\vz - \vr}$.

$\blacktriangleright$ Step 2: This step involves computing additive shares of $\clv{\va \vb} - \vr$ among all parties. For this, parties non-interactively generate $\sgr{\clv{\va \vb}}$ from $\sqr{\lv{\va}}, \sqr{\lv{\vb}}$ (via $\Picprod$). $P_i \in \Partyset$ sets its additive share of $\clv{\va \vb} - \vr$ as $\sgr{\clv{\va \vb} - \vr}_i = \sgr{\clv{\va \vb}}_i - \sgr{\vr}_i$. Observe that the shares $\sgr{\clv{\va \vb} - \vr}_i$ of $P_i \in \Hlpset$ define the additive shares of $\D = (\clv{\va \vb} - \vr)_{\Hlpset}$ among parties in $\Hlpset$. Similarly, the shares $\sgr{\clv{\va \vb} - \vr}_i$ of $P_i \in \Evlset$ define the additive shares of $(\clv{\va \vb} - \vr)_{\Evlset}$ among parties in $\Evlset$ (i.e. $\tsgr{(\clv{\va \vb} - r)_{\Evlset}}$ ).

$\blacktriangleright$ Step 3: Parties in $\Evlset$ generate additive shares of $\lv{\va}, \lv{{\vb}}$ among themselves ($\tsgr{\cdot}$-shares, via $\Picta$). Looking ahead, $\tsgr{\lv{\va}}, \tsgr{\lv{\vb}}$ aid in generating additive shares of $\E$ among $\Evlset$.

$\blacktriangleright$ Step 4: Parties in $\Hlpset$ send their additive shares of $\D$ (as defined in step 2) to $\Pking$, who reconstructs $\D$.

$\blacktriangleright$ Step 5: $P_i \in \Evlset \setminus \{\Pking\}$ non-interactively generates additive share, $\tsgr{\E}_i$, of $\E$ among parties in $\Evlset$ as $\tsgr{\E}_i = - \mv{\va} \tsgr{\lv{\vb}}_i - \mv{\vb} \tsgr{\lv{\va}}_i + \tsgr{(\clv{\va \vb} - \vr)_{\Evlset}}_i$. Note that it suffices for only one designated party in $\Evlset$ to add $\cmv{\va \vb}$ in its share of $\tsgr{\E}$, and without loss of generality we let this designated party be $\Pking$. For $\Pking = P_{t+1}$ in our case, $\tsgr{\E}_{t+1} = \cmv{\va \vb} - \mv{\va} \tsgr{\lv{\vb}}_{t+1} - \mv{\vb} \tsgr{\lv{\va}}_{t+1} + \tsgr{(\clv{\va \vb} - \vr)_{\Evlset}}_{t+1}$. Parties send their additive shares of $\E$ to $\Pking$, who reconstructs $\E$, and sends $\vz - \vr = \D + \E$ to parties in $\Evlset$.

$\blacktriangleright$Step 6: Parties non-interactively generate $\shr{\vz - \vr}$ (via $\Piptosh$) as explained earlier. Using $\shr{\vr}$ generated in step 1, parties compute $\shr{\vz} = \shr{\vz - \vr} + \shr{\vr}$, as required.

$\PiMult(\Partyset, \shr{\va}, \shr{\vb}, \istr)$Semi-honest: Multiplication protocolfig:piMultr

$\istr = 1$ denotes perform truncation, $\istr = 0$ denotes otherwise.

1 If $\istr = 0$: invoke $\PiRandR$ to generate $\sqr{\vr}$ where $\vr  \in \Z{\ell}$. Invoke $\Pictaf$ and $\Pisqtosh$ on $\sqr{\vr}$ to generate $\sgr{\vr}$ and $\shr{\vr}$, respectively.

* Else, invoke $\PiDSBits(\Partyset, 1)$ (fig:piDSBits) to generate $\shr{\vr}, \shr{\trunc{\vr}}$, and $\Pictashrf$ on $\shr{\vr}$ to generate $\sgr{\vr}$ .

2 Invoke $\Picprod$ on  $\sqr{\lv{\va}}, \sqr{\lv{\vb}}$ to generate $\sgr{\clv{\va \vb}}$, and compute $\sgr{\clv{\va \vb} - \vr} = \sgr{\clv{\va \vb}} - \sgr{\vr}$.

* $P_i \in \Evlset$ sets $\tsgr{(\clv{\va \vb} - r)_{\Evlset}}_i = \sgr{\clv{\va \vb} - r}_i$.

3 $P_i \in \Evlset$ invokes $\Picta$ on $\sqr{\lv{\va}}, \sqr{\lv{\vb}}$ to generate $\tsgr{\lv{\va}}_i, \tsgr{\lv{\vb}}_i$, respectively.

4 $P_i \in \Hlpset$ sends $\sgr{\clv{\va \vb} - \vr}_i$ to $\Pking$, who sets $\D = \sum_{i: P_i \in \Hlpset} \sgr{\clv{\va \vb} - \vr}_i$.

5 $P_i \in \Evlset$ computes $\tsgr{\zeta}_{i} = -\mv{\va} \tsgr{\lv{\vb}}_{i} - \mv{\vb} \tsgr{\lv{\va}}_{i} + \tsgr{(\clv{\va \vb} - \vr)_{\Evlset}}_i$, and sends $\tsgr{\zeta}_i$ to $\Pking$.

* $\Pking$ computes $\E = \cmv{\va \vb} + \sum_{i: P_i \in \Evlset} \tsgr{\zeta}_{i}$ and sends $\vz - \vr = \D + \E$ to all parties in $\Evlset$.

6 If $\istr = 0$: invoke $\Piptosh$ on $\vz - \vr$ to generate $\shr{\vz - \vr}$, and compute $\shr{\vz} = \shr{\vz - \vr} + \shr{\vr}$.

* Else, invoke $\Piptosh$ on $\trunc{(\vz - \vr)}$ to generate $\shr{\trunc{(\vz - \vr)}}$, and compute $\shr{\trunc{\vz}} = \shr{\trunc{(\vz - \vr)}} + \shr{\trunc{\vr}}$.

Protocol $\PiMult$ (fig:piMultr) incurs a communication of $t$ elements in the preprocessing phase and $2t$ elements in $2$ rounds in the online phase for multiplication when $\istr = 0$.

Analysis: Observe that the communication towards $\Pking$ in steps 4 and 5, can be performed in parallel, resulting in the overall round complexity of the protocol being two. Further, a communication of $t$ elements is required in step 4 and $2t$ elements is required in 5 (since $\Pking \in \Evlset$), thereby having a total communication complexity of $3t$ ring elements. This complexity resembles that of DN07. However, our sharing semantics enables us to push some of the steps mentioned above to a preprocessing phase, resulting in a fast online phase, which is non-trivial to achieve in the case of DN07. Elaborately, observe that since $\vr, \lv{\va}, \lv{\vb}$ are independent of the input (owing to our sharing semantics), computation involving these terms ranging from steps 1 to 4 can thus be moved to a preprocessing phase. This improves the online communication complexity by slashing the inward communication towards $\Pking$ by half. Thus, the online phase requires only $2t$ ring elements of communication while offloading $t$ elements of communication to the preprocessing phase.

Note that a straightforward extension of semi-honest multiplication of [31] to the preprocessing model, which can be derived from [38], does not provide an efficient solution. Although such a protocol has the same online complexity ($2t$ elements) as our online phase, it has the drawback of inflating the overall communication cost by a factor of $1.6\times$ over [31]. Elaborately, the online communication cost of $2t$ elements can be attained by appropriately defining the sharing semantics and using the $\Pking$ approach, similar to our protocol. However, this requires parties to generate the sharing of $\clv{\va \vb} = \lv{\va}\cdot\lv{\vb}$ from the shares of $\lv{\va}$ and $\lv{\vb}$ during the preprocessing phase, and requires a full-fledged multiplication, incurring a cost of $3t$ elements. This yields a protocol with a total cost of $5t$ elements in comparison to the $3t$ cost of the all-online DN07 protocol. Thus, departing from this approach, the novelty of our protocol lies in leveraging the interplay between the sharing semantics and redesigning the communication pattern among the parties to ensure that the total cost of $3t$ does not change.

Furthermore, our protocol design allows parties in $\Hlpset$ to remain shut in the online phase, thereby reducing the system's operational load. This is because parties in $\Hlpset$ only contribute towards the computation of $\D$, which can be completed in the preprocessing phase. However, the preprocessing phase becomes function-dependent due to the linear gates, for which the $\lv{}$ value for the output wires cannot be chosen randomly. Concretely, if $\vc$ is the output of a linear gate, say addition, with inputs $\va, \vb$, then $\lv{\vc}$ cannot be chosen randomly and should be defined as $\lv{\vc} = \lv{\va} + \lv{\vb}$.

Ideal functionality $\Fmpc$ for evaluating function $f$ in the $n$-party setting with semi-honest security appears in fig:Fmpc.

$\Fmpc$Semi-honest: Ideal functionality for function $f$fig:Fmpc
$\Fmpc$ interacts with the parties in $\Partyset$ and the adversary $\simsh$. Let $f$ denote the function to be  computed. Let $\wx_s$ be the input corresponding to the party $P_s$, and $\wy_s$ be the corresponding output, i.e $(\{\wy_s\}_{s=1}^{n}) = f(\{\wx_s\}_{s=1}^{n})$.

Step 1: $\Fmpc$ receives $(\INPUT,\wx_s)$ from $P_s \in \Partyset$, & computes $(\{\wy_s\}_{s=1}^{n}) = f(\{\wx_s\}_{s=1}^{n})$.

Step 2: $\Fmpc$ sends  $(\OUTPUT, \wy_s)$ to $P_s \in \Partyset$.

Incorporating truncation

To retain FPA semantics, it is required to truncate the result of multiplication, $\vz = \va \vb$, which ends up having $2d$ bits in the fractional part, by $d$ bits, i.e. compute $\trunc{\vz} = \vz / 2^d$. For this, we extend the probabilistic truncation technique of [68, 56, 57] proposed in the small party domain to the $n$-party setting. Given $(\vr, \trunc{\vr})$-pair, with $\trunc{\vr} = \vr/2^d$, the truncated value of $\vz$ can be obtained as $\trunc{\vz} = \trunc{(\vz - \vr)} + \trunc{\vr}$. Accuracy and correctness of this method follows from [68, 66].

$\Ftrgen$Ideal functionality $\Ftrgen$fig:Ftrgen

– Samples random $\vr \in \Z{\ell}$, and computes $\trunc{\vr} = \vr/ 2^{d}$.

– Generates $\shr{\cdot}$-shares of $\vr, \trunc{\vr}$ and set output share for $P_s \in \Partyset$ as $\wy_s = \{\shr{\vr}_s, \shr{\trunc{\vr}}_s \}$.

* Output:  Send $(\OUTPUT, \wy_s)$ to $P_s \in \Partyset$.

Our multiplication protocol can be modified to additionally perform truncation by incorporating the following two changes– (i) generate $\shr{\trunc{\vr}}$ in step 1, and (ii) compute $\shr{\trunc{\vz}} = \shr{\trunc{(\vz - \vr)}} + \shr{\trunc{\vr}}$, instead, in step 6. For (i), we rely on the ideal functionality, $\Ftrgen$ (fig:Ftrgen), for computing $\shr{\vr}, \shr{\trunc{\vr}}$. $\Ftrgen$ can be instantiated using the appropriate MPC protocol which will be used as a black-box in our multiplication. Thus, improvements in the MPC protocol that realizes $\Ftrgen$ can be inherited in our multiplication protocol. In our work, we instantiate $\Ftrgen$ using $\PiDSBits$ (fig:piDSBits), which is a slightly modified version of the doubly-shared random bit generation protocol of [29], adapted to our $n$-party setting. Concretely, $\PiDSBits$ generates $\ell$ doubly-shared random bits instead of a single bit, as done in the protocol of [29]. Here, a doubly-shared random bit is a bit which is arithmetic as well as Boolean shared.  We defer the details of $\PiDSBits$ to <ref> since it follows easily from the protocol of [29].
With respect to (ii), observe that it is a local operation, and hence performing truncation does not incur any additional overhead in the online phase.

Dot product

Given $\shr{\cdot}$-shares of vectors $\vec{x}$ and $\vec{y}$ of size $\nf$, dot product outputs $\shr{\vz}$ where $\vz = \vec{x} \band \vec{y} = \sum_{k = 1}^{\nf} \vx_k \vy_k$ and $\band$ denotes the dot product operation.

The design of our multiplication protocol enables easy extension to support dot product computation without incurring any overhead. Concretely, similar to multiplication,

\begin{align}
\vz - \vr &=  (\vec{x} \band \vec{y}) - \vr  \nonumber\\
&= \sum_{k=1}^{\nf}\cmv{\vx_k \vy_k} -\sum_{k=1}^{\nf} \mv{\vx_k} \lv{\vy_k} - \sum_{k=1}^{\nf} \mv{\vy_k} \lv{\vx_k} + \sum_{k=1}^{\nf} \clv{\vx_k \vy_k} - \vr \label{maskeddotp}
\end{align}

In each of the summands of $\vz - \vr$, each of the $\nf$ product terms can be generated similar to that in the multiplication protocol, which can then be locally summed up before sending it towards $\Pking$. Due to this simple extension, we defer the formal dot product protocol (fig:pidotp) to <ref>.
Looking ahead, for matrix multiplication, each element of the resultant matrix can be computed via a dot product.

Multi input multiplication

3-input and 4-input multiplication protocols have showcased their wide applicability in improving the online phase complexity [57, 73, 71]. Concretely, computing $\vz = \va \vb \vc$ (3-input) or $\vz = \va \vb \vc \vd$ (4-input) naively requires at least two sequential invocations of 2-input multiplication protocol in the online phase. Instead, 3-input and 4-input multiplication protocol, respectively, enables performing this computation with the same online complexity as that of a single 2-input multiplication. Thus, we design 3-input and 4-input multiplication protocols by extending the techniques of [73, 57] to the $n$-party setting.

Designing these protocols require modifications in the preprocessing steps.

Consider 3-input multiplication where the goal is to generate $\shr{\cdot}$-sharing of $\vz = \va \vb \vc$ given $\shr{\va}, \shr{\vb}, \shr{\vc}$. Note that

\begin{align*}
\vz - \vr
&= \va \vb \vc - \vr = (\mv{\va} - \lv{\va})(\mv{\vb} - \lv{\vb})(\mv{\vc} - \lv{\vc}) - \vr \\
&= \cmv{\va\vb\vc} - \cmv{\va\vc} \lv{\vb} - \cmv{\vb\vc} \lv{\va} - \cmv{\va\vb} \lv{\vc} \\
&~~~+ \mv{\va} \clv{\vb \vc} + \mv{\vb} \clv{\va \vc} + \mv{\vc} \clv{\va \vb} - \clv{\va \vb \vc} - \vr
\end{align*}

We follow an approach closely related to 2-input multiplication, with the difference being that parties additionally require to generate the additive sharing of $\clv{\vb \vc}, \clv{\va \vc}$ and $\clv{\va \vb \vc}$ during preprocessing. Given these sharings, parties proceed with a similar online phase as in $\piMult$ to compute the 3-input multiplication without inflating the online cost. Similarly, for 4-input multiplication, parties need to generate the additive sharing of $\clv{\va \vd}, \clv{\vb \vd}, \clv{\vc \vd}, \clv{\va \vb \vd}, \clv{\va \vc \vd}, \clv{\vb \vc \vd}, \clv{\va \vb \vc \vd}$ in addition to those required in the case of 3-input multiplication. The generation of these sharings follows a similar approach as the 2-input multiplication, and the details are deferred to <ref>. mmultsh compares the cost of computing $\vz = \va \vb \vc$ via a 2-input multiplication sequentially vs a 3-input multiplication, and computing $\vz = \va \vb \vc \vd$ via a 2-input and 4-input multiplication.

r r r r r

type     [c]2-1Building
[c]1-2Communication         [c]2-1Online

Prep.     Online

2-1$\vz = \va \vb \vc$     2-input mult.     $2t \ell$     $4t \ell$     $4$

3-input mult.     $6t \ell$     $2t \ell$      $2$

2-1$\vz = \va \vb \vc \vd$     2-input mult.     $3t \ell$     $6t \ell$     $4$

4-input mult.     $15t \ell$      $2t \ell$     $2$

Semi-honest: Communication and round complexity for computing multi-input multiplications

The recent work of [46] provides a method to reduce the round complexity of circuit evaluation. They group the (distinct) consecutive layers in the circuit into pairs and perform a parallel evaluation of all gates in the two layers in a group. Consider a multiplication gate with inputs $\vx, \vy$ (obtained as output from a previous layer) and output $\vz$. Their approach considers three cases: (i) if $\vx$ and $\vy$ are not the outputs of a multiplication gate, (ii) exactly one among $\vx,\vy$ is the output of a multiplication gate, and (iii) both $\vx, \vy$ are outputs of a multiplication gate.

We observe that case (ii) and (iii) in their approach resembles multi-input multiplication, which allows evaluating the second layer of multiplication ($\vz = \vx \cdot \vy$) non-interactively, thereby saving on rounds.

For instance, consider a 2-layer sub-circuit as in fig:multi-input where $\vx = \va \cdot \vb, \vy = \vc \cdot \vd$ are outputs of a multiplication gate which are fed as input to a multiplication gate in the next level. The approach of [46] allows computation of $\vz = (\va \cdot \vb) \cdot (\vc \cdot \vd)$ in a single shot, which is equivalent to computing $\vz$ via a 4-input multiplication in our case.
Similarly, when only one of the inputs (either $\vx$ or $\vy$) is the output of multiplication, computation of $\vz = \vx \cdot \vy$ resembles a 3-input multiplication.

Thus, cases (i), (ii), (iii) correspond to 2-input, 3-input, and 4-input multiplication, respectively, in our work and are sufficient to reduce round complexity of any circuit evaluation by half. Hence, we restrict our focus to 3 and 4-input multiplication.

§ EXTENDING TO MALICIOUS SECURITY

Using standard approaches [74, 56, 38], it is straightforward to adapt the semi-honest protocols such as input sharing and output reconstruction to the malicious setting. The details are provided in <ref> for completeness. Hence, in this section, we focus on the challenges encountered and their resolutions for obtaining a maliciously secure multiplication protocol.

Note that although a maliciously secure multiplication protocol can be achieved by compiling our semi-honest protocol using compiler techniques such as [1, 15], the resultant protocol has an expensive online phase. For instance, using the compiler of [1] yields a protocol that requires computation over extended rings and communicating $4t$ extended ring elements in the online phase. This is not favourable compared to working over plain rings, especially in the online phase. Further, compilers such as those in [15] require heavy computational machinery like reliance on zero-knowledge proofs in the online phase, which is also not desirable. Thus, to attain a computation and communication efficient online phase, departing from the aforementioned compiler-based approaches, we design a maliciously secure multiplication protocol that requires communicating $3t$ ring elements in each phase. It is worth noting that we can do this while retaining the benefits of requiring only $t+1$ parties in the online phase (for most of the computation). The remaining $t$ parties are required to come online only for a short one-time verification phase, that is deferred to the end of the computation. Deferring verification may result in a privacy breach [47]. However, we describe later why the privacy breach does not arise in our protocol.

To enable generation of $\shr{\vz} = \shr{\va  \vb}$ from $\shr{\va}$ and $\shr{\vb}$, we retain the high-level ideas from the semi-honest protocol.
Our task reduces to $\mynum{i}$ generating additive shares of $\clv{\va \vb}$ among parties in $\Evlset$ (i.e. $\tsgr{\clv{\va \vb}}$) given $\sqr{\lv{\va}}$ and $\sqr{\lv{\vb}}$, in the preprocessing phase, and $\mynum{ii}$ reconstructing  $\vz - \vr$ in the online phase.
Given $\mynum{i}$, computing $\tsgr{\vz - \vr}$ in the online phase is a local operation. Given  $\mynum{ii}$, parties can invoke $\Piptoshf$ to generate $\shr{\vz - \vr}$, and compute $\shr{\vz} = \shr{\vz - \vr} + \shr{\vr}$, where $\shr{\vr}$ is generated in the preprocessing phase, as discussed in the semi-honest case.

$\FMulPre$Ideal functionality $\FMulPre$fig:FMulPre
$\FMulPre$ interacts with the parties in $\Partyset$ and the adversary $\Sim$. Let $\T_{i}$ be the set of the honest parties.

* Input: $\FMulPre$ receives the $\sqr{\cdot}$-shares of $\va, \vb$ from the parties. It also receives $\sqr{\cdot}$-shares of $\vz = \va \vb$ of corrupt parties from $\Sim$. $\Sim$ is also allowed to send a special command, $(\abort, \Ab)$, which indicates that parties in $\Partyset$ with indices in $\Ab$ should $\abort$.

$\FMulPre$ proceeds as follows.

– Reconstruct $\va, \vb$ using the shares received from honest parties, and compute $\vz = \va \vb$.

– Compute the $\sqr{\cdot}$-share of $\vz$ to be held by the set of honest parties as the difference between $\vz$ and the sum of $\sqr{\cdot}$-shares of $\vz$ received from corrupt parties.

– Let $\wy_s$ denote the $\sqr{\cdot}$-shares of $\vz$
for party $P_s \in \Partyset$. If received $(\abort, \Ab)$ from $\Sim$, set  $\wy_s = \abort$ for $P_s$, where $s \in \Ab$.

* Output:  Send $(\OUTPUT, \wy_s)$ to every $P_s \in \Partyset$.

For task $\mynum{i}$, our idea for the semi-honest case, of making parties in $\Hlpset$ to send their shares to $\Pking$, does not work in the presence of a malicious adversary. To address this, we make black-box use of a maliciously secure multiplication protocol, abstracted as a functionality  $\FMulPre$ in fig:FMulPre, that computes $\sqr{\clv{\va \vb}}$ from $\sqr{\lv{\va}}, \sqr{\lv{\vb}}$. In this work, we instantiate $\FMulPre$ with the state-of-the-art multiplication protocol of [15] that provides $\abort$ security. Note that although the protocol of [15] relies on zero-knowledge proofs, this computation is carried out in the preprocessing phase of our multiplication protocol. Moreover, since preprocessing is done for many instances in one shot, the zero-knowledge proof can benefit from amortization.
The parties then invoke $\Picta$ to obtain $\tsgr{\clv{\va \vb}}$ from $\sqr{\clv{\va \vb}}$. Looking ahead, $\sqr{\clv{\va \vb}}$ also aids in performing the online verification check.

For task $\mynum{ii}$,  in the online phase, we retain the idea of parties in $\Evlset$ optimistically reconstructing $\vz - \vr$ from their additive shares ($\tsgr{\cdot}$-share) to ensure that only the parties in $\Evlset$ remain active for most of the computation. Moreover, this optimistic reconstruction requires only $\Order(t)$-element communication rather than the $\Order(t^{2})$ required for reconstruction from $\sqr{\cdot}$-shares (which is what will be used later for performing verification, albeit to perform only one such reconstruction). Thus, similar to the semi-honest protocol, parties in $\Evlset$ optimistically reconstruct $\vz - \vr$ towards $\Pking$, who further sends the reconstructed value to the parties in $\Evlset$. In the malicious setting, this approach requires additional care since a malicious party may send a wrong $\tsgr{\cdot}$-share of $\vz - \vr$ to $\Pking$ or a malicious $\Pking$ may send an incorrectly reconstructed (inconsistent) $\vz - \vr$ to the parties. To account for these behaviours, the protocol is augmented with a short one-off verification phase to verify the consistency and correctness of $\vz - \vr$. This phase is executed in the end of the protocol and requires the presence of all parties, and hence the possession of $\vz - \vr$ by all. This is in contrast to the semi-honest protocol where $\vz - \vr$ is given to only parties in $\Evlset$. To keep $\Hlpset$ disengaged for most of the online phase, sending $\vz - \vr$ to them is deferred till the end of the protocol. This send is a one-off and can be combined for all multiplication gates. Details of verification protocol  $\Pivrfy$ (fig:Pivrfy) are given next.

Verification comprises two checks– a consistency check to first verify that $\Pking$ has indeed sent the same $\vz - \vr$ to all the parties, followed by a correctness check to verify the correctness of the $\vz - \vr$. For the former, parties perform a hash-based consistency check of $\vz - \vr$,  and abort in case of any inconsistency. If $\vz - \vr$ is consistent, parties verify its correctness.

The high-level idea for verifying correctness is to robustly reconstruct $\vz - \vr$, but now from its $\sqr{\cdot}$-shares (can be computed given $\sqr{\lv{\va}}, \sqr{\lv{\va}}, \sqr{\clv{\va \vb}}$ that are generated in the preprocessing phase). Parties can then verify if this reconstructed value equals the value received from $\Pking$. Concretely, this is equivalent to robustly reconstructing $\sqr{\Omega} = \sqr{\vz - \vr - (\cmv{\va \vb} -\mv{\va} \lv{\vb} - \mv{\vb} \lv{\va} + \clv{\va \vb} - \vr)}$, where $\vz - \vr$ is the value received from $\Pking$, and verifying if $\Omega = 0$.

For robust reconstruction of $\sqr{\Omega}$, every party sends its $\sqr{\cdot}$-share to every other party who misses this share, and $\abort$s in case of inconsistencies in the received values. Elaborately, reconstruction of $\Omega$ towards $P_s \in \Partyset$ proceeds as follows. For each missing $\sqr{\cdot}$-share of $\Omega$ at $P_s$, each of the $t+1$ parties holding this share send it to $P_s$. $P_s$ uses this share for reconstruction if all the $t+1$ received values are consistent, else it $\abort$s. Presence of at least one honest party among the $t+1$ guarantees that inconsistency, if any, can be detected.
Since each share in $\sqr{\Omega}$ is held by $t+1$ parties, comprising at least one honest party, any cheating by up to $t$ corrupt parties is guaranteed to be detected. Note that this reconstruction requires communicating $\Order(t^2)$ ring elements to verify the correct computation of a single multiplication gate, the cost of which can be optimized using standard optimization techniques [1, 23]. Concretely, the correctness of $\vz - \vr$ for several multiplication gates can be verified with a single reconstruction by reconstructing a linear combination of $\Omega$ for several gates and verifying equality with $0$. Thus, only one robust reconstruction from $\sqr{\cdot}$-shares is required for several multiplication gates, whose cost gets amortized due to verification across multiple gates.

$\Pivrfy \left(\Partyset, \{ \shr{\va_i}, \shr{\vb_i}, \vz_i - \vr_i, \sqr{\clv{\va_i \vb_i}}, \sqr{\vr_i} \}_{i=1}^{m} \right)$Malicious: Verification protocol for all multiplication gatesfig:Pivrfy

Let $(\va_1, \vb_1, \vz_1),  \ldots, \allowbreak (\va_m, \vb_m, \vz_m)$ denote the inputs and outputs of the $m$ multiplication gates to be verified.

– Consistency Check. Invoke $\Picon$ on $\{\vz_1 - \vr_1, \ldots, \vz_m - \vr_m\}$.

– Correctness Check. Repeat the following $\kappa$ times.

- Generate random $\theta_1, \ldots, \theta_m \in \Z{\ell}$ and compute

\begin{align*}
\sqr{\Omega} =  \sum_{i=1}^{m} \theta_i \left( \vz_i - \vr_i - \left( \cmv{\va_i \vb_i} -\mv{\va_i} \sqr{\lv{\vb_i}} - \mv{\vb_i} \sqr{\lv{\va_i}} + \sqr{\clv{\va_i \vb_i}} - \sqr{\vr_i} \right) \right)
\end{align*}

- For each $\sqr{\cdot}$-share of $\Omega$, the $t+1$ parties possessing this share send it to every party that misses this share. If the recipient party receives inconsistent values for any missing share, it $\abort$s.

- Reconstruct $\Omega$ and $\abort$ if $\Omega \neq 0$.

It is worth noting that this random linear combination technique does not trivially work over rings. This is due to the existence of zero divisors which results in the linear combination being $0$ with a probability $1/2$ (which denotes the cheating probability of the adversary) [1]. Hence, to obtain the desired security, the verification check is repeated $\kappa$ times where $\kappa$ is the security parameter. This bounds the cheating probability of adversary to $1/2^{\kappa}$. Another approach is to perform the verification over extended rings [13, 14]. Specifically, verification operations are carried out over a ring $\Z{\ell}/f(x)$ which is a ring of all polynomials with coefficients in $\Z{\ell}$ modulo a degree $d$ polynomial $f(x)$ that is irreducible over $\Z{}$. Each element of $\Z{\ell}$ is lifted to a degree $d$ polynomial in $\Z{\ell}[x]/f(x)$, which increases the communication required to perform verification by a factor of $d$.

To summarize, the maliciously secure multiplication protocol (see fig:piMultMal) can be broken down into the following.

– Preprocessing phase which involves generation of $\sqr{\clv{\va \vb}}$ by invoking $\FMulPre$. Malicious behaviour, if any, will be caught by $\FMulPre$. $\sqr{\clv{\va \vb}}$ is non-interactively converted into $\tsgr{\cdot}$-shares of $\lv{\va \vb}$.
$\tsgr{\lv{\va}}, \tsgr{\lv{\vb}}$ is also generated non-interactively.

–  Generation of $\tsgr{\cdot}$-shares of $\lv{\va}, \lv{\vb}, \clv{\va \vb}$ during preprocessing enables computation of $\tsgr{\vz - \vr}$ in the online phase, and thereby reconstruction of $\vz - \vr$ via $\Pking$. The crucial point to note here is that this requires the presence of only parties in $\Evlset$ in the online phase. This is followed by non-interactive generation of $\shr{\vz - \vr}$ from which $\shr{\vz}$ is computed as $\shr{\vz} = \shr{\vz - \vr} + \shr{\vr}$, where $\shr{\vr}$ is generated during preprocessing.

– Finally, to catch malicious behaviour in the online phase, if any, in the verification phase the correctness of the generated $\shr{\vz}$ is checked simultaneously, for each $\vz$ that is the output of a multiplication gate. This is done by invoking $\Pivrfy$. Note that before this verification begins, $\Pking$ sends $\vz - \vr$ corresponding to all multiplication gates to parties in $\Hlpset$ in a single shot.

As pointed out in [47], deferring the correctness check to later may result in a privacy breach when using a sharing scheme that allows for redundancy (such as RSS or Shamir sharing). The details are elaborated in <ref>. However, the crucial point to note here is that although we rely on a variant of RSS which introduces redundancy, recall that while performing a reconstruction towards $\Pking$, we rely on $\tsgr{\cdot}$-sharing of $\vz - \vr$, which is a $(t+1)$-additive sharing. The use of additive sharing while performing reconstruction towards $\Pking$ eliminates any redundancy in the sharing scheme and thus, helps in overcoming this subtle privacy breach, as also shown in [47]. This privacy breach persists in [38], and is discussed in <ref>.

Protocol $\PiMultMal$ (fig:piMultMal) incurs a communication of $3t$ elements in the preprocessing phase and $3t$ elements in $2$ rounds in the online phase for multiplication when $\istr = 0$.

The ideal functionality $\Fmpc$ for evaluating a function $f$ in the $n$-party setting while providing malicious security (with $\abort$) appears in fig:FmpcMal.

$\Fmpcmal$Malicious: Ideal functionality for evaluating function $f$fig:FmpcMal
$\Fmpc$ interacts with the parties in $\Partyset$ and the adversary $\simmal$. Let $f$ denote the function to be  computed. Let $\wx_s$ be the input of party $P_s$, and $\wy_s$ be the corresponding output, i.e $(\{\wy_s\}_{s=1}^{n}) = f(\{\wx_s\}_{s=1}^{n})$. $\simmal$ is also allowed to send a special command, $(\abort, \Ab)$, which indicates that honest parties in $\Partyset$ with indices in $\Ab$ should $\abort$.

Step 1: $\Fmpc$ receives $(\INPUT,\wx_s)$ from $P_s \in \Partyset$. If $(\INPUT, \ast)$ already received from $P_s$, then ignore the current message. Otherwise, record $x_s^{\prime} = x_s$ internally.

Step 2: Compute $(\{\wy_s\}_{s=1}^{n}) = f(\{\wx_s\}_{s=1}^{n})$ and send the output $\wy_s$ for a corrupt $P_s$ to $\simmal$.

Step 3: If received $(\SIGNAL, \abort, \Ab)$ from $\simmal$, set $\wy_s = \abort$ for $P_s$, where $s \in \Ab$. Send $(\OUTPUT, \wy_s)$ to honest $P_s \in \Partyset$.

Multiplication with truncation Similar to the semi-honest protocol, truncation can be incorporated in the malicious multiplication as well without inflating the online communication. For this, we rely on maliciously secure ideal functionality, $\Ftrgenmal$ (fig:Ftrgenmal), to generate the $\shr{\cdot}$-shares of $(\vr, \trunc{\vr})$ and is instantiated using $\PiDSBitsMal$ [29] protocol in our work. On a high level, the semi-honest versions of interactive operations such as multiplication and reconstruction in $\PiDSBits$ are replaced with their maliciously secure counterparts in $\PiDSBitsMal$, and more details are provided in <ref>.

Dot product

Similar to the maliciously secure multiplication protocol that relied on $\FMulPre$ to generate $\sqr{\cdot}$-shares of the multiplicative term, $\clv{\va \vb}$ in the preprocessing phase, the maliciously secure dot product protocol invokes $\FDotPPre$ (fig:FDotPPre) to generate $\sqr{\cdot}$-shares of the multiplicative term, $\sum_{k=1}^{\nf} \clv{\vx_k \vy_k}$, required to compute the dot product as per equation (<ref>). Given $\sqr{\cdot}$-shares of $\sum_{k=1}^{\nf} \clv{\vx_k \vy_k}$, online phase proceeds similar to that of multiplication.

Observe that a trivial realization of $\FDotPPre$ can be reduced to $\nf$ instances of multiplication. However, we extend the ideas from [56] and rely on a distributed zero-knowledge proof [15] to eliminate the vector-size dependency in the preprocessing phase. Concretely, we instantiate $\FDotPPre$ using a semi-honest dot product protocol [48] whose cost matches that of semi-honest multiplication [31] (and thus is independent of the vector-size), followed by a verification phase to verify the correctness of the dot product computation. For the verification, we extend the verification technique for multiplication in [15], to now verify the correctness of dot product, such that the cost due to verification can be amortized away for multiple dot products, thereby resulting in vector-size independent preprocessing. Details of this extension are deferred to <ref>.

Multi input multiplication

This protocol is similar to its semi-honest counterpart with the difference that the preprocessing phase relies on invoking $\FMulPre$ for generating the required multiplicative terms. The details are deferred to <ref>. mmultmal compares the cost of computing multi-input multiplication via a 2-input multiplication sequentially vs. the multi-input multiplication protocol.

r r r r r

type     [c]2-1Building
[c]1-2Communication         [c]2-1Online

Prep.     Online

2-1$\vz = \va \vb \vc$     2-input mult.     $6t \ell$     $6t \ell$     $4$

3-input mult.     $12t \ell$     $3t \ell$      $2$

2-1$\vz = \va \vb \vc \vd$     2-input mult.     $9t \ell$     $9t \ell$     $4$

4-input mult.     $33t \ell$      $3t \ell$     $2$

Malicious: Communication and round complexity for computing multi-input multiplications

§ APPLICATIONS & BENCHMARKS

To evaluate the performance of our protocols, we benchmark some of the popular applications such as deep neural networks (NN), graph neural networks (GNN), similar sequence queries (SSQ), and biometric matching where MPC is used to achieve privacy. While these applications have been looked at in the small party setting [70, 56, 81, 5, 79, 85, 73, 68], we believe the $n$-party setting is a better fit for reasons described in the introduction. To the best of our knowledge, we are the first to benchmark these in the multiparty honest-majority setting for more than four parties.

Benchmark environment

The performance of our protocols is analyzed using a prototype implementation building over the ENCRYPTO library [27] in C++17.

We chose $64$ bit ring ($\Z{64}$) for our arithmetic world, and the operations over extended ring were carried out using the NTL library[<https://libntl.org>].

Since the correctness and accuracy of the applications considered in the secure computation setting are already established, our benchmark aims to demonstrate our protocols' performance and is not fully functional. Moreover, we believe that incorporating state-of-the-art code optimizations like GPU-assisted computing can enhance the efficiency of our protocols, which is left as future work. Since there is no defined way to capture an adversary's misbehaviour, following standard practice [68, 56, 28], we benchmark honest executions of the protocols, which also include the steps performed for verification in the malicious case.

Round trip time ($\rtt$)

We use multi-threading, wherever possible, to facilitate efficient computation and communication among the parties. The parties in the computation are emulated using Google Cloud (n1-standard-64 instances, 2.0 GHz Intel Xeon Skylake, 64 vCPUs, 240 GB RAM) with machines located in East Australia, South Asia, South East Asia, and West Europe. All our experiments are run for 5, 7, and 9 parties, each.

Benchmark parameters

We report the run-time and communication of the online phase and total (= preprocessing + online). To capture the effect of online round complexity and communication in one go, we also report the throughput ($\TP$ [4, 68, 56]) of the online phase. $\TP$ denotes the number of operations that can be performed in one minute. Finally, when deployed in the outsourced setting, one pays the price for the communication and up-time of the hired servers. To demonstrate how our protocols fare in this scenario, we additionally report the monetary cost (Cost) [67, 57] for the applications considered. This cost is estimated using Google Cloud Platform [80] pricing, where $1$ GB and $1$ hour of usage costs USD $0.08$ and USD $3.04$, respectively.

§.§ Comparison with DN07

In this section, we benchmark our semi-honest and malicious protocols over synthetic circuits comprising one million multiplications with varying depths of 1, 100, and 1000, and compare against the optimized ring variant of DN07 [13]. The gates are distributed equally across each level in the circuit.

The communication cost for 1 million multiplications is tabulated in cktcomm for the 5, 7, and 9 party settings. As can be observed, the online phase of our semi-honest protocol enjoys the benefits of pushing $33\%$ communication to a preprocessing phase compared to DN07. The observed values corroborate the claimed improvement in the online complexity of our protocol. Our malicious protocol retains the online communication cost of DN07 while incurring a similar overhead in the preprocessing.

Ref.     $n=5$     $n=7$     $n=9$

DN07 (semi)       (0, 45.78)        (0, 68.66)        (0, 91.55)

$\this$ (semi)                (15.26, 30.52)        (22.88, 45.78)        (30.51, 61.04)

$\this$  (mal)                  (45.79, 45.78)        (68.67, 68.67)        (91.57, 91.57)

Communication (Preprocessing, Online) in MB for 1 million multiplications

Note that pushing the communication to the preprocessing phase has several benefits. First, communication with respect to several instances can happen in a single shot and leverage the benefit of serialization. Second, with respect to resource-constrained devices such as mobile phones, the preprocessing communication can occur whenever they have access to a high-bandwidth Wi-Fi network (for instance, when the device is at home overnight). These benefits facilitate a fast online phase, as observed, that may happen over a low-bandwidth network.

The time taken to evaluate circuits of different depths appears in ckttime. Since the time for the  5, 7, and 9 party settings vary within the range [0, 0.5], we report values only for the 7-party setting in ckttime. With respect to the online run-time, our semi-honest protocol's time is expected to be similar to that of DN07. However, DN07 demonstrates around 1.5$\times$ higher run-time. This difference can be attributed to the asymmetry in the $\rtt$ among parties, which vanished when benchmarked over a symmetric $\rtt$ setting. Compared to the semi-honest protocol, the malicious variant incurs a minimal overhead of less than one second in the online run-time due to the one-time verification phase. However, the overhead is higher for the case of the overall run-time. Concretely, it is around 10 seconds and is due to the distributed zero-knowledge proof computation in the preprocessing phase. Note that this overhead is independent of the circuit depth and gets amortized for deeper circuits as evident from ckttime (depth 1 vs. 1000).

Ref.     $d=1$     $d=100$     $d=1000$

DN07 (semi)       (0, 0.65)        (0, 54.97)        (0, 549.69)

$\this$ (semi)                (0.47, 0.45)        (0.47, 30.75)        (0.47, 307.48)

$\this$  (mal)                  (10.52, 1.36)        (10.53, 68.67)        (10.54, 308.39)

Latency in seconds (Preprocessing, Online) for varying depth ($d$) circuits with 1 million multiplications for $n=7$

Monetary Cost

Another key highlight of our protocols is their improved monetary cost, as evident from fig:TableIVPlot. Concretely, for 9 parties (semi-honest), we observe a saving of 17$\%$ over DN07 for a depth-1 circuit, and it increases up to 72$\%$ for circuits with depth 1000. This is primarily due to the reduction in the number of online parties over DN07.

Comparing our semi-honest and malicious variants, the latter has an overhead of 8$\times$ for depth-1 circuit, and it reduces to 1.14$\times$ for depth-1000 circuit. This is justified because the verification cost is amortized for deeper circuits, as mentioned earlier. Interestingly, our malicious variant outperforms even the semi-honest DN07 upon reaching circuit depths of 100 and above.

A similar analysis holds in the symmetric $\rtt$ setting as well, where the saving is up to $56\%$ (for $d = 1000$).

Online Throughput ($\TP$):

Owing to the asymmetric $\rtt$ as described earlier, our semi-honest variant witnesses up to $1.78 \times$ improvements in $\TP$ (for a single execution) over DN07, which vanishes in the symmetric $\rtt$ setting. However, recall that our protocol requires only $t+1$ active parties in the online phase, which leaves several channels among the parties underutilized. Hence, we can leverage the load balancing technique where parties' roles are interchanged across various parallel executions. For instance, one approach is to make every party act as $\Pking$, i.e., in 5PC, in one execution, $\Pking = P_1, \Evlset = \{P_1, P_2, P_3\}, \Hlpset = \{P_4, P_5\}$, while in another execution $\Pking = P_2, \Evlset = \{P_2, P_3, P_4\}, \Hlpset = \{P_5, P_1\}$, and so on. To analyse the effect of load balancing, we performed experiments with similar $\rtt$ among the parties and observed a 1.5$\times$ improvement in our semi-honest variant over DN07. This is justified as we communicate over four channels among the parties as opposed to six in DN07.

We note that while enhancing the security from semi-honest to malicious, we observe a significant drop in $\TP$, which is about 3$\times$ for the depth-1 circuit. This is primarily due to increased run time owing to the verification in  online phase for malicious setting. However, this drop tends to zero for deeper circuits (as verification cost gets amortized), making online phase of our maliciously secure protocol on par with semi-honest one.

§.§ Deep Neural Networks (DNN) and Graph Neural Networks (GNN)

We benchmark three different neural networks (NN) [68, 74, 85] with increasing number of parameters–(i) NN-1: a 3-layer fully connected one from [70], (ii) NN-2: the LeNet [60] architecture, and (iii) NN-3: VGG16 [82] architecture (further details are deferred to <ref>). We benchmark the inference phase of the above NNs, which comprises computing activation matrices, followed by applying an activation function or pooling operation, depending on the network architecture. NN-1 and NN-2 are benchmarked over MNIST dataset [61] while NN-3 is benchmarked using CIFAR-10 dataset [58]. We also benchmark GNN inference, for which we use the simplified architecture of [35] given in [81]. This architecture (<ref>) is shown to achieve an accuracy of more than $99\%$ on MNIST classification [81]. To analyse the improvement of our protocols, we also benchmark (semi-honest) DN07 for the applications by adapting our building blocks to their setting.

The semi-honest benchmarks for the different NNs and GNN appear in comparison-nnsh (<ref>) while the malicious ones appear in comparison-nnmal (<ref>).  fig:nngraph gives a pictorial view of the trends observed while comparing the semi-honest variants and are described next. We incur a very minimal overhead in the run-time of our protocols when moving from five to nine parties over all the networks considered. Hence, we use $\pm \delta$ to denote this variation in the table. The trends witnessed in synthetic circuit benchmarks (<ref>) carry forward to neural networks as well due to reasons discussed previously. For instance, the improvement in the online run-time for our semi-honest variant is up to
4.3$\times$ over DN07. The effect of reduced run-time and improved communication results in a significant improvement in online throughput of our protocol over DN07. Concretely, the gain ranges up to 4.3$\times$.
Further, the improved run-time coupled with the reduced number of online parties for our case brings in a saving of up to 69$\%$
in monetary cost for NN-1. However, the improvement drops to 33$\%$
for deep network NN-3. The reduction in savings is due to improved run-time getting nullified by increased communication from NN-1 to NN-3, making communication the dominant factor in determining monetary cost.

Observe that, unlike the case in synthetic circuits (cktcomm), the total communication here is an order of magnitude higher. This is primarily due to the higher communication cost incurred for performing the truncation operation–specifically, generation of the doubly-shared bits ($\PiDSBits$, fig:piDSBits) in the preprocessing phase. It is worth noting that $\PiDSBits$ is used as a black-box, and an improved instantiation for it will lower the communication. Similar trends are observed for GNN as well, where the online run-time of DN07 is up to 3.5$\times$
higher than our semi-honest protocol.
This is reflected in the throughput where we gain up to 3.4$\times$.
Further, we observe savings of up to 15$\%$ in monetary cost due to the reduced number of active parties and lesser run-time.

Moving to the malicious setting, we incur an overhead of up to 3$\%$ in online run-time, 6$\%$ in communication, and 13$\%$ in monetary cost over the semi-honest counterpart. Details are deferred to <ref>.

§.§ Genome Sequence Matching

Given a genome sequence as a query, genome matching aims to identify the most similar sequence from a database of sequences. This task is also known as similar sequence query (SSQ). It requires the computation of Edit Distance (ED), which quantifies how different two sequences are by identifying the minimum number of additions, deletions, and substitutions required to transform one sequence to the other.

To compute the ED, we extend the (2-party) protocol from [79] which builds on top of the approximation from [5], to the $n$-party setting. The details of the approximation algorithm for ED computation appear in <ref>. The accuracy and correctness of this algorithm follow from [5]. Among the two phases of the ED algorithm, where the first phase happens non-interactively, we only focus on the second phase of ED, which requires interaction and benchmark the same.

The benchmarks for genome sequence matching appear in comparison-ssqshint, comparison-ssqshext (<ref>).
Following [79], we consider three cases with different number of sequences in the database ($\seqn$) and different block lengths ($\seql$). The benchmarks for $\seqn = 2000, \seql = 30$ are reported in comparison-ssqshint, while the ones for $\seqn = 1000, \seql = 25$ and $\seqn = 4000, \seql = 35$ appear in comparison-ssqshext. We witness similar trends here, where our semi-honest protocol has improvements of up to 4$\times$ in both online run-time and throughput over DN07. Our malicious variant incurs a minimal overhead in the range of 5-6$\%$ in online run-time and total communication over the semi-honest counterpart. For the monetary cost (fig:mon_nine_ssq), our semi-honest protocol has up to 66$\%$
saving over DN07, and malicious variant has around 42$\%$-54$\%$ overhead over semi-honest counterpart.

2-1Ref.     2-1$n$     [c]1-3Online            [c]1-3End-to-end

Commcommunication in MB
$\TP$$\TP$ denotes throughput
Commcommunication in GB
TimeTime in seconds
Costmonetary cost in USD

5     25.82     66.33     57.89     0.40     82.24     0.31

7     38.75     69.63     55.15     0.60     86.99     0.47

9     51.67     69.66     55.09     0.80     87.39     0.62

5     15.39      [c]3-117.61
$\pm$.02     [r]3-1217.93
$\pm$0.2      0.40     [c]3-121.69
$\pm$.02     0.11

7     23.08                 0.60          0.16

9     30.78                 0.80          0.21

5     22.79     [c]3-118.3
$\pm$.2     209.84     0.42     [c]3-134.52
$\pm$.2     0.17

7     33.88          209.49     0.64          0.25

9     44.06          207.23     0.85          0.30

Genome sequence matching for $\seqn = 2000, \seql = 30$.

§.§ Biometric Matching

We extend support for biometric matching, which finds application in many real-world tasks such as face recognition [37] and fingerprint matching [50]. The goal of such computation is to identify a sample from a database of $m$ samples that is “closest” to a sample $\vec{u}$ held by a user. We follow the general trend and reduce the biometric matching problem to that of finding the sample from the database which has the least Euclidean Distance ($\ED{}{}$) with the user's sample $\vec{u}$. Details of the protocol are deferred to <ref>.

The benchmarks for biometric matching appear in comparison-bioshext, comparison-bioshint (<ref>). The former table considers the case with 1024 and 65536 sequences in the database, while the latter considers 4096 and 16384 sequences.

As is evident from comparison-bioshext, our semi-honest protocol witnesses a 4.6$\times$
improvement over DN07 in both online run-time and throughput. Further, in terms of monetary cost, we observe a saving of around 85$\%$.

With respect to our maliciously secure protocol, we incur a minimal overhead of around 9.5$\%$ in terms of total communication and around 4$\%$ in online throughput over our semi-honest variant. We note that our malicious variant outperforms semi-honest DN07 in both online run-time and throughput, thereby achieving our goal of a fast online phase.

rrr|rrr|rrr[notes/para][tabularnote = Communication in MB and time in seconds.]

2-1#seq     2-1Ref.     2-1$n$     [c]1-3Online             [c]1-3End-to-end

$\TP$$\TP$ denotes throughput
Costmonetary cost in USD

5     0.63     55.52     69.17     6.92      66.55     0.20

7     0.94     58.27     65.90     10.38     69.32     0.30

9     1.25     58.30     65.88     13.84     69.35     0.40

5     0.09      [c]3-112.61
$\pm$.02     [c]3-1304.62
$\pm$.03     6.93      [c]3-114.79
$\pm$.02     0.03

7     0.13                10.40           0.05

9     0.18                13.86          0.06

5     0.14     [c]3-113.43
$\pm$.02     [c]3-1285.93
$\pm$.2     7.61      [c]3-126.67
$\pm$.02     0.08

7 	    0.21               11.42          0.11

9     0.28               15.22          0.14

5     40.14     88.64     43.32     443.34     108.53     0.40

7     60.23     93.04     41.27     665.00     114.45     0.59

9     80.31     93.10     41.16     886.67     114.55     0.79

5     5.62       [c]3-119.99
$\pm$.02      [c]3-1192.09
$\pm$.04      443.99     [c]3-124.62
$\pm$.1      0.13

7     8.44                   665.99           0.18

9     11.25                  887.99           0.23

5     8.44      [c]3-120.86
$\pm$.02     [c]3-1183.88
$\pm$.07     486.85     [c]3-137.33
$\pm$.05     0.18

7     12.67               730.28          0.26

9     16.89               972.72          0.33

Benchmarks for biometric matching.

§ CONCLUSION

This work improves the practical efficiency of $n$-party honest-majority protocols using function-dependent preprocessing. While our first construction achieves a fast online phase compared to the semi-honest protocol of DN07, the second enhances security by tolerating malicious adversaries with minimal overhead in the online phase. The active participation of half of the participants in both of our constructions is a major highlight. This reduction in online parties results in monetary benefits in real-world deployments.

§ ACKNOWLEDGEMENTS

The authors would like to acknowledge support from Centre for Networked Intelligence (a Cisco CSR initiative) at the Indian Institute of Science, Bengaluru, SERB MATRICS (Theoretical Sciences) Grant 2020, Google India AI/ML Research Award 2020, DST National Mission on Interdisciplinary Cyber-Physical Systems (NM-CPS) 2020,   National Security Council, India, and the support from Google Cloud to perform the benchmarking.

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No. 850990 (PSOTI). This work was co-funded by the Deutsche Forschungsgemeinschaft (DFG) – SFB 1119 CROSSING/236615297.

[1]
M. Abspoel, A. P. K. Dalskov, D. Escudero, and A. Nof, “An efficient
passive-to-active compiler for honest-majority MPC over rings,” in
ACNS, 2021.

[2]
A. Aly, E. Orsini, D. Rotaru, N. P. Smart, and T. Wood, “Zaphod: Efficiently
Combining LSSS and Garbled Circuits in SCALE,” in ACM
WAHC@CCS, 2019.

[3]
T. Araki, A. Barak, J. Furukawa, T. Lichter, Y. Lindell, A. Nof, K. Ohara,
A. Watzman, and O. Weinstein, “Optimized honest-majority MPC for malicious
adversaries - breaking the 1 billion-gate per second barrier,” in
IEEE S&P, 2017.

[4]
T. Araki, J. Furukawa, Y. Lindell, A. Nof, and K. Ohara, “High-throughput
semi-honest secure three-party computation with an honest majority,” in
ACM CCS, 2016.

[5]
G. Asharov, S. Halevi, Y. Lindell, and T. Rabin, “Privacy-preserving search of
similar patients in genomic data,” PETS, 2018.

[6]
A. Baccarini, M. Blanton, and C. Yuan, “Multi-party replicated secret sharing
over a ring with applications to privacy-preserving machine learning,”
ePrint Archive, 2020, <https://eprint.iacr.org/2020/1577>.

[7]
C. Baum, I. Damgård, T. Toft, and R. W. Zakarias, “Better preprocessing
for secure multiparty computation,” in ACNS, 2016.

[8]
A. Ben-Efraim, Y. Lindell, and E. Omri, “Optimizing semi-honest secure
multiparty computation for the internet,” in CCS, 2016.

[9]
A. Ben-Efraim, M. Nielsen, and E. Omri, “Turbospeedz: Double your online
spdz! improving SPDZ using function dependent preprocessing,” in
ACNS, 2019.

[10]
A. Ben-Efraim and E. Omri, “Concrete efficiency improvements for multiparty
garbling with an honest majority,” in LATINCRYPT, 2017.

[11]
M. Ben-Or, S. Goldwasser, and A. Wigderson, “Completeness theorems for
non-cryptographic fault-tolerant distributed computation (extended
abstract),” in STOC, 1988.

[12]
M. Blanton, A. Kang, and C. Yuan, “Improved building blocks for secure
multi-party computation based on secret sharing with honest majority,” in
ACNS, 2020.

[13]
D. Boneh, E. Boyle, H. Corrigan-Gibbs, N. Gilboa, and Y. Ishai,
“Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs,” in
CRYPTO, 2019.

[14]
E. Boyle, N. Gilboa, Y. Ishai, and A. Nof, “Practical fully secure three-party
computation via sublinear distributed zero-knowledge proofs,” in ACM
CCS, 2019.

[15]
——, “Efficient fully secure computation via distributed zero-knowledge
proofs,” in ASIACRYPT, 2020.

[16]
Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(Leveled) Fully Homomorphic
Encryption without Bootstrapping,” ACM Trans. Comput. Theory,

[17]
L. Braun, D. Demmler, T. Schneider, and O. Tkachenko, “MOTION - A
Framework for Mixed-Protocol Multi-Party Computation,” ACM Trans.
Priv. Secur., 2022.

[18]
M. Byali, H. Chaudhari, A. Patra, and A. Suresh, “FLASH: Fast and Robust
Framework for Privacy-preserving Machine Learning,” PETS, 2020.

[19]
S. Carpov, K. Deforth, N. Gama, M. Georgieva, D. Jetchev, J. Katz,
I. Leontiadis, M. Mohammadi, A. Sae-Tang, and M. Vuille, “Manticore:
Efficient Framework for Scalable Secure Multiparty Computation Protocols,”
ePrint Archive, 2021, <https://eprint.iacr.org/2021/200>.

[20]
N. Chandran, N. Dasgupta, D. Gupta, S. L. B. Obbattu, S. Sekar, and A. Shah,
“Efficient Linear Multiparty PSI and Extensions to Circuit/Quorum
PSI,” in ACM CCS, 2021.

[21]
H. Chaudhari, A. Choudhury, A. Patra, and A. Suresh, “ASTRA: High Throughput
3PC over Rings with Application to Secure Prediction,” in ACM
CCSW@CCS, 2019. [Online]. Available:

[22]
H. Chaudhari, R. Rachuri, and A. Suresh, “Trident: Efficient 4PC Framework
for Privacy Preserving Machine Learning,” in NDSS, 2020. [Online].
Available: <https://arxiv.org/abs/1912.02631>

[23]
K. Chida, D. Genkin, K. Hamada, D. Ikarashi, R. Kikuchi, Y. Lindell, and
A. Nof, “Fast large-scale honest-majority MPC for malicious adversaries,”
in CRYPTO, 2018.

[24]
P. Covington, J. Adams, and E. Sargin, “Deep neural networks for youtube
recommendations,” in RecSys, 2016.

[25]
R. Cramer, I. Damgård, D. Escudero, P. Scholl, and C. Xing,
“SPD$\mathbb{Z}_{2^k}$: Efficient MPC mod $2^k$ for Dishonest
Majority,” in CRYPTO, 2018.

[26]
R. Cramer, I. Damgård, and Y. Ishai, “Share conversion, pseudorandom
secret-sharing and applications to secure computation,” in TCC,

[27]
Cryptography and P. E. G. at TU Darmstadt, “ENCRYPTO Utils,” 2017,

[28]
A. Dalskov, D. Escudero, and M. Keller, “Fantastic Four: Honest-Majority
Four-Party Secure Computation With Malicious Security,” in USENIX
Security, 2021.

[29]
I. Damgård, D. Escudero, T. K. Frederiksen, M. Keller, P. Scholl, and
N. Volgushev, “New primitives for actively-secure MPC over rings with
applications to private machine learning,” in IEEE S&P, 2019.

[30]
I. Damgård, M. Keller, E. Larraia, V. Pastro, P. Scholl, and N. P. Smart,
“Practical covertly secure MPC for dishonest majority - or: Breaking the
SPDZ limits,” in ESORICS, 2013.

[31]
I. Damgård and J. B. Nielsen, “Scalable and unconditionally secure
multiparty computation,” in CRYPTO, 2007.

[32]
I. Damgård, C. Orlandi, and M. Simkin, “Yet another compiler for active
security or: Efficient MPC over arbitrary rings,” in CRYPTO,

[33]
I. Damgård, V. Pastro, N. P. Smart, and S. Zakarias, “Multiparty
computation from somewhat homomorphic encryption,” in CRYPTO, 2012.

[34]
E. Dans, “How signal cleverly exposed Facebook's disregard for privacy,”
Forbes, 2021,

[35]
M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional Neural
Networks on Graphs with Fast Localized Spectral Filtering,” in
NeurIPS, 2016.

[36]
C. Dwork, “Differential Privacy: A Survey of Results,” in TAMC,

[37]
Z. Erkin, M. Franz, J. Guajardo, S. Katzenbeisser, I. Lagendijk, and T. Toft,
“Privacy-preserving face recognition,” PETS, 2009.

[38]
D. Escudero and A. Dalskov, “Honest Majority MPC with Abort with Minimal
Online Communication,” in LATINCRYPT, 2021.

[39]
J. Furukawa, Y. Lindell, A. Nof, and O. Weinstein, “High-throughput secure
three-party computation for malicious adversaries and an honest majority,”
in EUROCRYPT, 2017.

[40]
D. Genkin, Y. Ishai, M. M. Prabhakaran, A. Sahai, and E. Tromer, “Circuits
resilient to additive attacks with applications to secure computation,” in
STOC, 2014.

[41]
C. Gentry, A. Sahai, and B. Waters, “Homomorphic encryption from learning with
errors: Conceptually-simpler, asymptotically-faster, attribute-based,” in
CRYPTO, 2013.

[42]
O. Goldreich, Foundations of cryptography: volume 2, basic
applications.1em plus 0.5em minus 0.4emCambridge university
press, 2009.

[43]
O. Goldreich, S. Micali, and A. Wigderson, “How to play any mental game or A
completeness theorem for protocols with honest majority,” in STOC,

[44]
S. D. Gordon, S. Ranellucci, and X. Wang, “Secure computation with low
communication from cross-checking,” in ASIACRYPT, 2018.

[45]
S. D. Gordon, D. Starin, and A. Yerukhimovich, “The More The Merrier:
Reducing the Cost of Large Scale MPC,” in EUROCRYPT, 2021.

[46]
V. Goyal, H. Li, R. Ostrovsky, A. Polychroniadou, and Y. Song, “ATLAS:
Efficient and Scalable MPC in the Honest Majority Setting,” in
CRYPTO, 2021.

[47]
V. Goyal, Y. Liu, and Y. Song, “Communication-efficient unconditional MPC
with guaranteed output delivery,” in CRYPTO, 2019.

[48]
V. Goyal and Y. Song, “Malicious Security Comes Free in Honest-Majority
MPC,” in CRYPTO, 2020.

[49]
G. Guido, M. I. Prete, S. Miraglia, and I. De Mare, “Targeting direct
marketing campaigns by neural networks,” Journal of Marketing
Management, 2011.

[50]
W. Henecka and T. Schneider, “Faster secure two-party computation with less
memory,” in AsiaCCS, 2013.

[51]
J. Katz, V. Kolesnikov, and X. Wang, “Improved non-interactive zero knowledge
with applications to post-quantum signatures,” in CCS, 2018.

[52]
M. Keller, E. Orsini, and P. Scholl, “MASCOT: Faster Malicious Arithmetic
Secure Computation with Oblivious Transfer,” in CCS, 2016.

[53]
M. Keller, V. Pastro, and D. Rotaru, “Overdrive: Making SPDZ great again,”
in EUROCRYPT, 2018.

[54]
M. Keller, P. Scholl, and N. P. Smart, “An architecture for practical actively
secure MPC with dishonest majority,” in CCS, 2013.

[55]
T. N. Kipf and M. Welling, “Semi-supervised classification with graph
convolutional networks,” in ICLR, 2017.

[56]
N. Koti, M. Pancholi, A. Patra, and A. Suresh, “SWIFT: Super-fast and Robust
Privacy-Preserving Machine Learning,” in USENIX Security, 2021.

[57]
N. Koti, A. Patra, R. Rachuri, and A. Suresh, “Tetrad: Actively Secure 4PC
for Secure Training and Inference,” in NDSS, 2022.

[58]
A. Krizhevsky, V. Nair, and G. Hinton, “The CIFAR-10 dataset,” 2014,
<https://www.cs.toronto.edu/ kriz/cifar.html>.

[59]
A. Lapets, N. Volgushev, A. Bestavros, F. Jansen, and M. Varia, “Secure MPC
for analytics as a web application,” in IEEE SecDev, 2016.

[60]
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning
applied to document recognition,” Proceedings of the IEEE, 1998.

[61]
Y. LeCun and C. Cortes, “MNIST handwritten digit database,” 2010,

[62]
C. Li, B. Pang, Y. Liu, H. Sun, Z. Liu, X. Xie, T. Yang, Y. Cui, L. Zhang, and
Q. Zhang, “Adsgnn: Behavior-graph augmented relevance modeling in sponsored
search,” in SIGIR, 2021.

[63]
Y. Lindell, “How to simulate it - A tutorial on the simulation proof
technique,” in Tutorials on the Foundations of Cryptography, 2017.

[64]
Y. Lindell, B. Pinkas, N. P. Smart, and A. Yanai, “Efficient constant round
multi-party computation combining BMR and SPDZ,” in CRYPTO, 2015.

[65]
M. Malone, “How does Facebook know what ads to show you? (example),”
Vici Media, 2021,

[66]
S. Mazloom, P. H. Le, S. Ranellucci, and S. D. Gordon, “Secure parallel
computation on national scale volumes of data,” in USENIX Security,

[67]
P. Miao, S. Patel, M. Raykova, K. Seth, and M. Yung, “Two-sided malicious
security for private intersection-sum with cardinality,” in CRYPTO,

[68]
P. Mohassel and P. Rindal, “ABY\({}^{\mbox{3}}\): A mixed protocol
framework for machine learning,” in CCS, 2018.

[69]
P. Mohassel, M. Rosulek, and Y. Zhang, “Fast and Secure Three-party
Computation: The Garbled Circuit Approach,” in CCS, 2015.

[70]
P. Mohassel and Y. Zhang, “SecureML: A System for Scalable
Privacy-Preserving Machine Learning,” in IEEE S&P, 2017.

[71]
S. Ohata and K. Nuida, “Communication-Efficient (Client-Aided) Secure
Two-Party Protocols and Its Application,” in FC, 2020.

[72]
K. Park, J. Lee, and J. Choi, “Deep neural networks for news
recommendations,” in CIKM, 2017.

[73]
A. Patra, T. Schneider, A. Suresh, and H. Yalame, “ABY2.0: Improved
Mixed-Protocol Secure Two-Party Computation,” in USENIX Security,

[74]
A. Patra and A. Suresh, “BLAZE: Blazing Fast Privacy-Preserving Machine
Learning,” in NDSS, 2020.

[75]
R. Poddar, S. Kalra, A. Yanai, R. Deng, R. A. Popa, and J. M. Hellerstein,
“Senate: A Maliciously-Secure MPC Platform for Collaborative Analytics,”
in USENIX Security, 2021.

[76]
M. S. Riazi, C. Weinert, O. Tkachenko, E. M. Songhori, T. Schneider, and
F. Koushanfar, “Chameleon: A Hybrid Secure Computation Framework for
Machine Learning Applications,” in AsiaCCS, 2018.

[77]
P. Rogaway and T. Shrimpton, “Cryptographic Hash-Function Basics:
Definitions, Implications, and Separations for Preimage Resistance,
Second-Preimage Resistance, and Collision Resistance,” in FSE, 2004.

[78]
D. Rotaru and T. Wood, “MArBled Circuits: Mixing Arithmetic and Boolean
Circuits with Active Security,” in INDOCRYPT, 2019.

[79]
T. Schneider and O. Tkachenko, “EPISODE: efficient privacy-preserving similar
sequence queries on outsourced genomic databases,” in AsiaCCS,

[80]
G. C. C. Services, “Google Cloud Platform,” 2008, network costs -
<https://cloud.google.com/vpc/network-pricing>, Computation costs -

[81]
L. Shen, X. Chen, J. Shi, Y. Dong, and B. Fang, “An Efficient 3-Party
Framework for Privacy-Preserving Neural Network Inference,” in
ESORICS, 2020.

[82]
K. Simonyan and A. Zisserman, “Very Deep Convolutional Networks for
Large-Scale Image Recognition,” in ICLR, 2015.

[83]
J. So, B. Güler, and A. S. Avestimehr, “CodedPrivateML: A Fast and
Privacy-Preserving Framework for Distributed Machine Learning,”
IEEE J. Sel. Areas Inf. Theory, 2021.

[84]
A. Suresh, “MPCLeague: Robust MPC Platform for Privacy-Preserving Machine
Learning,” PhD Thesis, 2021, <https://arxiv.org/pdf/2112.13338>.

[85]
S. Wagh, S. Tople, F. Benhamouda, E. Kushilevitz, P. Mittal, and T. Rabin,
“FALCON: Honest-Majority Maliciously Secure Framework for Private Deep
Learning,” PETS, 2020.

[86]
R. A. Wagner and M. J. Fischer, “The String-to-String Correction Problem,”
J. ACM, 1974.

[87]
X. Wang, S. Ranellucci, and J. Katz, “Authenticated garbling and efficient
maliciously secure two-party computation,” in CCS, 2017.

[88]
J. Yang, Z. Liu, S. Xiao, C. Li, D. Lian, S. Agrawal, A. Singh, G. Sun, and
X. Xie, “Graphformers: Gnn-nested transformers for representation learning
on textual graph,” in NeurIPS, 2021.

[89]
A. C. Yao, “Protocols for secure computations (extended abstract),” in
FOCS, 1982.

[90]
J. Zhu, Y. Cui, Y. Liu, H. Sun, X. Li, M. Pelger, T. Yang, L. Zhang, R. Zhang,
and H. Zhao, “Textgnn: Improving text encoder via graph neural network in
sponsored search,” in WWW, 2021.

§ PRELIMINARIES

Shared key setup

$\FSETUP$ [4, 68, 74] enables establishment of common random keys for a  pseudo-random function (PRF) $F$, among parties. This aids in non-interactively generating correlated randomness. Here $F : \{0, 1\}^{\csec} \times \{0, 1\}^{\csec} \rightarrow X$ is a secure PRF, with co-domain $X$ being $\Z{\ell}$.

The semi-honest functionality, $\FSETUP$ appears in fig:FSETUP. The functionality for the malicious case is similar, except that the adversary now has the capability to $\abort$.

To sample a random value $\vr \in \Z{\ell}$ among a set of $t+1$ parties $\T = \{P_1, \ldots, P_{t+1}\}$ non-interactively, each $P_i \in \T$ invokes $F_{\Key{\T}}(id_{\T})$ and obtains $\vr$. Here, $id_{\T}$ denotes a counter maintained by the parties in $\T$, and is updated after every PRF invocation. The appropriate keys used to sample is implicit from the context, from the identities of the parties that sample.

$\FSETUP$Ideal functionality for shared-key setupfig:FSETUP
$\FSETUP$ interacts with the parties in $\Partyset$ and the adversary $\Sim$. $\FSETUP$ picks random keys $\Key{\T}, \Key{{\T}^{\prime}}$ for every set $\T, {\T}^{\prime} \subseteq \Partyset$ of $t+1, t+2$ parties, respectively.

$\FSETUP$ picks random keys $\Key{ij}$ for every pair of parties $P_i,P_j \in \Partyset$ and $i<j$.

– Set $\wx_s = \{\Key{si}, \Key{js}\}_{\forall i: s<i \leq n, \forall j: 1 \leq j<s}$.

– Set $\wy_s = \{\Key{\T}\}_{\forall \T \subset \Partyset: \abs{\T} = t+1}$ when $P_s \in \T$.

– Set $\wz_s = \{\Key{{\T}^{\prime}}\}_{\forall {\T}^{\prime} \subseteq \Partyset: \abs{{\T}^{\prime}} = t+2}$ when $P_s \in {\T}^{\prime}$.

* Output:  Send $(\OUTPUT, \wx_s, \wy_s, \wz_s)$ to every $P_s \in \Partyset$.

Collision-Resistant Hash Function

A family of hash functions [77] $\{\Hash: \mathcal{K} \times \MS \rightarrow \mathcal{Y} \}$ is said to be collision resistant if for all PPT adversaries $\Adv$, given the hash function $\Hash_k$ for $k \in_R \mathcal{K}$, the following holds: $\Prob[(x, x^{\prime}) \leftarrow \Adv(k) : (x \neq x^{\prime}) \wedge \Hash_k(x) = \Hash_k(x^{\prime})] = \negl(\kappa)$, where $x, x^{\prime} \in \{0,1\}^{m}$, $m = \poly(\kappa)$, and $\kappa$ is security parameter.

Commitment Scheme

Let $\commit(x)$ denote the commitment of a value $x$ [69]. The commitment scheme $\commit(x)$ possesses two properties; hiding and binding. The former ensures privacy of value $x$ given its commitment $\commit(x)$, while the latter prevents a corrupt party from opening the commitment to a different value $x' \ne x$.

§ MPCLAN PROTOCOLS

§ BUILDING BLOCKS

For completeness, we discuss the building blocks used in our framework. These blocks are known from the literature [57, 73] and we show how these can be extended to $n$-party setting.

§.§ Communication cost

costshmal summarises communication cost and online round complexity of semi-honest and maliciously secure protocols.

§ ADDITIONAL BENCHMARKS

§.§ Deep NN and GNN

NN architecture

Among NNs, the first, NN-1, is a 3-layered fully connected network with ReLU activation after each layer, as considered in [68, 74, 56]. The second, NN-2, is LeNet [60] architecture, which contains two convolutional layers and two fully connected layers with ReLU activation after each layer. Additionally, for convolutional layers, this is followed by maxpool operation. Finally, NN-3 is VGG16 [82] architecture that comprises 16 layers in total, which includes fully connected, convolutional, ReLU activation, and maxpool layers. Last 2 NNs were considered in [85].

GNN architecture

The goal of spectral-based GNNs [35, 55] is to learn a function of signals $\vec{\vx_1}, \ldots, \vec{\vx_m}$ each of length $n$, on a graph $\graph = (\vertices, \edges, \Mat{M})$, where $\vertices$ is the set of $n$ vertices of the graph, $\edges$ is the set of edges and $\Mat{M}$ is the the graph description in terms of an $n \times n$ adjacency matrix. The $j$th component of every signal $\vec{\vx_i}$ corresponds to $j$th node of the graph. Training data is used to compute graph description $\Mat{M}$ , which is common for all signals considered.

The approximation of graph filters using a truncated expansion in terms of Chebyshev polynomials was put forth in [35].
Chebyshev polynomials are recursively defined as follows:

T_k(x) =
\begin{cases}
1 & \text{if } k = 0\\
x & \text{if } k = 1\\
2x T_{k-1}(x) - T_{k-2}(x) & \text{otherwise}
\end{cases}

and the inference phase for a $n \times c$ signal matrix $\Mat{X}$ with $f$ feature maps, where $c$ represents the dimension of feature vector for each node, with a $K$-localized filter matrix $\Theta_k$  can be performed as $\Mat{Y} = \sum_{k=0}^{K-1} T_k(\tilde{\Mat{L}}) \Mat{X} \Theta_k$. Here, $\tilde{\Mat{L}} = \frac{2}{\lambda_{max}} \cdot \Mat{L} - \Mat{I} \cdot \lambda_{max}$, and $\lambda_{max}$ is the largest eigenvalue of the normalized graph Laplacian $\Mat{L}$, $\Mat{Y}$ is an $n \times f$ dimensional matrix and the trainable parameter for the $k$th layer $\Theta_k$ is of dimension $c \times f$.

We use the simplified architecture of [35] given in [81]. The GNN architecture in the latter uses one graph convolution layer without pooling operation instead of the original model with two graph convolution layers, each of which is followed by a pooling operation. Further, $K$ is set to $5$ instead of $25$. This architecture is shown to achieve an accuracy of more than $99\%$ on MNIST classification in [81].

– Graph convolution layer:

- Input: $T_k(\tilde{\Mat{L}})$ with dimensions $784 \times 784$, $\Theta_k$ with dimensions $1 \times 32$, for $k \in \{0, \ldots, K-1\}$, and $28 \times 28$ image transformed into a vector $\vec{{\vx}}$ of dimension $784$.

- Output: $\sum_{k=0}^{K-1} T_k(\tilde{\Mat{L}}) \vec{\vx} \Theta_k$ with dimensions $784 \times 32$.

– ReLU activation: Calculates the ReLU for each input.

– Fully connected layer (FC): with 10 nodes.

Benchmarks for the semi-honest and maliciously secure protocol appear in comparison-nnsh, comparison-nnmal.

rrr|rrr|rrr[notes/para][tabularnote = Communication in MB and time in seconds.]

Type     2-1Ref.     2-1$n$     [c]1-3Online             [c]1-3End-to-end

$\TP$$\TP$ denotes throughput
Costmonetary cost in USD

5     0.16     [c]3-118.55
$\pm$.4     211.69     3.41     21.46     0.06

7     0.24          202.48     5.11     22.29     0.10

9     0.33          202.49     6.81     22.31     0.13

5     0.02     [c]3-14.61
$\pm$.02      [c]3-1832.61
$\pm$.04     3.41     [c]3-111.09
$\pm$.02     0.02

7     0.03               5.11          0.03

9     0.05               6.81          0.04

5     15.58     46.20     83.12     269.23     56.44     0.21

7     23.39     48.39     79.35     403.85     59.60     0.32

9     31.18     48.40     79.35     538.47     59.61     0.42

5     1.92       [c]3-111.08
$\pm$.02     [c]3-1346.60
$\pm$.3     269.50     [c]3-125.34
$\pm$.03     0.10

7     2.88                 404.25          0.14

9     3.84                 539.00          0.18

5     228.07     152.95     25.11     4288.26     213.77     1.34

7     342.24     160.10     23.99     6432.39     227.28     1.96

9     456.33     160.14     23.99     8576.52     227.33     2.56

5     29.70       [c]3-136.92
$\pm$.02      [c]3-1104.01
$\pm$.04     4292.06     [c]3-1104.09
$\pm$.03     0.91

7     44.55                  6438.09          1.08

9     59.40                  8584.12          1.71

5     20.14     7.26     528.66     956.21      17.00     0.20

7     30.22     7.54     509.38     1434.31     17.54     0.29

9     40.29     7.56     509.38     1912.41     17.57     0.38

5     5.34        [c]3-12.16
$\pm$.02      [c]3-11777.78
$\pm$.06     956.46      [c]3-18.97
$\pm$.02     0.17

7     8.00                   1434.69          0.26

9     10.67                  1912.92          0.33

Semi-honest: Benchmarks for deep NN and GNN.

Compared to our semi-honest variant for evaluating NNs, the malicious variant incurs a 2$\times$ higher online communication cost for NN-1 and NN-2. However, this difference closes in with deeper NNs, with the communication being 1.5$\times$ for NN-3. The drop in the difference can be attributed to the one-time cost of verification required in the malicious variant, which gets amortized over deeper circuits. Due to the same reason, in comparison to the semi-honest case, the malicious variant has an overhead of around $1$ second in the online run-time, which in turn reflects in the reduced throughput. Similar to the semi-honest evaluation of NNs, the overall communication is an order of magnitude higher than the online communication due to the cost incurred for truncation during preprocessing. Also, analogous to the trend observed for synthetic circuits, the overhead in overall run-time is approximately $11$ seconds owing to the distributed zero-knowledge proof verification required in the preprocessing phase. For GNN, the trend follows closely to that of NN-3,where malicious variant incurs 1.5$\times$ higher communication than its semi-honest counterpart.

rr|rrr|rrr[notes/para][ tabularnote = Communication in MB and time in seconds.]

Type     2-1$n$     [c]1-3Online            [c]1-3End-to-end

$\TP$$\TP$ denotes throughput
Costmonetary cost in USD

5     0.04      [c]3-15.44
$\pm$.02      [c]3-1706.40
$\pm$.04     3.59        [c]3-122.96
$\pm$.02      0.07

7     0.06                 5.39              0.10

9     0.08                 7.20              0.11

5     2.88      [c]3-111.93
$\pm$.03     [c]3-1322.63
$\pm$.2     286.18      [c]3-137.71
$\pm$.04      0.15

7     4.32                429.28            0.22

9     5.77                571.98            0.27

5     44.56     [c]3-137.91
$\pm$.02     [c]3-1101.27
$\pm$.04     4535.95     124.54     1.04

7     66.84               6804.06     126.69     1.53

9     89.12               9066.43     129.42     1.94

5     8.01      [c]3-13.02
$\pm$.02     1275.75     977.65      [c]3-122.39
$\pm$.03     0.23

7     12.01          1267.35     1466.49          0.34

9     16.02          1267.32     1954.95          0.42

Malicious: Benchmarks for deep NN and GNN.

§.§ Biometric Matching

Given a database of $m$ biometric samples $(\vec{s}_1, \ldots, \vec{s}_m)$ each of size $\nf$, and a user holding its sample $\vec{u}$, the goal of biometric matching is to identify the sample from the database that is “closest” to $\vec{u}$. The notion of “closeness” can be formalized by various distance metrics, of which Euclidean Distance ($\ED{}{}$) is the most widely used.

Following the general trend, we reduce our biometric matching problem to that of finding the sample from the database
which has the least $\ED{}{}$ with the user's sample $\vec{u}$.

We follow [70, 73] where $\ED{}{}$ between two vectors $\vec{x}, \vec{y}$ of length $\nf$ is given as

\begin{align} \label{EucDist}
\ED{\vec{x}}{\vec{y}} = \sum_{i=1}^{i=\nf}(\vx_i-\vy_i)^2 = \vec{z} \band \vec{z}
\end{align}

where $\vec{z} = ((\vx_1-\vy_1),\ldots,(\vx_\nf-\vy_\nf))$.

rrr|rrr|rrr[notes/para][tabularnote = Communication in MB and time in seconds.]

2-1#seq     2-1Ref.     2-1$n$     [c]1-3Online             [c]1-3End-to-end

$\TP$$\TP$ denotes throughput
Costmonetary cost in USD

5     2.51     66.51     57.73     27.70     79.85     0.24

7     3.76     69.81     55.00     41.55     83.24     0.36

9     5.02     69.87     54.97     55.40     83.30     0.48

3-1$\this$ (semi)
5     0.35      [c]3-115.07
$\pm$.02     [c]3-1254.86
$\pm$.03     27.74     [c]3-117.35
$\pm$.03     0.04

7     0.53                41.61          0.06

9     0.70                55.49          0.08

3-1$\this$ (mal)
5     0.53     [c]3-115.89
$\pm$.02     [c]3-1241.66
$\pm$.1     30.43     [c]3-129.27
$\pm$.02     0.09

7     0.80               45.65          0.13

9     1.07               60.81          0.16

5     10.03     77.51     49.54     110.83     93.47     0.29

7     15.06     81.35     47.20     166.24     97.70     0.45

9     20.07     81.36     47.14     221.66     97.71     0.59

3-1$\this$ (semi)
5     1.41       [c]3-117.53
$\pm$.02      [r]3-1219.16
$\pm$.04     110.99      [c]3-120.24
$\pm$.05      0.06

7     2.11                  166.49           0.09

9     2.81                  221.99           0.11

3-1$\this$ (mal)
5     2.11      [c]3-118.35
$\pm$.02     [c]3-1209.24
$\pm$.06     121.71     [c]3-132.30
$\pm$.03     0.11

7     3.17                182.58          0.16

9     4.23                243.19         0.20

Benchmarks for biometric matching for varying number of sequences in the database.

To achieve this goal of performing biometric matching securely, each $\vec{s}_i$, for all $i \in \{1, \ldots, m\}$ in the database is $\shrd$-shared among the $n$ parties participating in the computation. Specifically, each component $\vec{s}_{i_j}$, for all $j \in \{1, \ldots, \nf\}$ is $\shrd$-shared among all the parties. Similarly, the user also $\shrd$-shares its sample $\vec{u}$. The parties compute a $\shrd$-shared distance vector $\DV$ of size $m$, where the $i$th component corresponds to the $\ED{}{}$ between $\vec{u}$ and $\vec{s}_i$. For this, each party locally obtains $\shr{\vec{z}_i} = \shr{\vec{s}_i} - \shr{\vec{u}}$ and computes $\shr{\DV_i}$ according to Eq. <ref> using the dot product operation. The final step is then to identify the minimum of these $m$ components of $\DV$, which can be performed using the protocol $\Pi_{\min}$ for minpool operation. comparison-bioshint tabulates the benchmarks when the database has 4096 and 16384 samples.

The trend observed for 4096 and 16384 samples adheres to that observed from comparison-bioshext for the case of 1024 and 65536 samples. Specifically, these settings also enjoy a 4.6$\times$
improvement in online run-time and throughput and around 83$\%$ saving in the monetary cost compared to DN07. Moreover, similar to the prior case, the malicious variant incurs a minimal overhead of 4$\%$ in the online throughput and 9.5$\%$ in the total communication compared to our semi-honest setting.

§.§ Genome Sequence Matching

Given a genome sequence as a query, genome matching aims to identify the most similar sequence from a database of sequences. This task is also commonly referred to as Similar Sequence Query (SSQ) identification and has implications in the advancing field of medical science.
An SSQ algorithm on two sequences $s$ and $q$, requires the computation of Edit Distance (ED), which quantifies how different two sequences are by identifying the minimum number of additions, deletions, and substitutions needed to transform one sequence to the other.

To compute the ED, we extend the (2-party) protocol from [79] which builds on top of the approximation from [5], to the $n$-party setting. We describe high-level idea of the approximation algorithm for ED computation for a query sequence $\query$ against a database of sequences $\{\seq_1, \ldots, \seq_\seqn\}$.

$\PiED(\Partyset,\shr{\lut_\seq},\shr{\query})$Edit distance between query $\query$ and sequence $\seq$ with respect to a database of $\seqn$ sequences and $\seql$ blocksfig:piED

1. For $i = 1$ to $\seql$

* For $j = 1$ to $\seqn$

- Invoke $\PiEq$ on $\shr{\lut_\seq[i][j]}$ and $\shr{\query[i]}$ to generate $\shrB{\vb_j}$.

- Invoke $\PiBitA$ on $\shrB{\vb_j}$ and generate $\shr{\vb_j}$.

* Let $\vec{\vb} = \{\vb_1, \ldots, \vb_\seqn\}$. Compute $\shr{\dist_i} = \PiDotP(\shr{\vec{\vb}}, \shr{\lut_\seq[i][\cdot]} )$.

2. Compute $\shr{\dist} = \sum_{i=1}^{\seql} \shr{\dist_i}$.

The ED approximation algorithm has a non-interactive phase, during which the database owner with the sequences $\seq_1, \ldots, \seq_\seqn$, generates a Look-Up-Table ($\lut$) for each sequence. These $\lut$s are then secret-shared among all the parties. To generate the $\lut$, the sequences in the database are aligned with respect to a common reference genome sequence (using the Wagner-Fischer algorithm [86]), and divided into blocks of a fixed, predetermined size. Based on the most frequently occurring block sequences in the database, an $\lut$ is constructed consisting of these block values and their distance from each other. Specifically, for a database of $\seqn$ sequences $\{\seq_1, \ldots, \seq_\seqn\}$, each of length $\seql$ blocks, an $\lut_i$ is constructed for each $\seq_i$. Each $\lut$ has $\seqn$ columns, one corresponding to each $\seq_i$ in the database, and $\seql$ rows, one corresponding to each block of a sequence, where $\lut_\seq[i][j]$ corresponds to the ED between block $i$ of the sequence $\seq$ and $\seq_j$ . This completes the non-interactive phase of the ED approximation algorithm.

Given the $\lut$s, when a new query $\query$ has to be processed, its ED must be computed from every sequence $\seq$ in the database. For this, similar to the non-interactive phase, the query is first aligned with the reference sequence and broken down into blocks of the same fixed size. Then, the $i$th block from the query is matched with the $i$th block of each sequence in the $\lut$ for a sequence $\seq$. If the block values match, then the precomputed distance is taken as the output for that block; otherwise, the output is taken to be $0$. Finally, the resultant sum of distances for all the blocks is taken to be the approximated ED between $\query$ and the sequence $\seq$. Computing the ED to all such sequences $\seq$ in the database then allows the identification of the most similar sequence for the query using the minpool operation. Algorithms for ED computation between two sequences, and SSQ appear in fig:piED, fig:piSSQ, respectively, where accuracy and correctness follow from [5].

$\PiSSQ(\Partyset,\{\shr{\lut_\seq}\}_{s=1}^{\seqn},\shr{\query})$Similar sequence queriesfig:piSSQ

1. For $\seq= 1$ to $\seqn$

* Invoke $\PiED$ on $\shr{\lut_\seq}$ and $\shr{\query}$ to generate $\shr{\dist_\seq}$.

2. Invoke $\Pi_{\min}$ on $\shr{\dist_1}, \ldots, \shr{\dist_\seqn}$ to generate $\shr{\seq_{\min}} \in \{\dist_1, \ldots, \dist_\seqn\}$.

Since the generation of $\lut$s happens non-interactively, we only focus on the computation of ED with respect to the new query $\query$, which requires interaction, and benchmark the same.

comparison-ssqshext provides the benchmarks when the database consists of $\seqn = 1000, 4000$ for block length $\seql = 25, 35$ respectively.

As expected, the observations tabulated for the varying sequence lengths follows closely to the ones for the case of $\seqn = 2000$ and $\seql = 30$ given in comparison-ssqshint.

rrr|rrr|rrr[notes/para][tabularnote = Time in seconds.]

2-1$\seqn, \seql$     2-1Ref.     2-1$n$     [c]1-3Online            [c]1-3End-to-end

Commcommunication in MB
$\TP$$\TP$ denotes throughput
Commcommunication in GB
Costmonetary cost in USD

9-1$\seqn = 1000$
$\seql = 25$
5     10.85     60.58     63.39     0.17     74.13     0.25

7     16.28     63.60     60.38     0.25     77.76     0.37

9     21.71     63.62     60.37     0.33     77.79     0.50

3-1$\this$ (semi)
5     6.42       [c]3-116.12
$\pm$.01     [r]3-1236.21
$\pm$.15     0.17     [c]3-119.08
$\pm$.02     0.07

7     9.63                 0.25          0.10

9     12.84                0.33          0.13

3-1$\this$ (mal)
5     9.51      [c]3-116.8
$\pm$.1     228.71     0.18     [c]3-131.21
$\pm$.08     0.12

7     14.14          228.44     0.27          0.16

9     18.40          226.82     0.36          0.21

9-1$\seqn = 4000$
$\seql = 35$
5     59.87      72.08     53.27     0.92     92.04     0.43

7     89.86      75.65     50.76     1.39     98.90     0.64

9     119.81     75.67     50.72     1.85     98.93     0.84

3-1$\this$ (semi)
5     35.87       [c]3-119.34
$\pm$.02      [r]3-1198.55
$\pm$.35     0.92     [c]3-125.97
$\pm$.03      0.21

7     53.80                   1.39           0.31

9     71.74                   1.85           0.39

3-1$\this$ (mal)
5     53.11      [c]3-120.11
$\pm$.06     [c]3-1190.95
$\pm$.4     0.99     [c]3-141.83
$\pm$.06     0.29

7     78.96                1.48          0.42

9     102.68               1.97          0.52

Benchmarks for genome sequence matching for varying number of sequences ($\seqn$) and block length ($\seql$).

§ SECURITY PROOFS

Security proofs are given in the real-world/ideal-world simulation-based paradigm [63].
Let $\Advsh, \Advmal$ denote the real-world semi-honest, malicious adversary, respectively, corrupting at most $t$ parties in $\Partyset$, denoted by $\Cor$. Let $\simsh, \simmal$ denote the corresponding ideal world semi-honest, malicious adversary, respectively. Security proofs are given in the $\FSETUP, \Ftrgen$-hybrid (and $\Ftrgenmal, \FMulPre, \allowbreak \FDotPPre$-hybrid for malicious setting) model. For modularity, we provide simulation steps for each protocol separately.

The following is the strategy for simulating the computation of function $f$ (represented by a circuit $\ckt$). The simulator $\simsh$ knows the input and output of the adversary $\Advsh$, and sets the inputs of the honest parties to be $0$. $\simsh$ emulates $\FSETUP$ and gives the respective keys to the $\Advsh$. Knowing all the inputs and randomness, $\simsh$ can compute all the intermediate values for each building block in the clear. Thus, $\simsh$ proceeds to simulate each building block in topological order using the aforementioned values (input and output of $\Advsh$, randomness and intermediate values).
We provide the simulation steps for each of the sub-protocols separately for modularity. When carried out in the respective order, these steps result in the simulation steps for the entire computation. To distinguish the simulators for various protocols, we use the corresponding protocol name as the subscript of $\simsh$.

Sharing and Reconstruction

Simulation for input sharing (fig:piInr) and reconstruction appears in fig:ShRSim, fig:RecRSim, respectively.

$\simsh_{\sf Sh}$Semi-honest: Simulation for $\PiSh(P_s,\va)$fig:ShRSim

– Emulate $\FSETUP$ and give the respective shared keys to $\Advsh$.

– Samples shares of $\lv{\va}$ commonly held with $\Advsh$ using the respective PRF keys while other values are sampled randomly.

– If $P_s \in \Cor$, receive $\mv{\va}$ from $\Advsh$ on behalf of honest parties in $\Evlset$. Else, set $\va = 0$, $\mv{\va} = \lv{\va}$ and sends $\mv{\va}$ to $\Advsh$ on behalf of $P_s$ if there exists a corrupt party in $\Evlset$.

$\simsh_{\sf Rec}$Semi-honest: Simulation for reconstructionfig:RecRSim

– If $\Pking \in \Cor$, use the output $\va$, and $\mv{\va}$ and $\tsgr{\lv{\va}}_j$ held by corrupt $P_j \in \Cor \cap \Evlset$ to compute the shares $\tsgr{\lv{\va}}_i$ of each honest $P_i \in \Evlset$ such that $\mv{\va} - \va = \sum_{P_i \in \Evlset \backslash \Cor} \tsgr{\lv{\va}}_i + \sum_{P_j \in \Cor \cap \Evlset} \tsgr{\lv{\va}}_j$. Send the shares of the honest parties in $\Evlset$ to $\Advsh$.

– If $\Pking$ is honest, send output $\va$ to $\Advsh$ on behalf of $\Pking$.

Simulation steps for multiplication (fig:piMultr) are provided in fig:MultRSim0.

Observe that the adversary's view in the simulation is indistinguishable from its view in the real world since it only receives random value in each step of the protocol.

$\simsh_{\sf mult}$Semi-honest: Simulation for $\PiMult$fig:MultRSim0

– If $\istr = 0$: Sample $\sqr{\cdot}$-shares of $\vr$ commonly held with $\Advsh$ using the respective shared keys while other values are sampled randomly.

– Else if $\istr = 1$: Emulate $\Ftrgen$ to generate $\shr{\vr}, \shr{\trunc{\vr}}$.

– On behalf of every honest $P_i \in \Hlpset$, send a random value for $\sgr{\clv{\va \vb} - \vr}_i$ to $\Advsh$ if $\Pking \in \Cor$.

– If $\Pking \in \Cor$, send random value for $\tsgr{\zeta}_i$ to $\Advsh$ on behalf of the honest $P_i \in \Evlset$.

– If $\Pking \notin \Cor$, send a random $\vz - \vr$ to $\Advsh$, if there exists a corrupt party in $\Evlset$.

Other building blocks

Simulation steps for the remaining building blocks can be obtained analogously by simulating the steps for the respective underlying protocols in their order of invocations.

§.§ Malicious security

The following is the strategy for simulating the computation of function $f$ (represented by a circuit $\ckt$). The simulator emulates $\FSETUP$ and gives the respective keys to the malicious adversary, $\Advmal$. This is followed by the input sharing phase in which $\simmal$ extracts the input of $\Advmal$, using the known keys, and sets the inputs of the honest parties to be $0$. Knowing all the inputs, $\simmal$ can compute all the intermediate values for each building block in the clear. Further, $\simmal$ invokes $\Fmpcmal$ and obtains the function output on clear. $\simmal$ proceeds to simulate each building block in topological order using the aforementioned values (inputs of $\Advmal$, intermediate values, and function output).
As before, we provide the simulation steps for each of the sub-protocols separately for modularity. When carried out in the respective order, these steps result in the simulation steps for the entire computation. To distinguish the simulators for various protocols, the corresponding protocol name appears as the subscript of $\simmal$.

Simulation for sharing appears in fig:ShRSimMal.

$\simmal_{\sf Sh}$Malicious: Simulation for $\PiShMal(P_s,\va)$fig:ShRSimMal

– Emulate $\FSETUP$ and give the respective shared keys to $\Advmal$.

– Samples shares of $\lv{\va}$ commonly held with $\Advmal$ using the respective PRF keys while other values are sampled randomly.

– For $P_s \in \Cor$, receive $\mv{\va}$ from $\Advmal$ on behalf of honest parties in $\Evlset$, and obtain $\va = \mv{\va} - \lv{\va}$ (since $\simmal$ knows all the PRF keys, it knows $\lv{\va}$). Invoke $\Fmpcmal$ with $(\INPUT, \va)$ on behalf of $\Advmal$.

– On behalf of the honest parties, set its input $\va = 0$, $\mv{\va} = \lv{\va}$ and send $\mv{\va}$ to $\Advmal$ if there exists a corrupt party in $\Evlset$.

Verification: Send $\Hash(\mv{\va})$ to $\Advmal$ on behalf of the honest parties.
If inconsistent $\mv{\va}$s were received with respect to a corrupt party, invoke $\Fmpcmal$ with $(\SIGNAL, \abort)$.

Simulation for reconstruction (with $\abort$) appears in fig:RecRSimMal.

$\simmal_{\sf Rec}$Malicious: Simulation for reconstructionfig:RecRSimMal

– Use output $\va$ obtained from $\Fmpcmal$, $\mv{\va}$ and $\sqr{\lv{\va}}_j$ held by corrupt $P_j \in \Cor$ to compute the shares $\sqr{\lv{\va}}_i$ of each honest $P_i \in \Evlset$ such that $\mv{\va} - \va = \lv{\va}$. Send the shares of the honest parties in $\Evlset$ to $\Advmal$, and receive shares from $\Advmal$ on behalf of honest parties.

– If any honest party $P_i$ is unable to reconstruct the output, add $P_i$ to set $P$. Send $(\SIGNAL, \abort, P)$ to $\Fmpcmal$.

Simulation steps for multiplication (fig:piMultMal) are provided in fig:MultRSimMal0.

$\simmal_{\sf mult}$Malicious: Simulation for $\PiMultMal$fig:MultRSimMal0

– If $\istr = 0$: Sample $\sqr{\cdot}$-shares of $\vr$ commonly held with $\Advmal$ using the respective shared keys while other values are sampled randomly.

– Else if $\istr = 1$: Emulate $\Ftrgenmal$ to generate $\shr{\vr}, \shr{\trunc{\vr}}$.

– Emulate $\FMulPre$ to generate $\sqr{\cdot}$-shares of $\clv{\va
\vb}$.

– If $\Pking \in \Cor$, send random value for $\tsgr{\zeta}_i$ to $\Advmal$ on behalf of the honest $P_i \in \Evlset$.

– If $\Pking \notin \Cor$, send a random $\vz - \vr$ to $\Advmal$.

– Send $\Hash(\vz_1 - \vr_1 || \ldots || \vz_m - \vr_m)$ with respect to $m$ multiplications, to $\Advmal$ on behalf of the honest parties. If the hash values received from $\Advmal$ are inconsistent, invoke $\Fmpcmal$ with $(\SIGNAL, \abort)$.

– If $\Advmal$ has sent incorrect $\vz - \vr$ for any multiplication ($\simmal$ can detect this since it knows all inputs and randomness that should be used by $\Advmal$), generate random shares for $\Omega$ and simulate reconstruction steps of $\simmal_{\sf Rec}$. Invoke $\Fmpcmal$ with $(\SIGNAL, \abort)$.

– Else, if $\Advmal$ has behaved honestly throughout, simulate reconstruction of $\Omega = 0$ using steps from $\simmal_{\sf Rec}$. Invoke $\Fmpcmal$ with $(\SIGNAL, \abort)$.

Observe that since $\Advmal$ sees random shares in both the real-world protocol and in the simulation, indistinguishability of the simulation follows.

Other building blocks

Simulations for the remaining building blocks can be obtained analogously and using the steps for the underlying protocols.