# SWIFT: Super-fast and Robust Privacy-Preserving Machine Learning††thanks:
This article is the full and extended version of an article to appear in
USENIX Security’21.

Nishat Koti⋆, Mahak Pancholi⋆, Arpita Patra⋆, Ajith Suresh⋆
⋆Department of Computer Science and Automation, Indian Institute of Science,
Bangalore, India
{kotis, mahakp, arpita<EMAIL_ADDRESS>
###### Abstract

Performing machine learning (ML) computation on private data while maintaining
data privacy, aka Privacy-preserving Machine Learning (PPML), is an emergent
field of research. Recently, PPML has seen a visible shift towards the
adoption of the Secure Outsourced Computation (SOC) paradigm due to the heavy
computation that it entails. In the SOC paradigm, computation is outsourced to
a set of powerful and specially equipped servers that provide service on a
pay-per-use basis. In this work, we propose SWIFT, a robust PPML framework for
a range of ML algorithms in SOC setting, that guarantees output delivery to
the users irrespective of any adversarial behaviour. Robustness, a highly
desirable feature, evokes user participation without the fear of denial of
service.

At the heart of our framework lies a highly-efficient, maliciously-secure,
three-party computation (3PC) over rings that provides guaranteed output
delivery (GOD) in the honest-majority setting. To the best of our knowledge,
SWIFT is the first robust and efficient PPML framework in the 3PC setting.
SWIFT is as fast as (and is strictly better in some cases than) the best-known
3PC framework BLAZE (Patra et al. NDSS’20), which only achieves fairness. We
extend our 3PC framework for four parties (4PC). In this regime, SWIFT is as
fast as the best known fair 4PC framework Trident (Chaudhari et al. NDSS’20)
and twice faster than the best-known robust 4PC framework FLASH (Byali et al.
PETS’20).

We demonstrate our framework’s practical relevance by benchmarking popular ML
algorithms such as Logistic Regression and deep Neural Networks such as VGG16
and LeNet, both over a 64-bit ring in a WAN setting. For deep NN, our results
testify to our claims that we provide improved security guarantee while
incurring no additional overhead for 3PC and obtaining $2\times$ improvement
for 4PC.

##  1 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 [45, 41, 50, 43, 56, 15, 12, 16, 48]
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-share111The 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 [27, 25, 36, 34,
6, 26, 20, 35, 15, 12, 16, 48] 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 [7, 26, 21,
28, 24] 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 [4, 3, 15, 48, 16, 12].

We now motivate the need for robustness aka guaranteed output delivery (GOD)
over fairness222This ensures either all parties or none learn the output., or
even abort security333This 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 [15, 43, 56,
48, 16] 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 [18] 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 [44, 4, 31, 3,
14, 46, 15, 9, 48, 16, 12, 10].

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 [8] and Sharemind [7], 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 [48, 12, 42]) contemplate
as the setting for providing ML-as-a-service. Our protocols work over rings,
are cast in the preprocessing paradigm, and achieve GOD.

##### Related Work

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 [47,
14, 13], and high throughput protocols [7, 4, 3, 31, 17, 15, 46, 48, 10, 1,
30]. In the 3PC setting, [4, 15] provide efficient semi-honest protocols
wherein ASTRA [15] improved upon [4] 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 [3]. Later, a maliciously-secure 3PC protocol based on distributed
zero-knowledge techniques was proposed by Boneh et al. [9] providing abort
security. Further, building on [9] and enhancing the security to GOD, Boyle et
al. [10] 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 [48] 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 [10].

In the regime of 4PC, Gordon et al. [32] presented protocols achieving abort
security and GOD. However, [32] relied on expensive public-key primitives and
broadcast channels to achieve GOD. Trident [16] improved over the abort
protocol of [32], providing a fast online phase achieving security with
fairness, and presented a framework for mixed world computations [28]. A
robust 4PC protocol was provided in FLASH [12], 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 [40], Linear Regression [29, 51], k-means clustering [33, 11],
SVM Classification [58, 55], Logistic Regression [53]. In the 3PC SOC setting,
the works of ABY3 [43] and SecureNN [56], provide security with abort. This
was followed by ASTRA [15], 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 [12] which proposed efficient
building blocks for ML such as dot product, truncation, MSB extraction, and
bit conversion. The works of [45, 43, 56, 15, 48, 16, 12] 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.1 Our Contributions

We propose, SWIFT, a robust maliciously-secure framework for PPML in the SOC
setting, with a set of $3$ and $4$ servers having an honest-majority. At the
heart of our framework lies highly-efficient, maliciously-secure, 3PC and 4PC
over rings (both $\mathbb{Z}_{2^{\ell}}$ and $\mathbb{Z}_{2^{1}}$) that
provide GOD in the honest-majority setting. We cast our protocols in the
preprocessing model, which helps obtain a fast online phase. As mentioned
earlier, the input-independent (yet function-dependent) computations will be
performed in the preprocessing phase.

Building Blocks 1 | 3PC | 4PC
---|---|---
Ref. | Pre. | Online | Security | Ref. | Pre. | Online | Security
Comm. ($\ell$) | Rounds | Comm. ($\ell$) | Comm. ($\ell$) | Rounds | Comm. ($\ell$)
Multiplication | [9] | $1$ | 1 | $2$ | Abort |  |  |  |  |
[10] | - | 3 | $3$ | GOD | Trident | $3$ | 1 | $3$ | Fair
BLAZE | $3$ | 1 | $3$ | Fair | FLASH | $6$ | 1 | $6$ | GOD
SWIFT | $\mathbf{3}$ | $\mathbf{1}$ | $\mathbf{3}$ | GOD | SWIFT | $\mathbf{3}$ | $\mathbf{1}$ | $\mathbf{3}$ | GOD
Dot Product |  |  |  |  |  | Trident | $3$ | 1 | $3$ | Fair
BLAZE | $3\mathsf{n}$ | 1 | $3$ | Fair | FLASH | $6$ | 1 | $6$ | GOD
SWIFT | $\mathbf{3}$ | $\mathbf{1}$ | $\mathbf{3}$ | GOD | SWIFT | $\mathbf{3}$ | $\mathbf{1}$ | $\mathbf{3}$ | GOD
Dot Product with Truncation |  |  |  |  |  | Trident | $6$ | 1 | $3$ | Fair
BLAZE | $3\mathsf{n}+2$ | 1 | $3$ | Fair | FLASH | $8$ | 1 | $6$ | GOD
SWIFT | $\mathbf{15}$ | $\mathbf{1}$ | $\mathbf{3}$ | GOD | SWIFT | $\mathbf{4}$ | $\mathbf{1}$ | $\mathbf{3}$ | GOD
Bit Extraction |  |  |  |  |  | Trident | $\approx 8$ | $\log\ell+1$ | $\approx 7$ | Fair
BLAZE | 9 | $1+\log\ell$ | 9 | Fair | FLASH | $14$ | $\log\ell$ | $14$ | GOD
SWIFT | $\mathbf{9}$ | $\mathbf{1+\log\ell}$ | $\mathbf{9}$ | GOD | SWIFT | $\approx\mathbf{7}$ | $\mathbf{\log\ell}$ | $\approx\mathbf{7}$ | GOD
Bit to Arithmetic |  |  |  |  |  | Trident | $\approx 3$ | 1 | $3$ | Fair
BLAZE | $9$ | 1 | $4$ | Fair | FLASH | $6$ | 1 | $8$ | GOD
SWIFT | $\mathbf{9}$ | $\mathbf{1}$ | $\mathbf{4}$ | GOD | SWIFT | $\approx\mathbf{3}$ | $\mathbf{1}$ | $\mathbf{3}$ | GOD
Bit Injection |  |  |  |  |  | Trident | $\approx 6$ | 1 | $3$ | Fair
BLAZE | $12$ | 2 | $7$ | Fair | FLASH | $8$ | 2 | $10$ | GOD
SWIFT | $\mathbf{12}$ | $\mathbf{2}$ | $\mathbf{7}$ | GOD | SWIFT | $\approx\mathbf{6}$ | $\mathbf{1}$ | $\mathbf{3}$ | GOD

  * 1

– Notations: $\ell$ \- size of ring in bits, $\mathsf{n}$ \- size of vectors
for dot product.

Table 1: 3PC and 4PC: Comparison of SWIFT with its closest competitors in
terms of Communication and Round Complexity

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 [48]. We extend our 3PC
framework for 4 servers. In this regime, SWIFT is as fast as the best known
fair 4PC framework Trident [16] and twice faster than best known robust 4PC
framework FLASH [12]. We detail our contributions next.

##### Robust 3/4PC frameworks

The framework consists of a range of primitives realized in a privacy-
preserving way which is ensured via running computation in a secret-shared
fashion. We use secret-sharing over both $\mathbb{Z}_{2^{\ell}}$ and its
special instantiation $\mathbb{Z}_{2^{1}}$ and refer them as arithmetic and
respectively boolean sharing. Our framework consists of realizations for all
primitives needed for general MPC and PPML such as multiplication, dot-
product, truncation, bit extraction (given arithmetic sharing of a value
$\mathsf{v}$, this is used to generate boolean sharing of the most significant
bit ($\mathsf{msb}$) of the value), bit to arithmetic sharing conversion
(converts the boolean sharing of a single bit value to its arithmetic
sharing), bit injection (computes the arithmetic sharing of
$\mathsf{b}\cdot\mathsf{v}$, given the boolean sharing of a bit $\mathsf{b}$
and the arithmetic sharing of a ring element $\mathsf{v}$) and above all,
input sharing and output reconstruction in the SOC setting. A highlight of our
3PC framework, which, to the best of our knowledge is achieved for the first
time, is a robust dot-product protocol whose (amortized) communication cost is
independent of the vector size, which we obtain by extending the techniques of
[9, 10]. The performance comparison in terms of concrete cost for
communication and rounds, for PPML primitives in both 3PC and 4PC setting,
appear in Table 1. As claimed, SWIFT is on par with BLAZE for most of the
primitives (while improving security from fair to GOD) and is strictly better
than BLAZE in case of dot product and dot product with truncation. For 4PC,
SWIFT is on par with Trident in most cases (and is slightly better for dot
product with truncation and bit injection), while it is doubly faster than
FLASH. Since BLAZE outperforms the 3PC abort framework of ABY3 [43] while
Trident outperforms the known 4PC with abort [32], SWIFT attains robustness
with better cost than the know protocols with weaker guarantees. No
performance loss coupled with the strongest security guarantee makes our
robust framework an opt choice for practical applications including PPML.

##### Applications and Benchmarking

We demonstrate the practicality of our protocols by benchmarking PPML,
particularly, Logistic Regression (training and inference) and popular Neural
Networks (inference) such as [45], LeNet [38] and VGG16 [52] having millions
of parameters. The NN training requires mixed-world conversions [28, 43, 16],
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 [15, 48, 16, 12]).

##### New techniques and Comparisons with Prior Works

To begin with, we introduce a new primitive called Joint Message Passing
($\mathsf{jmp}$) that allows two servers to relay a common message to the
third server such that either the relay is successful or an honest server is
identified. The identified honest party enacts the role of a trusted third
party ($\mathsf{TTP}$) to take the computation to completion. $\mathsf{jmp}$
is extremely efficient as for a message of $\ell$ elements it only incurs the
minimal communication cost of $\ell$ elements (in an amortized sense). Without
any extra cost, it allows us to replace several pivotal private
communications, that may lead to abort, either because the malicious sender
does not send anything or sends a wrong message. All our primitives, either
for a general 3PC or a PPML task, achieve GOD relying on $\mathsf{jmp}$.

