SWIFT: Super-fast and Robust Privacy-Preserving Machine Learning

Introduction

Privacy Preserving Machine Learning (PPML), a booming field of research, allows Machine Learning (ML) computations over private data of users while ensuring the privacy of the data. PPML finds applications in sectors that deal with sensitive/confidential data, e.g. healthcare, finance, and in cases where organisations are prohibited from sharing client information due to privacy laws such as CCPA and GDPR. However, PPML solutions make the already computationally heavy ML algorithms more compute-intensive. An average end-user who lacks the infrastructure required to run these tasks prefers to outsource the computation to a powerful set of specialized cloud servers and leverage their services on a pay-per-use basis. This is addressed by the Secure Outsourced Computation (SOC) paradigm, and thus is an apt fit for the need of the moment. Many recent works exploit Secure Multiparty Computation (MPC) techniques to realize PPML in the SOC setting where the servers enact the role of the parties. Informally, MPC enables $n$ mutually distrusting parties to compute a function over their private inputs, while ensuring the privacy of the same against an adversary controlling up to $t$ parties. Both the training and prediction phases of PPML can be realized in the SOC setting. The common approach of outsourcing followed in the PPML literature, as well as by our work, requires the users to secret-shareThe threshold of the secret-sharing is decided based on the number of corrupt servers so that privacy is preserved. their inputs between the set of hired (untrusted) servers, who jointly interact and compute the secret-shared output, and reconstruct it towards the users.

In a bid to improve practical efficiency, many recent works cast their protocols into the preprocessing model wherein the input-independent (yet function-dependent) phase computationally heavy tasks are computed in advance, resulting in a fast online phase. This paradigm suits scenario analogous to PPML setting, where functions (ML algorithms) typically need to be evaluated a large number of times, and the function description is known beforehand. To further enhance practical efficiency by leveraging CPU optimizations, recent works propose MPC protocols that work over $32$ or $64$ bit rings. Lastly, solutions for a small number of parties have received a huge momentum due to the many cost-effective customizations that they permit, for instance, a cheaper realisation of multiplication through custom-made secret sharing schemes .

We now motivate the need for robustness aka guaranteed output delivery (GOD) over fairnessThis ensures either all parties or none learn the output., or even abort securityThis may allow the corrupt parties alone to learn the output., in the domain of PPML. Robustness provides the guarantee of output delivery to all protocol participants, no matter how the adversary misbehaves. Robustness is crucial for real-world deployment and usage of PPML techniques. Consider the following scenario wherein an ML model owner wishes to provide inference service. The model owner shares the model parameters between the servers, while the end-users share their queries. A protocol that provides security with abort or fairness will not suffice as in both the cases a malicious adversary can lead to the protocol aborting, resulting in the user not obtaining the desired output. This leads to denial of service and heavy economic losses for the service provider. For data providers, as more training data leads to more accurate models, collaboratively building a model enables them to provide better ML services, and consequently, attract more clients. A robust framework encourages active involvement from multiple data providers. Hence, for the seamless adoption of PPML solutions in the real world, the robustness of the protocol is of utmost importance. Several works realizing PPML via MPC settle for weaker guarantees such as abort and fairness. Achieving the strongest notion of GOD without degrading performance is an interesting goal which is the focus of this work. The hall-mark result of suggests that an honest-majority amongst the servers is necessary to achieve robustness. Consequent to the discussion above, we focus on the honest-majority setting with a small set of parties, especially 3 and 4 parties, both of which have drawn enormous attention recently .

The $3/4$-party setting enables simpler, more efficient, and customized secure protocols compared to the $n$-party setting. Real-world MPC applications and frameworks such as the Danish sugar beet auction and Sharemind , have demonstrated the practicality of $3$-party protocols. Additionally, in an outsourced setting, $3/4$PC is useful and relevant even when there are more parties. Specifically, here the entire computation is offloaded to $3/4$ hired servers, after initial sharing of inputs by the parties amongst the servers. This is precisely what we (and some existing papers ) contemplate as the setting for providing ML-as-a-service. Our protocols work over rings, are cast in the preprocessing paradigm, and achieve GOD.

We restrict the relevant work to a small number of parties and honest-majority, focusing first on MPC, followed by PPML. MPC protocols for a small population can be cast into orthogonal domains of low latency protocols , and high throughput protocols . In the 3PC setting, provide efficient semi-honest protocols wherein ASTRA improved upon by casting the protocols in the preprocessing model and provided a fast online phase. ASTRA further provided security with fairness in the malicious setting with an improved online phase compared to . Later, a maliciously-secure 3PC protocol based on distributed zero-knowledge techniques was proposed by Boneh et al. providing abort security. Further, building on and enhancing the security to GOD, Boyle et al. proposed a concretely efficient 3PC protocol with an amortized communication cost of $3$ field elements (can be extended to work over rings) per multiplication gate. Concurrently, BLAZE provided a fair protocol in the preprocessing model, which required communicating $3$ ring elements in each phase. However, BLAZE eliminated the reliance on the computationally intensive distributed zero-knowledge system (whose efficiency kicks in for large circuit or many multiplication gates) from the online phase and pushed it to the preprocessing phase. This resulted in a faster online phase compared to .

In the regime of 4PC, Gordon et al. presented protocols achieving abort security and GOD. However, relied on expensive public-key primitives and broadcast channels to achieve GOD. Trident improved over the abort protocol of , providing a fast online phase achieving security with fairness, and presented a framework for mixed world computations . A robust 4PC protocol was provided in FLASH , which requires communicating $6$ ring elements, each, in the preprocessing and online phases.

In the PPML domain, MPC has been used for various ML algorithms such as Decision Trees , Linear Regression , k-means clustering , SVM Classification , Logistic Regression . In the 3PC SOC setting, the works of ABY3 and SecureNN , provide security with abort. This was followed by ASTRA , which improves upon ABY3 and achieves security with fairness. ASTRA presents primitives to build protocols for Linear Regression and Logistic Regression inference. Recently, BLAZE improves over the efficiency of ASTRA and additionally tackles training for the above ML tasks, which requires building additional PPML building blocks, such as truncation and bit to arithmetic conversions. In the 4PC setting, the first robust framework for PPML was provided by FLASH which proposed efficient building blocks for ML such as dot product, truncation, MSB extraction, and bit conversion. The works of work over rings to garner practical efficiency. In terms of efficiency, BLAZE and respectively FLASH and Trident are the closest competitors of this work in 3PC and 4PC settings.

1 Our Contributions

To the best of our knowledge, SWIFT is the first robust and efficient PPML framework in the 3PC setting and is as fast as (and is strictly better in some cases than) the best known fair 3PC framework BLAZE . We extend our 3PC framework for 4 servers. In this regime, SWIFT is as fast as the best known fair 4PC framework Trident and twice faster than best known robust 4PC framework FLASH . We detail our contributions next.

We demonstrate the practicality of our protocols by benchmarking PPML, particularly, Logistic Regression (training and inference) and popular Neural Networks (inference) such as , LeNet and VGG16 having millions of parameters. The NN training requires mixed-world conversions , which we leave as future work. Our PPML blocks can be used to perform training and inference of Linear Regression, Support Vector Machines, and Binarized Neural Networks (as demonstrated in ).

Second, instead of using the multiplication of (which has the same overall communication cost as that of our online phase), we build a new protocol. This is because the former involves distributed zero-knowledge protocols. The cost of this heavy machinery gets amortized only for large circuits having millions of gates, which is very unlikely for inference and moderately heavy training tasks in PPML. As in BLAZE , we follow a similar structure for our multiplication protocol but differ considerably in techniques as our goal is to obtain GOD. Our approach is to manipulate and transform some of the protocol steps so that two other servers can locally compute the information required by a server in a round. However, this transformation is not straight forward since BLAZE was constructed with a focus towards providing only fairness (details appear in §3). The multiplication protocol forms a technical basis for our dot product protocol and other PPML building blocks. We emphasise again that the (amortized) cost of our dot product protocol is independent of the vector size.

Third, extending to 4PC brings several performance improvements over 3PC. Most prominent of all is a conceptually simple $\mathsf{jmp}$ instantiation, which forgoes the broadcast channel while retaining the same communication cost; and a dot product with cost independent of vector size sans the 3PC amortization technique.

Fourth, we provide robust protocols for input sharing and output reconstruction phase in the SOC setting, wherein a user shares its input with the servers, and the output is reconstructed towards a user. The need for robustness and communication efficiency together makes these tasks slightly non-trivial. As a highlight, we introduce a super-fast online phase for the reconstruction protocol, which gives $4\times$ improvement in terms of rounds (apart from improvement in the communication) compared to BLAZE. Although we aim for GOD, we ensure that an end-user is never part of broadcast which is relatively expensive than atomic point-to-point communication.