Second, instead of using the multiplication of [10] (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 [48], 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 [23] proposes a variant of
GOD in the 4PC setting, which is termed as private robustness. The authors of
[23] 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, [23] 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 [23] 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 [2]444Althought [23] states that the issue of private robustness
was identified and treated formally in [2], it is not clear whether [23]
achieves the FaF security of [2]. 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 [23] 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 [23] satisfying the FaF security
notion of [2] 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.

###  1.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.

##  2 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 [19].
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 [45, 43, 15, 16, 12, 48].

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.

For 3/4PC, the function to be computed is expressed as a circuit
$\mathsf{ckt}$, whose topology is public, and is evaluated over an arithmetic
ring $\mathbb{Z}_{2^{\ell}}$ or boolean ring $\mathbb{Z}_{2^{1}}$. For PPML,
we consider computation over the same algebraic structure. To deal with
floating-point values, we use Fixed-Point Arithmetic (FPA) [45, 43, 15, 12,
16, 48] representation in which 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 $x$ least significant bits
are reserved for the fractional part. The $\ell$-bit integer is then treated
as an element of $\mathbb{Z}_{2^{\ell}}$, and operations are performed modulo
$2^{\ell}$. We set $\ell=64,x=13$, leaving $\ell-x-1$ bits for the integer
part.

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
[50, 31, 3, 43, 15, 48, 10] for three server case and in [12, 16] 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.

######  Notation 2.1.

The $i^{th}$ element of a vector $\vec{\mathbf{x}}$ is denoted as
$\mathsf{x}_{i}$. The dot product of two $\mathsf{n}$ length vectors,
$\vec{\mathbf{x}}$ and $\vec{\mathbf{y}}$, is computed as
$\vec{\mathbf{x}}\odot\vec{\mathbf{y}}=\sum_{i=1}^{\mathsf{n}}\mathsf{x}_{i}\mathsf{y}_{i}$.
For two matrices $\mathbf{X},\mathbf{Y}$, the operation
$\mathbf{X}\circ\mathbf{Y}$ denotes the matrix multiplication. The bit in the
$i^{th}$ position of an $\ell$-bit value $\mathsf{v}$ is denoted by
$\mathsf{v}[i]$.

######  Notation 2.2.

For a bit $\mathsf{b}\in\\{0,1\\}$, we use $\mathsf{b}^{\sf R}$ to denote the
equivalent value of $\mathsf{b}$ over the ring $\mathbb{Z}_{2^{\ell}}$.
$\mathsf{b}^{\sf R}$ will have its least significant bit set to $\mathsf{b}$,
while all other bits will be set to zero.

##  3 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.

##### Secret Sharing Semantics

We use the following secret-sharing semantics.

  * $\circ$

$\left[\cdot\right]$-sharing: A value $\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$ is
$\left[\cdot\right]$-shared among $P_{1},P_{2}$, if $P_{s}$ for
$s\in\\{1,2\\}$ holds $\left[\mathsf{v}\right]_{s}\in\mathbb{Z}_{2^{\ell}}$
such that
$\mathsf{v}=\left[\mathsf{v}\right]_{1}+\left[\mathsf{v}\right]_{2}$.

  * $\circ$

$\langle\cdot\rangle$-sharing: A value $\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$ is
$\langle\cdot\rangle$-shared among $\mathcal{P}$, if

    * –

there exists
$\mathsf{v}_{0},\mathsf{v}_{1},\mathsf{v}_{2}\in\mathbb{Z}_{2^{\ell}}$ such
that $\mathsf{v}=\mathsf{v}_{0}+\mathsf{v}_{1}+\mathsf{v}_{2}$.

    * –

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

  * $\circ$

$\llbracket\cdot\rrbracket$-sharing: A value
$\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$ is $\llbracket\cdot\rrbracket$-shared
among $\mathcal{P}$, if

    * –

there exists $\alpha_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$ that is
$\left[\cdot\right]$-shared among $P_{1},P_{2}$.

    * –

there exists $\beta_{\mathsf{v}},\gamma_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$
such that $\beta_{\mathsf{v}}=\mathsf{v}+\alpha_{\mathsf{v}}$ and $P_{0}$
holds
$(\left[\alpha_{\mathsf{v}}\right]_{1},\left[\alpha_{\mathsf{v}}\right]_{2},\beta_{\mathsf{v}}+\gamma_{\mathsf{v}})$
while $P_{s}$ for $s\in\\{1,2\\}$ holds
$(\left[\alpha_{\mathsf{v}}\right]_{s},\beta_{\mathsf{v}},\gamma_{\mathsf{v}})$.

##### Arithmetic and Boolean Sharing

Arithmetic sharing refers to sharing over $\mathbb{Z}_{2^{\ell}}$ while
boolean sharing, denoted as $\llbracket\cdot\rrbracket^{\bf B}$, refers to
sharing over $\mathbb{Z}_{2^{1}}$.

##### Linearity of the Secret Sharing Scheme

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.

###  3.1 Joint Message Passing primitive

The $\mathsf{jmp}$ primitive allows two servers to relay a common message to
the third server such that either the relay is successful or an honest server
(or a conflicting pair) is identified. The striking feature of $\mathsf{jmp}$
is that it offers a rate-$1$ communication i.e. for a message of $\ell$
elements, it only incurs a communication of $\ell$ elements (in an amortized
sense). The task of $\mathsf{jmp}$ is captured in an ideal functionality (Fig.
1) and the protocol for the same appears in Fig. 2. Next, we give an overview.

Given two servers $P_{i},P_{j}$ possessing a common value
$\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$, protocol $\Pi_{\mathsf{jmp}}$ proceeds
as follows. First, $P_{i}$ sends $\mathsf{v}$ to $P_{k}$ while $P_{j}$ sends a
hash of $\mathsf{v}$ to $P_{k}$. The communication of the hash is done once
and for all from $P_{j}$ to $P_{k}$. In the simplest case, $P_{k}$ receives a
consistent (value, hash) pair, and the protocol terminates. In all other
cases, a $\mathsf{TTP}$ is identified as follows without having to communicate
$\mathsf{v}$ again. Importantly, the following part can be run once and for
all instances of $\Pi_{\mathsf{jmp}}$ with $P_{i},P_{j},P_{k}$ in the same
roles, invoked in the final 3PC protocol. Consequently, the cost relevant to
this part vanishes in an amortized sense, making the construction rate-1.

$\mathcal{F}_{\mathsf{jmp}}$ interacts with the servers in $\mathcal{P}$ and
the adversary $\mathcal{S}$.  Step 1: $\mathcal{F}_{\mathsf{jmp}}$ receives
$(\mathsf{Input},\mathsf{v}_{s})$ from $P_{s}$ for $s\in\\{i,j\\}$, while it
receives $(\mathsf{Select},\mathsf{ttp})$ from $\mathcal{S}$. Here
$\mathsf{ttp}$ denotes the server that $\mathcal{S}$ wants to choose as the
$\mathsf{TTP}$. Let $P^{\star}\in\mathcal{P}$ denote the server corrupted by
$\mathcal{S}$. Step 2: If $\mathsf{v}_{i}=\mathsf{v}_{j}$ and
$\mathsf{ttp}=\bot$, then set
$\mathsf{msg}_{i}=\mathsf{msg}_{j}=\bot,\mathsf{msg}_{k}=\mathsf{v}_{i}$ and
go to Step 5. Step 3: If $\mathsf{ttp}\in\mathcal{P}\setminus\\{P^{\star}\\}$,
then set $\mathsf{msg}_{i}=\mathsf{msg}_{j}=\mathsf{msg}_{k}=\mathsf{ttp}$.
Step 4: Else, $\mathsf{TTP}$ is set to be the honest server with smallest
index. Set $\mathsf{msg}_{i}=\mathsf{msg}_{j}=\mathsf{msg}_{k}=\mathsf{TTP}$
Step 5: Send $(\mathsf{Output},\mathsf{msg}_{s})$ to $P_{s}$ for
$s\in\\{0,1,2\\}$.

Figure 1: 3PC: Ideal functionality for $\mathsf{jmp}$ primitive

Each $P_{s}$ for $s\in\\{i,j,k\\}$ maintains a bit $\mathsf{b}_{s}$
initialized to $0$, 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;555hash 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.

######  Notation 3.1.

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})$.

Each server $P_{s}$ for $s\in\\{i,j,k\\}$ initializes bit $\mathsf{b}_{s}=0$.
Send Phase: $P_{i}$ sends $\mathsf{v}$ to $P_{k}$. Verify Phase: $P_{j}$ sends
$\mathsf{H}(\mathsf{v})$ to $P_{k}$. – $P_{k}$ broadcasts "(accuse,$P_{i}$)",
if $P_{i}$ is silent and $\mathsf{TTP}$ = $P_{j}$. Analogously for $P_{j}$. If
$P_{k}$ accuses both $P_{i},P_{j}$, then $\mathsf{TTP}$ = $P_{i}$. Otherwise,
$P_{k}$ receives some $\tilde{}\mathsf{v}$ and either sets $\mathsf{b}_{k}=0$
when the value and the hash are consistent or sets $\mathsf{b}_{k}=1$. $P_{k}$
then sends $\mathsf{b}_{k}$ to $P_{i},P_{j}$ and terminates if
$\mathsf{b}_{k}=0$. – If $P_{i}$ does not receive a bit from $P_{k}$, it
broadcasts "(accuse,$P_{k}$)" and $\mathsf{TTP}$ = $P_{j}$. Analogously for
$P_{j}$. If both $P_{i},P_{j}$ accuse $P_{k}$, then $\mathsf{TTP}$ = $P_{i}$.
Otherwise, $P_{s}$ for $s\in\\{i,j\\}$ sets $\mathsf{b}_{s}=\mathsf{b}_{k}$. –
$P_{i},P_{j}$ exchange their bits to each other. If $P_{i}$ does not receive
$\mathsf{b}_{j}$ from $P_{j}$, it broadcasts "(accuse,$P_{j}$)" and
$\mathsf{TTP}$ = $P_{k}$. Analogously for $P_{j}$. Otherwise, $P_{i}$ resets
its bit to $\mathsf{b}_{i}\vee\mathsf{b}_{j}$ and likewise $P_{j}$ resets its
bit to $\mathsf{b}_{j}\vee\mathsf{b}_{i}$. – $P_{s}$ for $s\in\\{i,j,k\\}$
broadcasts $\mathsf{H}_{s}=\mathsf{H}(\mathsf{v}^{*})$ if $b_{s}=1$, where
$\mathsf{v}^{*}=\mathsf{v}$ for $s\in\\{i,j\\}$ and
$\mathsf{v}^{*}=\tilde{}\mathsf{v}$ otherwise. If $P_{k}$ does not broadcast,
terminate. If either $P_{i}$ or $P_{j}$ does not broadcast, then
$\mathsf{TTP}$ = $P_{k}$. Otherwise, $\bullet$ If
$\mathsf{H}_{i}\neq\mathsf{H}_{j}$: $\mathsf{TTP}$ = $P_{k}$. $\bullet$ Else
if $\mathsf{H}_{i}\neq\mathsf{H}_{k}$: $\mathsf{TTP}$ = $P_{j}$. $\bullet$
Else if $\mathsf{H}_{i}=\mathsf{H}_{j}=\mathsf{H}_{k}$: $\mathsf{TTP}$ =
$P_{i}$.

Figure 2: 3PC: Joint Message Passing Protocol

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.

######  Lemma 3.2 (Communication).

Protocol $\Pi_{\mathsf{jmp}}$ (Fig. 2) requires $1$ round and an amortized
communication of $\ell$ bits overall.

###### Proof.

Server $P_{i}$ sends value $\mathsf{v}$ to $P_{k}$ while $P_{j}$ sends hash of
the same to $P_{k}$. This accounts for one round and communication of $\ell$
bits. $P_{k}$ then sends back its inconsistency bit to $P_{i},P_{j}$, who then
exchange it; this takes another two rounds. This is followed by servers
broadcasting hashes on their values and selecting a $\mathsf{TTP}$ based on
it, which takes one more round. All except the first round can be combined for
several instances of $\Pi_{\mathsf{jmp}}$ protocol and hence the cost gets
amortized. ∎

###  3.2 3PC Protocols

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

##### Sharing Protocol

Protocol $\Pi_{\mathsf{sh}}$ (Fig. 3) allows a server $P_{i}$ to generate
$\llbracket\cdot\rrbracket$-shares of a value
$\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$. In the preprocessing phase,
$P_{0},P_{j}$ for $j\in\\{1,2\\}$ along with $P_{i}$ sample a random
$\left[\alpha_{\mathsf{v}}\right]_{j}\in\mathbb{Z}_{2^{\ell}}$, while
$P_{1},P_{2},P_{i}$ sample random
$\gamma_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$. This allows $P_{i}$ to know
both $\alpha_{\mathsf{v}}$ and $\gamma_{\mathsf{v}}$ in clear. During the
online phase, if $P_{i}=P_{0}$, then $P_{0}$ sends
$\beta_{\mathsf{v}}=\mathsf{v}+\alpha_{\mathsf{v}}$ to $P_{1}$. $P_{0},P_{1}$
then $\mathsf{jmp\mbox{-}send}$ $\beta_{\mathsf{v}}$ to $P_{2}$ to complete
the secret sharing. If $P_{i}=P_{1}$, $P_{1}$ sends
$\beta_{\mathsf{v}}=\mathsf{v}+\alpha_{\mathsf{v}}$ to $P_{2}$. Then
$P_{1},P_{2}$ $\mathsf{jmp\mbox{-}send}$
$\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}$ to $P_{0}$. The case for
$P_{i}=P_{2}$ proceeds similar to that of $P_{1}$. The correctness of the
shares held by each server is assured by the guarantees of
$\Pi_{\mathsf{jmp}}$.

Preprocessing: – If $P_{i}=P_{0}$ : $P_{0},P_{j}$, for $j\in\\{1,2\\}$,
together sample random
$\left[\alpha_{\mathsf{v}}\right]_{j}\in\mathbb{Z}_{2^{\ell}}$, while
$\mathcal{P}$ together sample random
$\gamma_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$. – If $P_{i}=P_{1}$ :
$P_{0},P_{1}$ together sample random
$\left[\alpha_{\mathsf{v}}\right]_{1}\in\mathbb{Z}_{2^{\ell}}$, while
$\mathcal{P}$ together sample a random
$\left[\alpha_{\mathsf{v}}\right]_{2}\in\mathbb{Z}_{2^{\ell}}$. Also,
$P_{1},P_{2}$ together sample random
$\gamma_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$. – If $P_{i}=P_{2}$: Symmetric
to the case when $P_{i}=P_{1}$. Online: – If $P_{i}=P_{0}$ : $P_{0}$ computes
$\beta_{\mathsf{v}}=\mathsf{v}+\alpha_{\mathsf{v}}$ and sends
$\beta_{\mathsf{v}}$ to $P_{1}$. $P_{1},P_{0}$ $\mathsf{jmp\mbox{-}send}$
$\beta_{\mathsf{v}}$ to $P_{2}$. – If $P_{i}=P_{j}$, for $j\in\\{1,2\\}$ :
$P_{j}$ computes $\beta_{\mathsf{v}}=\mathsf{v}+\alpha_{\mathsf{v}}$, sends
$\beta_{\mathsf{v}}$ to $P_{3-j}$. $P_{1},P_{2}$ $\mathsf{jmp\mbox{-}send}$
$\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}$ to $P_{0}$.

Figure 3: 3PC: Generating $\llbracket\mathsf{v}\rrbracket$-shares by server
$P_{i}$

######  Lemma 3.3 (Communication).

Protocol $\Pi_{\mathsf{sh}}$ (Fig. 3) is non-interactive in the preprocessing
phase and requires $2$ rounds and an amortized communication of $2\ell$ bits
in the online phase.

###### Proof.

During the preprocessing phase, servers non-interactively sample the
$\left[\cdot\right]$-shares of $\alpha_{\mathsf{v}}$ and $\gamma_{\mathsf{v}}$
values using the shared key setup. In the online phase, when $P_{i}=P_{0}$, it
computes $\beta_{\mathsf{v}}$ and sends it to $P_{1}$, resulting in one round
and $\ell$ bits communicated. They then $\mathsf{jmp\mbox{-}send}$
$\beta_{\mathsf{v}}$ to $P_{2}$, which requires additional one round in an
amortized sense, and $\ell$ bits to be communicated. For the case when
$P_{i}=P_{1}$, it sends $\beta_{\mathsf{v}}$ to $P_{2}$, resulting in one
round and a communication of $\ell$ bits. Then, $P_{1},P_{2}$
$\mathsf{jmp\mbox{-}send}$ $\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}$ to
$P_{0}$. This again requires an additional one round and $\ell$ bits. The
analysis is similar in the case of $P_{i}=P_{2}$. ∎

##### Joint Sharing Protocol

Protocol $\Pi_{\mathsf{jsh}}$ (Fig. 4) allows two servers $P_{i},P_{j}$ to
jointly generate a $\llbracket\cdot\rrbracket$-sharing of a value
$\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$ that is known to both. Towards this,
servers execute the preprocessing of $\Pi_{\mathsf{sh}}$ (Fig. 3) to generate
$\left[\alpha_{\mathsf{v}}\right]$ and $\gamma_{\mathsf{v}}$. If
$(P_{i},P_{j})=(P_{1},P_{0})$, then $P_{1},P_{0}$ $\mathsf{jmp\mbox{-}send}$
$\beta_{\mathsf{v}}=\mathsf{v}+\alpha_{\mathsf{v}}$ to $P_{2}$. The case when
$(P_{i},P_{j})=(P_{2},P_{0})$ proceeds similarly. The case for
$(P_{i},P_{j})=(P_{1},P_{2})$ is optimized further as follows: servers locally
set
$\left[\alpha_{\mathsf{v}}\right]_{1}=\left[\alpha_{\mathsf{v}}\right]_{2}=0$.
$P_{1},P_{2}$ together sample random
$\gamma_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$, set
$\beta_{\mathsf{v}}=\mathsf{v}$ and $\mathsf{jmp\mbox{-}send}$
$\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}$ to $P_{0}$.

Preprocessing: – If $(P_{i},P_{j})=(P_{1},P_{0})$: Servers execute the
preprocessing of $\Pi_{\mathsf{sh}}(P_{1},\mathsf{v})$ and then locally set
$\gamma_{\mathsf{v}}=0$. – If $(P_{i},P_{j})=(P_{2},P_{0})$: Similar to the
case above. – If $(P_{i},P_{j})=(P_{1},P_{2})$: $P_{1},P_{2}$ together sample
random $\gamma_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$. Servers locally set
$\left[\alpha_{\mathsf{v}}\right]_{1}=\left[\alpha_{\mathsf{v}}\right]_{2}=0$.
Online: – If $(P_{i},P_{j})=(P_{1},P_{0})$: $P_{0},P_{1}$ compute
$\beta_{\mathsf{v}}=\mathsf{v}+\left[\alpha_{\mathsf{v}}\right]_{1}+\left[\alpha_{\mathsf{v}}\right]_{2}$.
$P_{0},P_{1}$ $\mathsf{jmp\mbox{-}send}$ $\beta_{\mathsf{v}}$ to $P_{2}$. – If
$(P_{i},P_{j})=(P_{2},P_{0})$: Similar to the case above. – If
$(P_{i},P_{j})=(P_{1},P_{2})$: $P_{1},P_{2}$ locally set
$\beta_{\mathsf{v}}=\mathsf{v}$. $P_{1},P_{2}$ $\mathsf{jmp\mbox{-}send}$
$\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}$ to $P_{0}$.

Figure 4: 3PC: $\llbracket\cdot\rrbracket$-sharing of a value
$\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$ jointly by $P_{i},P_{j}$

When the value $\mathsf{v}$ is available to both $P_{i},P_{j}$ in the
preprocessing phase, protocol $\Pi_{\mathsf{jsh}}$ can be made non-interactive
in the following way: $\mathcal{P}$ sample a random
$\mathsf{r}\in\mathbb{Z}_{2^{\ell}}$ and locally set their share according to
Table 2.

| $(P_{1},P_{2})$ | $(P_{1},P_{0})$ | $(P_{2},P_{0})$
---|---|---|---
| $\begin{aligned} \left[\alpha_{\mathsf{v}}\right]_{1}=0,&~{}\left[\alpha_{\mathsf{v}}\right]_{2}=0\\\ \beta_{\mathsf{v}}=\mathsf{v},&~{}\gamma_{\mathsf{v}}=\mathsf{r}-\mathsf{v}\end{aligned}$ | $\begin{aligned} \left[\alpha_{\mathsf{v}}\right]_{1}=-\mathsf{v},&~{}\left[\alpha_{\mathsf{v}}\right]_{2}=0\\\ \beta_{\mathsf{v}}=0,&~{}\gamma_{\mathsf{v}}=\mathsf{r}\end{aligned}$ | $\begin{aligned} \left[\alpha_{\mathsf{v}}\right]_{1}=0,&~{}\left[\alpha_{\mathsf{v}}\right]_{2}=-\mathsf{v}\\\ \beta_{\mathsf{v}}=0,&~{}\gamma_{\mathsf{v}}=\mathsf{r}\end{aligned}$
$\begin{aligned} P_{0}\\\ P_{1}\\\ P_{2}\end{aligned}$ | $\begin{aligned} (0,~{}0,~{}\mathsf{r}~{}~{}~{}~{}~{})\\\ (0,~{}\mathsf{v},~{}\mathsf{r}-\mathsf{v})\\\ (0,~{}\mathsf{v},~{}\mathsf{r}-\mathsf{v})\end{aligned}$ | $\begin{aligned} (-\mathsf{v},~{}0,~{}\mathsf{r})\\\ (-\mathsf{v},~{}0,~{}\mathsf{r})\\\ (~{}~{}0,~{}0,~{}\mathsf{r})\end{aligned}$ | $\begin{aligned} (0,~{}-\mathsf{v},~{}\mathsf{r})\\\ (0,~{}~{}~{}~{}0,~{}\mathsf{r})\\\ (0,~{}-\mathsf{v},~{}\mathsf{r})\end{aligned}$

Table 2: The columns depict the three distinct possibility of input
contributing pairs. The first row shows the assignment to various components
of the sharing. The last row, along with three sub-rows, specify the shares
held by the three servers.

######  Lemma 3.4 (Communication).

Protocol $\Pi_{\mathsf{jsh}}$ (Fig. 4) is non-interactive in the preprocessing
phase and requires $1$ round and an amortized communication of $\ell$ bits in
the online phase.

###### Proof.

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). ∎

##### Addition Protocol

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

##### Multiplication Protocol

Protocol
$\Pi_{\mathsf{mult}}(\mathcal{P},\llbracket\mathsf{x}\rrbracket,\llbracket\mathsf{y}\rrbracket)$
(Fig. 5) enables the servers in $\mathcal{P}$ to compute
$\llbracket\cdot\rrbracket$-sharing of $\mathsf{z}=\mathsf{x}\mathsf{y}$,
given the $\llbracket\cdot\rrbracket$-sharing of $\mathsf{x}$ and
$\mathsf{y}$. We build on the protocol of BLAZE [48] and discuss along the way
the differences and resemblances. We begin with a protocol for the semi-honest
setting, which is also the starting point of BLAZE. During the preprocessing
phase, $P_{0},P_{j}$ for $j\in\\{1,2\\}$ sample random
$\left[\alpha_{\mathsf{z}}\right]_{j}\in\mathbb{Z}_{2^{\ell}}$, while
$P_{1},P_{2}$ sample random $\gamma_{\mathsf{z}}\in\mathbb{Z}_{2^{\ell}}$. In
addition, $P_{0}$ locally computes
$\Gamma_{\mathsf{x}\mathsf{y}}=\alpha_{\mathsf{x}}\alpha_{\mathsf{y}}$ and
generates $\left[\cdot\right]$-sharing of the same between $P_{1},P_{2}$.
Since,

$\displaystyle\beta_{\mathsf{z}}$
$\displaystyle=\mathsf{z}+\alpha_{\mathsf{z}}=\mathsf{x}\mathsf{y}+\alpha_{\mathsf{z}}=(\beta_{\mathsf{x}}-\alpha_{\mathsf{x}})(\beta_{\mathsf{y}}-\alpha_{\mathsf{y}})+\alpha_{\mathsf{z}}$
$\displaystyle=\beta_{\mathsf{x}}\beta_{\mathsf{y}}-\beta_{x}\alpha_{\mathsf{y}}-\beta_{y}\alpha_{\mathsf{x}}+\Gamma_{\mathsf{x}\mathsf{y}}+\alpha_{\mathsf{z}}$
(1)

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:

  1. 1)

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

  2. 2)

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

  3. 3)

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:

$\displaystyle\mathsf{\beta}_{\mathsf{z}}^{\star}$
$\displaystyle=-(\beta_{\mathsf{x}}+\gamma_{\mathsf{x}})\alpha_{\mathsf{y}}-(\beta_{\mathsf{y}}+\gamma_{\mathsf{y}})\alpha_{\mathsf{x}}+2\Gamma_{\mathsf{x}\mathsf{y}}+\alpha_{\mathsf{z}}$
$\displaystyle=(-\beta_{\mathsf{x}}\alpha_{\mathsf{y}}-\beta_{\mathsf{y}}\alpha_{\mathsf{x}}+\Gamma_{\mathsf{x}\mathsf{y}}+\alpha_{\mathsf{z}})-(\gamma_{\mathsf{x}}\alpha_{\mathsf{y}}+\gamma_{\mathsf{y}}\alpha_{\mathsf{x}}-\Gamma_{\mathsf{x}\mathsf{y}})$
$\displaystyle=(\beta_{\mathsf{z}}-\beta_{\mathsf{x}}\beta_{\mathsf{y}})-(\gamma_{\mathsf{x}}\alpha_{\mathsf{y}}+\gamma_{\mathsf{y}}\alpha_{\mathsf{x}}-\Gamma_{\mathsf{x}\mathsf{y}})\hskip
23.0pt[\text{by Eq. \ref{eq:betaz}}]$
$\displaystyle=(\beta_{\mathsf{z}}-\beta_{\mathsf{x}}\beta_{\mathsf{y}})-\chi\hskip
13.0pt[\text{where
}\chi=\gamma_{\mathsf{x}}\alpha_{\mathsf{y}}+\gamma_{\mathsf{y}}\alpha_{\mathsf{x}}-\Gamma_{\mathsf{x}\mathsf{y}}]$

Now if $\chi$ can be made available to $P_{0}$, it can send
$\mathsf{\beta}_{\mathsf{z}}^{\star}+\chi$ to $P_{1}$ and $P_{2}$ who using
the knowledge of $\beta_{\mathsf{x}},\beta_{\mathsf{y}}$, can verify the
correctness of $\beta_{\mathsf{z}}$ by computing
$\beta_{\mathsf{z}}-\beta_{\mathsf{x}}\beta_{\mathsf{y}}$ and checking against
the value $\mathsf{\beta}_{\mathsf{z}}^{\star}+\chi$ received from $P_{0}$.
However, disclosing $\chi$ on clear to $P_{0}$ will cause a privacy issue when
$P_{0}$ is corrupt, because one degree of freedom on the pair
$(\gamma_{\mathsf{x}},\gamma_{\mathsf{y}})$ is lost and the same impact
percolates down to $(\beta_{\mathsf{x}},\beta_{\mathsf{y}})$ and further to
the actual values $(\mathsf{v}_{\mathsf{x}},\mathsf{v}_{\mathsf{y}})$ on the
wires $\mathsf{x},\mathsf{y}$. This is resolved through a random value
$\psi\in\mathbb{Z}_{2^{\ell}}$, sampled together by $P_{1}$ and $P_{2}$. Now,
$\chi$ and $\mathsf{\beta}_{\mathsf{z}}^{\star}$ are set to
$\gamma_{\mathsf{x}}\alpha_{\mathsf{y}}+\gamma_{\mathsf{y}}\alpha_{\mathsf{x}}-\Gamma_{\mathsf{x}\mathsf{y}}+\psi$,
$(\beta_{\mathsf{z}}-\beta_{\mathsf{x}}\beta_{\mathsf{y}}+\psi)-\chi$,
respectively and the check by $P_{1},P_{2}$ involves computing
$\beta_{\mathsf{z}}-\beta_{\mathsf{x}}\beta_{\mathsf{y}}+\psi$. The rest of
the logic in BLAZE goes on to discuss how to enforce $P_{0}$– (a) to compute a
correct $\chi$ (when honest), and (b) to share correct
$\Gamma_{\mathsf{x}\mathsf{y}}$ (when corrupt). Tying the ends together, they
identify the precise shared multiplication triple and map its components to
$\chi$ and $\Gamma_{\mathsf{x}\mathsf{y}}$ so that these values are correct by
virtue of the correctness of the product relation. This reduces ensuring the
correctness of these values to doing a single multiplication of two values in
the preprocessing phase.

Preprocessing: – $P_{0},P_{j}$ for $j\in\\{1,2\\}$ together sample random
$\left[\alpha_{\mathsf{z}}\right]_{j}\in\mathbb{Z}_{2^{\ell}}$, while
$P_{1},P_{2}$ sample random $\gamma_{\mathsf{z}}\in\mathbb{Z}_{2^{\ell}}$. –
Servers in $\mathcal{P}$ locally compute $\langle\cdot\rangle$-sharing of
$\mathsf{d}=\gamma_{\mathsf{x}}+\alpha_{\mathsf{x}}$ and
$\mathsf{e}=\gamma_{\mathsf{y}}+\alpha_{\mathsf{y}}$ by setting the shares as
follows (ref. Table 3):
$(\mathsf{d}_{0}\text{=}\left[\alpha_{\mathsf{x}}\right]_{2},\mathsf{d}_{1}\text{=}\left[\alpha_{\mathsf{x}}\right]_{1},\mathsf{d}_{2}\text{=}\gamma_{\mathsf{x}}),~{}~{}(\mathsf{e}_{0}\text{=}\left[\alpha_{\mathsf{y}}\right]_{2},\mathsf{e}_{1}\text{=}\left[\alpha_{\mathsf{y}}\right]_{1},\mathsf{e}_{2}\text{=}\gamma_{\mathsf{y}})$
– Servers in $\mathcal{P}$ execute
$\Pi_{\mathsf{mulPre}}(\mathcal{P},\mathsf{d},\mathsf{e})$ to generate
$\langle\mathsf{f}\rangle=\langle\mathsf{d}\mathsf{e}\rangle$. – $P_{0},P_{1}$
locally set $\left[\chi\right]_{1}=\mathsf{f}_{1}$, while $P_{0},P_{2}$
locally set $\left[\chi\right]_{2}=\mathsf{f}_{0}$. $P_{1},P_{2}$ locally
compute $\psi=\mathsf{f}_{2}-\gamma_{\mathsf{x}}\gamma_{\mathsf{y}}$. Online:
– $P_{0},P_{j}$, for $j\in\\{1,2\\}$, compute
$\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{j}=-(\beta_{\mathsf{x}}+\gamma_{\mathsf{x}})\left[\alpha_{\mathsf{y}}\right]_{j}-(\beta_{\mathsf{y}}+\gamma_{\mathsf{y}})\left[\alpha_{\mathsf{x}}\right]_{j}+\left[\alpha_{\mathsf{z}}\right]_{j}+\left[\chi\right]_{j}$.
– $P_{0},P_{1}$ $\mathsf{jmp\mbox{-}send}$
$\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{1}$ to $P_{2}$ and
$P_{0},P_{2}$ $\mathsf{jmp\mbox{-}send}$
$\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{2}$ to $P_{1}$. –
$P_{1},P_{2}$ compute
$\mathsf{\beta}_{\mathsf{z}}^{\star}=\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{1}+\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{2}$
and set
$\beta_{\mathsf{z}}=\mathsf{\beta}_{\mathsf{z}}^{\star}+\beta_{\mathsf{x}}\beta_{\mathsf{y}}+\psi$.
– $P_{1},P_{2}$ $\mathsf{jmp\mbox{-}send}$
$\beta_{\mathsf{z}}+\gamma_{\mathsf{z}}$ to $P_{0}$.