As a final remark, we note that the recent work of proposes a variant of GOD in the 4PC setting, which is termed as private robustness. The authors of state that private robustness is a variant of GOD which guarantees that the correct output is produced in the end, but without relying on an honest party learning the user’s private inputs. Thus, departing from the approach of employing a $\mathsf{TTP}$ to complete the computation when malicious behaviour is detected, attains GOD by eliminating a potentially corrupt party, and repeating the secure computation with fewer number of parties which are deemed to be honest. We point out a few concerns on this work. Firstly, as mentioned earlier, the goal of private robustness is to prevent an honest party learning the user’s input, thereby preventing it from misusing this private information (user’s input) in the future if it goes rogue. We note, however, that in the private robustness setting, although an honest party does not learn a user’s input as a part of the protocol, nothing prevents an adversary from revealing its view to an honest party. In such a scenario, if the honest party goes rogue in the future, it can use its view together with the view received from the adversary to obtain a user’s input. Hence, we believe that the attacks that can be launched in our variant for achieving GOD, can also be launched in the private robustness variant, making the two equivalent. Secondly and importantly, a formal treatment of private robustness is missing in which makes it unclear what additional security is achieved on top of traditional GOD security. Here, we additionally note that the notion of private robustness does not comply with the recently introduced notion of FaF security Althought states that the issue of private robustness was identified and treated formally in , it is not clear whether achieves the FaF security of . For a corruption threshold $t$ and an honest threshold $h^{*}$, FaF security demands that the view of any $t$ corrupt parties and separately the view of any $h^{*}$ honest parties must be simulatable. The latter part which is a new addition compared to traditional security definition requires the presence of a (semi-honest) simulator that can simulate the view of any subset of $h^{*}$ honest parties, given the input and output of those honest parties. This notion is shown to be achievable if and only if $2t+h^{*}<n$, where $n$ is the total number of parties. With $n=4$, $t=1$ and $h^{*}=1$, the results of does not satisfy FaF security since an honest party’s view may include the inputs of the other honest parties when a corrupt party, deviating from the protocol steps, sends its view to it. A formal analysis of protocols in satisfying the FaF security notion of is missing.. Lastly, we emphasize that the approach of eliminating a potentially corrupt party, and re-running the computation results in doubling or tripling the communication cost, thereby undermining the efficiency gains.

2 Organisation of the paper

The rest of the paper is organized as follows. In §2 we describe the system model, preliminaries and notations used. §3 and §4 detail our constructs in the 3PC and 4PC setting respectively. These are followed by the applications and benchmarking in §5. §A elaborates on additional preliminaries while the security proofs for our constructions are provided in §C.

Preliminaries

We consider a set of three servers $\mathcal{P}=\{P_{0},P_{1},P_{2}\}$ that are connected by pair-wise private and authentic channels in a synchronous network, and a static, malicious adversary that can corrupt at most one server. We use a broadcast channel for 3PC alone, which is inevitable . For ML training, several data-owners who wish to jointly train a model, secret share (using the sharing semantics that will appear later) their data among the servers. For ML inference, a model-owner and client secret share the model and the query, respectively, among the servers. Once the inputs are available in the shared format, the servers perform computations and obtain the output in the shared form. In the case of training, the output model is reconstructed towards the data-owners, whereas for inference, the prediction result is reconstructed towards the client. We assume that an arbitrary number of data-owners may collude with a corrupt server for training, whereas for the case of prediction, we assume that either the model-owner or the client can collude with a corrupt server. We prove the security of our protocols using a standard real-world / ideal-world paradigm. We also explore the above model for the four server setting with $\mathcal{P}=\{P_{0},P_{1},P_{2},P_{3}\}$. The aforementioned setting has been explored extensively .

Our constructions achieve the strongest security guarantee of GOD. A protocol is said to be robust or achieve GOD if all parties obtain the output of the protocol regardless of how the adversary behaves. In our model, this translates to all the data owners obtaining the trained model for the case of ML training, while the client obtaining the query output for ML inference. All our protocols are cast into: input-independent preprocessing phase and input-dependent online phase.

The servers use a one-time key setup, modelled as a functionality $\mathcal{F}_{\mathsf{setup}}$ (Fig. 27), to establish pre-shared random keys for pseudo-random functions (PRF) between them. A similar setup is used in for three server case and in for four server setting. The key-setup can be instantiated using any standard MPC protocol in the respective setting. Further, our protocols make use of a collision-resistant hash function, denoted by $\mathsf{H}()$, and a commitment scheme, denoted by $\mathsf{Com}()$. The formal details of key setup, hash function, and commitment scheme are deferred to §A.

Robust 3PC and PPML

In this section, we first introduce the sharing semantics for three servers. Then, we introduce our new Joint Message Passing ($\mathsf{jmp}$) primitive, which plays a crucial role in obtaining the strongest security guarantee of GOD, followed by our protocols in the three server setting.

We use the following secret-sharing semantics.

$P_{s}$ holds $(\mathsf{v}_{s},\mathsf{v}_{(s+1)\%3})$ for $s\in\{0,1,2\}$.

Given $\left[\cdot\right]$-shares of $\mathsf{v}_{1},\mathsf{v}_{2}$, and public constants $c_{1},c_{2}$, servers can locally compute $\left[\cdot\right]$-share of $c_{1}\mathsf{v}_{1}+c_{2}\mathsf{v}_{2}$ as $c_{1}\left[\mathsf{v}_{1}\right]+c_{2}\left[\mathsf{v}_{2}\right]$. It is trivial to see that linearity property is satisfied by $\langle\cdot\rangle$ and $\llbracket\cdot\rrbracket$ sharings.

1 Joint Message Passing primitive

Each $P_{s}$ for $s\in\{i,j,k\}$ maintains a bit $\mathsf{b}_{s}$ initialized to , as an indicator for inconsistency. When $P_{k}$ receives an inconsistent (value, hash) pair, it sets $\mathsf{b}_{k}=1$ and sends the bit to both $P_{i},P_{j}$, who cross-check with each other by exchanging the bit and turn on their inconsistency bit if the bit received from either $P_{k}$ or its fellow sender is turned on. A server broadcasts a hash of its value when its inconsistency bit is on;hash can be computed on a combined message across many calls of $\mathsf{jmp}$. $P_{k}$’s value is the one it receives from $P_{i}$. At this stage, there are a bunch of possible cases and a detailed analysis determines an eligible $\mathsf{TTP}$ in each case.

When $P_{k}$ is silent, the protocol is understood to be complete. This is fine irrespective of the status of $P_{k}$– an honest $P_{k}$ never skips this broadcast with inconsistency bit on, and a corrupt $P_{k}$ implies honest senders. If either $P_{i}$ or $P_{j}$ is silent, then $P_{k}$ is picked as $\mathsf{TTP}$ which is surely honest. A corrupt $P_{k}$ could not make one of $\{P_{i},P_{j}\}$ speak, as the senders (honest in this case) are in agreement on their inconsistency bit (due to their mutual exchange of inconsistency bit). When all of them speak and (i) the senders’ hashes do not match, $P_{k}$ is picked as $\mathsf{TTP}$; (ii) one of the senders conflicts with $P_{k}$, the other sender is picked as $\mathsf{TTP}$; and lastly (iii) if there is no conflict, $P_{i}$ is picked as $\mathsf{TTP}$. The first two cases are self-explanatory. In the last case, either $P_{j}$ or $P_{k}$ is corrupt. If not, a corrupt $P_{i}$ can have honest $P_{k}$ speak (and hence turn on its inconsistency bit), by sending a $\mathsf{v}^{\prime}$ whose hash is not same as that of $\mathsf{v}$ and so inevitably, the hashes of honest $P_{j}$ and $P_{k}$ will conflict, contradicting (iii). As a final touch, we ensure that, in each step, a server raises a public alarm (via broadcast) accusing a server which is silent when it is not supposed to be, and the protocol terminates immediately by labelling the server as $\mathsf{TTP}$ who is neither the complainer nor the accused.

We say that $P_{i},P_{j}$ $\mathsf{jmp\mbox{-}send}$ $\mathsf{v}$ to $P_{k}$ when they invoke $\Pi_{\mathsf{jmp}}(P_{i},P_{j},P_{k},\mathsf{v})$.

Using $\mathsf{jmp}$ in protocols. As mentioned in the introduction, the $\mathsf{jmp}$ protocol needs to be viewed as consisting of two phases (send, verify), where send phase consists of $P_{i}$ sending $\mathsf{v}$ to $P_{k}$ and the rest goes to verify phase. Looking ahead, most of our protocols use $\mathsf{jmp}$, and consequently, our final construction, either of general MPC or any PPML task, will have several calls to $\mathsf{jmp}$. To leverage amortization, the send phase will be executed in all protocols invoking $\mathsf{jmp}$ on the flow, while the verify for a fixed ordered pair of senders will be executed once and for all in the end. The verify phase will determine if all the sends were correct. If not, a $\mathsf{TTP}$ is identified, as explained, and the computation completes with the help of $\mathsf{TTP}$, just as in the ideal-world.

2 3PC Protocols

We now describe the protocols for 3 parties/servers and defer the security proofs to §C.1.