Figure 5: 3PC: Multiplication Protocol
($\mathsf{z}=\mathsf{x}\cdot\mathsf{y}$)

We differ from BLAZE in several ways. First, we do not simply rely on $P_{0}$
for the verification information $\mathsf{\beta}_{\mathsf{z}}^{\star}+\chi$,
as this may inevitably lead to abort when $P_{0}$ is corrupt. Instead, we find
(a slightly different) $\mathsf{\beta}_{\mathsf{z}}^{\star}$ that, instead of
entirely available to $P_{0}$, will be available in
$\left[\cdot\right]$-shared form between the two teams
$\\{P_{0},P_{1}\\},\\{P_{0},P_{2}\\}$, with both servers in
$\\{P_{0},P_{i}\\}$ holding $i$th share
$\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{i}$. With this edit, the
$i$th team can $\mathsf{jmp\mbox{-}send}$ the $i$th share of
$\mathsf{\beta}_{\mathsf{z}}^{\star}$ to the third server which computes
$\mathsf{\beta}_{\mathsf{z}}^{\star}$. Due to the presence of one honest
server in each team, this $\mathsf{\beta}_{\mathsf{z}}^{\star}$ is correct and
$P_{1},P_{2}$ directly use it to compute $\beta_{\mathsf{z}}$, with the
knowledge of $\psi,\beta_{\mathsf{x}},\beta_{\mathsf{y}}$. The outcome of our
approach is a win-win situation i.e. either success or $\mathsf{TTP}$
selection. Our approach of computing $\beta_{\mathsf{z}}$ from
$\mathsf{\beta}_{\mathsf{z}}^{\star}$ is a departure from BLAZE, where the
latter suggests computing $\beta_{\mathsf{z}}$ from the exchange
$P_{1},P_{2}$’s respective share of $\beta_{\mathsf{z}}$ (as in the semi-
honest construction) and use $\mathsf{\beta}_{\mathsf{z}}^{\star}$ for
verification. Our new $\mathsf{\beta}_{\mathsf{z}}^{\star}$ and $\chi$ are:

$\displaystyle\chi$
$\displaystyle=\gamma_{\mathsf{x}}\alpha_{\mathsf{y}}+\gamma_{\mathsf{y}}\alpha_{\mathsf{x}}+\Gamma_{\mathsf{x}\mathsf{y}}-\psi\hskip
8.53581pt\text{and}$ $\displaystyle\mathsf{\beta}_{\mathsf{z}}^{\star}$
$\displaystyle=-(\beta_{\mathsf{x}}+\gamma_{\mathsf{x}})\alpha_{\mathsf{y}}-(\beta_{\mathsf{y}}+\gamma_{\mathsf{y}})\alpha_{\mathsf{x}}+\alpha_{\mathsf{z}}+\chi$
$\displaystyle=(-\beta_{\mathsf{x}}\alpha_{\mathsf{y}}-\beta_{\mathsf{y}}\alpha_{\mathsf{x}}+\Gamma_{\mathsf{x}\mathsf{y}}+\alpha_{\mathsf{z}})-\psi=\beta_{\mathsf{z}}-\beta_{\mathsf{x}}\beta_{\mathsf{y}}-\psi$

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,

$\displaystyle\mathsf{d}\mathsf{e}$
$\displaystyle=(\gamma_{\mathsf{x}}+\alpha_{\mathsf{x}})(\gamma_{\mathsf{y}}+\alpha_{\mathsf{y}})=\gamma_{\mathsf{x}}\gamma_{\mathsf{y}}+\gamma_{\mathsf{x}}\alpha_{\mathsf{y}}+\gamma_{\mathsf{y}}\alpha_{\mathsf{x}}+\Gamma_{\mathsf{x}\mathsf{y}}$
$\displaystyle=(\gamma_{\mathsf{x}}\gamma_{\mathsf{y}}+\psi)+(\gamma_{\mathsf{x}}\alpha_{\mathsf{y}}+\gamma_{\mathsf{y}}\alpha_{\mathsf{x}}+\Gamma_{\mathsf{x}\mathsf{y}}-\psi)$
$\displaystyle=(\gamma_{\mathsf{x}}\gamma_{\mathsf{y}}+\psi)+\chi=\mathsf{f}$

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 [10] 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.

| $P_{0}$ | $P_{1}$ | $P_{2}$
---|---|---|---
$\langle\mathsf{v}\rangle$ | $(\mathsf{v}_{0},\mathsf{v}_{1})$ | $(\mathsf{v}_{1},\mathsf{v}_{2})$ | $(\mathsf{v}_{2},\mathsf{v}_{0})$
$\langle\mathsf{d}\rangle$ | $(\left[\alpha_{\mathsf{x}}\right]_{2},\left[\alpha_{\mathsf{x}}\right]_{1})$ | $(\left[\alpha_{\mathsf{x}}\right]_{1},\gamma_{\mathsf{x}})$ | $(\gamma_{\mathsf{x}},\left[\alpha_{\mathsf{x}}\right]_{2})$
$\langle\mathsf{e}\rangle$ | $(\left[\alpha_{\mathsf{y}}\right]_{2},\left[\alpha_{\mathsf{y}}\right]_{1})$ | $(\left[\alpha_{\mathsf{y}}\right]_{1},\gamma_{\mathsf{y}})$ | $(\gamma_{\mathsf{y}},\left[\alpha_{\mathsf{y}}\right]_{2})$
Table 3: The $\langle\cdot\rangle$-sharing of values $\mathsf{d}$ and
$\mathsf{e}$

$\left[\chi\right]_{2}\leftarrow\mathsf{f}_{0},~{}~{}\left[\chi\right]_{1}\leftarrow\mathsf{f}_{1},~{}~{}\gamma_{\mathsf{x}}\gamma_{\mathsf{y}}+\psi\leftarrow\mathsf{f}_{2}.$
(2)

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 [10] 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.

$\mathcal{F}_{\mathsf{MulPre}}$ interacts with the servers in $\mathcal{P}$
and the adversary $\mathcal{S}$. $\mathcal{F}_{\mathsf{MulPre}}$ receives
$\langle\cdot\rangle$-shares of $\mathsf{d},\mathsf{e}$ from the servers where
$P_{s}$, for $s\in\\{0,1,2\\}$, holds
$\langle\mathsf{d}\rangle_{s}=(\mathsf{d}_{s},\mathsf{d}_{(s+1)\%3})$ and
$\langle\mathsf{e}\rangle_{s}=(\mathsf{e}_{s},\mathsf{e}_{(s+1)\%3})$ such
that $\mathsf{d}=\mathsf{d}_{0}+\mathsf{d}_{1}+\mathsf{d}_{2}$ and
$\mathsf{e}=\mathsf{e}_{0}+\mathsf{e}_{1}+\mathsf{e}_{2}$. Let $P_{i}$ denotes
the server corrupted by $\mathcal{S}$. $\mathcal{F}_{\mathsf{MulPre}}$
receives $\langle\mathsf{f}\rangle_{i}=(\mathsf{f}_{i},\mathsf{f}_{(i+1)\%3})$
from $\mathcal{S}$ where $\mathsf{f}=\mathsf{d}\mathsf{e}$.
$\mathcal{F}_{\mathsf{MulPre}}$ proceeds as follows:  – Reconstructs
$\mathsf{d},\mathsf{e}$ using the shares received from honest servers and
compute $\mathsf{f}=\mathsf{d}\mathsf{e}$. – Compute
$\mathsf{f}_{(i+2)\%3}=\mathsf{f}-\mathsf{f}_{i}-\mathsf{f}_{(i+1)\%3}$ and
set the output shares as
$\langle\mathsf{f}\rangle_{0}=(\mathsf{f}_{0},\mathsf{f}_{1}),\langle\mathsf{f}\rangle_{1}=(\mathsf{f}_{1},\mathsf{f}_{2}),\langle\mathsf{f}\rangle_{2}=(\mathsf{f}_{2},\mathsf{f}_{0})$.
– Send $(\mathsf{Output},\langle\mathsf{f}\rangle_{s})$ to server
$P_{s}\in\mathcal{P}$.

Figure 6: 3PC: Ideal functionality for $\Pi_{\mathsf{mulPre}}$ protocol

######  Lemma 3.5 (Communication).

Protocol $\Pi_{\mathsf{mult}}$ (Fig. 5) requires an amortized cost of $3\ell$
bits in the preprocessing phase, and $1$ round and amortized cost of $3\ell$
bits in the online phase.

###### Proof.

In the preprocessing phase, generation of $\alpha_{\mathsf{z}}$ and
$\gamma_{\mathsf{z}}$ are non-interactive. This is followed by one execution
of $\Pi_{\mathsf{mulPre}}$, which requires an amortized communication cost of
$3\ell$ bits. During the online phase, $P_{0},P_{1}$
$\mathsf{jmp\mbox{-}send}$
$\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{1}$ to $P_{2}$, while
$P_{0},P_{2}$ $\mathsf{jmp\mbox{-}send}$
$\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{2}$ to $P_{1}$. This
requires one round and a communication of $2\ell$ bits. Following this,
$P_{1},P_{2}$ $\mathsf{jmp\mbox{-}send}$
$\beta_{\mathsf{z}}+\gamma_{\mathsf{z}}$ to $P_{0}$, which requires one round
and a communication of $\ell$ bits. However, $\mathsf{jmp\mbox{-}send}$ of
$\beta_{\mathsf{z}}+\gamma_{\mathsf{z}}$ can be delayed till the end of the
protocol, and will require only one round for the entire circuit and can be
amortized. ∎

##### Reconstruction Protocol

Protocol $\Pi_{\mathsf{rec}}$ (Fig. 7) allows servers to robustly reconstruct
value $\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$ from its
$\llbracket\cdot\rrbracket$-shares. Note that each server misses one share of
$\mathsf{v}$ which is held by the other two servers. Consider the case of
$P_{0}$ who requires $\gamma_{\mathsf{v}}$ to compute $\mathsf{v}$. During the
preprocessing, $P_{1},P_{2}$ compute a commitment of $\gamma_{\mathsf{v}}$,
denoted by $\mathsf{Com}(\gamma_{\mathsf{v}})$ and $\mathsf{jmp\mbox{-}send}$
the same to $P_{0}$. Similar steps are performed for the values
$\left[\alpha_{\mathsf{v}}\right]_{2}$ and
$\left[\alpha_{\mathsf{v}}\right]_{1}$ that are required by servers $P_{1}$
and $P_{2}$ respectively. During the online phase, servers open their
commitments to the intended server who accepts the opening that is consistent
with the agreed upon commitment.

Preprocessing: – $P_{0},P_{j}$, for $j\in\\{1,2\\}$, compute
$\mathsf{Com}(\left[\alpha_{\mathsf{v}}\right]_{j})$, while $P_{1},P_{2}$
compute $\mathsf{Com}(\gamma_{\mathsf{v}})$. – $P_{1},P_{2}$
$\mathsf{jmp\mbox{-}send}$ $\mathsf{Com}(\gamma_{\mathsf{v}})$ to $P_{0}$,
while $P_{0},P_{1}$ $\mathsf{jmp\mbox{-}send}$
$\mathsf{Com}(\left[\alpha_{\mathsf{v}}\right]_{1})$ to $P_{2}$, and
$P_{0},P_{2}$ $\mathsf{jmp\mbox{-}send}$
$\mathsf{Com}(\left[\alpha_{\mathsf{v}}\right]_{2})$ to $P_{1}$, Online: –
$P_{0},P_{1}$ open $\mathsf{Com}(\left[\alpha_{\mathsf{v}}\right]_{1})$ to
$P_{2}$. $P_{0},P_{2}$ open
$\mathsf{Com}(\left[\alpha_{\mathsf{v}}\right]_{2})$ to $P_{1}$. $P_{1},P_{2}$
open $\mathsf{Com}(\gamma_{\mathsf{v}})$ to $P_{0}$. – Each server accepts the
opening that is consistent with the agreed upon commitment. $P_{1},P_{2}$
compute
$\mathsf{v}=\beta_{\mathsf{v}}-\left[\alpha_{\mathsf{v}}\right]_{1}-\left[\alpha_{\mathsf{v}}\right]_{2}$,
while $P_{0}$ computes
$\mathsf{v}=(\beta_{\mathsf{v}}+\gamma_{\mathsf{v}})-\left[\alpha_{\mathsf{v}}\right]_{1}-\left[\alpha_{\mathsf{v}}\right]_{2}-\gamma_{\mathsf{v}}$.

Figure 7: 3PC: Reconstruction of $\mathsf{v}$ among the servers

######  Lemma 3.6 (Communication).

Protocol $\Pi_{\mathsf{rec}}$ (Fig. 7) requires $1$ round and a communication
of $6\ell$ bits in the online phase.

###### Proof.

The preprocessing phase consists of communication of commitment values using
the $\Pi_{\mathsf{jmp}}$ protocol. The hash-based commitment scheme allows
generation of a single commitment for several values and hence the cost gets
amortised away for multiple instances. During the online phase, each server
receives an opening for the commitment from other two servers, which requires
one round and an overall communication of $6\ell$ bits. ∎

##### The Complete 3PC

For the sake of completeness and to demonstrate how GOD is achieved, we show
how to compile the above primitives for a general 3PC. A similar approach will
be taken for 4PC and each PPML task, and we will avoid repetition. In order to
compute an arithmetic circuit over $\mathbb{Z}_{2^{\ell}}$, we first invoke
the key-setup functionality $\mathcal{F}_{\mathsf{setup}}$ (Fig. 27) for key
distribution and preprocessing of $\Pi_{\mathsf{sh}}$, $\Pi_{\mathsf{mult}}$
and $\Pi_{\mathsf{rec}}$, as per the given circuit. During the online phase,
$P_{i}\in\mathcal{P}$ shares its input $\mathsf{x}_{i}$ by executing online
steps of $\Pi_{\mathsf{sh}}$ (Fig. 3). This is followed by the circuit
evaluation phase, where severs evaluate the gates in the circuit in the
topological order, with addition gates (and multiplication-by-a-constant
gates) being computed locally, and multiplication gates being computed via
online of $\Pi_{\mathsf{mult}}$ (Fig. 5). Finally, servers run the online
steps of $\Pi_{\mathsf{rec}}$ (Fig. 7) on the output wires to reconstruct the
function output. To leverage amortization, only send phases of all the
$\mathsf{jmp}$ are run on the flow. At the end of preprocessing, the verify
phase for all possible ordered pair of senders are run. We carry on
computation in the online phase only when the verify phases in the
preprocessing are successful. Otherwise, the servers simply send their inputs
to the elected $\mathsf{TTP}$, who computes the function and returns the
result to all the servers. Similarly, depending on the output of the verify at
the end of the online phase, either the reconstruction is carried out or a
$\mathsf{TTP}$ is identified. In the latter case, computation completes as
mentioned before.

Let $\mathsf{ckt}$ denote the circuit representation of the function to be
evaluated. Servers invoke $\mathcal{F}_{\mathsf{setup}}$ to establish common
keys among themselves. $\bullet$ Preprocessing: Preprocessing phase of
$\Pi_{\mathsf{sh}},\Pi_{\mathsf{mult}},\Pi_{\mathsf{rec}}$ is executed
depending on $\mathsf{ckt}$ topology. For every pair of servers,
$P_{i},P_{j}\in\mathcal{P}$, the verification for $\mathsf{jmp}$ is executed
once, for all the $\mathsf{jmp}$ instances with $P_{i},P_{j}$ as the senders.
$\bullet$ Online phase: If $\mathsf{TTP}$ is identified in the preprocessing
phase, servers send their inputs to the $\mathsf{TTP}$, which evaluates the
function on the clear inputs, and sends the result back to the servers. Else,
– Input sharing:  The online phase of $\Pi_{\mathsf{sh}}$ is executed. –
Evaluation phase:  - Linear gates such as addition and multiplication-by-a-
constant are evaluated locally. - For multiplication gates, the online phase
of $\Pi_{\mathsf{mult}}$ is executed with only the send phase of
$\mathsf{jmp}$ being executed for $\mathsf{jmp}$ towards $P_{1},P_{2}$. All
communication towards $P_{0}$ is carried out in the verification phase. –
Verification phase: With respect to the multiplication gates, the
communication towards $P_{0}$ is carried out by invoking $\mathsf{jmp}$ (both
send and verify phase). This is followed by the verify phase of $\mathsf{jmp}$
for all $\mathsf{jmp}$ instances with $P_{1},P_{2}$ as the receivers. – If
$\mathsf{TTP}$ is identified at any point during verification, servers send
their inputs to the $\mathsf{TTP}$, which evaluates the function on the clear
inputs, and sends the result back to the servers. – Output reconstruction: If
verification succeeds without $\mathsf{TTP}$ identification, servers execute
online phase of $\Pi_{\mathsf{rec}}$.

Figure 8: Complete 3PC

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 [2]. 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.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.

Input Sharing: – $P_{0},P_{s}$, for $s\in\\{1,2\\}$, together sample random
$\left[\alpha_{\mathsf{v}}\right]_{s}\in\mathbb{Z}_{2^{\ell}}$, while
$P_{1},P_{2}$ together sample random
$\gamma_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$. – $P_{0},P_{1}$
$\mathsf{jmp\mbox{-}send}$
$\mathsf{Com}(\left[\alpha_{\mathsf{v}}\right]_{1})$ to $P_{2}$, while
$P_{0},P_{2}$ $\mathsf{jmp\mbox{-}send}$
$\mathsf{Com}(\left[\alpha_{\mathsf{v}}\right]_{2})$ to $P_{1}$, and
$P_{1},P_{2}$ $\mathsf{jmp\mbox{-}send}$ $\mathsf{Com}(\gamma_{\mathsf{v}})$
to $P_{0}$. – Each server sends
$(\mathsf{Com}(\left[\alpha_{\mathsf{v}}\right]_{1}),\mathsf{Com}(\left[\alpha_{\mathsf{v}}\right]_{2}),\mathsf{Com}(\gamma_{\mathsf{v}}))$
to $\mathsf{U}$ who accepts the values that form majority. Also,
$P_{0},P_{s}$, for $s\in\\{1,2\\}$, open
$\left[\alpha_{\mathsf{v}}\right]_{s}$ towards $\mathsf{U}$ while
$P_{1},P_{2}$ open $\gamma_{\mathsf{v}}$ towards $\mathsf{U}$. – $\mathsf{U}$
accepts the consistent opening, recovers
$\left[\alpha_{\mathsf{v}}\right]_{1},\left[\alpha_{\mathsf{v}}\right]_{2},\gamma_{\mathsf{v}}$,
computes
$\beta_{\mathsf{v}}=\mathsf{v}+\left[\alpha_{\mathsf{v}}\right]_{1}+\left[\alpha_{\mathsf{v}}\right]_{2}$,
and sends $\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}$ to all three servers. –
Servers broadcast the received value and accept the majority value if it
exists, and a default value, otherwise. $P_{1},P_{2}$ locally compute
$\beta_{\mathsf{v}}$ from $\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}$ using
$\gamma_{\mathsf{v}}$ to complete the sharing of $\mathsf{v}$. Output
Reconstruction: – Servers execute the preprocessing of
$\Pi_{\mathsf{rec}}(\mathcal{P},\llbracket\mathsf{v}\rrbracket)$ to agree upon
commitments of
$\left[\alpha_{\mathsf{v}}\right]_{1},\left[\alpha_{\mathsf{v}}\right]_{2}$
and $\gamma_{\mathsf{v}}$. – Each server sends
$\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}$ and commitments on
$\left[\alpha_{\mathsf{v}}\right]_{1},\left[\alpha_{\mathsf{v}}\right]_{2}$
and $\gamma_{\mathsf{v}}$ to $\mathsf{U}$, who accepts the values forming
majority. – $P_{0},P_{i}$ for $i\in\\{1,2\\}$ open
$\left[\alpha_{\mathsf{v}}\right]_{i}$ to $\mathsf{U}$, while $P_{1},P_{2}$
open $\gamma_{\mathsf{v}}$ to $\mathsf{U}$. – $\mathsf{U}$ accepts the
consistent opening and computes
$\mathsf{v}=(\beta_{\mathsf{v}}+\gamma_{\mathsf{v}})-\left[\alpha_{\mathsf{v}}\right]_{1}-\left[\alpha_{\mathsf{v}}\right]_{2}-\gamma_{\mathsf{v}}$.

Figure 9: 3PC: Input Sharing and Output Reconstruction

##### Input Sharing and Output Reconstruction in the SOC Setting

Protocol $\Pi_{\mathsf{sh}}^{\mathsf{SOC}}$ (Fig. 9) extends input sharing to
the SOC setting and allows a user $\mathsf{U}$ to generate the
$\llbracket\cdot\rrbracket$-shares of its input $\mathsf{v}$ among the three
servers. Note that the necessary commitments to facilitate the sharing are
generated in the preprocessing phase by the servers which are then
communicated to $\mathsf{U}$, along with the opening, in the online phase.
$\mathsf{U}$ selects the commitment forming the majority (for each share)
owing to the presence of an honest majority among the servers, and accepts the
corresponding shares. Analogously, protocol
$\Pi_{\mathsf{rec}}^{\mathsf{SOC}}$ (Fig. 9) allows the servers to reconstruct
a value $\mathsf{v}$ towards user $\mathsf{U}$. In either of the protocols, if
at any point, a $\mathsf{TTP}$ is identified, then servers signal the
$\mathsf{TTP}$’s identity to $\mathsf{U}$. $\mathsf{U}$ selects the
$\mathsf{TTP}$ as the one forming a majority and sends its input in the clear
to the $\mathsf{TTP}$, who computes the function output and sends it back to
$\mathsf{U}$.

##### MSB Extraction

Protocol $\Pi_{\mathsf{bitext}}$ allows servers to compute the boolean sharing
of the most significant bit ($\mathsf{msb}$) of a value $\mathsf{v}$ given its
arithmetic sharing $\llbracket\mathsf{v}\rrbracket$. To compute the
$\mathsf{msb}$, we use the optimized 2-input Parallel Prefix Adder (PPA)
boolean circuit proposed by ABY3 [43]. The PPA circuit consists of $2\ell-2$
AND gates and has a multiplicative depth of $\log\ell$.

| $P_{0}$ | $P_{1}$ | $P_{2}$
---|---|---|---
$\llbracket\mathsf{v}_{0}[i]\rrbracket^{\bf B}$ | $(0,0,0)$ | $(0,\mathsf{v}_{0}[i],\mathsf{v}_{0}[i])$ | $(0,\mathsf{v}_{0}[i],\mathsf{v}_{0}[i])$
$\llbracket\mathsf{v}_{1}[i]\rrbracket^{\bf B}$ | $(\mathsf{v}_{1}[i],0,0)$ | $(\mathsf{v}_{1}[i],0,0)$ | $(0,0,0)$
$\llbracket\mathsf{v}_{2}[i]\rrbracket^{\bf B}$ | $(0,\mathsf{v}_{2}[i],0)$ | $(0,0,0)$ | $(0,\mathsf{v}_{2}[i],0)$

Table 4: The $\llbracket\cdot\rrbracket^{\bf B}$-sharing corresponding to
$i^{th}$ bit of
$\mathsf{v}_{0}=\beta_{\mathsf{v}},\mathsf{v}_{1}=-\left[\alpha_{\mathsf{v}}\right]_{1}$
and $\mathsf{v}_{2}=-\left[\alpha_{\mathsf{v}}\right]_{2}$. Here
$i\in\\{0,\ldots,\ell-1\\}$.

Let
$\mathsf{v}_{0}=\beta_{\mathsf{v}},\mathsf{v}_{1}=-\left[\alpha_{\mathsf{v}}\right]_{1}$
and $\mathsf{v}_{2}=-\left[\alpha_{\mathsf{v}}\right]_{2}$. Then
$\mathsf{v}=\mathsf{v}_{0}+\mathsf{v}_{1}+\mathsf{v}_{2}$. Servers first
locally compute the boolean shares corresponding to each bit of the values
$\mathsf{v}_{0},\mathsf{v}_{1}$ and $\mathsf{v}_{2}$ according to Table 4. It
has been shown in ABY3 that
$\mathsf{v}=\mathsf{v}_{0}+\mathsf{v}_{1}+\mathsf{v}_{2}$ can also be
expressed as $\mathsf{v}=2c+s$ where
FA$(\mathsf{v}_{0}[i],\mathsf{v}_{1}[i],\mathsf{v}_{2}[i])\rightarrow(c[i],s[i])$
for $i\in\\{0,\ldots,\ell-1\\}$. Here FA denotes a Full Adder circuit while
$s$ and $c$ denote the sum and carry bits respectively. To summarize, servers
execute $\ell$ instances of FA in parallel to compute $\llbracket
c\rrbracket^{\bf B}$ and $\llbracket s\rrbracket^{\bf B}$. The FA’s are
executed independently and require one round of communication. The final
result is then computed as $\mathsf{msb}(2\llbracket c\rrbracket^{\bf
B}+\llbracket s\rrbracket^{\bf B})$ using the optimized PPA circuit.

######  Lemma 3.7 (Communication).

Protocol $\Pi_{\mathsf{bitext}}$ requires a communication cost of $9\ell-6$
bits in the preprocessing phase and require $\log\ell+1$ rounds and an
amortized communication of $9\ell-6$ bits in the online phase.

###### Proof.

In $\Pi_{\mathsf{bitext}}$, first round comprises of $\ell$ Full Adder (FA)
circuits executing in parallel, each comprising of single AND gate. This is
followed by the execution of the optimized PPA circuit of ABY3 [43], which
comprises of $2\ell-2$ AND gates and has a multiplicative depth of $\log\ell$.
Hence the communication cost follows from the multiplication for $3\ell-2$ AND
gates. ∎

##### Bit to Arithmetic Conversion

Given the boolean sharing of a bit $\mathsf{b}$, denoted as
$\llbracket\mathsf{b}\rrbracket^{\bf B}$, protocol $\Pi_{\mathsf{bit2A}}$
(Fig. 10) allows servers to compute the arithmetic sharing
$\llbracket\mathsf{b}^{\sf R}\rrbracket$. Here $\mathsf{b}^{\sf R}$ denotes
the equivalent value of $\mathsf{b}$ over ring $\mathbb{Z}_{2^{\ell}}$ (see
Notation 2.2). As pointed out in BLAZE, $\mathsf{b}^{\sf
R}=(\beta_{\mathsf{b}}\oplus\alpha_{\mathsf{b}})^{\sf
R}=\beta_{\mathsf{b}}^{\sf R}+\alpha_{\mathsf{b}}^{\sf
R}-2\beta_{\mathsf{b}}^{\sf R}\alpha_{\mathsf{b}}^{\sf R}$. Also
$\alpha_{\mathsf{b}}^{\sf
R}=(\left[\alpha_{\mathsf{b}}\right]_{1}\oplus\left[\alpha_{\mathsf{b}}\right]_{2})^{\sf
R}=\left[\alpha_{\mathsf{b}}\right]_{1}^{\sf
R}+\left[\alpha_{\mathsf{b}}\right]_{2}^{\sf
R}-2\left[\alpha_{\mathsf{b}}\right]_{1}^{\sf
R}\left[\alpha_{\mathsf{b}}\right]_{2}^{\sf R}$. During the preprocessing
phase, $P_{0},P_{j}$ for $j\in\\{1,2\\}$ execute $\Pi_{\mathsf{jsh}}$ on
$\left[\alpha_{b}\right]_{j}^{\sf R}$ to generate
$\llbracket\left[\alpha_{b}\right]_{j}^{\sf R}\rrbracket$. Servers then
execute $\Pi_{\mathsf{mult}}$ on $\llbracket\left[\alpha_{b}\right]_{1}^{\sf
R}\rrbracket$ and $\llbracket\left[\alpha_{b}\right]_{2}^{\sf R}\rrbracket$ to
generate $\llbracket\left[\alpha_{b}\right]_{1}^{\sf
R}\left[\alpha_{b}\right]_{2}^{\sf R}\rrbracket$ followed by locally computing
$\llbracket\alpha_{\mathsf{b}}^{\sf R}\rrbracket$. During the online phase,
$P_{1},P_{2}$ execute $\Pi_{\mathsf{jsh}}$ on $\beta_{\mathsf{b}}^{\sf R}$ to
jointly generate $\llbracket\beta_{\mathsf{b}}^{\sf R}\rrbracket$. Servers
then execute $\Pi_{\mathsf{mult}}$ protocol on
$\llbracket\beta_{\mathsf{b}}^{\sf R}\rrbracket$ and
$\llbracket\alpha_{\mathsf{b}}^{\sf R}\rrbracket$ to compute
$\llbracket\beta_{\mathsf{b}}^{\sf R}\alpha_{\mathsf{b}}^{\sf R}\rrbracket$
followed by locally computing $\llbracket\mathsf{b}^{\sf R}\rrbracket$.

######  Lemma 3.8 (Communication).

Protocol $\Pi_{\mathsf{bit2A}}$ (Fig. 10) requires an amortized communication
cost of $9\ell$ bits in the preprocessing phase and requires $1$ round and an
amortized communication of $4\ell$ bits in the online phase.