In this protocol, servers execute $\Pi_{\mathsf{jmp}}$ protocol once. Hence the overall cost follows from that of an instance of the $\Pi_{\mathsf{jmp}}$ protocol (Lemma 3.2). ∎

Given $\llbracket\cdot\rrbracket$-shares on input wires $\mathsf{x},\mathsf{y}$, servers can use linearity property of the sharing scheme to locally compute $\llbracket\cdot\rrbracket$-shares of the output of addition gate, $\mathsf{z}=\mathsf{x}+\mathsf{y}$ as $\llbracket\mathsf{z}\rrbracket=\llbracket\mathsf{x}\rrbracket+\llbracket\mathsf{y}\rrbracket$.

servers $P_{1},P_{2}$ locally compute $\left[\beta_{\mathsf{z}}\right]_{j}=(j-1)\beta_{\mathsf{x}}\beta_{\mathsf{y}}-\beta_{x}\left[\alpha_{\mathsf{y}}\right]_{j}-\beta_{y}\left[\alpha_{\mathsf{x}}\right]_{j}+\left[\Gamma_{\mathsf{x}\mathsf{y}}\right]_{j}+\left[\alpha_{\mathsf{z}}\right]_{j}$ during the online phase and mutually exchange their shares to reconstruct $\beta_{\mathsf{z}}$. $P_{1}$ then sends $\beta_{\mathsf{z}}+\gamma_{\mathsf{z}}$ to $P_{0}$, completing the semi-honest protocol. The correctness that asserts $\mathsf{z}=\mathsf{x}\mathsf{y}$ or in other words $\beta_{\mathsf{z}}-\alpha_{\mathsf{z}}=\mathsf{x}\mathsf{y}$ holds due to Eq. 1.

The following issues arise in the above protocol when a malicious adversary is considered:

When $P_{0}$ is corrupt, the $\left[\cdot\right]$-sharing of $\Gamma_{\mathsf{x}\mathsf{y}}$ performed by $P_{0}$ might not be correct, i.e. $\Gamma_{\mathsf{x}\mathsf{y}}\neq\alpha_{\mathsf{x}}\alpha_{\mathsf{y}}$.

When $P_{1}$ (or $P_{2}$) is corrupt, $\left[\cdot\right]$-share of $\beta_{\mathsf{z}}$ handed over to the fellow honest evaluator during the online phase might not be correct, causing reconstruction of an incorrect $\beta_{\mathsf{z}}$.

When $P_{1}$ is corrupt, the value $\beta_{\mathsf{z}}+\gamma_{\mathsf{z}}$ that is sent to $P_{0}$ during the online phase may not be correct.

All the three issues are common with BLAZE (copied verbatim), but we differ from BLAZE in handling them. We begin with solving the last issue first. We simply make $P_{1},P_{2}$ $\mathsf{jmp\mbox{-}send}$ $\beta_{\mathsf{z}}+\gamma_{\mathsf{z}}$ to $P_{0}$ (after $\beta_{\mathsf{z}}$ is computed). This either leads to success or a $\mathsf{TTP}$ selection. Due to $\mathsf{jmp}$’s rate-1 communication, $P_{1}$ alone sending the value to $P_{0}$ remains as costly as using $\mathsf{jmp}$ in amortized sense. Whereas in BLAZE, the malicious version simply makes $P_{2}$ to send a hash of $\beta_{\mathsf{z}}+\gamma_{\mathsf{z}}$ to $P_{0}$ (in addition to $P_{1}$’s communication of $\beta_{\mathsf{z}}+\gamma_{\mathsf{z}}$ to $P_{0}$), who $\mathtt{abort}$s if the received values are inconsistent.

For the remaining two issues, similar to BLAZE, we reduce both to a multiplication (on values unrelated to inputs) in the preprocessing phase. However, our method leads to either success or $\mathsf{TTP}$ selection, with no additional cost.

We start with the second issue. To solve it, where a corrupt $P_{1}$ (or $P_{2}$) sends an incorrect $\left[\cdot\right]$-share of $\beta_{\mathsf{z}}$, BLAZE makes use of server $P_{0}$ to compute a version of $\beta_{\mathsf{z}}$ for verification, based on $\beta_{\mathsf{x}}$ and $\beta_{\mathsf{y}}$, as follows. Using $\beta_{\mathsf{x}}+\gamma_{\mathsf{x}}$, $\beta_{\mathsf{y}}+\gamma_{\mathsf{y}}$, $\alpha_{\mathsf{x}}$, $\alpha_{\mathsf{y}}$, $\alpha_{\mathsf{z}}$ and $\Gamma_{\mathsf{x}\mathsf{y}}$, $P_{0}$ computes:

Clearly, both $P_{0}$ and $P_{i}$ can compute $\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{i}=-(\beta_{\mathsf{x}}+\gamma_{\mathsf{x}})\left[\alpha_{\mathsf{y}}\right]_{i}-(\beta_{\mathsf{y}}+\gamma_{\mathsf{y}})\left[\alpha_{\mathsf{x}}\right]_{i}+\left[\alpha_{\mathsf{z}}\right]_{i}+\left[\chi\right]_{i}$ given $\left[\chi\right]_{i}$. The rest of our discussion explains how (a) $i$th share of $\left[\chi\right]$ can be made available to $\{P_{0},P_{i}\}$ and (b) $\psi$ can be derived by $P_{1},P_{2}$, from a multiplication triple. Similar to BLAZE, yet for a different triple, we observe that $(\mathsf{d},\mathsf{e},\mathsf{f})$ is a multiplication triple, where $\mathsf{d}=(\gamma_{\mathsf{x}}+\alpha_{\mathsf{x}}),\mathsf{e}=(\gamma_{\mathsf{y}}+\alpha_{\mathsf{y}}),\mathsf{f}=(\gamma_{\mathsf{x}}\gamma_{\mathsf{y}}+\psi)+\chi$ if and only if $\chi$ and $\Gamma_{\mathsf{x}\mathsf{y}}$ are correct. Indeed,

Based on this observation, we compute the above multiplication triple using a multiplication protocol and extract out the values for $\psi$ and $\chi$ from the shares of $\mathsf{f}$ which are bound to be correct. This can be executed entirely in the preprocessing phase. Specifically, the servers (a) locally obtain $\langle\cdot\rangle$-shares of $\mathsf{d},\mathsf{e}$ as in Table 3, (b) compute $\langle\cdot\rangle$-shares of $\mathsf{f}(=\mathsf{d}\mathsf{e})$, say denoted by $\mathsf{f}_{0},\mathsf{f}_{1},\mathsf{f}_{2}$, using an efficient, robust 3-party multiplication protocol, say $\Pi_{\mathsf{mulPre}}$ (abstracted in a functionality Fig. 6) and finally (c) extract out the required preprocessing data locally as in Eq. 2. We switch to $\langle\cdot\rangle$-sharing in this part to be able to use the best robust multiplication protocol of that supports this form of secret sharing and requires communication of just $3$ elements. Fortunately, the switch does not cost anything, as both the step (a) and (c) (as above) involve local computation and the cost simply reduces to a single run of a multiplication protocol.

According to $\langle\cdot\rangle$-sharing, both $P_{0}$ and $P_{1}$ obtain $\mathsf{f}_{1}$ and hence obtain $\left[\chi\right]_{1}$. Similarly, $P_{0},P_{2}$ obtain $\mathsf{f}_{0}$ and hence $\left[\chi\right]_{2}$. Finally, $P_{1},P_{2}$ obtain $\mathsf{f}_{2}$ from which they compute $\psi=\mathsf{f}_{2}-\gamma_{\mathsf{x}}\gamma_{\mathsf{y}}$. This completes the informal discussion.

To leverage amortization, the send phase of $\mathsf{jmp\mbox{-}send}$ alone is executed on the fly and verify is performed once for multiple instances of $\mathsf{jmp\mbox{-}send}$. Further, observe that $P_{1},P_{2}$ possess the required shares in the online phase to compute the entire circuit. Hence, $P_{0}$ can come in only during verify of $\mathsf{jmp\mbox{-}send}$ towards $P_{1},P_{2}$, which can be deferred towards the end. Hence, the $\mathsf{jmp\mbox{-}send}$ of $\beta_{\mathsf{z}}+\gamma_{\mathsf{z}}$ to $P_{0}$ (enabling computation of the verification information) can be performed once, towards the end, thereby requiring a single round for sending $\beta_{\mathsf{z}}+\gamma_{\mathsf{z}}$ to $P_{0}$ for multiple instances. Following this, the verify of $\mathsf{jmp\mbox{-}send}$ towards $P_{0}$ is performed first, followed by performing the verify of $\mathsf{jmp\mbox{-}send}$ towards $P_{1},P_{2}$ in parallel.

We note that to facilitate a fast online phase for multiplication, our preprocessing phase leverages a robust multiplication protocol in a black-box manner to derive the necessary preprocessing information. A similar black-box approach is also taken for the dot product protocol in the preprocessing phase. This leaves room for further improvements in the communication cost, which can be obtained by instantiating the black-box with an efficient, robust protocol coupled with the fast online phase.