###### Proof.

In the preprocessing phase, servers run two instances of $\Pi_{\mathsf{jsh}}$,
which can be done non-interactively (ref. Table 2). This is followed by an
execution of entire multiplication protocol, which requires $6\ell$ bits to be
communicated (Lemma 3.5). Parallelly, the servers execute the preprocessing
phase of $\Pi_{\mathsf{mult}}$, resulting in an additional $3\ell$ bits of
communication (Lemma 3.5). During the online phase, $P_{1},P_{2}$ execute
$\Pi_{\mathsf{jsh}}$ once, which requires one round and $\ell$ bits to be
communicated. In $\Pi_{\mathsf{jsh}}$, the communication towards $P_{0}$ can
be deferred till the end, thereby requiring a single round for multiple
instances. This is followed by an execution of the online phase of
$\Pi_{\mathsf{mult}}$, which requires one round and a communication of $3\ell$
bits. ∎

Preprocessing: – $P_{0},P_{j}$ for $j\in\\{1,2\\}$ execute
$\Pi_{\mathsf{jsh}}$ on $\left[\alpha_{\mathsf{b}}\right]_{j}^{\sf R}$ to
generate $\llbracket\left[\alpha_{\mathsf{b}}\right]_{j}^{\sf R}\rrbracket$. –
Servers execute
$\Pi_{\mathsf{mult}}(\mathcal{P},\left[\alpha_{\mathsf{b}}\right]_{1}^{\sf
R},\left[\alpha_{\mathsf{b}}\right]_{2}^{\sf R})$ to generate
$\llbracket\mathsf{u}\rrbracket$ where
$\mathsf{u}=\left[\alpha_{\mathsf{b}}\right]_{1}^{\sf
R}\left[\alpha_{\mathsf{b}}\right]_{2}^{\sf R}$, followed by locally computing
$\llbracket\alpha_{\mathsf{b}}^{\sf
R}\rrbracket=\llbracket\left[\alpha_{\mathsf{b}}\right]_{1}^{\sf
R}\rrbracket+\llbracket\left[\alpha_{\mathsf{b}}\right]_{2}^{\sf
R}\rrbracket-2\llbracket\mathsf{u}\rrbracket$. – Servers execute the
preprocessing phase of
$\Pi_{\mathsf{mult}}(\mathcal{P},\beta_{\mathsf{b}}^{\sf
R},\alpha_{\mathsf{b}}^{\sf R})$ for $\mathsf{v}=\beta_{\mathsf{b}}^{\sf
R}\alpha_{\mathsf{b}}^{\sf R}$. Online: – $P_{1},P_{2}$ execute
$\Pi_{\mathsf{jsh}}(P_{1},P_{2},\beta_{\mathsf{b}}^{\sf R})$ to generate
$\llbracket\beta_{\mathsf{b}}^{\sf R}\rrbracket$. – Servers execute online
phase of $\Pi_{\mathsf{mult}}(\mathcal{P},\beta_{\mathsf{b}}^{\sf
R},\alpha_{\mathsf{b}}^{\sf R})$ to generate $\llbracket\mathsf{v}\rrbracket$
where $\mathsf{v}=\beta_{\mathsf{b}}^{\sf R}\alpha_{\mathsf{b}}^{\sf R}$,
followed by locally computing $\llbracket\mathsf{b}^{\sf
R}\rrbracket=\llbracket\beta_{\mathsf{b}}^{\sf
R}\rrbracket+\llbracket\alpha_{\mathsf{b}}^{\sf
R}\rrbracket-2\llbracket\mathsf{v}\rrbracket$.

Figure 10: 3PC: Bit2A Protocol

##### Bit Injection

Given the binary sharing of a bit $\mathsf{b}$, denoted as
$\llbracket\mathsf{b}\rrbracket^{\bf B}$, and the arithmetic sharing of
$\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$, protocol $\Pi_{\mathsf{BitInj}}$
computes $\llbracket\cdot\rrbracket$-sharing of $\mathsf{b}\mathsf{v}$.
Towards this, servers first execute $\Pi_{\mathsf{bit2A}}$ on
$\llbracket\mathsf{b}\rrbracket^{\bf B}$ to generate
$\llbracket\mathsf{b}\rrbracket$. This is followed by servers computing
$\llbracket\mathsf{b}\mathsf{v}\rrbracket$ by executing $\Pi_{\mathsf{mult}}$
protocol on $\llbracket\mathsf{b}\rrbracket$ and
$\llbracket\mathsf{v}\rrbracket$.

######  Lemma 3.9 (Communication).

Protocol $\Pi_{\mathsf{BitInj}}$ requires an amortized communication cost of
$12\ell$ bits in the preprocessing phase and requires $2$ rounds and an
amortized communication of $7\ell$ bits in the online phase.

###### Proof.

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. ∎

##### Dot Product

Given the $\llbracket\cdot\rrbracket$-sharing of vectors $\vec{\mathbf{x}}$
and $\vec{\mathbf{y}}$, protocol $\Pi_{\mathsf{dotp}}$ (Fig. 11) allows
servers to generate $\llbracket\cdot\rrbracket$-sharing of
$\mathsf{z}=\vec{\mathbf{x}}\odot\vec{\mathbf{y}}$ robustly.
$\llbracket\cdot\rrbracket$-sharing of a vector $\vec{\mathbf{x}}$ of size
$\mathsf{n}$, means that each element $\mathsf{x}_{i}\in\mathbb{Z}_{2^{\ell}}$
of $\vec{\mathbf{x}}$, for $i\in[\mathsf{n}]$, is
$\llbracket\cdot\rrbracket$-shared. We borrow ideas from BLAZE for obtaining
an online communication cost independent of $\mathsf{n}$ and use
$\mathsf{jmp}$ primitive to ensure either success or $\mathsf{TTP}$ selection.
Analogous to our multiplication protocol, our dot product offloads one call to
a robust dot product protocol to the preprocessing. By extending techniques of
[9, 10], we give an instantiation for the dot product protocol used in our
preprocessing whose (amortized) communication cost is constant, thereby making
our preprocessing cost also independent of $\mathsf{n}$.

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,

$\mathsf{\beta}_{\mathsf{z}}^{\star}=-\sum_{i=1}^{\mathsf{n}}(\beta_{\mathsf{x}_{i}}+\gamma_{\mathsf{x}_{i}})\alpha_{\mathsf{y}_{i}}-\sum_{i=1}^{\mathsf{n}}(\beta_{\mathsf{y}_{i}}+\gamma_{\mathsf{y}_{i}})\alpha_{\mathsf{x}_{i}}+\alpha_{\mathsf{z}}+{\chi}$
(3)

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}}$,

$\displaystyle\mathsf{f}$
$\displaystyle=\vec{\mathbf{d}}\odot\vec{\mathbf{e}}=\sum_{i=1}^{\mathsf{n}}\mathsf{d}_{i}\mathsf{e}_{i}=\sum_{i=1}^{\mathsf{n}}(\gamma_{\mathsf{x}_{i}}+\alpha_{\mathsf{x}_{i}})(\gamma_{\mathsf{y}_{i}}+\alpha_{\mathsf{y}_{i}})$
$\displaystyle=\sum_{i=1}^{\mathsf{n}}(\gamma_{\mathsf{x}_{i}}\gamma_{\mathsf{y}_{i}}+\psi_{i})+\sum_{i=1}^{\mathsf{n}}\chi_{i}=\sum_{i=1}^{\mathsf{n}}(\gamma_{\mathsf{x}_{i}}\gamma_{\mathsf{y}_{i}}+\psi_{i})+\chi$
$\displaystyle=\sum_{i=1}^{\mathsf{n}}(\gamma_{\mathsf{x}_{i}}\gamma_{\mathsf{y}_{i}}+\psi_{i})+\left[\chi\right]_{1}+\left[\chi\right]_{2}=\mathsf{f}_{2}+\mathsf{f}_{1}+\mathsf{f}_{0}.$

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

Using the above relation, the preprocessing phase proceeds as follows:
$P_{0},P_{j}$ for $j\in\\{1,2\\}$ sample a random
$\left[\alpha_{\mathsf{z}}\right]_{j}\in\mathbb{Z}_{2^{\ell}}$, while
$P_{1},P_{2}$ sample random $\gamma_{\mathsf{z}}$. Servers locally prepare
$\langle\vec{\mathbf{d}}\rangle,\langle\vec{\mathbf{e}}\rangle$ similar to
that of multiplication protocol. Servers then execute a robust 3PC dot product
protocol, denoted by $\Pi_{\mathsf{dotpPre}}$ (the task is abstracted away in
the functionality Fig. 12), that takes
$\langle\vec{\mathbf{d}}\rangle,\langle\vec{\mathbf{e}}\rangle$ as input and
compute $\langle\mathsf{f}\rangle$ with
$\mathsf{f}=\vec{\mathbf{d}}\odot\vec{\mathbf{e}}$. Given
$\langle\mathsf{f}\rangle$, the $\psi$ and $\left[\chi\right]$ values are
extracted as follows (ref. Eq. 4):

$\psi=\mathsf{f}_{2}-\sum_{i=1}^{\mathsf{n}}\gamma_{\mathsf{x}_{i}}\gamma_{\mathsf{y}_{i}},~{}~{}\left[\chi\right]_{1}=\mathsf{f}_{1},~{}~{}\left[\chi\right]_{2}=\mathsf{f}_{0},$
(4)

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

Preprocessing: – $P_{0},P_{j}$, for $j\in\\{1,2\\}$, together sample random
$\left[\alpha_{\mathsf{z}}\right]_{j}\in\mathbb{Z}_{2^{\ell}}$, while
$P_{1},P_{2}$ sample random $\gamma_{\mathsf{z}}\in\mathbb{Z}_{2^{\ell}}$. –
Servers locally compute $\langle\cdot\rangle$-sharing of
$\vec{\mathbf{d}},\vec{\mathbf{e}}$ with
$\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 follows:
$\displaystyle({\langle\mathsf{d}_{i}\rangle}_{0}\text{=}(\left[\alpha_{\mathsf{x}_{i}}\right]_{2},\left[\alpha_{\mathsf{x}_{i}}\right]_{1}),{\langle\mathsf{d}_{i}\rangle}_{1}\text{=}(\left[\alpha_{\mathsf{x}_{i}}\right]_{1},\gamma_{\mathsf{x}_{i}}),{\langle\mathsf{d}_{i}\rangle}_{2}\text{=}(\gamma_{\mathsf{x}_{i}},\left[\alpha_{\mathsf{x}_{i}}\right]_{2}))$
$\displaystyle({\langle\mathsf{e}_{i}\rangle}_{0}\text{=}(\left[\alpha_{\mathsf{y}_{i}}\right]_{2},\left[\alpha_{\mathsf{y}_{i}}\right]_{1}),{\langle\mathsf{e}_{i}\rangle}_{1}\text{=}(\left[\alpha_{\mathsf{y}_{i}}\right]_{1},\gamma_{\mathsf{y}_{i}}),{\langle\mathsf{e}_{i}\rangle}_{2}\text{=}(\gamma_{\mathsf{y}_{i}},\left[\alpha_{\mathsf{y}_{i}}\right]_{2}))$
– Servers execute
$\Pi_{\mathsf{dotpPre}}(\mathcal{P},\langle\vec{\mathbf{d}}\rangle,\langle\vec{\mathbf{e}}\rangle)$
to generate
$\langle\mathsf{f}\rangle=\langle\vec{\mathbf{d}}\odot\vec{\mathbf{e}}\rangle$.
– $P_{0},P_{1}$ locally set $\left[\chi\right]_{1}=\mathsf{f}_{1}$, while
$P_{0},P_{2}$ locally set $\left[\chi\right]_{2}=\mathsf{f}_{0}$.
$P_{1},P_{2}$ locally compute
$\psi=\mathsf{f}_{2}-\sum_{i=1}^{\mathsf{n}}\gamma_{\mathsf{x}_{i}}\gamma_{\mathsf{y}_{i}}$.
Online: – $P_{0},P_{j}$, for $j\in\\{1,2\\}$, compute
$\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{j}=-\sum_{i=1}^{\mathsf{n}}((\beta_{\mathsf{x}_{i}}+\gamma_{\mathsf{x}_{i}})\left[\alpha_{\mathsf{y}_{i}}\right]_{j}+(\beta_{\mathsf{y}_{i}}+\gamma_{\mathsf{y}_{i}})\left[\alpha_{\mathsf{x}_{i}}\right]_{j})+\left[\alpha_{\mathsf{z}}\right]_{j}+\left[\chi\right]_{j}$.
– $P_{0},P_{1}$ $\mathsf{jmp\mbox{-}send}$
$\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{1}$ to $P_{2}$ and
$P_{0},P_{2}$ $\mathsf{jmp\mbox{-}send}$
$\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{2}$ to $P_{1}$. –
$P_{1},P_{2}$ locally compute
$\mathsf{\beta}_{\mathsf{z}}^{\star}=\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{1}+\left[\mathsf{\beta}_{\mathsf{z}}^{\star}\right]_{2}$
and set
$\beta_{\mathsf{z}}=\mathsf{\beta}_{\mathsf{z}}^{\star}+\sum_{i=1}^{\mathsf{n}}(\beta_{\mathsf{x}_{i}}\beta_{\mathsf{y}_{i}})+\psi$.
– $P_{1},P_{2}$ $\mathsf{jmp\mbox{-}send}$
$\beta_{\mathsf{z}}+\gamma_{\mathsf{z}}$ to $P_{0}$.

Figure 11: 3PC: Dot Product Protocol
($\mathsf{z}=\vec{\mathbf{x}}\odot\vec{\mathbf{y}}$)

$\mathcal{F}_{\mathsf{DotPPre}}$ interacts with the servers in $\mathcal{P}$
and the adversary $\mathcal{S}$. $\mathcal{F}_{\mathsf{DotPPre}}$ receives
$\langle\cdot\rangle$-shares of vectors
$\vec{\mathbf{d}}=(\mathsf{d}_{1},\ldots,\mathsf{d}_{\mathsf{n}}),\vec{\mathbf{e}}=(\mathsf{e}_{1},\ldots,\mathsf{e}_{\mathsf{n}})$
from the servers. Let $\mathsf{v}_{j,s}$ for
$j\in[\mathsf{n}],s\in\\{0,1,2\\}$ denote the share of $\mathsf{v}_{j}$ such
that $\mathsf{v}_{j}=\mathsf{v}_{j,0}+\mathsf{v}_{j,1}+\mathsf{v}_{j,2}$.
Server $P_{s}$, for $s\in\\{0,1,2\\}$, holds
$\langle\mathsf{d}_{j}\rangle_{s}=(\mathsf{d}_{j,s},\mathsf{d}_{j,(s+1)\%3})$
and
$\langle\mathsf{e}_{j}\rangle_{s}=(\mathsf{e}_{j,s},\mathsf{e}_{j,(s+1)\%3})$
where $j\in[\mathsf{n}]$. Let $P_{i}$ denotes the server corrupted by
$\mathcal{S}$. $\mathcal{F}_{\mathsf{MulPre}}$ receives
$\langle\mathsf{f}\rangle_{i}=(\mathsf{f}_{i},\mathsf{f}_{(i+1)\%3})$ from
$\mathcal{S}$ where $\mathsf{f}=\vec{\mathbf{d}}\odot\vec{\mathbf{e}}$.
$\mathcal{F}_{\mathsf{DotPPre}}$ proceeds as follows:  – Reconstructs
$\mathsf{d}_{j},\mathsf{e}_{j}$, for $j\in[\mathsf{n}]$, using the shares
received from honest servers and compute
$\mathsf{f}=\sum_{j=1}^{n}\mathsf{d}_{j}\mathsf{e}_{j}$. – Compute
$\mathsf{f}_{(i+2)\%3}=\mathsf{f}-\mathsf{f}_{i}-\mathsf{f}_{(i+1)\%3}$ and
set the output shares as
$\langle\mathsf{f}\rangle_{0}=(\mathsf{f}_{0},\mathsf{f}_{1}),\langle\mathsf{f}\rangle_{1}=(\mathsf{f}_{1},\mathsf{f}_{2}),\langle\mathsf{f}\rangle_{2}=(\mathsf{f}_{2},\mathsf{f}_{0})$.
– Send $(\mathsf{Output},\langle\mathsf{f}\rangle_{s})$ to server
$P_{s}\in\mathcal{P}$.

Figure 12: 3PC: Ideal functionality for $\Pi_{\mathsf{dotpPre}}$ protocol

The ideal world functionality for realizing $\Pi_{\mathsf{dotpPre}}$ is
presented in Fig. 12. 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 [9, 10] 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. Details appear in §B.

######  Lemma 3.10 (Communication).

Protocol $\Pi_{\mathsf{dotp}}$ (Fig. 11) requires an amortized communication
of $3\ell$ bits in the preprocessing phase and requires $1$ round and an
amortized communication of $3\ell$ bits in the online phase.

###### Proof.

During the preprocessing phase, servers execute $\Pi_{\mathsf{dotpPre}}$. This
requires communicating $3\ell$ bits for a single semi-honest dot product
protocol and $\mathcal{O}(\frac{\sqrt{\mathsf{n}}}{\sqrt{m}})$ extended ring
elements for its verification. By appropriately setting the values of
$\mathsf{n},m$, the cost of communicating
$\mathcal{O}(\frac{\sqrt{\mathsf{n}}}{\sqrt{m}})$ elements can be amortized
away, thereby resulting in an amortized communication cost of $3\ell$ bits in
the preprocessing phase. The online phase follows similarly to that of
$\Pi_{\mathsf{mult}}$, the only difference being that servers combine their
shares corresponding to all the $\mathsf{n}$ multiplications into one and then
exchange. This requires one round and an amortized communication of $3\ell$
bits. ∎

##### Truncation

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 [45, 43, 15, 12, 48] that re-adjusts
the shares after multiplication so that FPA semantics are maintained. As shown
in SecureML [45], 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 [43].

Protocol $\Pi_{\mathsf{trgen}}$ is inspired from [43, 16] and proceeds as
follows to generate
$(\left[\mathsf{r}\right],\llbracket\mathsf{r}^{d}\rrbracket)$. Analogous to
the approach of ABY3 [43], servers generate a boolean sharing of an $\ell$-bit
value $\mathsf{r}=\mathsf{r}_{1}\oplus\mathsf{r}_{2}$, non-interactively. Each
server truncates its share of $\mathsf{r}$ locally to obtain a boolean sharing
of $\mathsf{r}^{d}$ by removing the lower $d$ bits. To obtain the arithmetic
shares of $(\mathsf{r},\mathsf{r}^{d})$ from their boolean sharing, we do not,
however, rely on the approach of ABY3 as it requires more rounds. Instead, we
implicitly perform a boolean to arithmetic conversion, as was proposed in
Trident [16], to obtain the arithmetic shares of
$(\mathsf{r},\mathsf{r}^{d})$. This entails performing two dot product
operations and constitutes the cost for $\Pi_{\mathsf{trgen}}$.

– To generate each bit $\mathsf{r}[i]$ of $\mathsf{r}$ for
$i\in\\{0,\ldots,\ell-1\\}$, $P_{0},P_{j}$ for $j\in\\{1,2\\}$ sample random
$\mathsf{r}_{j}[i]\in\mathbb{Z}_{2}$ and define
$\mathsf{r}[i]=\mathsf{r}_{1}[i]\oplus\mathsf{r}_{2}[i]$. – Servers generate
$\llbracket\cdot\rrbracket$-shares of $(\mathsf{r}_{j}[i])^{\sf R}$ for
$i\in\\{0,\ldots,\ell-1\\},j\in\\{1,2\\}$ non-interactively following Table 2.
– Define $\vec{\mathbf{x}}$ and $\vec{\mathbf{y}}$ such that
$\mathsf{x}=2^{i-d+1}(\mathsf{r}_{1}[i])^{\sf R}$ and
$\mathsf{y}_{i}=(\mathsf{r}_{2}[i])^{\sf R}$, respectively, for
$i\in\\{d,\ldots,\ell-1\\}$. Define $\vec{\mathbf{p}}$ and $\vec{\mathbf{q}}$
such that $\mathsf{p}_{i}=2^{i+1}(\mathsf{r}_{1}[i])^{\sf R}$ and
$\mathsf{q}_{i}=(\mathsf{r}_{2}[i])^{\sf R}$, respectively, for
$i\in\\{0,\ldots,\ell-1\\}$. Servers execute $\Pi_{\mathsf{dotp}}$ to compute
$\llbracket\cdot\rrbracket$-shares of
$\mathsf{A}=\vec{\mathbf{x}}\odot\vec{\mathbf{y}}$ and
$\mathsf{B}=\vec{\mathbf{p}}\odot\vec{\mathbf{q}}$. – Servers locally compute
$\llbracket{\mathsf{r}^{d}}\rrbracket=\sum_{i=d}^{\ell-1}2^{i-d}(\llbracket({\mathsf{r}_{1}[i]})^{\sf
R}\rrbracket+\llbracket(\mathsf{r}_{2}[i])^{\sf
R}\rrbracket)-\llbracket\mathsf{A}\rrbracket$, and
$\llbracket\mathsf{r}\rrbracket=\sum_{i=0}^{\ell-1}2^{i}(\llbracket({\mathsf{r}_{1}[i]})^{\sf
R}\rrbracket+\llbracket({\mathsf{r}_{2}[i]})^{\sf
R}\rrbracket)-\llbracket\mathsf{B}\rrbracket$. – $P_{0}$ locally computes
$\beta_{\mathsf{r}}=\mathsf{r}+\alpha_{\mathsf{r}}$. $P_{0},P_{1}$ set
$\left[\mathsf{r}\right]_{1}=-\left[\alpha_{\mathsf{r}}\right]_{1}$ and
$P_{0},P_{2}$ set
$\left[\mathsf{r}\right]_{2}=\beta_{\mathsf{r}}-\left[\alpha_{\mathsf{r}}\right]_{2}$.

Figure 13: 3PC: Generating Random Truncated Pair $(\mathsf{r},\mathsf{r}^{d})$

We now give details for generating
$(\left[\mathsf{r}\right],\llbracket\mathsf{r}^{d}\rrbracket)$. For this,
servers proceed as follows: $P_{0},P_{j}$ for $j\in\\{1,2\\}$ sample random
$\mathsf{r}_{j}\in\mathbb{Z}_{2^{\ell}}$. Recall that the bit at $i\text{th}$
position in $\mathsf{r}$ is denoted as $\mathsf{r}[i]$. Define
$\mathsf{r}[i]=\mathsf{r}_{1}[i]\oplus\mathsf{r}_{2}[i]$ for
$i\in\\{0,\ldots,\ell-1\\}$. For $\mathsf{r}$ defined as above, we have
$\mathsf{r}^{d}[i]=\mathsf{r}_{1}[i+d]\oplus\mathsf{r}_{2}[i+d]$ for
$i\in\\{0,\ldots,\ell-d-1\\}$. Further,

$\displaystyle\mathsf{r}$
$\displaystyle=\sum_{i=0}^{\ell-1}2^{i}\mathsf{r}[i]=\sum_{i=0}^{\ell-1}2^{i}(\mathsf{r}_{1}[i]\oplus\mathsf{r}_{2}[i])$
$\displaystyle=\sum_{i=0}^{\ell-1}2^{i}\left((\mathsf{r}_{1}[i])^{\sf
R}+(\mathsf{r}_{2}[i])^{\sf R}-2(\mathsf{r}_{1}[i])^{\sf
R}\cdot(\mathsf{r}_{2}[i])^{\sf R}\right)$
$\displaystyle=\sum_{i=0}^{\ell-1}2^{i}\left((\mathsf{r}_{1}[i])^{\sf
R}+(\mathsf{r}_{2}[i])^{\sf
R}\right)-\sum_{i=0}^{\ell-1}\left(2^{i+1}(\mathsf{r}_{1}[i])^{\sf
R}\right)\cdot(\mathsf{r}_{2}[i])^{\sf R}$ (5)

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

$\displaystyle\mathsf{r}^{d}$
$\displaystyle=\sum_{i=d}^{\ell-1}2^{i-d}\left((\mathsf{r}_{1}[i])^{\sf
R}+(\mathsf{r}_{2}[i])^{\sf
R}\right)-\sum_{i=d}^{\ell-1}\left(2^{i-d+1}(\mathsf{r}_{1}[i])^{\sf
R}\right)\cdot(\mathsf{r}_{2}[i])^{\sf R}$ (6)

The servers non-interactively generate $\llbracket\cdot\rrbracket$-shares
(arithmetic shares) for each bit of $\mathsf{r}_{1}$ and $\mathsf{r}_{2}$ as
in Table 2. Given their $\llbracket\cdot\rrbracket$-shares, the servers
execute $\Pi_{\mathsf{dotp}}$ twice to compute
$\llbracket\cdot\rrbracket$-share of
$\mathsf{A}=\sum_{i=d}^{\ell-1}(2^{i-d+1}(\mathsf{r}_{1}[i])^{\sf
R})\cdot(\mathsf{r}_{2}[i])^{\sf R}$, and
$\mathsf{B}=\sum_{i=0}^{\ell-1}(2^{i+1}(\mathsf{r}_{1}[i])^{\sf
R})\cdot(\mathsf{r}_{2}[i])^{\sf R}$. Using these values, the servers can
locally compute the $\llbracket\cdot\rrbracket$-shares for
($\mathsf{r},\mathsf{r}^{d}$) pair following Equation 3.3 and 6, respectively.
Note that servers need $\left[\cdot\right]$-shares of $\mathsf{r}$ and not
$\llbracket\cdot\rrbracket$-shares. The $\left[\cdot\right]$-shares can be
computed from the $\llbracket\cdot\rrbracket$-shares locally as follows. Let
$(\alpha_{\mathsf{r}},\beta_{\mathsf{r}},\gamma_{\mathsf{r}})$ be the values
corresponding to the $\llbracket\cdot\rrbracket$-shares of $\mathsf{r}$. Since
$P_{0}$ knows the entire value $\mathsf{r}$ in clear, and it knows
$\alpha_{\mathsf{r}}$, it can locally compute $\beta_{\mathsf{r}}$. Now, the
servers set $\left[\cdot\right]$-shares as:
$\left[\mathsf{r}\right]_{1}=-\left[\alpha_{\mathsf{r}}\right]_{1}$ and
$\left[\mathsf{r}\right]_{2}=\beta_{\mathsf{r}}-\left[\alpha_{\mathsf{r}}\right]_{2}$.
The protocol appears in Fig. 13.

######  Lemma 3.11 (Communication).

Protocol $\Pi_{\mathsf{trgen}}$ (Fig. 13) requires an amortized communication
of $12\ell$ bits.

###### Proof.

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. ∎

##### Dot Product with Truncation

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.

Preprocessing: – Servers execute the preprocessing of
$\Pi_{\mathsf{dotp}}(\mathcal{P},\\{\llbracket\mathsf{x}_{i}\rrbracket,\llbracket\mathsf{y}_{i}\rrbracket\\}_{i\in[\mathsf{n}]})$.
– In parallel, servers execute $\Pi_{\mathsf{trgen}}(\mathcal{P})$ to generate
the truncation pair
$(\left[\mathsf{r}\right],\llbracket\mathsf{r}^{d}\rrbracket)$. Online: –
$P_{0},P_{j}$, for $j\in\\{1,2\\}$, compute
$\left[\Psi\right]_{j}=-\sum_{i=1}^{\mathsf{n}}((\beta_{\mathsf{x}_{i}}+\gamma_{\mathsf{x}_{i}})\left[\alpha_{\mathsf{y}_{i}}\right]_{j}+(\beta_{\mathsf{y}_{i}}+\gamma_{\mathsf{y}_{i}})\left[\alpha_{\mathsf{x}_{i}}\right]_{j})-\left[\mathsf{r}\right]_{j}$
and set
$\left[{(\mathsf{z}-\mathsf{r})^{\star}}\right]_{j}=\left[\Psi\right]_{j}+\left[\chi\right]_{j}$.
– $P_{1},P_{0}$ $\mathsf{jmp\mbox{-}send}$
$\left[{(\mathsf{z}-\mathsf{r})}^{\star}\right]_{1}$ to $P_{2}$ and
$P_{2},P_{0}$ $\mathsf{jmp\mbox{-}send}$
$\left[{(\mathsf{z}-\mathsf{r})}^{\star}\right]_{2}$ to $P_{1}$. –
$P_{1},P_{2}$ locally compute
$(\mathsf{z}-\mathsf{r})^{\star}=\left[{(\mathsf{z}-\mathsf{r})}^{\star}\right]_{1}+\left[{(\mathsf{z}-\mathsf{r})}^{\star}\right]_{2}$
and set
$(\mathsf{z}-\mathsf{r})={(\mathsf{z}-\mathsf{r})}^{\star}+\sum_{i=1}^{\mathsf{n}}(\beta_{\mathsf{x}_{i}}\beta_{\mathsf{y}_{i}})+\psi$.
– $P_{1},P_{2}$ locally truncate $(\mathsf{z}-\mathsf{r})$ to obtain
${(\mathsf{z}-\mathsf{r})}^{d}$ and execute
$\Pi_{\mathsf{jsh}}(P_{1},P_{2},{(\mathsf{z}-\mathsf{r})}^{d})$ to generate
$\llbracket{(\mathsf{z}-\mathsf{r})}^{d}\rrbracket$. – Servers locally compute
$\llbracket\mathsf{z}\rrbracket=\llbracket{(\mathsf{z}-\mathsf{r})}^{d}\rrbracket+\llbracket\mathsf{r}^{d}\rrbracket$
.