On the security of our framework: We emphasize that we follow the standard traditional (real-world / ideal-world based) security definition of MPC, according to which, in the 4-party setting with 1 corruption, exactly 1 party is assumed to be corrupt, and rest are honest. As per this definition, disclosing the honest parties’s inputs to a selected honest party is not a breach of security. Indeed, in our framework, the data sharing and the computation on the shared data is done in a way that any malicious behaviour leads to establishment of a $\mathsf{TTP}$ who is enabled to receive all the inputs and compute the output on the clear. There has been a recent study on the additional requirement of hiding the inputs from a quorum of honest parties (treating them as semi-honest), termed as Friends-and-Foes (FaF) security notion . This is a stronger security goal than the standard one and it has been shown that one cannot obtain FaF-secure robust 3PC. We leave FaF-secure 4PC for future exploration.

3 Building Blocks for PPML using 3PC

This section provides details on robust realizations of the following building blocks for PPML in 3-server setting– i) Dot Product, ii) Truncation, iii) Dot Product with Truncation, iv) Secure Comparison, and v) Non-linear Activation functions– Sigmoid and ReLU. We provide the security proofs in §C.1. We begin by providing details of input sharing and reconstruction in the SOC setting.

Protocol $\Pi_{\mathsf{BitInj}}$ is essentially an execution of $\Pi_{\mathsf{bit2A}}$ (Lemma 3.8) followed by one invocation of $\Pi_{\mathsf{mult}}$ (Lemma 3.5) and the costs follow. ∎

To begin with, $\mathsf{z}=\vec{\mathbf{x}}\odot\vec{\mathbf{y}}$ can be viewed as $\mathsf{n}$ parallel multiplication instances of the form $\mathsf{z}_{i}=\mathsf{x}_{i}\mathsf{y}_{i}$ for $i\in[n]$, followed by adding up the results. Let $\mathsf{\beta}_{\mathsf{z}}^{\star}=\sum_{i=1}^{\mathsf{n}}\mathsf{\beta}_{\mathsf{z}_{i}}^{\star}$. Then,

where $\chi=\sum_{i=1}^{\mathsf{n}}(\gamma_{\mathsf{x}_{i}}\alpha_{\mathsf{y}_{i}}+\gamma_{\mathsf{y}_{i}}\alpha_{\mathsf{x}_{i}}+\Gamma_{\mathsf{x}_{i}\mathsf{y}_{i}}-\psi_{i})$.

Apart from the aforementioned modification, the online phase for dot product proceeds similar to that of multiplication protocol. $P_{0},P_{1}$ locally compute $\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{1}$ as per Eq. 3 and $\mathsf{jmp\mbox{-}send}$ $\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{1}$ to $P_{2}$. $P_{1}$ obtains $\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{2}$ in a similar fashion. $P_{1},P_{2}$ reconstruct $\mathsf{\beta}_{\mathsf{z}}^{\star}=\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{1}+\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{2}$ and compute $\beta_{\mathsf{z}}=\mathsf{\beta}_{\mathsf{z}}^{\star}+\sum_{i=1}^{\mathsf{n}}\beta_{\mathsf{x}_{i}}\beta_{\mathsf{y}_{i}}+\psi$. Here, the value $\psi$ has to be correctly generated in the preprocessing phase satisfying Eq. 3. Finally, $P_{1},P_{2}$ $\mathsf{jmp\mbox{-}send}$ $\beta_{\mathsf{z}}+\gamma_{\mathsf{z}}$ to $P_{0}$.

We now provide the details for preprocessing phase that enable servers to obtain the required values ($\chi,\psi$) with the invocation of a dot product protocol in a black-box way. Towards this, let $\vec{\mathbf{d}}=[\mathsf{d}_{1},\ldots,\mathsf{d}_{\mathsf{n}}]$ and $\vec{\mathbf{e}}=[\mathsf{e}_{1},\ldots,\mathsf{e}_{\mathsf{n}}]$, where $\mathsf{d}_{i}=\gamma_{\mathsf{x}_{i}}+\alpha_{\mathsf{x}_{i}}$ and $\mathsf{e}_{i}=\gamma_{\mathsf{y}_{i}}+\alpha_{\mathsf{y}_{i}}$ for $i\in[\mathsf{n}]$, as in the case of multiplication. Then for $\mathsf{f}=\vec{\mathbf{d}}\odot\vec{\mathbf{e}}$,

where $\mathsf{f}_{2}=\sum_{i=1}^{\mathsf{n}}(\gamma_{\mathsf{x}_{i}}\gamma_{\mathsf{y}_{i}}+\psi_{i}),\mathsf{f}_{1}=\left[\chi\right]_{1}$ and $\mathsf{f}_{0}=\left[\chi\right]_{2}$.

It is easy to see from the semantics of $\langle\cdot\rangle$-sharing that both $P_{1},P_{2}$ obtain $\mathsf{f}_{2}$ and hence $\psi$. Similarly, both $P_{0},P_{1}$ obtain $\mathsf{f}_{1}$ and hence $\left[\chi\right]_{1}$, while $P_{0},P_{2}$ obtain $\left[\chi\right]_{2}$.

Working over fixed-point values, repeated multiplications using FPA arithmetic can lead to an overflow resulting in loss of significant bits of information. This put forth the need for truncation that re-adjusts the shares after multiplication so that FPA semantics are maintained. As shown in SecureML , the method of truncation would result in loss of information on the least significant bits and affect the accuracy by a very minimal amount.

For truncation, servers execute $\Pi_{\mathsf{trgen}}$ (Fig. 13) to generate $(\left[\mathsf{r}\right],\llbracket\mathsf{r}^{d}\rrbracket)$-pair, where $\mathsf{r}$ is a random ring element, and $\mathsf{r}^{d}$ is the truncated value of $\mathsf{r}$, i.e the value $\mathsf{r}$ right-shifted by $d$ bit positions. Recall that $d$ denotes the number of bits allocated for the fractional part in the FPA representation. Given $(\mathsf{r},\mathsf{r}^{d})$, the truncated value of $\mathsf{v}$, denoted as ${\mathsf{v}}^{d}$, is computed as ${\mathsf{v}}^{d}={(\mathsf{v}-\mathsf{r})}^{d}+\mathsf{r}^{d}$. The correctness and accuracy of this method was shown in ABY3 .

Similarly, for $\mathsf{r}^{d}$ we have the following,

All the operations in $\Pi_{\mathsf{trgen}}$ are non-interactive except for the two dot product calls required to compute $\mathsf{A},\mathsf{B}$. The cost thus follows from Lemma 3.10. ∎

Given the $\llbracket\cdot\rrbracket$-sharing of vectors $\vec{\mathbf{x}}$ and $\vec{\mathbf{y}}$, protocol $\Pi_{\mathsf{dotpt}}$ (Fig. 14) allows servers to generate $\llbracket{\mathsf{z}}^{d}\rrbracket$, where ${\mathsf{z}}^{d}$ denotes the truncated value of $\mathsf{z}=\vec{\mathbf{x}}\odot\vec{\mathbf{y}}$. A naive way is to compute the dot product using $\Pi_{\mathsf{dotp}}$, followed by performing truncation using the ($\mathsf{r},\mathsf{r}^{d}$) pair. Instead, we follow the optimization of BLAZE where the online phase of $\Pi_{\mathsf{dotp}}$ is modified to integrate the truncation using $(\mathsf{r},\mathsf{r}^{d})$ at no additional cost.

The preprocessing phase now consists of the execution of one instance of $\Pi_{\mathsf{trgen}}$ (Fig. 13) and the preprocessing corresponding to $\Pi_{\mathsf{dotp}}$ (Fig. 11). In the online phase, servers enable $P_{1},P_{2}$ to obtain $\mathsf{z}^{\star}-\mathsf{r}$ instead of $\mathsf{\beta}_{\mathsf{z}}^{\star}$, where $\mathsf{z}^{\star}=\mathsf{\beta}_{\mathsf{z}}^{\star}-\alpha_{\mathsf{z}}$. Using $\mathsf{z}^{\star}-\mathsf{r}$, both $P_{1},P_{2}$ then compute $(\mathsf{z}-\mathsf{r})$ locally, truncate it to obtain ${(\mathsf{z}-\mathsf{r})}^{d}$ and execute $\Pi_{\mathsf{jsh}}$ to generate $\llbracket{(\mathsf{z}-\mathsf{r})}^{d}\rrbracket$. Finally, servers locally compute the result as $\llbracket{\mathsf{z}}^{d}\rrbracket=\llbracket{(\mathsf{z}-\mathsf{r})}^{d}\rrbracket+\llbracket\mathsf{r}^{d}\rrbracket$. The formal details for $\Pi_{\mathsf{dotpt}}$ protocol appear in Fig. 14.

Secure comparison allows servers to check whether $\mathsf{x}<\mathsf{y}$, given their $\llbracket\cdot\rrbracket$-shares. In FPA representation, checking $\mathsf{x}<\mathsf{y}$ is equivalent to checking the $\mathsf{msb}$ of $\mathsf{v}=\mathsf{x}-\mathsf{y}$. Towards this, servers locally compute $\llbracket\mathsf{v}\rrbracket=\llbracket\mathsf{x}\rrbracket-\llbracket\mathsf{y}\rrbracket$ and extract the $\mathsf{msb}$ of $\mathsf{v}$ using $\Pi_{\mathsf{bitext}}$. In case an arithmetic sharing is desired, servers can apply $\Pi_{\mathsf{bit2A}}$ (Fig. 10) protocol on the outcome of $\Pi_{\mathsf{bitext}}$ protocol.

We now elaborate on two of the most prominently used activation functions: i) Rectified Linear Unit (ReLU) and (ii) Sigmoid (Sig).

(i) ReLU: The ReLU function, $\mathsf{relu}(\mathsf{v})=\mathsf{max}(0,\mathsf{v})$, can be viewed as $\mathsf{relu}(\mathsf{v})=\overline{\mathsf{b}}\cdot\mathsf{v}$, where bit $\mathsf{b}=1$ if $\mathsf{v}<0$ and otherwise. Here $\overline{\mathsf{b}}$ denotes the complement of $\mathsf{b}$. Given $\llbracket\mathsf{v}\rrbracket$, servers execute $\Pi_{\mathsf{bitext}}$ on $\llbracket\mathsf{v}\rrbracket$ to generate $\llbracket\mathsf{b}\rrbracket^{\bf B}$. $\llbracket\cdot\rrbracket^{\bf B}$-sharing of $\overline{\mathsf{b}}$ is locally computed by setting $\beta_{\overline{\mathsf{b}}}=1\oplus\beta_{\mathsf{b}}$. Servers execute $\Pi_{\mathsf{BitInj}}$ protocol on $\llbracket\overline{\mathsf{b}}\rrbracket^{\bf B}$ and $\llbracket\mathsf{v}\rrbracket$ to obtain the desired result.

One instance of $\mathsf{relu}$ protocol comprises of execution of one instance of $\Pi_{\mathsf{bitext}}$, followed by $\Pi_{\mathsf{BitInj}}$. The cost, therefore, follows from Lemma 3.7, and Lemma 3.9. ∎

(ii) Sig: In this work, we use the MPC-friendly variant of the Sigmoid function . Note that $\mathsf{sig}(\mathsf{v})=\overline{\mathsf{b}_{1}}\mathsf{b}_{2}(\mathsf{v}+1/2)+\overline{\mathsf{b}_{2}}$, where $\mathsf{b}_{1}=1$ if $\mathsf{v}+1/2<0$ and $\mathsf{b}_{2}=1$ if $\mathsf{v}-1/2<0$. To compute $\llbracket\mathsf{sig}(\mathsf{v})\rrbracket$, servers proceed in a similar fashion as in ReLU, and hence, we skip the details.

The formal details of the MPC-friendly variant of the Sigmoid function is given below:

An instance of $\mathsf{sig}$ protocol involves the execution of the following protocols in order– i) two parallel instances of $\Pi_{\mathsf{bitext}}$ protocol, ii) once instance of $\Pi_{\mathsf{mult}}$ protocol over boolean value, and iii) one instance of $\Pi_{\mathsf{BitInj}}$ and $\Pi_{\mathsf{bit2A}}$ in parallel. The cost follows from Lemma 3.7, Lemma 3.8 and Lemma 3.9. ∎

The goal of maxpool is to find the maximum value in a vector $\vec{\mathbf{x}}$ of $m$ values. Maximum between two elements $\mathsf{x}_{i}$, $\mathsf{x}_{j}$ can be computed by applying secure comparison, which returns a binary sharing of a bit $\mathsf{b}$ such that $\mathsf{b}=0$ if $\mathsf{x}_{i}>\mathsf{x}_{j}$, or $1$, otherwise, followed by computing $(\mathsf{b})^{\bf B}(\mathsf{x}_{j}-\mathsf{x}_{i})+\mathsf{x}_{i}$, which can be performed using bit injection (3.3). To find the maximum value in vector $\vec{\mathbf{x}}$, the servers first group the values in $\vec{\mathbf{x}}$ into pairs and securely compare each pair to obtain the maximum of the two. This results in a vector of size $m/2$. This process is repeated for $\operatorname{O}\left(\log m\right)$ rounds to obtain the maximum value in the entire vector.

Linear matrix operations, such as addition of two matrices $\mathbf{A},\mathbf{B}$ to generate matrix $\mathbf{C}=\mathbf{A}+\mathbf{B}$, can be computed by extending the scalar operations (addition, in this case) with respect to each element of the matrix. Matrix multiplication, on the other hand, can be expressed as a collection of dot products, where the element in the $i^{\text{th}}$ row and $j^{\text{th}}$ column of $\mathbf{C}=\mathbf{A}\times\mathbf{B}$, where $\mathbf{A},\mathbf{B}$ are matrices of dimension $\mathsf{p}\times\mathsf{q}$, $\mathsf{q}\times\mathsf{r}$, respectively, can be computed as a dot product of the $i^{\text{th}}$ row of $\mathbf{A}$ and the $j^{\text{th}}$ column of $\mathbf{B}$. Thus, computing $\mathbf{C}$ of dimension $\mathsf{p}\times\mathsf{r}$ requires $\mathsf{p}\mathsf{r}$ dot products whose communication cost (amortized) is equal to that of computing $\mathsf{p}\mathsf{r}$ multiplications in our case. This improves the cost of matrix multiplication over the naive approach which requires $\mathsf{p}\mathsf{q}\mathsf{r}$ multiplications.

Convolutions form an important building block in several neural network architectures and can be represented as matrix multiplications, as explained in the example below. Consider a 2-dimensional convolution ($\mathsf{CV}$) of a $3\times 3$ input matrix $\mathbf{X}$ with a kernel $\mathbf{K}$ of size $2\times 2$. This can be represented as a matrix multiplication as follows.

Generally, convolving a $f\times f$ kernel over a $w\times h$ input with $p\times p$ padding using $s\times s$ stride having $i$ input channels and $o$ output channels, is equivalent to performing a matrix multiplication on matrices of dimension $(w^{\prime}\cdot h^{\prime})\times(i\cdot f\cdot f)$ and $(i\cdot f\cdot f)\times(o)$ where $w^{\prime}=\dfrac{w-f+2p}{s}+1$ and $h^{\prime}=\dfrac{h-f+2p}{s}+1$. We refer readers to (cf. “Linear and Convolutional Layer”) and for more details.

Robust 4PC and PPML

In this section, we extend our 3PC results to the 4-party case and observe substantial efficiency gain. First, the use of broadcast is eliminated. Second, the preprocessing of multiplication becomes substantially computationally light, eliminating the multiplication protocol (used in the preprocessing) altogether. Third, we achieve a dot product protocol with communication cost independent of the size of the vector, completely eliminating the complex machinery required as in the 3PC case. At the heart of our 4PC constructions lies an efficient 4-party $\mathsf{jmp}$ primitive, denoted as $\mathsf{jmp4}$, that allows two servers to send a common value to a third server robustly.

This section is organized as follows. We begin with the secret-sharing semantics for $4$ servers, for which we only use an extended version of $\llbracket\cdot\rrbracket$-sharing. We then explain the joint message passing primitive for four servers, followed by our 4PC protocols. We conclude this section with a detailed analysis about achieving private robustness.

For a value $\mathsf{v}$, the shares for $P_{0},P_{1}$ and $P_{2}$ remain the same as that for 3PC case. That is, $P_{0}$ holds $(\left[\alpha_{\mathsf{v}}\right]_{1},\left[\alpha_{\mathsf{v}}\right]_{2},\beta_{\mathsf{v}}+\gamma_{\mathsf{v}})$ while $P_{i}$ for $i\in\{1,2\}$ holds $(\left[\alpha_{\mathsf{v}}\right]_{i},\beta_{\mathsf{v}},\gamma_{\mathsf{v}})$. The shares for the fourth server $P_{3}$ is defined as $(\left[\alpha_{\mathsf{v}}\right]_{1},\left[\alpha_{\mathsf{v}}\right]_{2},\gamma_{\mathsf{v}})$. Clearly, the secret is defined as $\mathsf{v}=\beta_{\mathsf{v}}-\left[\alpha_{\mathsf{v}}\right]_{1}-\left[\alpha_{\mathsf{v}}\right]_{2}$.

1 4PC Joint Message Passing Primitive

We say that $P_{i},P_{j}$ $\mathsf{jmp4\mbox{-}send}$ $\mathsf{v}$ to $P_{k}$ when they invoke $\Pi_{\mathsf{jmp4}}(P_{i},P_{j},P_{k},\mathsf{v},P_{l})$.