Figure 14: 3PC: Dot Product Protocol with Truncation

######  Lemma 3.12 (Communication).

Protocol $\Pi_{\mathsf{dotpt}}$ (Fig. 14) requires an amortized communication
of $15\ell$ bits in the preprocessing phase and requires $1$ round and an
amortized communication of $3\ell$ bits in the online phase.

###### Proof.

During the preprocessing phase, servers execute the preprocessing phase of
$\Pi_{\mathsf{dotp}}$, resulting in an amortized communication of $3\ell$ bits
(Lemma 3.10). In parallel, servers execute one instance of
$\Pi_{\mathsf{trgen}}$ protocol resulting in an additional communication of
$12\ell$ bits (Lemma 3.11).

The online phase follows from that of $\Pi_{\mathsf{dotp}}$ protocol except
that, now, $P_{1},P_{2}$ compute additive shares of $\mathsf{z}-\mathsf{r}$,
where $\mathsf{z}=\vec{\mathbf{x}}\odot\vec{\mathbf{y}}$, which is achieved
using two executions of $\Pi_{\mathsf{jmp}}$ in parallel. This requires one
round and an amortized communication cost of $2\ell$ bits. $P_{1},P_{2}$ then
jointly share the truncated value of $\mathsf{z}-\mathsf{r}$ with $P_{0}$,
which requires one round and $\ell$ bits. However, this step can be deferred
till the end for multiple dot product with truncation instances, which
amortizes the cost. ∎

##### Secure Comparison

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.

##### Activation Functions

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

######  Lemma 3.13 (Communication).

Protocol $\mathsf{relu}$ requires an amortized communication of $21\ell-6$
bits in the preprocessing phase and requires $\log\ell+3$ rounds and an
amortized communication of $16\ell-6$ bits in the online phase.

###### Proof.

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 [45, 43, 15]. 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 [45,
43, 15] is given below:

$\displaystyle\mathsf{sig}(\mathsf{v})=\left\\{\begin{array}[]{lll}0&\quad\mathsf{v}<-\frac{1}{2}\\\
\mathsf{v}+\frac{1}{2}&\quad-\frac{1}{2}\leq\mathsf{v}\leq\frac{1}{2}\\\
1&\quad\mathsf{v}>\frac{1}{2}\end{array}\right.$

######  Lemma 3.14 (Communication).

Protocol $\mathsf{sig}$ requires an amortized communication of $39\ell-9$ bits
in the preprocessing phase and requires $\log\ell+4$ rounds and an amortized
communication of $29\ell-9$ bits in the online phase.

###### Proof.

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. ∎

##### Maxpool, Matrix Operations and Convolutions

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.

$\mathsf{CV}\left(\begin{bmatrix}\mathsf{x}_{1}&\mathsf{x}_{2}&\mathsf{x}_{3}\\\
\mathsf{x}_{4}&\mathsf{x}_{5}&\mathsf{x}_{6}\\\
\mathsf{x}_{7}&\mathsf{x}_{8}&\mathsf{x}_{9}\end{bmatrix},\begin{bmatrix}\mathsf{k}_{1}&\mathsf{k}_{2}\\\
\mathsf{k}_{3}&\mathsf{k}_{4}\end{bmatrix}\right)=\begin{bmatrix}\mathsf{x}_{1}&\mathsf{x}_{2}&\mathsf{x}_{4}&\mathsf{x}_{5}\\\
\mathsf{x}_{2}&\mathsf{x}_{3}&\mathsf{x}_{5}&\mathsf{x}_{6}\\\
\mathsf{x}_{4}&\mathsf{x}_{5}&\mathsf{x}_{7}&\mathsf{x}_{8}\\\
\mathsf{x}_{5}&\mathsf{x}_{6}&\mathsf{x}_{8}&\mathsf{x}_{9}\end{bmatrix}\begin{bmatrix}\mathsf{k}_{1}\\\
\mathsf{k}_{2}\\\ \mathsf{k}_{3}\\\ \mathsf{k}_{4}\end{bmatrix}$

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 [56] (cf. “Linear and
Convolutional Layer”) and [54] for more details.

##  4 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.

##### Secret Sharing Semantics

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

###  4.1 4PC Joint Message Passing Primitive

The $\mathsf{jmp4}$ primitive enables two servers $P_{i}$, $P_{j}$ to send a
common value $\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$ to a third server $P_{k}$,
or identify a $\mathsf{TTP}$ in case of any inconsistency. This primitive is
analogous to $\mathsf{jmp}$ (Fig. 2) in spirit but is significantly optimized
and free from broadcast calls. Similar to the 3PC counterpart, each server
maintains a bit and $P_{i}$ sends the value, and $P_{j}$ the hash of it to
$P_{k}$. $P_{k}$ sets its inconsistency bit to $1$ when the (value, hash) pair
is inconsistent. This is followed by relaying the bit to all the servers, who
exchange it among themselves and agree on the bit that forms majority ($1$
indicates the presence of inconsistency, and $0$ indicates consistency). The
presence of an honest majority among $P_{i},P_{j},P_{l}$, guarantees agreement
on the presence/absence of an inconsistency as conveyed by $P_{k}$. Observe
that inconsistency can only be caused either due to a corrupt sender sending
an incorrect value (or hash), or a corrupt receiver falsely announcing the
presence of inconsistency. Hence, the fourth server, $P_{l}$, can safely be
employed as $\mathsf{TTP}$. The ideal functionality appears in Fig. 15, and
the protocol appears in Fig. 16.

######  Notation 4.1.

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 [12]. 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.

$\mathcal{F}_{\mathsf{jmp4}}$ interacts with the servers in $\mathcal{P}$ and
the adversary $\mathcal{S}$. Step 1: $\mathcal{F}_{\mathsf{jmp}}$ receives
$(\mathsf{Input},\mathsf{v}_{s})$ from senders $P_{s}$ for $s\in\\{i,j\\}$,
$(\mathsf{Input},\bot)$ from receiver $P_{k}$ and fourth server $P_{l}$, while
it receives $(\mathsf{Select},\mathsf{ttp})$ from $\mathcal{S}$. Here
$\mathsf{ttp}$ is a boolean value, with a $1$ indicating that
$\mathsf{TTP}=P_{l}$ should be established. Step 2: If
$\mathsf{v}_{i}=\mathsf{v}_{j}$ and $\mathsf{ttp}=0$, or if $\mathcal{S}$ has
corrupted $P_{l}$, set
$\mathsf{msg}_{i}=\mathsf{msg}_{j}=\mathsf{msg}_{l}=\bot,\mathsf{msg}_{k}=\mathsf{v}_{i}$
and go to Step 4. Step 3: Else : Set
$\mathsf{msg}_{i}=\mathsf{msg}_{j}=\mathsf{msg}_{k}=\mathsf{msg}_{l}=P_{l}$.
Step 4: Send $(\mathsf{Output},\mathsf{msg}_{s})$ to $P_{s}$ for
$s\in\\{0,1,2,3\\}$.

Figure 15: 4PC: Ideal functionality for $\mathsf{jmp4}$ primitive

$P_{s}\in\mathcal{P}$ initializes an inconsistency bit $\mathsf{b}_{s}=0$. If
$P_{s}$ remains silent instead of sending $\mathsf{b}_{s}$ in any of the
following rounds, the recipient sets $\mathsf{b}_{s}$ to $1$. Send Phase:
$P_{i}$ sends $\mathsf{v}$ to $P_{k}$. Verify Phase: $P_{j}$ sends
$\mathsf{H}(\mathsf{v})$ to $P_{k}$. – $P_{k}$ sets $\mathsf{b}_{k}=1$ if the
received values are inconsistent or if the value is not received. – $P_{k}$
sends $\mathsf{b}_{k}$ to all servers. $P_{s}$ for $s\in\\{i,j,l\\}$ sets
$\mathsf{b}_{s}=\mathsf{b}_{k}$. – $P_{s}$ for $s\in\\{i,j,l\\}$ mutually
exchange their bits. $P_{s}$ resets $\mathsf{b}_{s}=\mathsf{b}^{\prime}$ where
$\mathsf{b}^{\prime}$ denotes the bit which appears in majority among
$\mathsf{b}_{i},\mathsf{b}_{j},\mathsf{b}_{l}$. – All servers set
$\mathsf{TTP}=P_{l}$ if $\mathsf{b}^{\prime}=1$, terminate otherwise.

Figure 16: 4PC: Joint Message Passing Primitive

######  Lemma 4.2 (Communication).

Protocol $\Pi_{\mathsf{jmp4}}$ (Fig. 16) requires $1$ round and an amortized
communication of $\ell$ bits in the online phase.

###### Proof.

Server $P_{i}$ sends the value $\mathsf{v}$ to $P_{k}$ while $P_{j}$ sends
hash of the same to $P_{k}$. This accounts for one round of communication.
Values sent by $P_{j}$ for several instances can be concatenated and hashed to
obtain a single value. Hence the cost of sending the hash gets amortized over
multiple instances. Similarly, the two round exchange of inconsistency bits to
establish a $\mathsf{TTP}$ can be combined for multiple instances, thereby
amortizing this cost. Thus, the amortized cost of this protocol is $\ell$
bits. ∎

###  4.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.

##### Sharing Protocol

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

Preprocessing: – If $P_{i}=P_{0}$ : $P_{0},P_{3},P_{j}$, for $j\in\\{1,2\\}$,
together sample random
$\left[\alpha_{\mathsf{v}}\right]_{j}\in\mathbb{Z}_{2^{\ell}}$, while
$\mathcal{P}$ sample random $\gamma_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$. –
If $P_{i}=P_{1}$ : $P_{0},P_{3},P_{1}$ together sample random
$\left[\alpha_{\mathsf{v}}\right]_{1}\in\mathbb{Z}_{2^{\ell}}$, while
$\mathcal{P}$ sample a random
$\left[\alpha_{\mathsf{v}}\right]_{2}\in\mathbb{Z}_{2^{\ell}}$. Also,
$P_{1},P_{2},P_{3}$ sample random
$\gamma_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$. – If $P_{i}=P_{2}$: Analogous
to the case when $P_{i}=P_{1}$. – If $P_{i}=P_{3}$: $P_{0},P_{3},P_{j}$, for
$j\in\\{1,2\\}$, sample random
$\left[\alpha_{\mathsf{v}}\right]_{j}\in\mathbb{Z}_{2^{\ell}}$.
$P_{1},P_{2},P_{3}$ together sample random
$\gamma_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$. Online: – If $P_{i}=P_{0}$ :
$P_{0}$ computes $\beta_{\mathsf{v}}=\mathsf{v}+\alpha_{\mathsf{v}}$ and sends
$\beta_{\mathsf{v}}$ to $P_{1}$. $P_{0},P_{1}$ $\mathsf{jmp4\mbox{-}send}$
$\beta_{\mathsf{v}}$ to $P_{2}$. – If $P_{i}=P_{j}$, for $j\in\\{1,2\\}$ :
$P_{j}$ computes $\beta_{\mathsf{v}}=\mathsf{v}+\alpha_{\mathsf{v}}$, sends
$\beta_{\mathsf{v}}$ to $P_{3-j}$. $P_{1},P_{2}$ $\mathsf{jmp4\mbox{-}send}$
$\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}$ to $P_{0}$. – If $P_{i}=P_{3}$:
$P_{3}$ sends
$\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}=\mathsf{v}+\alpha_{\mathsf{v}}+\gamma_{\mathsf{v}}$
to $P_{0}$. $P_{3},P_{0}$ $\mathsf{jmp4\mbox{-}send}$
$\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}$ to both $P_{1}$ and $P_{2}$.

Figure 17: 4PC: Generating $\llbracket\mathsf{v}\rrbracket$-shares by server
$P_{i}$

######  Lemma 4.3 (Communication).

In the online phase, $\Pi_{\mathsf{sh4}}$ (Fig. 17) requires $2$ rounds and an
amortized communication of $2\ell$ bits when $P_{0},P_{1},P_{2}$ share a
value, whereas it requires an amortized communication of $3\ell$ bits when
$P_{3}$ shares a value.

###### Proof.

The proof for $P_{0},P_{1},P_{2}$ sharing a value follows from 3.3. For the
case when $P_{3}$ wants to share a value $\mathsf{v}$, it first sends
$\beta_{\mathsf{v}}+\gamma_{\mathsf{v}}$ to $P_{0}$ which requires one round
and $\ell$ bits of communication. This is followed by $2$ parallel calls to
$\Pi_{\mathsf{jmp4}}$ which together require one round and an amortized
communication of $2\ell$ bits. ∎

##### Joint Sharing Protocol

Protocol $\Pi_{\mathsf{jsh4}}$ enables a pair of (unordered) servers
$(P_{i},P_{j})$ to jointly generate a $\llbracket\cdot\rrbracket$-sharing of
value $\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$ known to both of them. In case of
an inconsistency, the server outside the computation serves as a
$\mathsf{TTP}$. The protocol is described in Fig. 18.

When $P_{3},P_{0}$ want to jointly share a value $\mathsf{v}$ which is
available in the preprocessing phase, protocol $\Pi_{\mathsf{jsh4}}$ can be
performed with a single element of communication (as opposed to $2$ elements
in Fig. 18). $P_{0},P_{3}$ can jointly share $\mathsf{v}$ as follows.
$P_{0},P_{3},P_{1}$ sample a random $\mathsf{r}\in\mathbb{Z}_{2^{\ell}}$ and
set $\left[\alpha_{\mathsf{v}}\right]_{1}=\mathsf{r}$. $P_{0},P_{3}$ set
$\left[\alpha_{\mathsf{v}}\right]_{2}=-(\mathsf{r}+\mathsf{v})$ and
$\mathsf{jmp4\mbox{-}send}$ $\left[\alpha_{\mathsf{v}}\right]_{2}$ to $P_{2}$.
This is followed by servers locally setting
$\gamma_{\mathsf{v}}=\beta_{\mathsf{v}}=0$.

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.

######  Lemma 4.4 (Communication).

In the online phase, $\Pi_{\mathsf{jsh4}}$ (Fig. 18) requires $1$ round and an
amortized communication of $2\ell$ bits when $(P_{3},P_{s})$ for