We note that the end goal of $\mathsf{jmp4}$ primitive relates closely to the bi-convey primitive of FLASH . Bi-convey allows two servers $S_{1},S_{2}$ to convey a value to a server $R$, and in case of an inconsistency, a pair of honest servers mutually identify each other, followed by exchanging their internal randomness to recover the clear inputs, computing the circuit, and sending the output to all. Note, however, that $\mathsf{jmp4}$ primitive is more efficient and differs significantly in techniques from the bi-convey primitive. Unlike in bi-convey, in case of an inconsistency, $\mathsf{jmp4}$ enables servers to learn the $\mathsf{TTP}$’s identity unanimously. Moreover, bi-convey demands that honest servers, identified during an inconsistency, exchange their internal randomness (which comprises of the shared keys established during the key-setup phase) to proceed with the computation. This enforces the need for a fresh key-setup every time inconsistency is detected. On the efficiency front, $\mathsf{jmp4}$ simply halves the communication cost of bi-convey, giving a $2\times$ improvement.

2 4PC Protocols

In this section, we revisit the protocols from 3PC (§3) and suggest optimizations leveraging the presence of an additional honest party in the system. We provide security proofs in §C.2.

To enable $P_{i}$ to share a value $\mathsf{v}$, protocol $\Pi_{\mathsf{sh4}}$ (Fig. 17) proceeds similar to that of 3PC case with the addition that $P_{3}$ also samples the values $\left[\alpha_{\mathsf{v}}\right]_{1},\left[\alpha_{\mathsf{v}}\right]_{2},\gamma_{\mathsf{v}}$ using the shared randomness with the respective servers. On a high level, $P_{i}$ computes $\beta_{\mathsf{v}}=\mathsf{v}+\left[\alpha_{\mathsf{v}}\right]_{1}+\left[\alpha_{\mathsf{v}}\right]_{2}$ and sends $\beta_{\mathsf{v}}$ (or $\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}$) to another server and they together $\mathsf{jmp4\mbox{-}send}$ this information to the intended servers. The formal protocol for sharing a value $\mathsf{v}$ by $P_{i}$ is given in Fig. 17

We further observe that servers can generate a $\llbracket\cdot\rrbracket$-sharing of $\mathsf{v}$ non-interactively when $\mathsf{v}$ is available with $P_{0},P_{1},P_{2}$. For this, servers set $\left[\alpha_{\mathsf{v}}\right]_{1}=\left[\alpha_{\mathsf{v}}\right]_{2}=\gamma_{\mathsf{v}}=0$ and $\beta_{\mathsf{v}}=\mathsf{v}$. We abuse notation and use $\Pi_{\mathsf{jsh4}}(P_{0},P_{1},P_{2},\mathsf{v})$ to denote this sharing.

In some protocols, $P_{3}$ is required to generate $\langle\cdot\rangle$-sharing of a value $\mathsf{v}$ in the preprocessing phase, where $\langle\cdot\rangle$-sharing of $\mathsf{v}$ is same as that defined in 3PC (where $\mathsf{v}=\mathsf{v}_{0}+\mathsf{v}_{1}+\mathsf{v}_{2}$, and $P_{0}$ possesses $(\mathsf{v}_{0},\mathsf{v}_{1})$, $P_{1}$ possesses $(\mathsf{v}_{1},\mathsf{v}_{2})$, and $P_{2}$ possess $(\mathsf{v}_{2},\mathsf{v}_{0})$) with the addition that $P_{3}$ now possesses $(\mathsf{v}_{0},\mathsf{v}_{1},\mathsf{v}_{2})$. We call the resultant protocol $\Pi_{\mathsf{ash4}}$ and it appears in Fig. 19.

Note that servers can locally convert $\langle\mathsf{v}\rangle$ to $\llbracket\mathsf{v}\rrbracket$ by setting their shares as shown in Table 5.

Given the $\llbracket\cdot\rrbracket$-shares of $\mathsf{x}$ and $\mathsf{y}$, protocol $\Pi_{\mathsf{mult4}}$ (Fig. 20) allows servers to compute $\llbracket\mathsf{z}\rrbracket$ with $\mathsf{z}=\mathsf{x}\mathsf{y}$. When compared with the state-of-the-art 4PC GOD protocol of FLASH , our solution improves communication in both, the preprocessing and online phase, from $6$ to $3$ ring elements. Moreover, our communication cost matches with the state-of-the-art 4PC protocol of Trident that only provides security with fairness.

Given $\llbracket\mathsf{v}\rrbracket$, protocol $\Pi_{\mathsf{rec4}}$ (Fig. 21) enables servers to robustly reconstruct the value $\mathsf{v}$ among the servers. Note that every server lacks one share for reconstruction and the same is available with three other servers. Hence, they communicate the missing share among themselves, and the majority value is accepted. As an optimization, two among the three servers can send the missing share while the third one can send a hash of the same for verification. Notice that, as opposed to the 3PC case, this protocol does not require commitments. The formal protocol for reconstruction is given in Fig. 21.

3 Building Blocks for PPML using 4PC

This section provides details on robust realizations of the PPML building blocks in 4-server setting (for the same blocks as in §3.3). We provide the security proofs in §C.2.

where $\mathsf{c}_{\mathsf{b}}=\beta_{\mathsf{b}}\oplus\gamma_{\mathsf{b}},~{}\mathsf{e}_{\mathsf{b}}=\alpha_{\mathsf{b}}\oplus\gamma_{\mathsf{b}},~{}\mathsf{c}_{\mathsf{v}}=\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}$ and $\mathsf{e}_{\mathsf{v}}=\alpha_{\mathsf{v}}+\gamma_{\mathsf{v}}$. The protocol proceeds with $P_{3}$ generating $\langle\cdot\rangle$-shares of $\mathsf{e}_{\mathsf{b}}^{\sf R}$ and $\mathsf{e}_{\mathsf{z}}=\mathsf{e}_{\mathsf{b}}^{\sf R}\mathsf{e}_{\mathsf{v}}$, followed by verification of the same by $P_{0},P_{1},P_{2}$. If verification succeeds, then to enable $P_{2}$ to compute $\beta_{\mathsf{z}}=\mathsf{z}+\alpha_{\mathsf{z}}$, $P_{1},P_{0}$ $\mathsf{jmp4\mbox{-}send}$ the missing share of $\beta_{\mathsf{z}}$ to $P_{2}$. Similarly for $P_{1}$. Next, $P_{1},P_{2}$ reconstruct $\beta_{\mathsf{z}}$, and $\mathsf{jmp4\mbox{-}send}$ $\beta_{\mathsf{z}}+\gamma_{\mathsf{z}}$ to $P_{0}$ completing the protocol.

Given $\llbracket\cdot\rrbracket$-shares of two $\mathsf{n}$-sized vectors $\vec{\mathbf{x}},\vec{\mathbf{y}}$, protocol $\Pi_{\mathsf{dotp4}}$ (Fig. 24) enables servers to compute $\llbracket\mathsf{z}\rrbracket$ with $\mathsf{z}=\vec{\mathbf{x}}\odot\vec{\mathbf{y}}$. The protocol is essentially similar to $\mathsf{n}$ instances of multiplications of the form $\mathsf{z}_{i}=\mathsf{x}_{i}\mathsf{y}_{i}$ for $i\in[\mathsf{n}]$. But instead of communicating values corresponding to each of the $\mathsf{n}$ instances, servers locally sum up the shares and communicate a single value. This helps to obtain a communication cost independent of the size of the vectors.

In more detail, the dot product protocol proceeds as follows. During the preprocessing phase, similar to the multiplication protocol $P_{0},P_{1},P_{3}$ sample a random $\left[\Gamma_{\vec{\mathbf{x}}\odot\vec{\mathbf{y}}}\right]_{1}$. $P_{0},P_{3}$ compute $\Gamma_{\vec{\mathbf{x}}\odot\vec{\mathbf{y}}}=\sum_{i=1}^{\mathsf{n}}\alpha_{\mathsf{x}_{i}}\alpha_{\mathsf{y}_{i}}$ and $\mathsf{jmp4\mbox{-}send}$ $\left[\Gamma_{\vec{\mathbf{x}}\odot\vec{\mathbf{y}}}\right]_{2}=\Gamma_{\vec{\mathbf{x}}\odot\vec{\mathbf{y}}}-\left[\Gamma_{\vec{\mathbf{x}}\odot\vec{\mathbf{y}}}\right]_{1}$ to $P_{2}$. $P_{1},P_{2},P_{3}$ sample a random $\psi$, and generate its $\left[\cdot\right]$-shares locally. Servers $P_{3},P_{j}$ for $j\in\{1,2\}$ then compute $\left[\chi\right]_{j}=\sum_{i=1}^{\mathsf{n}}(\gamma_{\mathsf{x}_{i}}\left[\alpha_{\mathsf{y}_{i}}\right]_{j}+\gamma_{\mathsf{y}_{i}}\left[\alpha_{\mathsf{x}_{i}}\right]_{j})+\left[\Gamma_{\vec{\mathbf{x}}\odot\vec{\mathbf{y}}}\right]_{j}-\left[\psi\right]_{j}$, and $\mathsf{jmp4\mbox{-}send}$ $\left[\chi\right]_{j}$ to $P_{0}$. The formal protocol is given in Fig. 24.

Given the $\llbracket\cdot\rrbracket$-sharing of a value $\mathsf{v}$ and a random truncation pair $(\left[\mathsf{r}\right],\llbracket\mathsf{r}^{d}\rrbracket)$, the $\llbracket\cdot\rrbracket$-sharing of the truncated value ${\mathsf{v}}^{d}$ (right shifted value by, say, $d$ positions) can be computed as follows. Servers open the value $(\mathsf{v}-\mathsf{r})$, truncate it and add it to $\llbracket{\mathsf{r}}^{d}\rrbracket$ to obtain $\llbracket{\mathsf{v}}^{d}\rrbracket$. The protocol for generating the truncation pair $(\left[\mathsf{r}\right],\llbracket\mathsf{r}^{d}\rrbracket)$ is described in Fig. 25.

The cost follows directly from that of $\Pi_{\mathsf{jmp4}}$ (Lemma 4.2 and 4.4). ∎

Protocol $\Pi_{\mathsf{dotpt4}}$ (Fig. 26) enables servers to generate $\llbracket\cdot\rrbracket$-sharing of the truncated value of $\mathsf{z}=\vec{\mathbf{x}}\odot\vec{\mathbf{y}}$, denoted as ${\mathsf{z}}^{d}$, given the $\llbracket\cdot\rrbracket$-sharing of $\mathsf{n}$-sized vectors $\vec{\mathbf{x}}$ and $\vec{\mathbf{y}}$. This protocol is similar to the 3PC protocol.

Here, as in the 3PC case, we consider two activation functions – ReLU and Sig.

One instance of $\mathsf{relu}$ protocol comprises of execution of one instance of $\Pi_{\mathsf{bitext4}}$, followed by $\Pi_{\mathsf{bitinj4}}$. The cost, therefore, follows from Lemma 4.8, and Lemma 4.10. ∎

An instance of $\mathsf{sig}$ protocol involves the execution of the following protocols in order– i) two parallel instances of $\Pi_{\mathsf{bitext4}}$ protocol, ii) one instance of $\Pi_{\mathsf{mult4}}$ protocol over boolean value, and iii) one instance of $\Pi_{\mathsf{bitinj4}}$ and $\Pi_{\mathsf{bit2A4}}$ in parallel. The cost follows from Lemma 4.8, Lemma 4.9 and Lemma 4.10. ∎

Applications and Benchmarking

In this section, we empirically show the practicality of our protocols for PPML. We consider training and inference for Logistic Regression, and inference for $3$ different Neural Networks (NN). NN training requires additional tools to allow mixed world computations, which we leave as future work. We refer readers to SecureML , ABY3 , BLAZE , FALCON for a detailed description of the training and inference steps for the aforementioned ML algorithms. All our benchmarking is done over the publicly available MNIST and CIFAR-10 dataset. For training, we use a batch size of $B=128$ and define $1$ KB = $8192$ bits.

In 3PC, we compare our results against the best-known framework BLAZE that provides fairness in the same setting. We observe that the technique of making the dot product cost independent of feature size can also be applied to BLAZE to obtain better costs. Hence, for a fair comparison, we additionally report these improved values for BLAZE. Further, we only consider the PPA circuit based variant of bit extraction for BLAZE since we aim for high throughput; the GC based variant results in huge communication and is not efficient for deep NNs. Our results imply that we get GOD at no additional cost compared to BLAZE. For 4PC, we compare our results with two best-known works FLASH (which is robust) and Trident (which is fair). Our results halve the cost of FLASH and are on par with Trident.

We implement our protocols using the publicly available ENCRYPTO library in C++17. We obtained the code of BLAZE and FLASH from the respective authors and executed them in our environment. The collision-resistant hash function was instantiated using SHA-256. We have used multi-threading, and our machines were capable of handling a total of 32 threads. Each experiment is run for 20 times, and the average values are reported.

MNIST is a collection of $28\times 28$ pixel, handwritten digit images along with a label between and $9$ for each image. It has $60,000$ and respectively, $10,000$ images in the training and test set. We evaluate logistic regression, and NN-1, NN-2 (cf. §5.2) on this dataset.

CIFAR-10 consists of $32\times 32$ pixel images of $10$ different classes such as dogs, horses, etc. There are $50,000$ images for training and $10,000$ for testing, with $6000$ images in each class. We evaluate NN-3 (cf. §5.2) on this dataset.

We use throughput ($\mathsf{TP}$) as the benchmarking parameter following BLAZE and ABY3 as it would help to analyse the effect of improved communication and round complexity in a single shot. Here, $\mathsf{TP}$ denotes the number of operations (“iterations" for the case of training and “queries" for the case of inference) that can be performed in unit time. We consider minute as the unit time since most of our protocols over WAN requires more than a second to complete. An iteration in ML training consists of a forward propagation phase followed by a backward propagation phase. In the former phase, servers compute the output from the inputs. At the same time, in the latter, the model parameters are adjusted according to the difference in the computed output and the actual output. The inference can be viewed as one forward propagation of the algorithm alone. In addition to $\mathsf{TP}$, we provide the online and overall communication and latency for all the benchmarked ML algorithms.

We observe that due to our protocols’ asymmetric nature, the communication load is unevenly distributed among all the servers, which leaves several communication channels under-utilized. Thus, to improve the performance, we perform load balancing, where we run several parallel execution threads, each with roles of the servers changed. This helps in utilizing all channels and improving the performance. We report the communication and runtime of the protocols for online phase and total (= preprocessing + online).

1 Logistic Regression

In Logistic Regression, one iteration comprises updating the weight vector $\vec{\mathbf{w}}$ using the gradient descent algorithm (GD). It is updated according to the function given below: $\vec{\mathbf{w}}=\vec{\mathbf{w}}-\frac{\alpha}{B}\mathbf{X}_{i}^{T}\circ\left(\mathsf{sig}(\mathbf{X}_{i}\circ\vec{\mathbf{w}})-\mathbf{Y}_{i}\right).$ where $\alpha$ and $\mathbf{X}_{i}$ denote the learning rate, and a subset, of batch size B, randomly selected from the entire dataset in the $i$th iteration, respectively. The forward propagation comprises of computing the value $\mathbf{X}_{i}\circ\vec{\mathbf{w}}$ followed by an application of a sigmoid function on it. The weight vector is updated in the backward propagation, which internally requires the computation of a series of matrix multiplications, and can be achieved using a dot product. The update function can be computed using $\llbracket\cdot\rrbracket$ shares as: $\llbracket\vec{\mathbf{w}}\rrbracket=\llbracket\vec{\mathbf{w}}\rrbracket-\frac{\alpha}{B}\llbracket\mathbf{X}_{j}^{T}\rrbracket\circ(\mathsf{sig}(\llbracket\mathbf{X}_{j}\rrbracket\circ\llbracket\vec{\mathbf{w}}\rrbracket)-\llbracket\mathbf{Y}_{j}\rrbracket).$ We summarize our results in Table 6.

We observe that the online $\mathsf{TP}$ for the case of 3PC inference is slightly lower compared to that of BLAZE. This is because the total number of rounds for the inference phase is slightly higher in our case due to the additional rounds introduced by the verification mechanism (aka verify phase which also needs broadcast). This gap becomes less evident for protocols with more number of rounds, as is demonstrated in the case of NN (presented next), where verification for several iterations is clubbed together, making the overhead for verification insignificant.

For the case of 4PC, our solution outperforms FLASH in terms of communication as well as throughput. Concretely, we observe a $2\times$ improvement in $\mathsf{TP}$ for inference and a $2.3\times$ improvement for training. For Trident , we observe a drop of $15.86\%$ in $\mathsf{TP}$ for inference due to the extra rounds required for verification to achieve GOD. This loss is, however, traded-off with the stronger security guarantee. For training, we are on par with Trident as the effect of extra rounds becomes less significant for more number of rounds, as will also be evident from the comparisons for NN inference.

As a final remark, note that our 4PC sees roughly $2.5\times$ improvement compared to our 3PC for logistic regression.

2 NN Inference

We consider the following popular neural networks for benchmarking. These are chosen based on the different range of model parameters and types of layers used in the network. We refer readers to for a detailed architecture of the neural networks.

NN-1: This is a $3$-layered fully connected network with ReLU activation after each layer. This network has around $118$K parameters and is chosen from .

NN-2: This network, called LeNet , contains $2$ convolutional layers and $2$ fully connected layers with ReLU activation after each layer, additionally followed by maxpool for convolutional layers. This network has approximately $431$K parameters.

NN-3: This network, called VGG16 , was the runner-up of ILSVRC-2014 competition. This network has $16$ layers in total and comprises of fully-connected, convolutional, ReLU activation and maxpool layers. This network has about $138$ million parameters.

Table 7 summarise our benchmarking results for 3PC NN inference. As illustrated, the performance of our 3PC framework is on par with BLAZE while providing better security guarantee.

Table 8 summarises NN inference for 4PC setting. Here, we outperform FLASH in every aspect, with the improvement in $\mathsf{TP}$ being at least $2.5\times$ for each NN architecture. Further, we are on par with Trident because the extra rounds required for verification get amortized with an increase in the number of rounds required for computing NN inference. This establishes the practical relevance of our work.

As a final remark, note that our 4PC sees roughly $3\times$ improvement compared to our 3PC for NN inference. This reflects the improvements brought in by the additional honest server in the system.

Conclusion

In this work, we presented an efficient framework for PPML that achieves the strongest security of GOD or robustness. Our 3PC protocol builds upon the recent work of BLAZE and achieves almost similar (in some cases, better) performance albeit improving the security guarantee. For the case of 4PC, we outperform the best-known– (a) robust protocol of FLASH by $2\times$ performance-wise and (b) fair protocol of Trident by uplifting its security.

We leave the problem of extending our framework to support mixed-world conversions as well as to design protocols to support algorithms like Decision Trees, k-means Clustering etc. as open problem.

Acknowledgements

We thank our shepherd Guevara Noubir, and anonymous reviewers for their valuable feedback.

Nishat Koti would like to acknowledge financial support from Cisco PhD Fellowship 2020. Mahak Pancholi would like to acknowledge financial support from Cisco MTech Fellowship 2020. Arpita Patra would like to acknowledge financial support from SERB MATRICS (Theoretical Sciences) Grant 2020 and Google India AI/ML Research Award 2020. Ajith Suresh would like to acknowledge financial support from Google PhD Fellowship 2019. The authors would also like to acknowledge the financial support from Google Cloud to perform the benchmarking.

References

Appendix A Preliminaries

One key shared between every pair– $k_{01},k_{02},\allowbreak k_{12}$ for the servers $(P_{0},P_{1}),(P_{0},P_{2})$and$(P_{1},P_{2})$, respectively.

One shared key known to all the servers– $k_{\mathcal{P}}$.

The key setup is modelled via a functionality $\mathcal{F}_{\mathsf{setup}}$ (Fig. 27) that can be realised using any secure MPC protocol. Analogously, key setup functionality for 4PC is given in Fig. 28.

To generate a 3-out-of-3 additive sharing of i.e. $\zeta_{s}$ for $s\in\{0,1,2\}$ such that $P_{s}$ holds $\zeta_{s}$, and $\zeta_{0}+\zeta_{1}+\zeta_{2}=0$, servers proceed as follows. Every pair of servers, $P_{s},P_{(s+1)\%3}$, non-interactively generate $\mathsf{r}_{s}$, as described earlier, and each $P_{s}$ sets $\zeta_{s}=\mathsf{r}_{s}-\mathsf{r}_{(s-1)\%3}$.

A.2 Collision Resistant Hash Function

Consider a hash function family $\mathsf{H}=\mathcal{K}\times\mathcal{L}\rightarrow\mathcal{Y}$. The hash function $\mathsf{H}$ is said to be collision resistant if, for all probabilistic polynomial-time adversaries $\mathcal{A}$, given the description of $\mathsf{H}_{k}$ where $k\in_{R}\mathcal{K}$, there exists a negligible function $\mathsf{negl}()$ such that $\Pr[(x_{1},x_{2})\leftarrow\mathcal{A}(k):(x_{1}\neq x_{2})\wedge\mathsf{H}_{k}(x_{1})=\mathsf{H}_{k}(x_{2})]\leq\mathsf{negl}(\kappa)$, where $m=\mathsf{poly}(\kappa)$ and $x_{1},x_{2}\in_{R}\{0,1\}^{m}$.

A.3 Commitment Scheme

Let $\mathsf{Com}(x)$ denote the commitment of a value $x$. The commitment scheme $\mathsf{Com}(x)$ possesses two properties; hiding and binding. The former ensures privacy of the value $\mathsf{v}$ given just its commitment $\mathsf{Com}(\mathsf{v})$, while the latter prevents a corrupt server from opening the commitment to a different value $x^{\prime}\neq x$. The practical realization of a commitment scheme is via a hash function $\mathcal{H}()$ given below, whose security can be proved in the random-oracle model (ROM)– for $(c,o)=(\mathcal{H}(x||r),\allowbreak x||r)=\mathsf{Com}(x;r)$.

As mentioned earlier, a trivial way to instantiate $\Pi_{\mathsf{dotpPre}}$ is to treat a dot product operation as $\mathsf{n}$ multiplications. However, this results in a communication cost that is linearly dependent on the feature size. Instead, we instantiate $\Pi_{\mathsf{dotpPre}}$ by a semi-honest dot product protocol followed by a verification phase to check the correctness. For the verification phase, we extend the techniques of to provide support for verification of dot product tuples. Setting the verification phase parameters appropriately gives a $\Pi_{\mathsf{dotpPre}}$ whose (amortized) communication cost is independent of the feature size. We provide the details next.

To realize $\mathcal{F}_{\mathsf{DotPPre}}$, the approach is to run a semi-honest dot product protocol followed by a verification phase to check the correctness of the output. For verification, the work of provides techniques to verify the correctness of $m$ multiplication triples (and degree-two relations) at a cost of $\mathcal{O}(\sqrt{m})$ extended ring elements, albeit with abort security. While improves their techniques to provide robust verification for multiplication, we show how to extend the techniques in to robustly verify the correctness of $m$ dot product tuples (dot product being a degree two relation), with vectors of dimension $\mathsf{n}$, at a cost of $\mathcal{O}(\sqrt{\mathsf{n}m})$ extended ring elements. Thus, the cost to realize one instance of $\mathcal{F}_{\mathsf{DotPPre}}$ can be brought down to only the cost of a semi-honest dot product computation (which is $3$ ring elements and independent of the vector dimension), where the cost due to verification can be amortized away by setting $\mathsf{n},m$ appropriately.

Now, to complete the $\langle\cdot\rangle$-sharing of $\mathsf{f}$, $P_{i}$ sends $\mathsf{f}_{i}$ to $P_{i-1}$. To check the correctness of the computation $\langle\mathsf{f}\rangle=\langle\vec{\mathbf{d}}\odot\vec{\mathbf{e}}\rangle$, each $P_{i}\in\mathcal{P}$ needs to prove that the $\mathsf{f}_{i}$ it sent in the semi-honest protocol satisfies 7, i.e.

This difference in the expected message that should be sent (computed using $P_{i}$’s correct input shares) and actual message that is sent by $P_{i}$ is captured by a circuit $c$, defined below.

Here, $c$ takes as input $u=4\mathsf{n}+2$ values: $\langle\cdot\rangle$-shares of $\vec{\mathbf{d}},\vec{\mathbf{e}}$ held by $P_{i}$, i.e. $\{\mathsf{d}_{j,i},\mathsf{d}_{j,{i+1}},\mathsf{e}_{j,i},\mathsf{e}_{j,{i+1}}\}_{j=1}^{\mathsf{n}}$, the additive share of zero, $\zeta_{i}$, that $P_{i}$ holds, and the additive share $\mathsf{f}_{i}$ sent by $P_{i}$. For correct computation with respect to $P_{i}$, we require the difference in the expected message and the actual message to be , i.e.,

We now explain how to verify the correctness for $m$ dot product tuples assuming that the operations are carried out over a prime-order field. The verification can be extended to support operations over rings following the techniques of . To verify the correctness for $m$ dot product tuples, $\{\vec{\mathbf{d}}_{k},\vec{\mathbf{e}}_{k},\mathsf{f}_{k}\}_{k=1}^{m}$ where $\mathsf{f}_{k}=\vec{\mathbf{d}}_{k}\odot\vec{\mathbf{e}}_{k}$, the output of $c$ (which is the difference in the expected and actual message sent) for each of the corresponding dot product tuple must be . To check correctness of all dot products at once, it suffices to check if a random linear combination of the output of each $c$ (for each dot product) is . This is because the random linear combination of the differences will be with high probability if $\mathsf{f}_{k}=\vec{\mathbf{d}}_{k}\odot\vec{\mathbf{e}}_{k}$ for each $k\in\{1,\ldots,m\}$. We remark that the definition of $c(\cdot)$ in enables the verification of only multiplication triples. With the re-definition of $c$ as in 9, we can now verify the correctness of dot products while the rest of the verification steps remain similar to that in . We elaborate on the details, next.

A verification circuit, constructed as follows, enables $P_{i}$ to prove the correctness of the additive share of $\mathsf{f}$ that it sent, for $m$ instances of dot product at once. Note that the proof system is designed for the distributed-verifier setting where the proof generated by $P_{i}$ will be shared among $P_{i-1},P_{i+1}$, who can together verify its correctness. First, a sub-circuit $g$ is defined as: group $L$ small $c$ circuits and take a random linear combination of the values on their output wires. Since each $c$ circuit takes $u=4\mathsf{n}+2$ inputs as described earlier, $g$ takes in $uL$ inputs. Precisely, $g$ is defined as follows: