# Hawk: Accurate and Fast Privacy-Preserving Machine Learning Using Secure
Lookup Table Computation

Hamza Saleem  University of Southern California<EMAIL_ADDRESS>,  Amir
Ziashahabi  University of Southern California<EMAIL_ADDRESS>,  Muhammad
Naveed  University of Southern California<EMAIL_ADDRESS>and  Salman
Avestimehr  University of Southern California<EMAIL_ADDRESS>
###### Abstract.

Training machine learning models on data from multiple entities without direct
data sharing can unlock applications otherwise hindered by business, legal, or
ethical constraints. In this work, we design and implement new privacy-
preserving machine learning protocols for logistic regression and neural
network models. We adopt a two-server model where data owners secret-share
their data between two servers that train and evaluate the model on the joint
data. A significant source of inefficiency and inaccuracy in existing methods
arises from using Yao’s garbled circuits to compute non-linear activation
functions. We propose new methods for computing non-linear functions based on
secret-shared lookup tables, offering both computational efficiency and
improved accuracy.

Beyond introducing leakage-free techniques, we initiate the exploration of
relaxed security measures for privacy-preserving machine learning. Instead of
claiming that the servers gain no knowledge during the computation, we contend
that while some information is revealed about access patterns to lookup
tables, it maintains $\epsilon$-$d_{\mathcal{X}}$-privacy. Leveraging this
relaxation significantly reduces the computational resources needed for
training. We present new cryptographic protocols tailored to this relaxed
security paradigm and define and analyze the leakage. Our evaluations show
that our logistic regression protocol is up to $9\times$ faster, and the
neural network training is up to $688\times$ faster than SecureML (Mohassel
and Zhang, 2017). Notably, our neural network achieves an accuracy of $96.6\%$
on MNIST in 15 epochs, outperforming prior benchmarks (Mohassel and Zhang,
2017; Wagh et al., 2019) that capped at $93.4\%$ using the same architecture.

secure multi-party computation, privacy-preserving ML

††journalyear: YYYY††journalvolume: YYYY††journalnumber: X††doi:
XXXXXXX.XXXXXXX

##  1\. Introduction

Machine learning (ML) has become an indispensable tool in various domains,
from advertising and healthcare to finance and retail, enabling the training
of predictive models. The accuracy of these models is significantly enhanced
when trained on vast datasets aggregated from diverse sources. However,
numerous challenges, such as privacy concerns, stringent regulations, and
competitive business landscapes, often hinder collaborative data-sharing
endeavors.

Privacy-Preserving Machine Learning (PPML) using secure computation allows
multiple entities to train models on their aggregated data without revealing
their individual datasets. In this paradigm, data owners distribute their
private data among several non-colluding servers using secret-sharing
techniques. These servers then perform training on the combined data without
gaining insights into the individual datasets.

Past works on PPML have focused on training logistic regression models (Wu et
al., 2013; Mohassel and Zhang, 2017) and neural networks (Mohassel and Zhang,
2017; Wagh et al., 2019; Demmler et al., 2015; Mohassel and Rindal, 2018). A
significant bottleneck in existing work is using expensive protocols, such as
Yao’s garbled circuits, for computing non-linear activation functions.
Furthermore, prior works (Mohassel and Zhang, 2017; Wagh et al., 2019) resort
to non-standard or approximate activation functions, resulting in accuracy
loss.

In this work, we present two novel protocols $\textsc{Hawk}_{\text{Single}}$
and $\textsc{Hawk}_{\text{Multi}}$, designed for accurate and efficient
computation of activation functions and their derivatives. These protocols
leverage secret shared precomputed lookup tables. We begin by introducing the
$\textsc{Hawk}_{\text{Single}}$ protocol, which offers plaintext accuracy and
robust security in a semi-honest adversary model. Its primary limitation,
however, is its reliance on consuming one lookup table for each function
computation, necessitating a vast number of such tables. To mitigate this
limitation, we subsequently introduce $\textsc{Hawk}_{\text{Multi}}$, enabling
lookup table reusability. The $\textsc{Hawk}_{\text{Multi}}$ protocol poses
several security and efficiency challenges, which we further address to
achieve a fast and secure protocol. Although methods such as Oblivious RAM
(ORAM) (Goldreich and Ostrovsky, 1996) can be employed to eliminate
information leakage in our context, we opt for a slightly relaxed security
model to prioritize performance improvements. Our
$\textsc{Hawk}_{\text{Multi}}$ protocol permits table reuse but at the cost of
revealing limited information about the access patterns. We rigorously analyze
the leakage of the $\textsc{Hawk}_{\text{Multi}}$ protocol and prove that it
preserves $\epsilon$-$d_{\mathcal{X}}$-privacy for the leaked access patterns.

Building on $\textsc{Hawk}_{\text{Single}}$ and $\textsc{Hawk}_{\text{Multi}}$
we develop efficient PPML protocols tailored for logistic regression and
neural network training in a two-server secure computation environment. Our
evaluations, conducted on Amazon EC2, showcase the performance gains of our
system.

###  1.1. Our Contributions

Computing Standard Activation Functions. We propose a novel method to
accurately compute activation functions in a secure computation setting and
achieve accuracy similar to plaintext training. Past methods either use non-
standard activations or approximate them. As shown in Figure 9, using non-
standard activation functions may cause accuracy to plummet to random guess
levels, potentially affecting convergence. Hence, using standard activation
functions is crucial to harness machine learning advancements rather than
relying on makeshift functions for secure computation.

Generic Method for Precise Univariate Function Computation. We introduce a
universal method for securely computing any univariate function. It can be
directly used to compute any univariate activation function, which constitutes
most of the activation functions used in all but the last layer of a neural
network. Our method computes activations much faster than the state-of-the-
art. This method creates secret shared lookup tables for all possible inputs;
we use recent advances in low-precision machine learning to confine the size
of the lookup tables.

Precise Computation of Multivariate Functions. We demonstrate the application
of our method to compute multivariate activations, notably $\mathsf{Softmax}$.
We highlight that this is the first method to compute $\mathsf{Softmax}$ in a
secure computation setting accurately.

Beyond Activation Functions. While we demonstrate the applicability of our
protocols for activation function computation, their potential extends far
beyond these specific functions. The underlying principle of precomputed
lookup tables can be applied to a wide range of MPC applications where the
input domain can be bounded. For example, in private set intersection (Hazay
and Venkitasubramaniam, 2017), our protocol can enable efficient comparison of
elements in private sets. Similarly, secure auctions (Bogetoft et al., 2006)
can benefit from lookup tables to ensure privacy while evaluating bids.
Furthermore, our protocols can be used to securely compute histograms (Mazloom
and Gordon, 2018), enabling private data analysis. These applications
highlight the versatility of our protocols for MPC across various domains.

An Alternate Representation for DReLU Activation. We present an alternate
representation of the $\mathsf{DReLU}$ activation function for fixed-point
numbers, which allows us to reduce the entries in the lookup table for
$\mathsf{DReLU}$ by a factor of $2^{11}$.

Relaxed Security Setting. In addition to introducing leakage-free methods
using $\mathsf{Hawk}_{\mathsf{Single}}$, we initiate the study of a new
security model for PPML. This relaxed model allows some information leakage
about access patterns, but the leakage is proven to preserve
$d_{\mathcal{X}}$-privacy. We leverage this model to develop
$\mathsf{Hawk}_{\mathsf{Multi}}$ protocol to significantly reduce
computational resources while training.

Experimental results. We implement our framework and perform various
experiments for training and inference of logistic regression and neural
networks using six different datasets in both LAN and WAN settings. Section 8
shows that our protocols are significantly faster than state-of-the-art in a
two-party setting and achieve accuracy similar to plaintext training.

##  2\. Related Work

This section overviews prior studies across fields such as access pattern
privacy, PPML, and secure MPC pertinent to our work.

Access Pattern Privacy literature focuses on achieving full or partial
obliviousness during data retrieval. ORAM (Goldreich and Ostrovsky, 1996)
algorithms provide complete obliviousness by ensuring that the physical access
patterns for any two equal-length logical patterns are indistinguishable.
While ORAM addresses access pattern leakage and has been extensively studied
in both client-server (Goldreich and Ostrovsky, 1996; Shi et al., 2011;
Stefanov et al., 2018; Asharov et al., 2020; Pinkas and Reinman, 2010) and
multi-party (Doerner and Shelat, 2017; Wang et al., 2014; Zahur et al., 2016;
Pinkas and Reinman, 2010; Gordon et al., 2012) settings, it carries an
inevitable overhead of $\Omega(log(n))$ (Goldreich and Ostrovsky, 1996; Boyle
and Naor, 2016; Larsen and Nielsen, 2018).

A natural approach for circumventing this overhead is relaxing full
obliviousness for a weaker privacy notion, such as differential privacy.
Differential privacy introduces a neighborhood concept and ensures closeness
between neighboring access sequences rather than all sequences. Despite the
relaxation, (Persiano and Yeo, 2023) show that the $\Omega(log(n))$ lower
bound also applies to DP-ORAM (Wagh et al., 2018) structures. Nonetheless,
various studies have employed differentially private access patterns to offer
performance enhancements for specific algorithms, such as searchable symmetric
encryption (SSE) (Shang et al., 2021), sorting and merging of lists (Chan et
al., 2022), histograms (Allen et al., 2019), and graph-parallel computation
(Mazloom and Gordon, 2018). The performance enhancement for these algorithms
stems from the fact that they generally rely on a full memory scan. Therefore,
the problem of access pattern privacy is reduced to hiding the number of
accesses for each element. For lookup tables, where only a limited number of
elements are accessed, these algorithms fail to deliver an efficient solution.

PPML Using Secure MPC. Previous MPC studies have explored decision trees
(Lindell and Pinkas, 2000), K-means clustering (Jagannathan and Wright, 2005;
Bunn and Ostrovsky, 2007), SVM (Yu et al., 2006; Vaidya et al., 2008), and
regression techniques (Wenliang Du and Atallah, 2001; Du et al., 2004; Sanil
et al., 2004; Slavkovic et al., 2007). However, these works incur high
efficiency overheads and lack implementation. SecureML (Mohassel and Zhang,
2017) provides protocols for secure training and inference of linear
regression, logistic regression, and neural networks in a two-server setting.
They present alternate functions to approximate the non-linear activations
($\mathsf{Sigmoid}$, $\mathsf{ReLU}$, and $\mathsf{Softmax}$), which are
evaluated using garbled circuits. However, garbled circuits have a high
communication overhead, and approximating activation functions reduces the
model’s accuracy. QUOTIENT (Agrawal et al., 2019) presents protocols for
neural network training in a two-server setting, utilizing quantization for
various network components. However, using garbled circuits and oblivious
transfer produces high overheads.

SecureNN (Wagh et al., 2019) and ABY3 (Mohassel and Rindal, 2018) present
privacy-preserving neural network training protocols in a three-server honest
majority setting. Like SecureML, they approximate $\mathsf{Softmax}$, which
reduces the model accuracy, as discussed in Section 8.4. Falcon (Wagh et al.,
2021) combines techniques from SecureNN (Wagh et al., 2019) and ABY3 (Mohassel
and Rindal, 2018) to improve the training performance. Our two-server
protocol, as shown in Section 8, outperforms these in efficiency. Another
pertinent work in the three-server setting is Pika (Wagh, 2022a), which adopts
a lookup table-centric approach to computing non-linear functions. Pika relies
on Private Information Retrieval (PIR) and Function Secret Sharing (FSS)
(Boyle et al., 2015) to hide access patterns. Despite providing full
obliviousness, their protocol has an overhead of $O(n)$ stemming from FFS key
generation, FFS evaluation, and dot product operation with all lookup table
elements. In fact, $\Omega(n)$ overhead is intrinsic to PIR (Beimel et al.,
2004). Pika only provides performance evaluations for generic functions and
inference tasks. We compare our protocols with Pika for sigmoid function
computation in Appendix F.

A parallel line of work focuses on secure neural network inference. A party or
a group of parties evaluates the model on a client’s private data, keeping the
model private. Gilad-Barach et al.(Dowlin et al., 2016) employ HE for secure
inference, albeit with accuracy compromises. MiniONN (Liu et al., 2017)
optimizes the secure inference protocols of SecureML (Mohassel and Zhang,
2017) by reducing the offline cost of matrix multiplication. Using a third-
party dealer, Chameleon (Riazi et al., 2018) removes the oblivious transfer
protocols required for multiplication. Gazelle (Juvekar et al., 2018)
optimizes linear operations using specialized packing schemes for HE.
Baccarini et al. (Baccarini et al., 2023) present ring-based protocols for MPC
operations applied to NN inference. SIRNN (Rathee et al., 2021) presents a
lookup table based protocol that uses digit decomposition with oblivious
transfers to compute non-linear functions efficiently. We compare our
protocols with SIRNN for sigmoid function computation in Appendix F.

Other PPML Approaches. Shokri and Shmatikov (Shokri and Shmatikov, 2015)
explore privacy-preserving neural network training with horizontally
partitioned data. The servers train separately and share only parameter
updates, using differential privacy (Dwork and Roth, 2014) to minimize
leakage. Wu et al.(Wu et al., 2013) and Kim et al.(Kim et al., 2017) employ
homomorphic encryption for logistic regression, approximating the logistic
function with polynomials. The complexity is exponential in the polynomial
degree, and the approximation reduces the model accuracy. Crawford et al.
(Crawford et al., 2018) use fully homomorphic encryption to train logistic
regression models using encrypted lookup tables. However, the approach incurs
high overhead, and using low-precision numbers reduces the model’s accuracy.
In contrast, our protocols are orders of magnitude more efficient and achieve
accuracy similar to plaintext training.

We primarily compare our techniques with SecureML (Mohassel and Zhang, 2017)
as this is the only work we found for logistic regression and neural network
training in a two-server client-aided setting. While recent works exist
(Agrawal et al., 2019; Wagh et al., 2019; Mohassel and Rindal, 2018; Wagh et
al., 2021), their settings differ, making direct comparisons challenging. We
compare our online cost with theirs as they lack an offline phase. We further
remark that the idea of employing lookup tables for function evaluation is not
novel with past works (Damgrd et al., 2017; Dessouky et al., 2017; Keller et
al., 2017; Boyle et al., 2015; Rathee et al., 2021) suggesting circuit and
FSS-based protocols. However, these works necessitate representing functions
as either boolean or arithmetic circuits, with each gate evaluated using a
lookup table. It is non-trivial to directly represent functions like
exponential, logarithm, etc, used in ML activation, as circuits. This
complexity typically leads to reliance on circuit-friendly approximations,
such as the Taylor series, which compromises accuracy and introduces
inefficiencies (see Figure 9). Our lookup table based protocols are
fundamentally different as they enable direct computation of ML activations
without resorting to circuit approximations. Furthermore, our main
contribution is the $\textsc{Hawk}_{\text{Multi}}$ protocol that allows for
the reuse of a lookup table by leveraging metric differentially private access
patterns, missing in prior research.

##  3\. Preliminaries

###  3.1. Machine Learning

Logistic Regression is a binary classification algorithm commonly, often used
for tasks like medical diagnosis. Given $n$ training examples
$\boldsymbol{x_{1},x_{2},...,x_{n}}\in\mathbb{R}^{D}$ with binary labels
$y_{1},y_{2},...,y_{n}$, the goal is to learn a coefficient vector
$\boldsymbol{w}\in\mathbb{R}^{D}$ which minimizes the distance between
$g(\boldsymbol{x_{i}})=f(\boldsymbol{x_{i}.w})$ and the true label $y_{i}$.
The activation function $f$ is used to bound the dot product of
$\boldsymbol{x_{i}}$ and $\boldsymbol{w}$ between 0 and 1 for binary
classification. The $\mathsf{Sigmoid}$ function is typically chosen for $f$,
defined as: $f(z)=\frac{1}{1+e^{-z}}$. To learn $\boldsymbol{w}$, we define a
cost function $C(\boldsymbol{w})$ and find $\boldsymbol{w}$ using the
optimization $\operatorname*{arg\,min}_{\boldsymbol{w}}C(\boldsymbol{w})$. We
use the cross-entropy cost function defined as: $C_{i}(\boldsymbol{w})=-y\log
f(\boldsymbol{x_{i}.w})-(1-y)\log(1-f(\boldsymbol{x_{i}.w}))$, with the
overall cost being the average across all examples:
$C(\boldsymbol{w})=\frac{1}{n}\sum_{i=1}^{n}C_{i}(\boldsymbol{w})$.

Neural Networks extend logistic regression to handle more complex tasks. A
neural network consists of $l$ layers where each layer $i$ contains $d_{i}$
neurons. The output of each neuron is computed by applying a non-linear
activation to the dot product of its coefficient vector $\boldsymbol{w}$ and
the input $\boldsymbol{x}$. Activation functions, like the ReLU:
$f(z)=max(0,z)$, are commonly used. The first layer receives inputs from the
dataset, with each subsequent layer performing calculations and forwarding the
output to the next layer using ‘forward propagation’. For classification, the
probability of the input example belonging to each class is computed by
applying the $\mathsf{Softmax}$ function:
$f(z_{i})=\frac{e^{z_{i}}}{\sum_{i=1}^{d_{l}}e^{z_{i}}}$ to each neuron in the
output layer, where $d_{l}$ denotes the total neurons in the output layer. The
$\mathsf{Softmax}$ output is a probability value between 0 and 1 for each
class, summing up to 1. To train the network, we apply the Stochastic Gradient
Descent (SGD) algorithm and update the coefficients of all neurons
recursively, starting from the last layer and moving towards the first layer
in a ‘backward propagation’ step. For further details on related ML concepts
like SGD and batching, refer to Appendix A.

###  3.2. Secure Computation

Secure computation allows parties to compute a joint function of their data
while keeping their data private.

Preprocessing Model of Secure Computation divides a protocol into two phases:
a data-independent offline phase used to create correlated randomness and an
online phase. This model allows most of the heavy computation to be delegated
to the offline preprocessing phase, rendering the online phase more
computationally efficient.

Additive Secret-Sharing. In a secure two-party computation (2PC) setting,
secret values are additively secret-shared between the parties $P_{0}$ and
$P_{1}$. To share a secret $x\in\mathbb{Z}_{n}$, a random $r\in\mathbb{Z}_{n}$
is generated. The share for the first party is computed as $\langle
x\rangle_{0}=r$, while the second party’s share is $\langle
x\rangle_{1}=x-r\pmod{n}$. To reconstruct $x$, one party sends its share to
the other party, which then computes $x=\langle x\rangle_{0}+\langle
x\rangle_{1}\pmod{n}$, denoted as $Rec(x_{0},x_{1})$. We use $\langle
x\rangle_{i}$ to denote $P_{i}$’s share of $x$.

Secure Addition. The parties can non-interactively add two secret-shared
values $x$ and $y$ where each $P_{i}$ computes $\langle z\rangle_{i}=\langle
x\rangle_{i}+\langle y\rangle_{i}\pmod{n}$ as their share of the sum.

Secure Multiplication. To multiply two secret-shared values $x$ and $y$, the
parties use Beaver’s multiplication triples (Beaver, 1991). Initially, the
parties possess shares of $a$, $b$, and $c$ where $a$ and $b$ are random
values in $\mathbb{Z}_{n}$ and $c=ab\pmod{n}$. Each party $P_{i}$ computes
$\langle d\rangle_{i}=\langle x\rangle_{i}-\langle a\rangle_{i}\pmod{n}$ and
$\langle e\rangle_{i}=\langle y\rangle_{i}-\langle b\rangle_{i}\pmod{n}$ and
compute $d=Rec(d_{0},d_{1})$ and $e=Rec(e_{0},e_{1})$ to reconstruct $d$ and
$e$. Each party $P_{i}$ then computes $\langle z\rangle_{i}=\langle
x\rangle_{i}e+\langle y\rangle_{i}d+\langle c\rangle_{i}-ide$ as their share
of the product.

###  3.3. Metric Differential Privacy ($d_{\mathcal{X}}$-privacy)

######  Definition 0.

A randomized algorithm $\mathcal{L}$ is $\epsilon$-differentially private if
for all datasets $D_{1}$ and $D_{2}$ differing in a single value and for all
$S\subset Range(\mathcal{L})$: $Pr[\mathcal{L}(D_{1})\in S]\leq
e^{\epsilon}Pr[\mathcal{L}(D_{2})\in S]$, where the probability space is over
the coin flips of the mechanism $\mathcal{L}$.

While the above definition captures differential privacy in a centralized
setting, there are scenarios where data privacy at the individual level is
paramount. Local Differential Privacy (LDP) obfuscates individual data records
when clients distrust the central curator, altering data before statistical
analysis.

######  Definition 0.

A randomized algorithm $\mathcal{L}$ provides $\epsilon$-LDP if for each pair
of inputs $x$ and $x^{\prime}$ and for all $S\subset Range(\mathcal{L})$:
$Pr[\mathcal{L}(x)\in S]\leq e^{\epsilon}Pr[\mathcal{L}(x^{\prime})\in S]$.

In this work, we adopt a natural generalization of the conventional
differential privacy (Dwork and Roth, 2014) presented by Chatzikokolakis et
al. (Chatzikokolakis et al., 2013). This extension is particularly relevant
when the domain $\mathcal{X}$ is viewed as a metric space. Termed as metric
differential privacy or $d_{\mathcal{X}}$-privacy, this approach is adept at
modeling situations where indistinguishability is best expressed through a
metric between secret inputs. Geo-Indistinguishability is presented as a
canonical example for $d_{\mathcal{X}}$-privacy (Chatzikokolakis et al., 2013;
Andrés et al., 2013), where a user wishes to share their location with a
service to receive nearby restaurant recommendations. Instead of disclosing
the precise coordinates, the user can employ $d_{\mathcal{X}}$-privacy to
share an approximated location to receive relevant suggestions without
compromising their exact whereabouts.

The input domain $\mathcal{X}$ for an activation function can be viewed as a
metric space. For instance, if for some $x,x_{1},x_{2}\in\mathcal{X}$,
$|x-x_{1}|<|x-x_{2}|$, then usually, $f(x_{1})$ provides a better
approximation of $f(x)$ than $f(x_{2})$. Mechanisms from standard or local DP
can be adapted to suit $d_{\mathcal{X}}$-privacy by choosing a fitting metric
for the confidential data. We leverage local $d_{\mathcal{X}}$-privacy to
obfuscate each individual table lookup in our $\mathsf{Hawk}_{\mathsf{Multi}}$
protocol, ensuring enhanced privacy from computing servers.

######  Definition 0.

A randomized algorithm $\mathcal{L}$ provides local
$\epsilon$-$d_{\mathcal{X}}$-privacy if for each pair of inputs $x$ and
$x^{\prime}$ and for all $S\subset Range(\mathcal{L})$: $Pr[\mathcal{L}(x)\in
S]\leq e^{\epsilon.d_{\mathcal{X}}(x,x^{\prime})}Pr[\mathcal{L}(x^{\prime})\in
S]$, where $d_{\mathcal{X}}(.,.)$ is a distance metric.

We define the distance metric as the absolute difference between two points,
i.e., $d_{\mathcal{X}}(x,x^{\prime})=|x-x^{\prime}|$. We choose
$d_{\mathcal{X}}$-privacy as the noising mechanism to obfuscate table lookups
while ensuring the noised value remains close to the original. This proximity
is crucial for maintaining model accuracy. By definition,
$d_{\mathcal{X}}$-privacy offers a stronger privacy guarantee for inputs that
are close to each other due to similar output distributions after adding
noise. We can achieve a stronger guarantee for distant input values by adding
large noise but at the cost of utility. Our protocol aims to balance privacy,
accuracy, and efficiency. Opting for stronger privacy guarantees and higher
accuracy would require more lookup tables, each with a smaller privacy budget
but at a higher offline phase and storage costs. Conversely, optimizing for
privacy and efficiency would necessitate adding more noise to each lookup,
potentially compromising accuracy. Lastly, for leakage analysis, it is common
in related studies (Mazloom and Gordon, 2018) to focus on access pattern
leakage. Analyzing potential leaks for the underlying input data tends to be
quite complex.

Differential privacy employs various mechanisms to introduce controlled
randomness to query results. In general, mechanisms designed for differential
privacy can be extended to $d_{\mathcal{X}}$-privacy. The geometric mechanism
adds integer-valued noise from a symmetric geometric distribution to the
output of $f$, ensuring $\epsilon$-$d_{\mathcal{X}}$-privacy.

######  Definition 0.

Let $f:\mathcal{X}\rightarrow\mathbb{Z}$ and let $\gamma$ be drawn from a
symmetric geometric distribution with the probability mass function:
$G_{x}=\frac{1-e^{-\epsilon}}{1+e^{-\epsilon}}\cdot e^{-\epsilon\cdot
d_{\mathcal{X}}(x,x^{\prime})}$. Then, $\mathcal{A}(.)=f(.)+\gamma$ is
$\epsilon$-$d_{\mathcal{X}}$-private.

We provide the proof in Appendix C.

Figure 1. Overview of our PPML setup.

##  4\. Security Model

We consider a setting where clients $C_{0},..,C_{n-1}$ want to train ML models
on their joint data. The data can be horizontally or vertically partitioned
among the clients. The clients outsource the computation to two untrusted but
non-colluding servers, $P_{0}$ and $P_{1}$. The clients secret share the input
data between $P_{0}$ and $P_{1}$ that employ secure 2PC techniques to train ML
models on this data. Figure 1 depicts an overview of the setup.

Client-Aided Offline Phase. We use a client-aided offline phase. Since clients
must initially upload their data to the servers, we further mandate them to
generate and transmit random numbers and lookup tables, which are later
utilized in the online phase. This strategy considerably enhances the
efficiency of the offline phase by imposing only a marginal additional load on
the clients, who are uninvolved post this phase. An alternative is the server-
aided offline phase, where the computing servers use homomorphic encryption
and oblivious transfer based techniques to generate required randomness.
However, as noted by past work (Mohassel and Zhang, 2017), this method is a
significant bottleneck for PPML due to extensive cryptographic tasks. Aiming
for practical PPML protocols, we adopt a client-aided offline phase, which
provides a significant speed up as seen in Table 5. The only limitation of a
client-aided offline phase is that the participating clients can not collude
with the computing servers. This “Client-Aided Setting” has been formalized
and adopted in several past works on PPML (Mohassel and Zhang, 2017; Kamara et
al., 2011; Gascón et al., 2016). It is worth noting that each client supplies
randomness and lookup tables exclusively for their specific batch of training
data. We refer to the client executing the offline phase as a $\mathsf{Client-
Aide}$.

###  4.1. Security Definition

We consider a semi-honest adversary $\mathcal{A}$, which adheres to protocol
specifications but tries to obtain information about the clients’ data. We
assume $\mathcal{A}$ can corrupt at most one of the two servers and any client
subset, provided corrupt clients don’t collude with servers. The security
definition requires that adversary $\mathcal{A}$ only learns the data of
corrupted clients and the final trained model but does not learn the data of
any honest client.

We prove the security of our protocols using the simulation paradigm (Canetti,
1998, 2001; Goldreich et al., 1987). The universal composition framework
(Canetti, 2001) facilitates security arguments for diverse protocol
compositions. End-to-end training security follows from the composition of
underlying protocols. Security is modeled using two interactions: a real
interaction where the servers run a two-party protocol $\Pi$ in the presence
of an adversary $\mathcal{A}$ as defined above and an environment
$\mathcal{Z}$, and an ideal interaction where the servers send the inputs to a
functionality $\mathcal{F}$ that performs the desired computation truthfully.

######  Definition 0.

A protocol $\Pi$ securely realizes $\mathcal{F}$ if, for every adversary
$\mathcal{A}$ acting in the real world
$\real[\mathcal{Z},\mathcal{A},\Pi,\lambda]$, there is an adversary
$\mathcal{S}$ in the ideal world
$\mathsf{Ideal}[\mathcal{Z},\mathcal{S},\mathcal{F},\lambda]$, such that the
probability of $\mathcal{A}$ succeeding in the real world interaction and the
probability of $\mathcal{S}$ succeeding in the ideal world interaction, given
the security parameter $\lambda$, are related as:

$|Pr[\real[\mathcal{Z},\mathcal{A},\Pi,\lambda]=1]-Pr[\mathsf{Ideal}[\mathcal{Z},\mathcal{S},\mathcal{F},\lambda]=1]|=\mathsf{negl}(\lambda)$

We introduce two important modifications to the security definition to
establish security for $\mathsf{Hawk}_{\mathsf{Multi}}$ protocol, which
permits access pattern leakages. Firstly, we allow some leakage in the ideal
world to mirror the information learned by the adversary in the real world by
observing the lookup table accesses. The leakage function is a randomized
function of the access patterns. Secondly, we impose an extra condition
requiring this leakage function to maintain $d_{\mathcal{X}}$-privacy. In the
ideal interaction, each party $P_{i}$ forwards its input to the ideal
functionality. The ideal functionality reconstructs the input received
$x_{1},x_{2},..,x_{n}$, computes the output $f(x_{1},x_{2},..x_{n})$, and
sends $\langle f(x_{1},x_{2},..x_{n})\rangle_{0}$ to $P_{0}$ and $\langle
f(x_{1},x_{2},..x_{n})\rangle_{1}$ to $P_{1}$. Concurrently, the ideal
functionality computes a leakage function $\mathcal{L}$ of the input and sends
$\mathcal{L}$ to the simulator $\mathcal{S}$. Our protocols operate in a
hybrid world with access to secure, ideal functionalities, which we substitute
with secure computation techniques in our application. Per Canetti’s classic
result (Canetti, 2000), proving security involves treating these as trusted
functionality calls.

######  Definition 0.

A protocol $\Pi$ securely realizes $\mathcal{F}$ with leakage $\mathcal{L}$
and $(\lambda,\epsilon)$-security, while making calls to an ideal
functionality $\mathcal{G}$, if, $\mathcal{L}$ is
$\epsilon$-$d_{\mathcal{X}}$-private, and for every adversary $\mathcal{A}$
acting in the $\mathcal{G}$-hybrid world
$\mathsf{Hybrid}[\mathcal{G},\mathcal{Z},\mathcal{A},\Pi,(X_{0},X_{1}),\lambda]$,
there is an adversary $\mathcal{S}$ in the ideal world
$\mathsf{Ideal}[\mathcal{Z},\mathcal{S(L(X))},\mathcal{F},(X_{0},X_{1}),\lambda]$,
such that the probability of $\mathcal{A}$ succeeding in the hybrid world
interaction and the probability of $\mathcal{S}$ succeeding in the ideal world
interaction, on valid inputs $X_{0}$ and $X_{1}$, are related as:

$|Pr[\mathsf{Hybrid}[\mathcal{G},\mathcal{Z},\mathcal{A},\Pi,(X_{0},X_{1}),\lambda]=1]-\\\
Pr[\mathsf{Ideal}[\mathcal{Z},\mathcal{S(L(X))},\mathcal{F},(X_{0},X_{1}),\lambda]=1]|=\mathsf{negl}(\lambda)$

##  5\. Accelerating Secure Computation with Lookup Tables

We propose two novel secure computation protocols that employ lookup tables to
evaluate a specific univariate function, $y=f(x)$. These protocols enable the
secure computation of non-linear activations. Furthermore, we detail how to
extend our method to devise specialized protocols for certain multivariate
functions. Specifically, we present a protocol for computing the
$\mathsf{Softmax}$ function using univariate functions. We use the
prepossessing model of secure computation discussed in Section 3.2.

During the offline phase, for a party $P_{i}$, a lookup table $L^{f}_{i}$ can
be constructed, where $f:X\to Y$ is a univariate function and $X$ and $Y$ are
the domain and range of $f$, respectively. Each entry in $L^{f}_{i}$ is of the
form $key:\mathsf{PRF}(K,x)$, $value:\langle f(x)\rangle_{i}$ for every $x\in
X$. Here $\mathsf{PRF}(K,\cdot)$ denotes a pseudo-random function with key
$K$. In the online phase, $P_{i}$ holds a secret share $\langle x\rangle_{i}$
and seeks to determine $\langle f(x)\rangle_{i}$. As $\langle x\rangle_{i}$ is
a secret share generated in the online phase, it cannot directly serve as a
key for the value $\langle f(x)\rangle_{i}$. The key for this value must be
deterministically derived from $x$. During the online phase, computation
parties collaborate to securely compute $\mathsf{PRF}(K,x)$ from the shares
$\langle x\rangle_{i}$ and use it to retrieve $\langle f(x)\rangle_{i}$ from
the lookup table $L^{f}_{i}$. To this end, we propose two protocols
$\textsc{Hawk}_{\text{Single}}$ and $\textsc{Hawk}_{\text{Multi}}$. While
$\textsc{Hawk}_{\text{Single}}$ provides perfect security, it comes with a
higher offline cost and increased storage overhead. In contrast,
$\textsc{Hawk}_{\text{Multi}}$ permits table reuse, substantially reducing
these overheads, but it does introduce some access pattern leakage, which is
proved to be $d_{\mathcal{X}}$-private.

Algorithm 1 Table Generation:
$\Pi_{\textsc{Hawk}_{\text{Single}}(\mathsf{Client-Aide})}^{\mathsf{offline}}$

  1. Input:

Total number of lookup tables $m$, function $f:X\to Y$, and a cryptographic
hash function $H$.

Output: $P_{i}$ gets lookup tables $L^{f,c}_{i}$ for $0\leq c<m$.

  2. 1

$\mathsf{Client-Aide}$ sends a random key $k_{i}$ to $P_{i}$.

  3. 2

For $0\leq c\leq m-1$:

    1. 2.1

For all $x\in X$:

      1. a

$\mathsf{Client-Aide}$ computes additive secret shares $\langle{y}\rangle_{0}$
and $\langle{y}\rangle_{1}$ of $y=f(x)$.

      2. b

$\mathsf{Client-Aide}$ adds the $key:H(x+H(k_{1}||c))$,
$value:\langle{y}\rangle_{0}$ pair in $L^{f,c}_{0}$.

      3. c

$\mathsf{Client-Aide}$ adds the $key:H(x+H(k_{0}||c))$,
$value:\langle{y}\rangle_{1}$ pair in $L^{f,c}_{1}$.

    2. 2.2

$\mathsf{Client-Aide}$ randomly permutes all key value pairs in $L^{f,c}_{0}$
and $L^{f,c}_{1}$.

  4. 3

$\mathsf{Client-Aide}$ sends all $L^{f,c}_{0}$ for $0\leq c<m$ to $P_{0}$.

  5. 4

$\mathsf{Client-Aide}$ sends all $L^{f,c}_{1}$ for $0\leq c<m$ to $P_{1}$.

Algorithm 2 Query Table:
$\Pi_{\textsc{Hawk}_{\text{Single}}(P_{0},P_{1})}^{\mathsf{online}}$

1:For $i\in\\{0,1\\}$, $P_{i}$ holds key $k_{i}$, $\langle{x}\rangle_{i}$, and
a cryptographic hash function $H$.

2:$P_{i}$ gets secret share $\langle{y}\rangle_{i}$ of $y=f(x)$.

3: Initialization: $P_{i}$ receives lookup tables $L^{f,c}_{i}$ for all $0\leq
c<m$ from $\mathsf{Client-Aide}$. $P_{0}$ and $P_{1}$ initialize $c=0$.

4:$P_{i}$ computes $\langle x\rangle_{i}+H(k_{i}||c)$ and sends it to
$P_{1-i}$.

5:$P_{i}$ computes $H(x+H(k_{1-i}||c))=H(\langle x\rangle_{i}+\langle
x\rangle_{1-i}+H(k_{1-i}||c))$.

6:$P_{i}$ retrieves the value: $\langle{y}\rangle_{i}$ corresponding to the
key: $H(x+H(k_{1-i}||c))$ from $L^{f,c}_{i}$.

7:$P_{0}$ and $P_{1}$ increment $c=c+1$.

8:$P_{i}$ outputs $\langle{y}\rangle_{i}$.

###  5.1. $\textsc{Hawk}_{\text{Single}}$: Single Use Lookup Table Protocol

In the online phase of $\textsc{Hawk}_{\text{Single}}$, each computation of
$f$ consumes an entire table. We generate a distinct table for every lookup
during the offline phase. The offline and online phases are detailed in
Algorithms 1 and 2, respectively. Here, $c$ ensures each table has distinct
keys. For practical utility, the size of the table for
$\textsc{Hawk}_{\text{Single}}$ must be minimized. Note that each
$\mathsf{Client-Aide}$ supplies lookup tables exclusively for their specific
batch of training data.

Reducing the Size of Lookup Tables. We harness recent advancements in low
precision machine learning (Gupta et al., 2015; Sun et al., 2019), discussed
in Appendix B, to trim the table size. Neural networks trained with 16-bit
fixed-point values retain their accuracy (Gupta et al., 2015). By adopting
16-bit values for activation function inputs and outputs, our lookup tables
are constrained to $2^{16}$ entries.

Our experiments on the MNIST dataset (classifying as “0” or “not 0”) and the
Arcene dataset (distinguishing “cancer” from “normal”) validate that 16-bit
fixed-point numbers suffice for activation functions without compromising
model accuracy. Figure 2 shows accuracy results for privacy-preserving
logistic regression (PPLR) using our protocols, which employ 16-bit fixed-
point representation for $\mathsf{Sigmoid}$, and provides a comparison with
plaintext training using 32-bit floating-point numbers. We observe that our
protocol retains the model accuracy. Specifically, allocating 11 to 13 bits
for the fractional component and the remaining for the integer part yields
accuracy nearly identical to plaintext training.

$-50$$0$$50$$100$$150$$200$$250$$300$$350$$400$$450$$500$$550$$600$$650$$700$$750$80859095100Number
of IterationsAccuracy ($\%$) Plaintext Sigmoid¡int=3, frac=13¿ Sigmoid¡int=5,
frac=11¿ Sigmoid¡int=9, frac=7¿

$0$$100$$200$$300$$400$$500$$600$$700$$800$1030507090Number of
IterationsAccuracy ($\%$) Plaintext Sigmoid¡int=3, frac=13¿ Sigmoid¡int=5,
frac=11¿ Sigmoid¡int=9, frac=7¿

Figure 2. a) MNIST (—B— = 128) b) Arcene (—B— = 100)
Accuracy comparison of plaintext training with our PPLR protocol considering
different bit representations for the Sigmoid function.

Optimizing Lookups for Derivatives. In certain cases, we can compute the
derivative from the activation function or vice versa. For instance,
$\mathsf{DSigmoid}(x)=\mathsf{Sigmoid}(x)(1-\mathsf{Sigmoid}(x))$ and
$\mathsf{ReLU}(x)=x\mathsf{DReLU}(x))$, where $\mathsf{DSigmoid}$ and
$\mathsf{DReLU}$ represent the derivative of $\mathsf{Sigmoid}$ and
$\mathsf{ReLU}$ respectively. Our protocol, which leverages this relationship
for $\mathsf{ReLU}$ and $\mathsf{DReLU}$, is detailed in Algorithm 7. Once the
parties have $\mathsf{DReLU}(x)$, they can use a secure multiplication to
compute $\mathsf{ReLU}(x)$. This substantially cuts down the need for
additional lookup tables. While the concept of computing $\mathsf{ReLU}(x)$
from $\mathsf{DReLU}(x)$ is not novel (Wagh et al., 2019), our contribution
lies in harnessing this relationship to halve the lookup tables needed for
neural networks, thereby streamlining the offline phase.

An Alternate Representation for DReLU. We present an alternate representation
of the $\mathsf{DReLU}$ activation, aiming to reduce the size of its
associated lookup table substantially. Note that $\mathsf{DReLU}(x)$ = 1 if
$x>0$ and 0 otherwise. Our key observation is that, unlike other activation
functions, $\mathsf{DReLU}$ does not require precise numbers. For instance,
given $x_{1}=2$ and $x_{2}=2.57$, both yield
$\mathsf{DReLU}(x_{1})=\mathsf{DReLU}(x_{2})=1$. This suggests that the
fractional component of the number can be disregarded without affecting the
computation of $\mathsf{DReLU}$. However, for $0<x<1$, eliminating the
fractional component results in $x=0$, leading to incorrect computation of
$\mathsf{DReLU}(x)=0$. To address this, we propose the following
representation for $\mathsf{DReLU}$ for fixed point numbers:
$\mathsf{DReLU}(x)=1$ iff $\left\lfloor x+(2^{l_{d}}-1)\right\rfloor\geq 1$
and $0$ otherwise, where $l_{d}$ represents bit count for the decimal part and
$\left\lfloor.\right\rfloor$ signifies truncation by $l_{d}$ bits. This novel
representation can substantially reduce the $\mathsf{DReLU}$ lookup table
entries, allowing us to drop fractional bits and only retain integer bits. For
instance, if $l_{d}$ bits represent the fractional segment of a number and
$l_{i}$ bits correspond to the integer segment, a lookup table requires
$2^{l_{d}+l_{i}}$ entries. With our proposed representation, only $2^{l_{i}}$
entries are needed, reducing the lookup table size for $\mathsf{DReLU}$ by a
factor of $2^{l_{d}}$. In our context, this factor is $2^{13}$. As highlighted
in previous work (Mohassel and Zhang, 2017), each participant $P_{i}$ can
locally truncate their share of $x$. However, as this truncation introduces a
small error (refer to Theorem 1 in (Mohassel and Zhang, 2017) for details), we
opt to retain one fractional bit instead of truncating all of them.

Addressing Storage Overhead. Despite our optimizations, the storage demands of
lookup tables render $\textsc{Hawk}_{\text{Single}}$ suitable only for
logistic regression and secure inference but not for neural network training,
as shown in Table 5. To address this, we introduce
$\textsc{Hawk}_{\text{Multi}}$, which permits multiple reuses of a single
lookup table. While this approach introduces some leakage regarding access
patterns, we prove the leakage is bounded by
$\epsilon$-$d_{\mathcal{X}}$-privacy.

Algorithm 3 $\Pi_{\mathsf{SC}(P_{0},P_{1})}^{\mathsf{online}}$: Share
Conversion Protocol

1:For $i\in\\{0,1\\}$, $P_{i}$ knows $n$ and $N$ where $N>n$. $P_{i}$ holds
$\langle x\rangle_{i}^{n}$ and shares of a random $r$; $\langle
r\rangle_{i}^{n}$ and $\langle r\rangle_{i}^{N}$.

2:$P_{i}$ gets fresh share $\langle x\rangle_{i}^{N}$ of $x$.

3:$P_{i}$ computes $\langle x\rangle_{i}^{n}-\langle r\rangle_{i}^{n}$ and
sends it to $P_{1-i}$

4:Each party reconstructs $z=x-r$.

5:$P_{0}$ outputs $\langle x\rangle_{0}^{N}=z+\langle r\rangle_{0}^{N}$ and
$P_{1}$ outputs $\langle x\rangle_{1}^{N}=\langle r\rangle_{1}^{N}$ as their
share of $x$ in $\mathbb{Z}_{N}$

Algorithm 4 Table Generation:
$\Pi_{\textsc{Hawk}_{\text{Multi}}(\mathsf{Client-Aide})}^{\mathsf{offline}}$

  1. Input:

A function $f:X\to Y$, total tables required $m$, cryptographic hash function
$H$, field modulus $n$, order of an elliptic curve $N$, generator of the curve
$G$.

Output: For $i\in\\{0,1\\}$, $P_{i}$ gets lookup tables $L^{f,c}_{i}$ for
$0\leq c<m$.

  2. 1

$\mathsf{Client-Aide}$ generates random keys $k_{i}$ and $s_{i}\mod{N}$ and
sends to $P_{i}$.

  3. 2

For $0\leq c\leq m-1$:

    1. 2.1

$\mathsf{Client-Aide}$ computes random $s^{c}_{0}=H(s_{0}||c)\mod{N}$.

    2. 2.2

$\mathsf{Client-Aide}$ computes random $s^{c}_{1}=H(s_{1}||c)\mod{N}$.

    3. 2.3

For all $x\in X$:

      1. a

$\mathsf{Client-Aide}$ computes
$\kappa=k_{0}k_{1}\times(xG+s^{c}_{0}G+s^{c}_{1}G)$.

      2. b

$\mathsf{Client-Aide}$ computes additive secret shares $\langle{y}\rangle_{0}$
and $\langle{y}\rangle_{1}$ of $y=f(x)$.

      3. c

$\mathsf{Client-Aide}$ adds $key:H(\kappa),value:\langle{y}\rangle_{0}$ in
$L^{f}_{0}$.

      4. d

$\mathsf{Client-Aide}$ adds $key:H(\kappa),value:\langle{y}\rangle_{1}$ in
$L^{f}_{1}$.

    4. 2.4

$\mathsf{Client-Aide}$ randomly permutes all key-value pairs in $L^{f,c}_{0}$
and $L^{f,c}_{1}$.

  4. 3

$\mathsf{Client-Aide}$ sends all $L^{f,c}_{0}$ for $0\leq c<m$ to $P_{0}$.

  5. 4

$\mathsf{Client-Aide}$ sends all $L^{f,c}_{1}$ for $0\leq c<m$ to $P_{1}$.

Algorithm 5 Query Table:
$\Pi_{\textsc{Hawk}_{\text{Multi}}(P_{0},P_{1})}^{\mathsf{online}}$

1:For $i\in\\{0,1\\}$, $P_{i}$ holds random keys $k_{i}$ and $s_{i}$,
$\langle{x}\rangle_{i}^{n}$ , a cryptographic hash function $H$, $\langle
r\rangle_{i}^{n}$ and $\langle r\rangle_{i}^{N}$, order of an elliptic curve
$N$, share of $d_{\mathcal{X}}$-private noise $\langle\gamma\rangle_{i}^{n}$.

2:$P_{i}$ gets secret share $\langle{y}\rangle_{i}$ of $y=f(x)$.

3: Initialization: $P_{i}$ receives lookup tables $L^{f,c}_{i}$ for all $0\leq
c<m$ from $\mathsf{Client-Aide}$, $P_{i}$ initializes $c=0$. $P_{i}$ receives
per query privacy budget $\epsilon$ and total privacy budget $\epsilon_{T}$.
$P_{i}$ initializes $\epsilon_{r}=\epsilon_{T}$.

4:$P_{i}$ computes noisy input $\langle\hat{x}\rangle_{i}^{n}=\langle
x\rangle_{i}^{n}+\langle\gamma\rangle_{i}^{n}$

5:$P_{i}$ executes $\Pi_{SC(P_{0},P_{1})}^{\mathsf{online}}$ with inputs
$\langle\hat{x}\rangle_{i}^{n}$, $\langle r\rangle_{i}^{n}$ and $\langle
r\rangle_{i}^{N}$ and receives output $\langle\hat{x}\rangle_{i}^{N}$.

6:$P_{0}$ computes random value $s^{c}_{0}=H(s_{0}||c)\mod N$.

7:$P_{1}$ computes random value $s^{c}_{1}=H(s_{1}||c)\mod N$.

8:$P_{0}$ computes $k_{0}(\langle\hat{x}\rangle_{0}^{N}G+s^{c}_{0}G)$ and
sends it to $P_{1}$.

9:$P_{1}$ computes $k_{1}(\langle\hat{x}\rangle_{1}^{N}G+s^{c}_{1}G)$ and
sends it to $P_{0}$.

10:$P_{0}$ computes $k_{0}k_{1}(\langle\hat{x}\rangle_{1}^{N}G+s^{c}_{1}G)$
and sends it to $P_{1}$.

11:$P_{1}$ computes $k_{1}k_{0}(\langle\hat{x}\rangle_{0}^{N}G+s^{c}_{0}G)$
and sends it to $P_{0}$.

12:$P_{i}$ computes $\kappa=k_{0}k_{1}(\hat{x}G+s^{c}_{0}G+s^{c}_{1}G)\equiv
k_{0}k_{1}(\langle\hat{x}\rangle_{1}^{N}G+s^{c}_{1}G)+k_{0}k_{1}(\langle\hat{x}\rangle_{0}^{N}G+s^{c}_{0}G)$.

13:$P_{i}$ retrieves the value: $\langle y\rangle_{i}$ corresponding to the
key: $H(\kappa)$ from $L^{f,c}_{i}$, and outputs $\langle y\rangle_{i}$.

14:$P_{i}$ computes $\epsilon_{r}=\epsilon_{r}-\epsilon$.

15:If $\epsilon_{r}==0$ :

  1. .1

$P_{i}$ increments $c=c+1$.

  2. .2

$P_{i}$ sets $\epsilon_{r}=\epsilon_{T}$

###  5.2. $\textsc{Hawk}_{\text{Multi}}$: Multi-Use Lookup Table Protocol

Algorithms 4 and 5 detail the offline and online phases of our
$\textsc{Hawk}_{\text{Multi}}$ protocol, respectively. The core concept of the
$\textsc{Hawk}_{\text{Multi}}$ protocol is the efficient reuse of a lookup
table for multiple lookups. However, naively reusing a lookup table poses
several challenges, as elaborated below.

Lookup Table Reuse. Directly reusing a lookup table to compute $f(x)$ for
identical $x$ values multiple times risks leaking the frequency distribution
of $x$. While parties might not directly learn $x$, they can deduce a
histogram representing each key’s access frequency in the table. As
demonstrated by Naveed et al. (Naveed et al., 2015), this leakage may reveal
plaintext when combined with auxiliary data.

Rather than entirely eliminating this access pattern leakage as in ORAM which
has an inherent overhead of $\Omega(log(n))$ (Goldreich and Ostrovsky, 1996;
Boyle and Naor, 2016; Larsen and Nielsen, 2018), our
$\textsc{Hawk}_{\text{Multi}}$ protocol employs $d_{\mathcal{X}}$-privacy to
limit it. This approach offers a balance between efficiency and privacy,
precisely quantifying the leaked information. We analyze this leakage in
detail in Section 6.1. With the $\textsc{Hawk}_{\text{Multi}}$ protocol, a
lookup table remains reusable until the allocated privacy budget
$\epsilon_{T}$ is depleted. Once exhausted, the table is discarded in favor of
a new one.

Secure Deterministic Key Lookup. The objective is to securely compute a
deterministic key $\mathsf{PRF}(K,x)$ from the shares $\langle x\rangle_{i}$
and use it to retrieve the value $\langle f(x)\rangle_{i}$ from the lookup
table $L^{f}_{i}$. In the $\textsc{Hawk}_{\text{Single}}$, this is achieved by
using the same pseudorandom pad $H(k_{i}||c)$ to obscure $x$ for every key-
value pair in a lookup table. This approach remains secure as each table is
utilized once per activation function computation, and the pad is never
reused.

In the $\textsc{Hawk}_{\text{Multi}}$ protocol, we utilize the hardness of the
elliptic curve discrete logarithm problem (ECDLP) (Hankerson and Menezes,
2005) to securely compute $\mathsf{PRF}(K,x)$. ECDLP, foundational to elliptic
curve cryptography (ECC), posits that given elliptic curve points $P,Q\in
E(\mathbb{F}_{q})$, determining $a$ such that $Q=aP$ is computationally
challenging. ECC is integral to $\textsc{Hawk}_{\text{Multi}}$ for two
additional properties, homomorphism and efficiency. ECC naturally supports
homomorphic operations such as $xG=\langle x\rangle_{0}^{N}G+\langle
x\rangle_{1}^{N}G$, where $N$ denotes the elliptic curve order and $G$ is the
curve generator. We leverage this homomorphism to securely compute
$\mathsf{PRF}(K,x)$. Furthermore, compared to RSA, ECC requires $12\times$
smaller keys for 128 bits of security, leading to faster computations and
reduced communication (Maletsky, 2020).

We iteratively detail the protocol design, starting with the core concept and
refining it to the finalized protocol. Suppose parties $P_{0}$ and $P_{1}$
possess shares $\langle x\rangle_{0}^{N}$ and $\langle x\rangle_{1}^{N}$ of
$x$. They also have secret random keys $k_{0}$ and $k_{1}$, respectively. In
the subsequent section, we present a protocol to convert a share $\langle
x\rangle_{i}$ of $x$ from $\langle x\rangle_{i}^{n}$ to $\langle
x\rangle_{i}^{N}$. $P_{0}$ computes $k_{0}(\langle x\rangle_{0}^{N}G)$ and
forwards it to $P_{1}$ which then computes $k_{1}k_{0}(\langle
x\rangle_{0}^{N}G)$. Similarly, $P_{1}$ sends $k_{1}(\langle
x\rangle_{1}^{N}G)$ to $P_{0}$ which computes $k_{0}k_{1}(\langle
x\rangle_{1}^{N}G)$. Due to the ECDL assumption, $k_{i}(\langle
x\rangle_{i}^{N}G)$ does not leak information about $\langle x\rangle_{i}^{N}$
or $k_{i}$. Subsequently, $P_{1}$ sends $k_{1}k_{0}(\langle
x\rangle_{0}^{N}G)$ to $P_{0}$ and $P_{0}$ sends $k_{0}k_{1}(\langle
x\rangle_{1}^{N}G)$ to $P_{1}$. Each party $P_{i}$ can then compute
$\kappa=k_{0}k_{1}(xG)\equiv k_{0}k_{1}(\langle
x\rangle_{1}^{N}G)+k_{0}k_{1}(\langle x\rangle_{0}^{N}G)$. This allows $P_{0}$
and $P_{1}$ to securely compute $\mathsf{PRF}(K,x)$, where $K=k_{0}k_{1}$
which can be used as a key for table lookup.

Converting Additive Shares To A Larger Group. For the
$\textsc{Hawk}_{\text{Multi}}$ protocol, we start by converting additive
shares from $\mathbb{Z}_{n}$ to $\mathbb{Z}_{N}$, where $N>n$ and $N$ is the
order of the elliptic curve $E$. Algorithm 3 presents a one-round protocol for
share conversion based on (Damgård and Thorbek, 2008). The protocol requires
shares of a random $r$ in both $\mathbb{Z}_{n}$ and $\mathbb{Z}_{N}$, which
can be precomputed in the offline phase.

Mitigating Malleability. Given $k_{0}k_{1}(xG)$, it is possible to compute
$k_{0}k_{1}\cdot$ $(axG)\equiv a\times(k_{0}k_{1}(xG))$ for any arbitrary $a$.
While this does not directly reveal $x$, it might leak crucial information in
our protocol when multiple lookups are performed on a table. A malicious party
could compute $k_{0}k_{1}(axG)$ for various $a$ values and cross-check all
past and future lookups $k_{0}k_{1}(bG)$ to determine if any
$k_{0}k_{1}(axG)=k_{0}k_{1}(bG)$, thereby inferring if $b$ is a multiple of
$x$. To counter this, we use $k_{0}k_{1}(xG+s_{0}G+s_{1}G)$ as the lookup
table key. Here $k_{0}$ and $s_{0}$ are random keys known only to $P_{0}$,
while $k_{1}$ and $s_{1}$ are known only to $P_{1}$. Having these two sets of
keys ensures no party $P_{i}$ can independently compute
$k_{0}k_{1}(axG+s_{0}G+s_{1}G)$. Furthermore, instead of directly using
$s_{0}$ and $s_{1}$, the parties use distinct $s_{0}^{c}$ and $s_{1}^{c}$ for
each table where $c$ denotes the lookup table index and
$s^{c}_{i}=H(s_{i}||c)$. This guarantees that the lookup key differs for each
$x$ across different lookup tables.

Reducing Number of Elliptic Curve Scalar Multiplications.

Optimization 1. During the offline phase, a $\mathsf{Client-Aide}$ must
generate $m$ tables, each of size $2^{16}$. A significant computational
bottleneck in our $\textsc{Hawk}_{\text{Multi}}$ protocol arises when
computing elliptic curve scalar multiplications in step 2.3a of Algorithm 4.
This step requires four scalar multiplications and two point additions on the
elliptic curve. This translates to a daunting $m\times 2^{18}$ scalar
multiplications and $m\times 2^{17}$ point additions in total. We introduce an
optimization to reduce these numbers drastically: scalar multiplications are
cut down to $m+1$, and point additions to $m\times 2^{16}$. Specifically, the
$\mathsf{Client-Aide}$ initially calculates $(k_{0}k_{1})\cdot G$. For a table
$L^{f,c}$, it then computes $(k_{0}k_{1})(s^{c}_{0}+s^{c}_{1})\cdot G$. The
key for $x=0$ is set as
$\mathsf{PRF}(K,0)=(k_{0}k_{1})(s^{c}_{0}+s^{c}_{1})\cdot G$. All subsequent
keys are iteratively determined as
$\mathsf{PRF}(K,i)=\mathsf{PRF}(K,i-1)+(k_{0}k_{1})\cdot G$, requiring only a
single point addition.

Optimization 2. In Algorithm 5, steps 5 and 6, if executed directly, demand
three scalar multiplications and one point addition for each party on the
elliptic curve. We suggest an optimization to bring this down to a single
scalar multiplication per party. Each party $P_{i}$ first evaluates
$k_{i}(\langle x\rangle_{i}^{N}+s^{c}_{i})$, and subsequently computes
$k_{i}(\langle x\rangle_{i}^{N}+s^{c}_{i})\cdot G$, which requires just one
scalar multiplication.

Ensuring Differentially Private Access Patterns. While our
$\textsc{Hawk}_{\text{Multi}}$ protocol conceals the input $x$ during lookups,
repeated lookups on the same table might inadvertently reveal a histogram of
the frequency of each pseudorandom key’s access in the table. To address this,
our $\textsc{Hawk}_{\text{Multi}}$ protocol uses $d_{\mathcal{X}}$-privacy to
limit this leakage. Rather than using their actual input share $\langle
x\rangle_{i}$, each party computes a perturbed input share
$\langle\hat{x}\rangle_{i}$ by incorporating $d_{\mathcal{X}}$-private noise
$\langle\gamma\rangle_{i}$ as outlined in step 1 of Algorithm 5. This ensures
that the parties only learn noisy access patterns, maintaining
$\epsilon$-$d_{\mathcal{X}}$-privacy. The shares of noise $\gamma$ are
generated in the offline phase.

###  5.3. Computing Activation Functions

We now describe how we compute different activation functions using our
protocols. We use $\Pi^{\mathsf{online}}_{\mathsf{Lookup}}$ to denote either
$\Pi^{\mathsf{online}}_{\textsc{Hawk}_{\text{Single}}}$ or
$\Pi^{\mathsf{online}}_{\textsc{Hawk}_{\text{Multi}}}$.

Algorithm 6 DReLU: $\Pi_{\mathsf{DReLU}(P_{0},P_{1})}$

1:$P_{i}$ holds $\langle{x}\rangle_{i}$, lookup table
$L^{\mathsf{DReLU}}_{i}$.

2:$P_{i}$ gets $\langle z\rangle_{i}$ = $\langle\mathsf{DReLU}(x)\rangle_{i}$

3:$P_{i}$ calls $\Pi_{\mathsf{Lookup}(P_{i},P_{1-i})}^{\mathsf{online}}$ with
inputs $(\left\lfloor\langle{x}\rangle_{i}+i\times(2^{l_{d}}-1)\right\rfloor$,
$L^{\mathsf{DReLU}}_{i})$

4:$P_{i}$ learns $\langle z\rangle_{i}$ =
$\langle\mathsf{DReLU}(x)\rangle_{i}$.

Algorithm 7 ReLU: $\Pi_{\mathsf{ReLU}(P_{0},P_{1})}$

1:$P_{i}$ holds $\langle{x}\rangle_{i}$,
$\langle\mathsf{DReLU}(x)\rangle_{i}$.

2:$P_{i}$ gets $\langle z\rangle_{i}$ = $\langle\mathsf{ReLU}(x)\rangle_{i}$

3:For $i\in\\{0,1\\}$, $P_{i}$ calls $\Pi_{\mathsf{SecMul}(P_{i},P_{1-i})}$
having inputs $(\langle\mathsf{DReLU}(x)\rangle_{i},\langle x\rangle_{i})$ and
learns $\langle z\rangle_{i}=\langle x\mathsf{DReLU}(x)\rangle_{i}$. Here
$\Pi_{\mathsf{SecMul}}$ denotes secure multiplication using Beaver’s triples.

4:$P_{i}$ outputs $\langle z\rangle_{i}$ =
$\langle\mathsf{ReLU}(x)\rangle_{i}=\langle x\mathsf{DReLU}(x)\rangle_{i}$.

ReLU and DReLU. Algorithm 6 and 7 describe our protocols for computing
$\mathsf{DReLU}$ and $\mathsf{ReLU}$ respectively. We use the property:
$\mathsf{ReLU}(x)=x\mathsf{DReLU}(x)$, to compute $\mathsf{ReLU}(x)$ from
$\mathsf{DReLU}(x)$.

Algorithm 8 Sigmoid: $\Pi_{\mathsf{Sigmoid}(P_{0},P_{1})}$

1:$P_{i}$ holds $\langle{x}\rangle_{i}$, lookup table
$L^{\mathsf{Sigmoid}}_{i}$.

2:$P_{i}$ gets $\langle z\rangle_{i}$ =
$\langle\mathsf{Sigmoid}(x)\rangle_{i}$.

3:For $i\in\\{0,1\\}$, $P_{i}$ calls
$\Pi_{\mathsf{Lookup}(P_{i},P_{1-i})}^{\mathsf{online}}$ with inputs
$(\langle{x}\rangle_{i},L^{\mathsf{Sigmoid}}_{i})$

4:$P_{i}$ learns $\langle z\rangle_{i}$ =
$\langle\mathsf{Sigmoid}(x)\rangle_{i}$.

Sigmoid. Algorithm 8 describes our protocol to compute $\mathsf{Sigmoid}(x)$.
It is worth noting that the prior works (Mohassel and Zhang, 2017; Wagh et
al., 2019) do not provide any method to compute $\mathsf{Sigmoid}$ accurately.

Softmax. Algorithm 9 describes our protocol for computing $\mathsf{Softmax}$.
As $\mathsf{Softmax}$ involves $d_{l}$ inputs, using our protocols naively
requires $2^{n\times d_{l}}$ entries in the lookup table given $x_{j}$ is an
$n$-bit number, which is impractical. We introduce a method that substantially
reduces the lookup table size, albeit with a slight increase in online
computation. Rather than directly computing $\mathsf{Softmax}$ using a single
lookup table, we employ two distinct tables: one for the exponential function,
$\mathsf{exp}(x)=e^{x}$, and another for the inverse,
$\mathsf{inverse}(x)=\frac{1}{x}$. Existing literature lacks a precise method
for $\mathsf{Softmax}$ computation, resorting to non-standard functions
(Mohassel and Zhang, 2017; Wagh et al., 2019), which leads to accuracy
degradation ( see Figure 9 ).

Algorithm 9 Softmax: $\Pi_{\mathsf{Softmax}(P_{0},P_{1})}$

1:For $i\in\\{0,1\\}$ and $j\in\\{1,..,d_{l}\\}$, $P_{i}$ holds
$\langle{x_{j}}\rangle_{i}$, lookup tables $L^{\exp}_{i}$ and
$L^{\mathsf{inverse}}_{i}$.

2:For neuron $j\in\\{1,..,d_{l}\\}$, $P_{i}$ gets
$\langle\mathsf{Softmax}(x_{j})\rangle_{i}$.

3:For $j\in\\{1,..,d_{l}\\}$, $P_{i}$ calls
$\Pi^{\mathsf{online}}_{\mathsf{Lookup}(P_{i},P_{1-i})}$ with inputs
$(\langle{x_{j}}\rangle_{i},L^{\exp}_{i})$ and learns $\langle
e^{x_{j}}\rangle_{i}$.

4:$P_{i}$ locally computes $\langle s\rangle_{i}=\sum_{j=1}^{d_{l}}\langle
e^{x_{j}}\rangle_{i}$ as the sum of the exponential terms.

5:$P_{i}$ calls $\Pi^{\mathsf{online}}_{\mathsf{Lookup}(P_{i},P_{1-i})}$ with
inputs $(\langle{s}\rangle_{i},L^{\mathsf{inverse}}_{i})$ and learns
$\langle\frac{1}{s}\rangle_{i}$ as the share of the inverse of the sum $s$.

6:For $j\in\\{1,..,d_{l}\\}$, $P_{i}$ runs
$\Pi_{\mathsf{SecMul}(P_{i},P_{1-i})}$ with inputs $(\langle
e^{x_{j}}\rangle_{i},\langle\frac{1}{s}\rangle_{i})$ and learns
$\langle\mathsf{Softmax}(x_{j})\rangle_{i}$.

###  5.4. Rounds and Communication Complexity

Table 1 details the rounds and communication complexities of sub-protocols
employed in training both logistic regression models and neural networks. For
the $\textsc{Hawk}_{\text{Single}}$ protocol, with $l$-bit numbers ($l=64$),
the associated protocols: $\Pi_{\mathsf{Lookup}}$, $\Pi_{\mathsf{Sigmoid}}$
and, $\Pi_{\mathsf{DReLU}}$, demand a single communication round with a
complexity of $l$ bits. The $\Pi_{\mathsf{ReLU}}$ requires an extra round due
to an additional secure multiplication following $\mathsf{DReLU}$. Meanwhile,
$\Pi_{\mathsf{Softmax}}$ requires three rounds, attributed to the computations
of the exponential function, the inverse function, and a secure
multiplication. Here, $d_{l}$ denotes the number of neurons in the output
layer.

For the $\textsc{Hawk}_{\text{Multi}}$ protocol, we adopt numbers of
$l^{\prime}=256$ bits. The associated protocols: $\Pi_{\mathsf{Lookup}}$,
$\Pi_{\mathsf{Sigmoid}}$, and $\Pi_{\mathsf{DReLU}}$, require three
communication rounds with a complexity of $l+2l^{\prime}$. The
$\textsc{Hawk}_{\text{Multi}}$ based protocol $\Pi_{\mathsf{Softmax}}$
requires a total of seven rounds.

The efficiency improvements in training PPML models in our case, relative to
SecureML, stem from the fast computation of non-linear activations such as
$\mathsf{ReLU}$, $\mathsf{Sigmoid}$, $\mathsf{Softmax}$, and their
derivatives. Past works (Mohassel and Zhang, 2017; Liu et al., 2017; Juvekar
et al., 2018) leveraged Yao’s garbled circuits for these computations.
Transitioning secret shares between arithmetic and Yao sharing introduces an
overhead of 7$l\kappa$ \+ ($l^{2}$ \+ $l$)$/2$ (Demmler et al., 2015).

##  6\. Security Analysis

Our privacy-preserving training and inference protocols primarily modify
SecureML’s activation function computation, replacing it with our
$\textsc{Hawk}_{\text{Single}}$ or $\textsc{Hawk}_{\text{Multi}}$ based
protocols: $\Pi_{\mathsf{Sigmoid}}$, $\Pi_{\mathsf{ReLU}}$,
$\Pi_{\mathsf{DReLU}}$, and $\Pi_{\mathsf{Softmax}}$. Each protocol either
exclusively employs $\Pi_{\textsc{Hawk}_{\text{Single}}}^{\mathsf{online}}$ or
$\Pi_{\textsc{Hawk}_{\text{Multi}}}^{\mathsf{online}}$, or combines them with
secure multiplication. Consequently, our security analysis focuses on the
$\Pi_{\textsc{Hawk}_{\text{Single}}}^{\mathsf{online}}$ and
$\Pi_{\textsc{Hawk}_{\text{Multi}}}^{\mathsf{online}}$ protocols, given their
composability. The overall security of our protocols follows from SecureML’s
subprotocols composed with our
$\Pi_{\textsc{Hawk}_{\text{Single}}}^{\mathsf{online}}$ or
$\Pi_{\textsc{Hawk}_{\text{Multi}}}^{\mathsf{online}}$ protocols.

Protocol | Rounds | Communication
---|---|---
$\textsc{Hawk}_{\text{Single}}$ | $\textsc{Hawk}_{\text{Multi}}$ | $\textsc{Hawk}_{\text{Single}}$ | $\textsc{Hawk}_{\text{Multi}}$
$\Pi_{\mathsf{Lookup}}$ | 1 | 3 | $l$ | $l+2l^{\prime}$
$\Pi_{\mathsf{DReLU}}$ | 1 | 3 | $l$ | $l+2l^{\prime}$
$\Pi_{\mathsf{ReLU}}$ (after $\mathsf{DReLU}$) | 1 | 1 | $l$ | $l$
$\Pi_{\mathsf{Sigmoid}}$ | 1 | 3 | $l$ | $l+2l^{\prime}$
$\Pi_{\mathsf{Softmax}}$ | 3 | 7 |  $l$(1 + 2$d_{l}$) | $l(1+2d_{l})+2l^{\prime}(1+d_{l})$

Table 1. Total rounds and communication complexity of
$\textsc{Hawk}_{\text{Single}}$ and $\textsc{Hawk}_{\text{Multi}}$ protocols.
($l$ = 64 bits, $l^{{}^{\prime}}$ = 256 bits)

Functionality $\mathcal{F}_{\mathsf{SingleLookup}}$ Parameters: Servers
$P_{0},P_{1}$ Data: On input $\langle x\rangle_{0}$ and $\langle
x\rangle_{1}$, store $\langle x\rangle_{0}$ and $\langle x\rangle_{1}$
internally. Computation: On input $f$ from $P_{0}$ or $P_{1}$, reconstruct
$x=\langle x\rangle_{0}+\langle x\rangle_{1}\pmod{n}$, compute $y=f(x)$,
create additive shares $\langle y\rangle_{0}$ and $\langle y\rangle_{1}$, and
send $\langle y\rangle_{0}$ to $P_{0}$ and $\langle y\rangle_{1}$ to $P_{1}$.

Figure 3. Ideal Functionality $\mathcal{F}_{\mathsf{SingleLookup}}$

Functionality $\mathcal{F}_{\mathsf{SC}}$ Parameters: Servers $P_{0},P_{1}$
Data: On input $\langle x\rangle_{0}^{n}$ and $\langle x\rangle_{1}^{n}$,
store $\langle x\rangle_{0}^{n}$ and $\langle x\rangle_{1}^{n}$ internally.
Computation: On input $N>n$ from $P_{0}$ or $P_{1}$, reconstruct $x=\langle
x\rangle_{0}^{n}+\langle x\rangle_{1}^{n}\pmod{n}$, create random additive
shares $\langle x\rangle_{0}^{N}$ and $\langle x\rangle_{1}^{N}$ of $x$, and
send $\langle x\rangle_{0}^{N}$ to $P_{0}$ and $\langle x\rangle_{1}^{N}$ to
$P_{1}$.

Figure 4. Ideal Functionality $\mathcal{F}_{\mathsf{SC}}$

Functionality $\mathcal{F}_{\mathsf{MultiLookup}}$ Parameters: Servers
$P_{0},P_{1}$ Data: On inputs $\langle x\rangle_{0}$ and $\langle
x\rangle_{1}$, store internally. Computation: 1 Reconstruct $x=\langle
x\rangle_{0}+\langle x\rangle_{1}\pmod{n}$. 2 Compute
$\hat{x}=x+\gamma\pmod{n}$, with $\gamma$ drawn using geometric mechanism in
Definition 4. 3 On input $f$ from $P_{0}$ or $P_{1}$, compute $y=f(\hat{x})$.
4 Create additive shares $\langle y\rangle_{0}$ and $\langle y\rangle_{1}$ of
$y$. 5 Send $\langle y\rangle_{0}$ to $P_{0}$ and $\langle y\rangle_{1}$ to
$P_{1}$.

Figure 5. Ideal Functionality $\mathcal{F}_{\mathsf{MultiLookup}}$

######  Theorem 1.

Protocol $\Pi_{\mathsf{Hawk}_{\mathsf{Single}}}^{\mathsf{online}}$ in
Algorithm 2 securely realizes the functionality
$\mathcal{F}_{\mathsf{SingleLookup}}$ against semi-honest adversaries.

###### Proof Sketch.

Consider an adversary $\mathcal{A}$ that corrupts either $P_{0}$ or $P_{1}$.
Without loss of generality, let’s focus on the case where $\mathcal{A}$
corrupts $P_{0}$. We construct a simulator $\mathcal{S}$ that simulates
$\mathcal{A}$ in the ideal world. The simulator $\mathcal{S}$ runs
$\mathcal{A}$. $\mathcal{S}$ generates a random value $r$ to mimic the honest
server $P_{1}$’s message $\langle x\rangle_{1}+H(k_{1}||c)\pmod{n}$ and
forwards it to $\mathcal{A}$. To simulate the honest server’s output,
$\mathcal{S}$ uses $\langle y\rangle_{1}$ received from
$\mathcal{F}_{\mathsf{SingleLookup}}$.

The indistinguishability between the real and ideal worlds stems from the fact
that the sole message exchanged, $\langle x\rangle_{1}+H(k_{1}||c)\pmod{n}$,
is computationally indistinguishable from a random value $r$, owing to the
one-time pseudorandom pad $H(k_{1}||c)$. ∎

######  Theorem 2.

Protocol $\Pi_{\mathsf{SC}}^{\mathsf{online}}$ in Algorithm 3 securely
realizes the functionality $\mathcal{F}_{\mathsf{SC}}$ against semi-honest
adversaries.

###### Proof Sketch.

Given the symmetry of our protocol with respect to both servers, we focus on
the scenario where an adversary corrupts party $P_{0}$. To simulate the honest
server $P_{1}$ in the ideal world, the simulator $\mathcal{S}$ generates a
random value $s$ representing the message $\langle x\rangle_{1}^{n}+\langle
r\rangle_{1}^{n}\pmod{n}$ and sends it to $\mathcal{A}$. $\mathcal{S}$ employs
$\langle x\rangle_{1}^{N}$ obtained from $\mathcal{F}_{\mathsf{SC}}$ to
simulate the honest server’s output.

The indistinguishability between the real and ideal worlds stems from the fact
that the sole message exchanged is $\langle x\rangle_{1}^{n}+\langle
r\rangle_{1}^{n}\pmod{n}$, with $\langle r\rangle_{1}^{n}$ being a random
share of $r$. Consequently, $\langle x\rangle_{1}^{n}+\langle
r\rangle_{1}^{n}\pmod{n}$ is computationally indistinguishable from a random
$s$ of equivalent length. ∎

###  6.1. Leakage Analysis

We begin by discussing the leakage function $\mathcal{L}$ for our
$\mathsf{Hawk}_{\mathsf{Multi}}$ protocol. Intuitively, our
$\mathsf{Hawk}_{\mathsf{Multi}}$ protocol leaks a perturbed profile of access
patterns to a lookup table $L^{f,c}$, where $c$ is the table index. Note that
the protocol does not reveal the input $x$ to any party. Instead, it only
reveals a distorted frequency distribution of accesses to a table $L^{f,c}$
without associating access to a specific input $x$ due to the pseudorandom
nature of the key $\kappa$. For instance, if we access a lookup table
$\text{r}_{\text{Multi}}=10$ times, each with
$\epsilon$-$d_{\mathcal{X}}$-privacy, before exhausting our total privacy
budget $\epsilon_{T}$, the $\mathsf{Hawk}_{\mathsf{Multi}}$ protocol merely
discloses if the ten lookups were distinct or if there were repeated lookups
for a particular key $\kappa$. Furthermore, adding noise $\gamma$ to $x$
before each lookup ensures that parties remain unaware if a key repetition was
genuine or noise-induced. We employ the geometric mechanism in Definition 4 to
sample the noise $\gamma$.

######  Definition 0.

The leakage function $\mathcal{L}$ is $\kappa$, where $\kappa$ is a
pseudorandom key for a lookup table $L^{f,c}$ and
$\kappa=k_{0}k_{1}(\hat{x}G+s_{0}^{c}G+s_{1}^{c}G)$, where $k_{i}$ and
$s_{i}^{c}$ are secret random keys of a party $P_{i}$, $G$ is the generator of
an elliptic curve $E$, and $\hat{x}=x+\gamma$, with $\gamma$ being random
noise as per Definition 4.

######  Theorem 4.

The leakage function $\mathcal{L}$ is local
$\epsilon$-$d_{\mathcal{X}}$-private as per Definition 3.

The preservation of local $\epsilon$-$d_{\mathcal{X}}$-privacy by
$\mathcal{L}$ is a consequence of our utilization of the geometric mechanism,
as defined in Definition 4, to sample noise $\gamma$. We prove this mechanism
to preserve $\epsilon$-$d_{\mathcal{X}}$-privacy in Appendix C. Given the
post-processing resilience of differential privacy (Fernandes, 2022; Dwork and
Roth, 2014), $\mathcal{L}$ also maintains
$\epsilon$-$d_{\mathcal{X}}$-privacy.

######  Theorem 5.

Protocol $\Pi_{\mathsf{Hawk}_{\mathsf{Multi}}}^{\mathsf{online}}$ in Algorithm
5 securely realizes the functionality $\mathcal{F}_{\mathsf{MultiLookup}}$
with $\mathcal{L}$ leakage in ($\mathcal{F}_{\mathsf{SC}}$)-hybrid model as
per Definition 2.

###### Proof Sketch.

Consider an adversary $\mathcal{A}$ that corrupts either server $P_{0}$ or
$P_{1}$. Given the protocol’s symmetry concerning both servers, we focus on
the scenario where $\mathcal{A}$ corrupts $P_{0}$. We describe a simulator
$\mathcal{S}$ to simulate $\mathcal{A}$ in the ideal world. The simulator
$\mathcal{S}$ runs $\mathcal{A}$. $\mathcal{S}$ employs random $s$ to simulate
the honest server $P_{1}$’s output of $\mathcal{F}_{\mathsf{SC}}$.
$\mathcal{S}$ also generates random points $R$ and $S$ on the elliptic curve
$E$ to simulate $P_{1}$’s messages
$k_{1}(\langle\hat{x}\rangle_{1}^{N}G+s^{c}_{1}G)$ and
$k_{1}k_{0}(\langle\hat{x}\rangle_{0}^{N}G+s^{c}_{0}G)$ and sends it to
$\mathcal{A}$. $\mathcal{S}$ also sends leakage function $\mathcal{L}$ in
Definition 3 to $\mathcal{A}$. $\mathcal{S}$ uses $\langle y\rangle_{1}$
received from $\mathcal{F}_{\mathsf{MultiLookup}}$ to simulate the honest
server’s output.

The adversary $\mathcal{A}$’s view in the ideal and real worlds is
indistinguishable because $\langle x\rangle_{1}^{N}$ is computationally
indistinguishable from a random value $s$. Moreover, according to the elliptic
curve discrete log assumption
$k_{1}(\langle\hat{x}\rangle_{1}^{N}G+s^{c}_{1}G)$ and
$k_{1}k_{0}(\langle\hat{x}\rangle_{0}^{N}G+s^{c}_{0}G)$ are indistinguishable
from random points $R$ and $S$ on $E$ as $\langle\hat{x}\rangle_{0}^{N}$,
$\langle\hat{x}\rangle_{1}^{N}$, $k_{0}$, $k_{1}$, $s_{0}^{c}$, and
$s_{1}^{c}$ are uniform random in $\mathbb{Z}_{N}$. The only leakage in the
real world and the ideal world is $\mathcal{L}$ as defined in Definition 3
which is proved to preserve $\epsilon$-$d_{\mathcal{X}}$-privacy. ∎

##  7\. End-to-end Training Protocols

###  7.1. Privacy-Preserving Logistic Regression

Logistic regression necessitates the computation of the $\mathsf{Sigmoid}$
function. While previous studies have approximated $\mathsf{Sigmoid}$ using
polynomials (Aono et al., 2016), achieving satisfactory accuracy demands high-
degree polynomials, leading to inefficiencies. SecureML uses a piece-wise
function and Yao’s garbled circuits for Sigmoid approximation, but the
overhead and accuracy loss from this method remain a concern. We introduce the
$\Pi_{\mathsf{Sigmoid}}$ protocol to directly compute $\mathsf{Sigmoid}$,
enabling efficient training of logistic regression models without compromising
plaintext training accuracy. Algorithm 10 in Appendix D presents our complete
PPLR protocol. After the dot product computation of input examples with
coefficients during the forward pass, parties employ $\Pi_{\mathsf{Sigmoid}}$
for $\mathsf{Sigmoid}$ computation, subsequently proceeding to backward
propagation.

###  7.2. Privacy-Preserving Neural Network

Training neural networks securely introduces complexity and inefficiency
primarily during the computation of non-linear activations, such as
$\mathsf{ReLU}$, $\mathsf{DReLU}$, and $\mathsf{Softmax}$. SecureML employs
Yao’s garbled circuits for $\mathsf{ReLU}$ and $\mathsf{DReLU}$ computations.
They also suggest an approximation for $\mathsf{Softmax}$ as
$f(z_{i})=\frac{ReLU(z_{i})}{\sum_{j=1}^{d_{l}}ReLU(z_{j})}$. However, this
function demands a division garbled circuit, leading to inefficiencies, and
the approximation compromises accuracy, as highlighted in Section 8.4.

In Section 5.3, we introduce efficient protocols for computing
$\mathsf{ReLU}$, $\mathsf{DReLU}$, and $\mathsf{Softmax}$. We can adeptly
train diverse neural networks by integrating the methods from Section 7.1 and
the protocols in Section 5.3. For instance, SecureML’s 3-layer neural network,
comprising two fully connected layers with $\mathsf{ReLU}$ activation and an
output layer with $\mathsf{Softmax}$ activation, can be implemented in the
forward pass using $\Pi_{\mathsf{SecMul}}$, $\Pi_{\mathsf{ReLU}}$, and
$\Pi_{\mathsf{Softmax}}$. Back-propagation, on the other hand, requires
$\Pi_{\mathsf{SecMul}}$ and $\Pi_{\mathsf{DReLU}}$. Although our framework is
readily extendable to CNNs, we focus on DNNs in our evaluation and defer CNNs
to future work.

##  8\. Evaluation

###  8.1. Implementation

We implement our system in C++ with $\sim 13,570$ lines of code. We use the
Eigen library (Guennebaud et al., 2010) for matrix operations, libsecp256k1
(Wuille et al., 2013) for EC implementation, and Crypto++ (Dai et al., 2019)
for cryptographic operations.

$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{-2}$$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$nTime
(s) SecureML $\textsc{Hawk}_{\text{Single}}$ $\textsc{Hawk}_{\text{Multi}}$

$150$$200$$250$$300$$350$$400$$450$$500$$550$$600$$650$$700$$750$$800$$850$$0$$1$$2$$3$dTime
(s) SecureML $\textsc{Hawk}_{\text{Single}}$ $\textsc{Hawk}_{\text{Multi}}$

$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$nTime
(s) SecureML $\textsc{Hawk}_{\text{Single}}$ $\textsc{Hawk}_{\text{Multi}}$

$150$$200$$250$$300$$350$$400$$450$$500$$550$$600$$650$$700$$750$$800$$850$$0$$50$$100$$150$$200$dTime
(s) SecureML $\textsc{Hawk}_{\text{Single}}$ $\textsc{Hawk}_{\text{Multi}}$

Figure 6. a) LAN setting (d=784) b) LAN setting (n=10,000) c) WAN setting
(d=784) d) WAN setting (n=10,000)
Comparison of our PPLR protocols with SecureML. Here n denotes number of data
records, and d denotes the data dimension.

We adopt a field size of $2^{64}$ and represent numbers using C++’s native
unsigned long integer datatype. Following SecureML’s fixed-point
representation (Mohassel and Zhang, 2017), we allocate 13 bits to the
fractional component. For lookup tables, numbers are represented with 16 bits
divided between integer and fractional parts. The lookup tables for
$\mathsf{Sigmoid}$ allocate 3 bits for the integer and 13 for the fractional
part. For $\mathsf{DReLU}$ tables, based on the alternate representation from
Section 5.1, we use 4 integer bits and 1 fractional bit. For the
$\mathsf{Softmax}$ tables, the exponential function is represented with 6
integer and 10 fractional bits, while the inverse function uses 14 integer and
2 fractional bits, ensuring the necessary high dynamic range. In our
experiments involving $\mathsf{Hawk}_{\mathsf{Multi}}$ protocol, $N$ is set to
match the order of the SECP256K1 curve.

###  8.2. Experimental Setup

Our experiments utilize two “Amazon EC2 c4.8x large” instances, aligning with
the setup in previous work (Mohassel and Zhang, 2017). We assess performance
in both LAN and WAN settings:

LAN setting: Both ”Amazon EC2 c4.8x large” instances are hosted within the
same region, achieving an average bandwidth of 620 MB/s and a network delay of
0.25ms.

WAN setting: The instances are hosted in separate regions: US East and US
West. This configuration yields an average bandwidth of 32 MB/s and a network
delay of 48 ms.

We use these datasets to evaluate our protocols: MNIST (LeCun et al., 2010),
Gisette (Guyon, 2003b; Guyon et al., 2005), Arcene (Guyon, 2003a; Guyon et
al., 2005), Fashion MNIST (Xiao et al., 2017), Iris (FISHER, 1936), and the
Adult dataset (Becker, 1994). We describe each dataset in Appendix E.

Each data point represents the average of 10 runs. To assess scalability, we
create synthetic datasets from MNIST by altering record count and data
dimensions. For our $\textsc{Hawk}_{\text{Multi}}$ protocol, we experiment by
adjusting the total privacy budget, $\epsilon_{T}$, of the lookup tables,
where $\epsilon_{T}=\epsilon\times\text{r}_{\text{Multi}}$, with $\epsilon$ as
the per-access privacy budget and $\text{r}_{\text{Multi}}$ denoting each
lookup table’s reuse frequency.

###  8.3. Privacy Preserving Logistic Regression

This section evaluates our PPLR protocol’s performance and scalability,
compares it with SecureML (Mohassel and Zhang, 2017), and assesses the
accuracy against plaintext training.

Framework | MNIST | Gisette | Arcene | Fashion MNIST
---|---|---|---|---
Tensorflow | 99.19 | 98 | 86 | 95.97
$\textsc{Hawk}_{\text{Single}}$ | 99.21 | 98.1 | 86 | 95.97
$\textsc{Hawk}_{\text{Multi}}$ ($\epsilon_{T}=0.01)$ | 99.21 | 98.1 | 86 | 95.97
$\textsc{Hawk}_{\text{Multi}}$ ($\epsilon_{T}=0.001)$ | 99.20 | 97.1 | 85 | 95.89
$\textsc{Hawk}_{\text{Multi}}$ ($\epsilon_{T}=0.0005)$ | 98.80 | 95.2 | 85 | 95.51

Table 2. Accuracy comparison of our PPLR protocols with plaintext training
$(\text{r}_{\text{Multi}}\textbf{= 10})$.

24681097.59898.59999.5EpochsAccuracy
(%)$\epsilon_{T}=\infty$$\epsilon_{T}=0.01$$\epsilon_{T}=0.001$$\epsilon_{T}=0.0006$

24681091929394959697EpochsAccuracy
(%)$\epsilon_{T}=\infty$$\epsilon_{T}=0.01$$\epsilon_{T}=0.001$$\epsilon_{T}=0.0006$

Figure 7. a) MNIST dataset b) Gissette dataset
Training trajectory for PPLR across various $\epsilon_{T}$ values

Framework | LAN (s) | WAN (s) | Offline (s) | Storage
---|---|---|---|---
SecureML | 10.84 | 612.78 | - | -
$\textsc{Hawk}_{\text{Single}}$ | 3.2 | 70.2 | 57.58 | 36.62 GB
$\textsc{Hawk}_{\text{Multi}}$ ($\epsilon_{T}=0.01$) | 4 | 144 | 18.3 | 0.37 GB

Table 3. Comparison of PPLR with SecureML on MNIST (—B— = 128,
$\text{r}_{\text{Multi}}\textbf{= 100}$). SecureML does not report the offline
cost.

Accuracy Performance. Table 2 indicates our $\textsc{Hawk}_{\text{Single}}$
protocol matches plaintext training accuracy across various datasets. For
$\textsc{Hawk}_{\text{Multi}}$, there is no accuracy loss at
$\epsilon_{T}=0.01$ and only a minor decline at $\epsilon_{T}=0.0005$,
suggesting that $\textsc{Hawk}_{\text{Multi}}$ offers robust privacy without
significant accuracy compromises. Figure 7 illustrates the training trajectory
on MNIST and Gissette datasets with $\textsc{Hawk}_{\text{Multi}}$,
highlighting the influence of varying $\epsilon_{T}$. Comparing with SecureML
(Mohassel and Zhang, 2017), in the task of classifying MNIST digits as zero
vs. non-zero, our protocols achieve 99.21% accuracy, closely followed by a
Tensorflow model at 99.19%. In contrast, SecureML reaches 98.62%. Notably,
SecureML’s accuracy suffers more from non-standard activations, especially
with neural networks, with a drop of $\sim 3\%$ for the MNIST dataset, as
discussed in Section 8.4.

$0$$5$$10$$15$$90$$92$$94$$96$EpochsAccuracy$\epsilon_{T}=\infty$$\epsilon_{T}=0.1$$\epsilon_{T}=0.05$$\epsilon_{T}=0.02$
Figure 8. Training trajectory for PPNN across various $\epsilon_{T}$ values
for MNIST. $0$$10$$20$$30$$20$$40$$60$$80$$100$EpochsAccuracy Tensorflow
($\alpha=2^{-5}$) Tensorflow ($\alpha=2^{-9}$) $\textsc{Hawk}_{\text{Multi}}$
($\alpha=2^{-5}$) $\textsc{Hawk}_{\text{Multi}}$ ($\alpha=2^{-9}$) Smax approx
($\alpha=2^{-5}$) Smax approx ($\alpha=2^{-9}$) Figure 9. Accuracy comparison
of PPNN training on MNIST. Here $\alpha$ denotes learning rate and for
$\textsc{Hawk}_{\text{Multi}}$, $\epsilon_{T}=0.1$. The Softmax approximation
used by past works causes accuracy drop.

$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{0}$$10^{2}$$10^{4}$$10^{6}$$10^{8}$nTime
(s) SecureML $\textsc{Hawk}_{\text{Single}}$ $\textsc{Hawk}_{\text{Multi}}$

$150$$200$$250$$300$$350$$400$$450$$500$$550$$600$$650$$700$$750$$800$$850$$20$$40$$60$$80$$100$dTime
(s) $\textsc{Hawk}_{\text{Single}}$ $\textsc{Hawk}_{\text{Multi}}$

$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$nTime
(s) $\textsc{Hawk}_{\text{Single}}$ $\textsc{Hawk}_{\text{Multi}}$

$150$$200$$250$$300$$350$$400$$450$$500$$550$$600$$650$$700$$750$$800$$850$$100$$150$$200$$250$$300$dTime
(s) $\textsc{Hawk}_{\text{Single}}$ $\textsc{Hawk}_{\text{Multi}}$

Figure 10. a) LAN setting (d=784) b) LAN setting (n=10,000) c) WAN setting
(d=784) d) WAN setting (n=10,000)
Comparison of our PPNN protocols with SecureML. Here, n denotes number of data
records, and d denotes the data dimension.

Computation and Communication Performance. Table 3 details our PPLR
experiments in LAN and WAN environments. The online phase for
$\textsc{Hawk}_{\text{Single}}$ requires 3.2s (LAN) and 70.2s (WAN) with a
lookup table storage overhead of 36.62GB per party. In contrast,
$\textsc{Hawk}_{\text{Multi}}$ has an online duration of 4s (LAN) and 144s
(WAN) but reduces storage cost to 0.37GB for $\text{r}_{\text{Multi}}=100$.
This table underlines the balance between privacy, offline cost, and storage.
While $\textsc{Hawk}_{\text{Single}}$ offers perfect security with a faster
online phase, $\textsc{Hawk}_{\text{Multi}}$ demands fewer lookup tables,
ensuring $d_{\mathcal{X}}$-privacy against access pattern leaks. Relative to
SecureML, our methods are up to 3.4x and 8.7x faster in LAN and WAN,
respectively.

For scalability experiments, we vary the dataset size $n$ and the data
dimension $d$. Figure 6 illustrates that PPLR training time scales linearly
with $n$. As $d$ grows, our PPLR time increases sublinearly, while SecureML’s
rises linearly. In WAN, with $d$ ranging from 200 to 1000, SecureML’s time
increases from 72s to 124s. In contrast, our protocols remain steady at around
12s for $\textsc{Hawk}_{\text{Single}}$ and 24s for
$\textsc{Hawk}_{\text{Multi}}$, as $d$ increases. In WAN, the overall time is
largely influenced by communication time, which, for our protocols, stays
nearly constant as $d$ increases.

###  8.4. Privacy Preserving Neural Networks

To evaluate our protocols for training neural networks, we consider an
architecture similar to prior works (Mohassel and Zhang, 2017; Wagh et al.,
2019). The neural network is fully connected, consisting of 2 hidden layers,
each with 128 neurons and an output layer with 10 neurons. The hidden layers
use $\mathsf{ReLU}$, and the output layer uses $\mathsf{Softmax}$ activation.

Framework | MNIST | Iris | Adult
---|---|---|---
Tensorflow | 96.6 | 96.56 | 85.4
$\textsc{Hawk}_{\text{Single}}$ | 96.6 | 95.56 | 85.4
$\textsc{Hawk}_{\text{Multi}}$ $(\epsilon_{T}=0.1)$ | 96.34 | 96.56 | 85.4
$\textsc{Hawk}_{\text{Multi}}$ $(\epsilon_{T}=0.05)$ | 96.09 | 96.56 | 85.2
$\textsc{Hawk}_{\text{Multi}}$ $(\epsilon_{T}=0.02)$ | 95.99 | 96.56 | 85.2

Table 4. Accuracy comparison of our PPNN protocols with plaintext
training$(\text{r}_{\text{Multi}}\text{= 10})$.

| Framework | LAN | WAN
---|---|---|---
Offline (hours) | Online (hours) | Offline (hours) | Online (hours) | Lookup Table Storage
| $\textsc{Hawk}_{\text{Single}}$ | 0.47 | 0.02 | 0.47 | 0.21 | 407.5 GB
2PC |  $\textsc{Hawk}_{\text{Multi}}$ ($\epsilon_{T}=1$) | 0.35 | 0.11 | 0.35 | 0.37 | 4.1 GB
SecureML (server-aided) (Mohassel and Zhang, 2017) | 80.5 | 1.17 | 4277 | 59 | -
SecureML (client-aided) (Mohassel and Zhang, 2017) | 4.15 | 2.87 | - | - | -
| Quotient (Agrawal et al., 2019) | - | 8.72 | - | 50.74 | -
3PC | Falcon (Wagh et al., 2021) | - | 0.17 | - | 3.76 | -
ABY3 (Mohassel and Rindal, 2018) | - | 0.75 | - | - | -
SecureNN (Wagh et al., 2019) | - | 1.03 | - | 7.83 | -

Table 5. Comparison of privacy-preserving neural network training using MNIST
dataset (—B— = 128, $\text{r}_{\text{Multi}}=100$).

Framework | Logistic Regression | Neural Networks
---|---|---
LAN (ms) | WAN (ms) | LAN (s) | WAN (s)
Offline | Online | Offline | Online | Offline | Online | Offline | Online
SecureML (server-aided) | 51 | 3.9 | 2010 | 429 | 13.8 | 0.20 | 472 | 1.2
$\textsc{Hawk}_{\text{Single}}$ | 96 | 3.7 | 96 | 171 | 1.43 | 0.08 | 1.43 | 0.82

Table 6. Secure inference time comparison with SecureML on MNIST for 100
samples.

Accuracy Performance. The neural network trained on MNIST using our PPNN
protocol can reach an accuracy of $96.6\%$ within 15 epochs, similar to a
Tensorflow model. Neural networks trained on Iris (FISHER, 1936) and the Adult
dataset (Becker, 1994) using our $\textsc{Hawk}_{\text{Single}}$ protocol
closely match plaintext training accuracies, as shown in Table 4. However,
with $\textsc{Hawk}_{\text{Multi}}$, accuracy slightly diminishes as
$\epsilon_{T}$ decreases. For instance, at $\epsilon_{T}=0.02$, MNIST accuracy
drops by $\sim 0.5\%$. Figure 8 depicts the MNIST training trajectory under
$\textsc{Hawk}_{\text{Multi}}$, emphasizing the effect of different
$\epsilon_{T}$ values. Additionally, Figure 11 illustrates the correlation
between the total number of lookup tables required and various privacy budget
thresholds necessary to achieve specific accuracy levels. As expected
$\textsc{Hawk}_{\text{Single}}$ protocol requires the highest number of lookup
tables. For the $\textsc{Hawk}_{\text{Multi}}$ protocol, a decrease in
$\epsilon_{T}$ in case of the Adult dataset necessitates an increase in the
number of lookup tables to maintain the same level of accuracy.

Previous studies (Mohassel and Zhang, 2017; Wagh et al., 2019; Mohassel and
Rindal, 2018) report around $93.4\%$ accuracy on MNIST using the same setup.
This discrepancy primarily stems from their use of a non-standard activation
function for $\mathsf{Softmax}$. Figure 9 contrasts our training protocol’s
accuracy with plaintext training. When we emulate the $\mathsf{Softmax}$
approximation ($f(z_{i})=\frac{ReLU(z_{i})}{\sum_{j=1}^{d_{l}}ReLU(z_{j})}$)
from prior works (Mohassel and Zhang, 2017; Wagh et al., 2019; Mohassel and
Rindal, 2018) in a plaintext NN model, we notice a decline in accuracy and
delayed convergence. Notably, our protocol surpasses $90\%$ accuracy on MNIST
in under 1.06 epochs, while earlier works (Mohassel and Zhang, 2017; Wagh et
al., 2019; Mohassel and Rindal, 2018) need more epochs for comparable results.
As shown in Figure 9, our protocol benefits from a larger learning rate,
leading to quicker convergence. In contrast, the $\mathsf{Softmax}$
approximation can cause accuracy to plummet after a certain number of epochs.
This decline, consistent across various learning rates, suggests that such
approximations might be even more detrimental for more complex tasks,
potentially causing substantial accuracy losses.

Computation and Communication Performance. Table 5 compares our PPNN protocols
with SecureML (Mohassel and Zhang, 2017). While we also reference other works
(Agrawal et al., 2019; Wagh et al., 2019; Mohassel and Rindal, 2018; Wagh et
al., 2021) that encompass both 2PC and 3PC protocols, a direct comparison is
challenging due to differing settings, as highlighted in Section 2. In LAN,
our PPNN protocol’s online phase outperforms SecureML’s client-aided approach
by $26-144\times$. SecureML, in the WAN context, omits client-aided protocol
training times, offering only metrics for the setting with server-generated
random shares. This method increases offline costs but reduces online time
through matrix multiplication speed gains. Our WAN-based PPNN protocol is
$159-281\times$ faster than SecureML’s server-aided variant. For the client-
aided variant, factoring in a 2.45 slowdown from the LAN setting, our
protocol’s speed advantage over SecureML in WAN surges to $391-688\times$.
While our PPNN protocol drastically reduces offline costs compared to
SecureML, our $\textsc{Hawk}_{\text{Single}}$ adds a lookup table storage
overhead of 407.5GB. In contrast, our $\textsc{Hawk}_{\text{Multi}}$ reduces
this overhead to 4.1GB per party. Compared with Quotient (Agrawal et al.,
2019), another 2PC protocol, our PPNN protocol’s online phase is
$79-436\times$ and $137-242\times$ faster in LAN and WAN, respectively. Our
PPNN protocols even outperform several 3PC protocols, including SecureNN,
ABY3, and Falcon (Mohassel and Rindal, 2018; Wagh et al., 2019, 2021),
boasting speeds up to $52\times$ in LAN and $37\times$ in WAN.

Figure 10 presents our scalability experiments. Our protocol’s training times
scale linearly with $n$ and sub-linearly with $d$. SecureML only provides
results for the client-aided LAN setting.

###  8.5. Secure Inference

In this section, we evaluate the efficacy of our protocol for secure inference
using the MNIST dataset (LeCun et al., 2010). Our
$\textsc{Hawk}_{\text{Single}}$ protocol is better suited for secure inference
than $\textsc{Hawk}_{\text{Multi}}$ due to its reduced online cost. The cost
of secure inference using $\textsc{Hawk}_{\text{Single}}$ for both logistic
regression and neural networks is shown in Table 6, alongside a comparison
with SecureML (Mohassel and Zhang, 2017). The neural network architecture
referenced is the same as discussed in Section 8.4.

SecureML (Mohassel and Zhang, 2017) only presents the inference times for
their server-aided protocol. For neural networks, they only report inference
times using the square activation function. While the square activation is
faster than $\mathsf{ReLU}$, it compromises slightly on accuracy, as
highlighted in SecureML (Mohassel and Zhang, 2017). Our client-aided protocol
has a higher online cost for dot product operation because matrix
multiplication isn’t feasible (Mohassel and Zhang, 2017). Moreover, we employ
the $\mathsf{ReLU}$ activation function, ensuring the preservation of
plaintext accuracy. In terms of secure inference, our
$\textsc{Hawk}_{\text{Single}}$ protocol’s online phase is up to $2.5\times$
faster than SecureML for both logistic regression and neural networks.
Additionally, the offline phase of $\textsc{Hawk}_{\text{Single}}$ outperforms
SecureML across most scenarios.

##  9\. Conclusion

In this work, we present novel lookup table protocols for PPML that achieve
both accuracy and efficiency in activation function computation. We present
$\textsc{Hawk}_{\text{Single}}$, offering leakage-free security, and
$\textsc{Hawk}_{\text{Multi}}$, enabling table reuse at the cost of leakage
which preserves $d_{\mathcal{X}}$-privacy. Our PPML protocols for logistic
regression and neural networks demonstrate significant performance gains,
reaching up to $688\times$ faster training for neural networks than SecureML
(Mohassel and Zhang, 2017) with plaintext accuracy. Beyond activation
functions, our approach applies to various MPC applications, paving the way
for wider adoption of PPML and secure collaborative data analysis.

###### Acknowledgements.

This research received no specific grant from any funding agency in the
public, commercial, or not-for-profit sectors.

## References

  * (1)
  * Agrawal et al. (2019) Nitin Agrawal, Ali Shahin Shamsabadi, Matt J. Kusner, and Adrià Gascón. 2019.  QUOTIENT: Two-Party Secure Neural Network Training and Prediction _(CCS ’19)_. 1231–1247.
  * Allen et al. (2019) Joshua Allen, Bolin Ding, Janardhan Kulkarni, Harsha Nori, Olga Ohrimenko, and Sergey Yekhanin. 2019\.  An algorithmic framework for differentially private data analysis on trusted processors.  _Advances in Neural Information Processing Systems_ 32 (2019).
  * Andrés et al. (2013) Miguel E. Andrés, Nicolás E. Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. 2013\.  Geo-Indistinguishability: Differential Privacy for Location-Based Systems. In _Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security_ _(CCS ’13)_. Association for Computing Machinery, 901–914.
  * Aono et al. (2016) Yoshinori Aono, Takuya Hayashi, Le Trieu Phong, and Lihua Wang. 2016.  Scalable and Secure Logistic Regression via Homomorphic Encryption. In _Proceedings of the Sixth ACM Conference on Data and Application Security and Privacy_ _(CODASPY ’16)_. 142–144.  https://doi.org/10.1145/2857705.2857731
  * Asharov et al. (2020) Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico, and Elaine Shi. 2020\.  OptORAMa: optimal oblivious RAM. In _Advances in Cryptology–EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part II 30_. Springer, 403–432.
  * Audhkhasi et al. (2013) Kartik Audhkhasi, Osonde Osoba, and Bart Kosko. 2013.  Noise benefits in backpropagation and deep bidirectional pre-training.  _Proceedings of the IJCNN_ , 1–8.
  * Baccarini et al. (2023) Alessandro N. Baccarini, Marina Blanton, and Chen Yuan. 2023\.  Multi-Party Replicated Secret Sharing over a Ring with Applications to Privacy-Preserving Machine Learning.  _Proc. Priv. Enhancing Technol._ 2023 (2023), 608–626.
  * Beaver (1991) Donald Beaver. 1991\.  Efficient multiparty protocols using circuit randomization. In _Annual International Cryptology Conference_. Springer, 420–432.
  * Becker (1994) Barry Becker. 1994\.  Adult Data Set.  https://archive.ics.uci.edu/ml/datasets/Adult.
  * Beimel et al. (2004) Amos Beimel, Yuval Ishai, and Tal Malkin. 2004.  Reducing the Servers’ Computation in Private Information Retrieval: PIR with Preprocessing.  _Journal of Cryptology_ 17 (2004), 125–151.
  * Bishop (1995) C. M. Bishop. 1995\.  Training with Noise is Equivalent to Tikhonov Regularization.  _Neural Computation_ 7 (1995), 108–116.
  * Bogetoft et al. (2006) Peter Bogetoft, Ivan Damgrd, Thomas Jakobsen, Kurt Nielsen, Jakob Pagter, and Tomas Toft. 2006.  A Practical Implementation of Secure Auctions Based on Multiparty Integer Computation. In _Financial Cryptography and Data Security_. Springer Berlin Heidelberg, 142–147.
  * Bottou and Bousquet (2008) Léon Bottou and Olivier Bousquet. 2008.  The Tradeoffs of Large Scale Learning. In _Advances in Neural Information Processing Systems_. 161–168.
  * Boyle et al. (2015) Elette Boyle, Niv Gilboa, and Yuval Ishai. 2015.  Function Secret Sharing. In _Advances in Cryptology - EUROCRYPT 2015_ , Elisabeth Oswald and Marc Fischlin (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 337–367.
  * Boyle and Naor (2016) Elette Boyle and Moni Naor. 2016.  Is there an oblivious RAM lower bound?. In _Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science_. 357–368.
  * Bunn and Ostrovsky (2007) Paul Bunn and Rafail Ostrovsky. 2007.  Secure Two-Party k-Means Clustering. In _Proceedings of the 14th ACM Conference on Computer and Communications Security_ _(CCS ’07)_. Association for Computing Machinery, 486–497.
  * Canetti (1998) Ran Canetti. 1998\.  Security and Composition of Multi-party Cryptographic Protocols.  Cryptology ePrint Archive, Report 1998/018.
  * Canetti (2000) Ran Canetti. 2000\.  Security and composition of multiparty cryptographic protocols.  _Journal of Cryptology_ 13 (2000), 143–202.
  * Canetti (2001) R. Canetti. 2001\.  Universally composable security: a new paradigm for cryptographic protocols. In _Proceedings 42nd IEEE Symposium on Foundations of Computer Science_. 136–145.
  * Chan et al. (2022) T.-H. Hubert Chan, Kai-Min Chung, Bruce Maggs, and Elaine Shi. 2022\.  Foundations of Differentially Oblivious Algorithms.  _J. ACM_ 69, 4 (Aug. 2022), 1–49.  https://doi.org/10.1145/3555984
  * Chatzikokolakis et al. (2013) Konstantinos Chatzikokolakis, Miguel E. Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. 2013\.  Broadening the Scope of Differential Privacy Using Metrics. In _Privacy Enhancing Technologies_ , Emiliano De Cristofaro and Matthew Wright (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 82–102.
  * Crawford et al. (2018) Jack Crawford, Craig Gentry, S. Halevi, Daniel Platt, and V. Shoup. 2018.  Doing Real Work with FHE: The Case of Logistic Regression.  _Proceedings of the 6th Workshop on Encrypted Computing & Applied Homomorphic Cryptography_ (2018).
  * Dai et al. (2019) Wei Dai et al. 2019\.  Crypto++.  https://www.cryptopp.com/.
  * Damgrd et al. (2017) Ivan Damgrd, Jesper Buus Nielsen, Michael Nielsen, and Samuel Ranellucci. 2017.  The TinyTable Protocol for 2-Party Secure Computation, or: Gate-Scrambling Revisited. In _Advances in Cryptology – CRYPTO 2017_.
  * Damgård and Thorbek (2008) Ivan Damgård and Rune Thorbek. 2008.  Efficient Conversion of Secret-shared Values Between Different Fields.  _IACR Cryptology ePrint Archive_ 2008 (01 2008), 221\.
  * Demmler et al. (2015) Daniel Demmler, Thomas Schneider, and Michael Zohner. 2015\.  ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In _NDSS_.
  * Dessouky et al. (2017) G. Dessouky, F. Koushanfar, A. Sadeghi, T. Schneider, Shaza Zeitouni, and Michael Zohner. 2017\.  Pushing the Communication Barrier in Secure Computation using Lookup Tables.  _IACR Cryptol. ePrint Arch._ (2017).
  * Doerner and Shelat (2017) Jack Doerner and Abhi Shelat. 2017.  Scaling ORAM for Secure Computation. In _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_. ACM, Dallas Texas USA, 523–535.  https://doi.org/10.1145/3133956.3133967
  * Dowlin et al. (2016) Nathan Dowlin, Ran Gilad-Bachrach, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. 2016.  _CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy_.  Technical Report.
  * Du et al. (2004) Wenliang Du, Yunghsiang Han, and Shigang Chen. 2004.  Privacy-Preserving Multivariate Statistical Analysis: Linear Regression And Classification.  (04 2004).  https://doi.org/10.1137/1.9781611972740.21
  * Dwork and Roth (2014) Cynthia Dwork and Aaron Roth. 2014.  The Algorithmic Foundations of Differential Privacy.  _Found. Trends Theor. Comput. Sci._ 9, 3–4 (Aug. 2014), 211–407.  https://doi.org/10.1561/0400000042
  * Fernandes (2022) Natasha Fernandes. 2022\.  Differential privacy for metric spaces: information-theoretic models for privacy and utility with new applications to metric domains.  (10 2022).  https://doi.org/10.25949/21365637.v1
  * FISHER (1936) R. A. FISHER. 1936\.  THE USE OF MULTIPLE MEASUREMENTS IN TAXONOMIC PROBLEMS.  _Annals of Eugenics_ 7 (1936).  https://doi.org/10.1111/j.1469-1809.1936.tb02137.x
  * Gascón et al. (2016) A. Gascón, Phillipp Schoppmann, B. Balle, Mariana Raykova, Jack Doerner, Samee Zahur, and David Evans. 2016.  Secure Linear Regression on Vertically Partitioned Datasets.  _IACR Cryptol. ePrint Arch._ (2016).
  * Goldreich et al. (1987) O. Goldreich, S. Micali, and A. Wigderson. 1987.  How to Play ANY Mental Game _(STOC ’87)_.
  * Goldreich and Ostrovsky (1996) Oded Goldreich and Rafail Ostrovsky. 1996.  Software protection and simulation on oblivious RAMs.  _J. ACM_ 43, 3 (May 1996), 431–473.  https://doi.org/10.1145/233551.233553
  * Gordon et al. (2012) S Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Fernando Krell, Tal Malkin, Mariana Raykova, and Yevgeniy Vahlis. 2012.  Secure two-party computation in sublinear (amortized) time. In _Proceedings of the 2012 ACM conference on Computer and communications security_. 513–524.
  * Guennebaud et al. (2010) Gaël Guennebaud, Benoît Jacob, et al. 2010\.  Eigen v3.  http://eigen.tuxfamily.org.
  * Gupta et al. (2015) Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. 2015.  Deep Learning with Limited Numerical Precision. In _Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37_ _(ICML’15)_. 1737–1746.
  * Guyon (2003a) Isabelle Guyon. 2003a.  Arcene Data Set.  https://archive.ics.uci.edu/ml/datasets/Arcene.
  * Guyon (2003b) Isabelle Guyon. 2003b.  Gisette Data Set.  https://archive.ics.uci.edu/ml/datasets/Gisette.
  * Guyon et al. (2005) Isabelle Guyon, Steve Gunn, Asa Ben-Hur, and Gideon Dror. 2005\.  Result Analysis of the NIPS 2003 Feature Selection Challenge.  In _NIPS 17_ , L. K. Saul, Y. Weiss, and L. Bottou (Eds.). 545–552.
  * Hankerson and Menezes (2005) Darrel Hankerson and Alfred Menezes. 2005.  _Elliptic Curve Discrete Logarithm Problem_.  Springer US, Boston, MA, 186–189.
  * Hazay and Venkitasubramaniam (2017) Carmit Hazay and Muthuramakrishnan Venkitasubramaniam. 2017\.  Scalable Multi-party Private Set-Intersection. In _Public-Key Cryptography – PKC 2017_ , Serge Fehr (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 175–203.
  * Jagannathan and Wright (2005) Geetha Jagannathan and Rebecca N. Wright. 2005.  Privacy-Preserving Distributed k-Means Clustering over Arbitrarily Partitioned Data. In _Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining_ _(KDD ’05)_. Association for Computing Machinery, 593–599.
  * Juvekar et al. (2018) Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. 2018\.  GAZELLE: A Low Latency Framework for Secure Neural Network Inference. In _Proceedings of the 27th USENIX Conference on Security Symposium_ _(SEC’18)_. 1651–1668.
  * Kamara et al. (2011) Seny Kamara, Payman Mohassel, and Mariana Raykova. 2011\.  Outsourcing Multi-Party Computation.  Cryptology ePrint Archive, Report 2011/272.
  * Keller et al. (2017) Marcel Keller, Emmanuela Orsini, Dragos Rotaru, Peter Scholl, Eduardo Soria-Vazquez, and Srinivas Vivek. 2017.  Faster Secure Multi-Party Computation of AES and DES Using Lookup Tables.  Cryptology ePrint Archive, Report 2017/378.
  * Kim et al. (2017) Miran Kim, Yongsoo Song, Shuang Wang, Xia Yuhou, and Xiaoqian Jiang. 2017.  Secure Logistic Regression Based on Homomorphic Encryption: Design and Evaluation.  _JMIR Medical Informatics_ (08 2017).
  * Larsen and Nielsen (2018) Kasper Green Larsen and Jesper Buus Nielsen. 2018.  Yes, there is an oblivious RAM lower bound!. In _Annual International Cryptology Conference_. Springer, 523–542.
  * LeCun et al. (2010) Yann LeCun, Corinna Cortes, and CJ Burges. 2010.  MNIST handwritten digit database.  _ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist_ 2 (2010).
  * Lindell and Pinkas (2000) Yehuda Lindell and Benny Pinkas. 2000.  Privacy Preserving Data Mining. In _Advances in Cryptology — CRYPTO 2000_. Springer Berlin Heidelberg, 36–54.
  * Liu et al. (2017) Jian Liu, Mika Juuti, Yao Lu, and N. Asokan. 2017\.  Oblivious Neural Network Predictions via MiniONN Transformations. In _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ _(CCS ’17)_. 619–631.  https://doi.org/10.1145/3133956.3134056
  * Maletsky (2020) Kerry Maletsky. 2020\.  RSA vs ECC Comparison for Embedded Systems.  https://ww1.microchip.com/downloads/en/DeviceDoc/00003442A.pdf.
  * Mazloom and Gordon (2018) Sahar Mazloom and S. Dov Gordon. 2018.  Secure Computation with Differentially Private Access Patterns. In _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_. ACM, Toronto Canada, 490–507.  https://doi.org/10.1145/3243734.3243851
  * Micikevicius et al. (2018) Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory Diamos, Erich Elsen, David Garcia, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, and Hao Wu. 2018\.  Mixed Precision Training. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=r1gs9JgRZ
  * Mohassel and Rindal (2018) Payman Mohassel and Peter Rindal. 2018.  ABY3: A mixed protocol framework for machine learning. In _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_. 35–52.
  * Mohassel and Zhang (2017) Payman Mohassel and Yupeng Zhang. 2017.  SecureML: A System for Scalable Privacy-Preserving Machine Learning. 19–38.
  * Murray and Edwards (1994) Alan F. Murray and Peter J. Edwards. 1994.  Enhanced MLP Performance and Fault Tolerance Resulting from Synaptic Weight Noise During Training.  _IEEE Transactions on Neural Networks_ 5 (1994), 792–802.
  * Naveed et al. (2015) Muhammad Naveed, Seny Kamara, and Charles V Wright. 2015\.  Inference attacks on property-preserving encrypted databases. In _Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security_. 644–655.
  * Persiano and Yeo (2023) Giuseppe Persiano and Kevin Yeo. 2023.  Lower bound framework for differentially private and oblivious data structures. In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 487–517.
  * Pinkas and Reinman (2010) Benny Pinkas and Tzachy Reinman. 2010.  Oblivious RAM revisited. In _Advances in Cryptology–CRYPTO 2010: 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings 30_. Springer, 502–519.
  * Rathee et al. (2021) Deevashwer Rathee, Mayank Rathee, Rahul Kranti Kiran Goli, Divya Gupta, Rahul Sharma, Nishanth Chandran, and Aseem Rastogi. 2021.  SiRnn: A Math Library for Secure RNN Inference.  _2021 IEEE Symposium on Security and Privacy (SP)_ (2021), 1003–1020.
  * Riazi et al. (2018) M. Sadegh Riazi, Christian Weinert, Oleksandr Tkachenko, Ebrahim M. Songhori, Thomas Schneider, and Farinaz Koushanfar. 2018.  Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications. In _Proceedings of the 2018 on Asia Conference on Computer and Communications Security_ _(ASIACCS ’18)_. 707–721.  https://doi.org/10.1145/3196494.3196522
  * Sanil et al. (2004) Ashish P. Sanil, Alan F. Karr, Xiaodong Lin, and Jerome P. Reiter. 2004.  Privacy Preserving Regression Modelling via Distributed Computation. In _Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD ’04)_. Association for Computing Machinery, 677–682.  https://doi.org/10.1145/1014052.1014139
  * Shang et al. (2021) Zhiwei Shang, Simon Oya, Andreas Peter, and Florian Kerschbaum. 2021\.  Obfuscated access and search patterns in searchable encryption.  _arXiv preprint arXiv:2102.09651_ (2021).
  * Shi et al. (2011) Elaine Shi, T H Hubert Chan, Emil Stefanov, and Mingfei Li. 2011\.  Oblivious RAM with O ((log N) 3) worst-case cost. In _Advances in Cryptology–ASIACRYPT 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings 17_. Springer, 197–214.
  * Shokri and Shmatikov (2015) Reza Shokri and Vitaly Shmatikov. 2015.  Privacy-Preserving Deep Learning. In _Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security_ _(CCS ’15)_. 1310–1321.  https://doi.org/10.1145/2810103.2813687
  * Slavkovic et al. (2007) Aleksandra B. Slavkovic, Yuval Nardi, and Matthew M. Tibbits. 2007\.  Secure Logistic Regression of Horizontally and Vertically Partitioned Distributed Databases. In _Proceedings of the Seventh IEEE International Conference on Data Mining Workshops_ _(ICDMW ’07)_. IEEE Computer Society, 723–728.  https://doi.org/10.1109/ICDMW.2007.84
  * Stefanov et al. (2018) Emil Stefanov, Marten van Dijk, Elaine Shi, T-H Hubert Chan, Christopher Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. 2018\.  Path ORAM: an extremely simple oblivious RAM protocol.  _Journal of the ACM (JACM)_ 65, 4 (2018), 1–26.
  * Sun et al. (2019) Xiao Sun, Jungwook Choi, Chia-Yu Chen, Naigang Wang, Swagath Venkataramani, Vijayalakshmi (Viji) Srinivasan, Xiaodong Cui, Wei Zhang, and Kailash Gopalakrishnan. 2019.  Hybrid 8-bit Floating Point (HFP8) Training and Inference for Deep Neural Networks.  In _Advances in Neural Information Processing Systems 32_. 4900–4909.
  * Vaidya et al. (2008) Jaideep Vaidya, Hwanjo Yu, and Xiaoqian Jiang. 2008\.  Privacy-preserving SVM classification.  _Knowledge and Information Systems_ 14 (02 2008), 161–178.  https://doi.org/10.1007/s10115-007-0073-7
  * Wagh (2022a) Sameer Wagh. 2022a.  Pika: Secure Computation using Function Secret Sharing over Rings.  _Proceedings on Privacy Enhancing Technologies_ 2022, 4 (oct 2022), 351–377.  https://doi.org/10.56553/popets-2022-0113
  * Wagh (2022b) Sameer Wagh. 2022b.  Pika: Secure Computation using Function Secret Sharing over Rings.  _Proceedings on Privacy Enhancing Technologies_ 2022, 4 (Oct. 2022), 351–377.  https://doi.org/10.56553/popets-2022-0113
  * Wagh et al. (2018) Sameer Wagh, Paul Cuff, and Prateek Mittal. 2018.  Differentially Private Oblivious RAM.  _Proceedings on Privacy Enhancing Technologies_ 2018, 4 (Aug. 2018), 64–84.  https://doi.org/10.1515/popets-2018-0032
  * Wagh et al. (2019) Sameer Wagh, Divya Gupta, and Nishanth Chandran. 2019.  SecureNN: Efficient and Private Neural Network Training. In _Privacy Enhancing Technologies Symposium_. (PETS 2019).
  * Wagh et al. (2021) Sameer Wagh, Shruti Tople, Fabrice Benhamouda, Eyal Kushilevitz, Prateek Mittal, and Tal Rabin. 2021.  Falcon Honest-Majority Maliciously Secure Framework for Private Deep Learning.  _Proceedings on Privacy Enhancing Technologies_ 2021, 1 (2021).
  * Wang et al. (2018) Naigang Wang, Jungwook Choi, Daniel Brand, Chia-Yu Chen, and Kailash Gopalakrishnan. 2018.  Training Deep Neural Networks with 8-bit Floating Point Numbers.  In _Advances in Neural Information Processing Systems 31_. 7675–7684.
  * Wang et al. (2014) Xiao Shaun Wang, Yan Huang, TH Hubert Chan, Abhi Shelat, and Elaine Shi. 2014.  SCORAM: oblivious RAM for secure computation. In _Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security_. 191–202.
  * Wenliang Du and Atallah (2001) Wenliang Du and M. J. Atallah. 2001.  Privacy-preserving cooperative scientific computations. In _Proceedings. 14th IEEE Computer Security Foundations Workshop, 2001._ 273–282.
  * Wu et al. (2013) Shuang Wu, Tadanori Teruya, and Junpei Kawamoto. 2013\.  Privacy-preservation for Stochastic Gradient Descent Application to Secure Logistic Regression. In _The 27th Annual Conference of the Japanese Society for Artificial Intelligence_.
  * Wuille et al. (2013) Pieter Wuille, Tim Ruffing, et al. 2013\.  libsecp256k1.  https://github.com/bitcoin-core/secp256k1.
  * Xiao et al. (2017) Han Xiao, Kashif Rasul, and Roland Vollgraf. 2017.  _Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms_.
  * Yu et al. (2006) Hwanjo Yu, Jaideep Vaidya, and Xiaoqian Jiang. 2006\.  Privacy-Preserving SVM Classification on Vertically Partitioned Data. In _Advances in Knowledge Discovery and Data Mining_. 647–656.
  * Zahur et al. (2016) Samee Zahur, Xiao Wang, Mariana Raykova, Adrià Gascón, Jack Doerner, David Evans, and Jonathan Katz. 2016.  Revisiting Square-Root ORAM: Efficient Random Access in Multi-party Computation. 218–234.  https://doi.org/10.1109/SP.2016.21 ISSN: 2375-1207.

##  Appendix A Machine Learning

Stochastic Gradient Descent (SGD) is a commonly used iterative algorithm to
find the local minimum of a function. We use SGD to minimize the cross-entropy
cost function and learn $\boldsymbol{w}$. The coefficient vector
$\boldsymbol{w}$ is first initialized to 0 or random values. Then in each
iteration, we randomly select a data point $(\boldsymbol{x_{i}},y_{i})$ and
update $\boldsymbol{w}$ as $w_{j}=w_{j}-\alpha\frac{\partial
C_{i}(\boldsymbol{w})}{\partial w_{j}}$, where $\alpha$ is the learning rate
that controls the step towards the minimum taken in each iteration.
Substituting the cost function, we get the update rule:
$w_{j}=w_{j}-\alpha(f(\boldsymbol{x_{i}.w})-y_{i})x_{ij}$.

Batching. Instead of updating $\boldsymbol{w}$ using a single data sample in
each iteration, the dataset is divided into random batches of size $|B|$ and
$\boldsymbol{w}$ is updated by averaging the partial derivative of the samples
in a batch. With batching, the vectorized form of the update rule for the
$k$th batch is given as:
$\boldsymbol{w}=\boldsymbol{w}-\alpha\frac{1}{|B|}\boldsymbol{X}^{T}_{k}(f(\boldsymbol{X}_{k}\times\boldsymbol{w})-\boldsymbol{Y}_{k})$.
One pass through the training samples is called an epoch.

Learning Rate. The learning rate $\alpha$ determines the step size of the SGD
towards the minimum. A large $\alpha$ corresponds to larger steps, which may
result in divergence due to overstepping the minimum. In contrast, a small
$\alpha$ may increase the total iterations required.

Termination. When the cost does not decrease significantly for several
iterations, SGD is considered to have converged to a minimum, and we can
terminate. We can then use the learned coefficient vector $\boldsymbol{w}$ for
inference.

Algorithm 10 Logistic Regression: $\Pi_{\mathsf{Logistic}(P_{0},P_{1})}$

Input: $\langle\boldsymbol{X}\rangle,\langle\boldsymbol{Y}\rangle$
Output: $\boldsymbol{w}$
Common Randomness:
$\langle\boldsymbol{U}\rangle,\langle\boldsymbol{V}\rangle,\langle\boldsymbol{Z}\rangle,\langle\boldsymbol{V^{\prime}}\rangle,\langle\boldsymbol{Z^{\prime}}\rangle,$

  1. 1

Initialize lookup table counters $c_{1},\dots,c_{m}=0$, where m is the number
of clients.

  2. 2

For $i\in\\{0,1\\}$, $P_{i}$ computes
$\langle\boldsymbol{E}\rangle_{i}=\langle\boldsymbol{X}\rangle_{i}-\langle\boldsymbol{U}\rangle_{i}$.
The parties reconstruct $\boldsymbol{E}$ using
$Rec(\langle\boldsymbol{E}\rangle_{0},\langle\boldsymbol{E}\rangle_{1})$.

  3. 3

For $1\leq j\leq t$

    1. 33.1

Parties select a mini-batch denoted by $B_{j}$.

    2. 33.2

For $i\in\\{0,1\\}$, $P_{i}$ computes
$\langle\boldsymbol{F}_{j}\rangle_{i}=\langle\boldsymbol{w}\rangle_{i}-\langle\boldsymbol{V}[j]\rangle$.
The parties reconstruct $\boldsymbol{F}_{j}$ using
$Rec(\langle\boldsymbol{F}_{j}\rangle_{0},\langle\boldsymbol{F}_{j}\rangle_{1})$.

    3. 33.3

For $i\in\\{0,1\\}$, $P_{i}$ computes
$\langle\boldsymbol{G}_{B_{j}}\rangle_{i}=\langle\boldsymbol{X}_{B_{j}}\rangle_{i}\times\boldsymbol{F}_{j}+\boldsymbol{E}_{B_{j}}\times\langle\boldsymbol{w}\rangle_{i}+\langle\boldsymbol{Z}_{j}\rangle_{i}-i\cdot\boldsymbol{E}_{B_{j}}\times\boldsymbol{F}_{j}$

    4. 33.4

For $i\in\\{0,1\\}$, $P_{i}$ calls $\Pi_{\mathsf{Sigmoid}(P_{0},P_{1})}$ with
inputs ($\langle\boldsymbol{G}_{B_{j}}\rangle_{i}$,
$L^{\mathsf{Sigmoid}}_{i}$) and sets the output as
$\langle\boldsymbol{Y}^{*}_{B_{j}}\rangle_{i}$.

    5. 33.5

For $i\in\\{0,1\\}$, $P_{i}$ computes
$\langle\boldsymbol{D}_{B_{j}}\rangle_{i}=\langle\boldsymbol{Y}^{*}_{B_{j}}\rangle_{i}-\langle\boldsymbol{Y}_{B_{j}}\rangle_{i}$

    6. 33.6

For $i\in\\{0,1\\}$, $P_{i}$ computes
$\langle\boldsymbol{F}^{{}^{\prime}}_{j}\rangle_{i}=\langle\boldsymbol{D}_{B_{j}}\rangle_{i}-\langle\boldsymbol{V}^{{}^{\prime}}_{j}\rangle_{i}$.
The parties reconstruct $\boldsymbol{F}^{{}^{\prime}}_{j}$ using
$Rec(\langle\boldsymbol{F}^{{}^{\prime}}_{j}\rangle_{0},\langle\boldsymbol{F}^{{}^{\prime}}_{j}\rangle_{1})$.

    7. 33.7

For $i\in\\{0,1\\}$, $P_{i}$ computes
$\langle\boldsymbol{\Delta}\rangle_{i}=\langle\boldsymbol{X}^{T}_{B_{j}}\rangle_{i}\times\boldsymbol{F}^{{}^{\prime}}_{j}+\boldsymbol{E}^{T}_{B_{j}}\times\langle\boldsymbol{D}_{B_{j}}\rangle_{i}+\langle\boldsymbol{Z}^{{}^{\prime}}_{j}\rangle_{i}-i\cdot\boldsymbol{E}^{T}_{B_{j}}\times\boldsymbol{F}^{{}^{\prime}}_{j}$

    8. 33.8

For $i\in\\{0,1\\}$, $P_{i}$ truncates $\langle\boldsymbol{\Delta}\rangle_{i}$
element-wise to get $\lfloor\langle\boldsymbol{\Delta}\rangle_{i}\rfloor$

    9. 33.9

For $i\in\\{0,1\\}$, $P_{i}$ updates the coefficient vector as
$\langle\boldsymbol{w}\rangle_{i}:=\langle\boldsymbol{w}\rangle_{i}-\frac{\alpha}{|B|}\lfloor\langle\boldsymbol{\Delta}\rangle_{i}\rfloor$

  4. 4

The parties reconstruct $\boldsymbol{w}$ using
$Rec(\langle\boldsymbol{w}\rangle_{0},\langle\boldsymbol{w}\rangle_{1})$ and
output $\boldsymbol{w}$.

##  Appendix B Reduced Precision Training

ML algorithms are inherently resilient to error, setting them apart from
conventional algorithms that demand precise computations and high dynamic
range number representations. High precision computation for training ML
algorithms is unnecessary (Bottou and Bousquet, 2008). In fact, introducing
minor noise during training can enhance neural network generalization, thereby
mitigating over-fitting (Murray and Edwards, 1994; Bishop, 1995; Audhkhasi et
al., 2013).

A recent trend in neural network training is to use approximate computing
techniques to reduce memory requirements and improve computing efficiency
(Micikevicius et al., 2018). Gupta et al. (Gupta et al., 2015) show that
training neural networks using 16-bit fixed-point representation with
stochastic rounding can yield accuracy similar to the 32-bit floating-point
format. Wang et al. (Wang et al., 2018) employ a combination of 16-bit and
8-bit floating-point numbers for various deep-learning tasks. Sun et al. (Sun
et al., 2019) present an 8-bit hybrid floating-point format and demonstrate
its robustness by training neural networks for various tasks while preserving
accuracy.

##  Appendix C Proofs

######  Theorem 1.

The geometric mechanism defined in Definition 4 satisfies
$d_{\mathcal{X}}$-privacy.

###### Proof Sketch.

Let $x,x^{\prime}\in\mathcal{X}$. Let $p_{x}$ and $p_{x^{\prime}}$ denote the
probability mass functions of $G_{x}$ and $G_{x^{\prime}}$ respectively. Then,
for some $z\in\mathcal{Y}$, we have,

$\displaystyle\dfrac{p_{x}(z)}{p_{x^{\prime}}(z)}$
$\displaystyle=\dfrac{\frac{1-e^{-\epsilon}}{1+e^{-\epsilon}}\cdot
e^{-\epsilon\cdot
d_{\mathcal{X}}(x,z)}}{\frac{1-e^{-\epsilon}}{1+e^{-\epsilon}}\cdot
e^{-\epsilon\cdot d_{\mathcal{X}}(x^{\prime},z)}}$
$\displaystyle=\dfrac{e^{-\epsilon\cdot
d_{\mathcal{X}}(x,z)}}{e^{-\epsilon\cdot d_{\mathcal{X}}(x^{\prime},z)}}$
$\displaystyle=e^{\epsilon\cdot(d_{\mathcal{X}}(x^{\prime},z)-d_{\mathcal{X}}(x,z))}$

Using the triangle inequality for the metric $d_{\mathcal{X}}(.,.)$ and as
$d_{\mathcal{X}}(x,x^{\prime})=d_{\mathcal{X}}(x^{\prime},x)$ , we get:

$\dfrac{p_{x}(z)}{p_{x^{\prime}}(z)}\leq e^{\epsilon\cdot
d_{\mathcal{X}}(x,x^{\prime})}$

which completes the proof.

∎

##  Appendix D Logistic Regression Protocol

We present our complete Logistic Regression protocol in Algorithm 10. To
implement logistic regression, we use SecureML’s linear regression algorithm
and add our $\Pi_{\mathsf{Sigmoid}}$ protocol for computing the
$\mathsf{Sigmoid}$ function.

We can denote the input matrix for the $i$th layer as a $|B|\times d_{i}$
matrix $\boldsymbol{X_{i}}$ and the coefficient matrix as a $d_{i-1}\times
d_{i}$ matrix $\boldsymbol{W_{i}}$. In iteration $k$, during the forward pass,
the input to the first layer $\boldsymbol{X_{0}}$ is initialized as batch $k$
of the input data, and $\boldsymbol{X_{i}}$, for each layer $i$, is computed
as $\boldsymbol{X_{i}}=f(\boldsymbol{X_{i-1}}\times\boldsymbol{W_{i}})$.
During the back propagation, given a cost function $C(\boldsymbol{W})$, such
as the cross-entropy function, we first compute
$\boldsymbol{\Delta_{i}}=\frac{\delta
C(\boldsymbol{W})}{\delta\boldsymbol{Z_{i}}}$ for each layer $i$, where
$\boldsymbol{Z_{i}}=\boldsymbol{X_{i-1}}\times\boldsymbol{W_{i}}$. For the
output layer $l$, $\boldsymbol{\Delta_{l}}$ is computed as:
$\boldsymbol{\Delta_{l}}=\frac{\delta
C(\boldsymbol{W})}{\delta\boldsymbol{X_{l}}}\odot\frac{\delta
f(\boldsymbol{Z_{l}})}{\delta\boldsymbol{Z_{l}}}$; here $\frac{\delta
f(\boldsymbol{Z_{l}})}{\delta\boldsymbol{Z_{l}}}$ is the derivative of the
activation function and $\odot$ represents element-wise multiplication. Given
$\boldsymbol{\Delta_{l}}$ for the output layer, $\boldsymbol{\Delta_{i}}$ for
previous layers is computed as:
$\boldsymbol{\Delta_{i}}=(\boldsymbol{\Delta_{i+1}}\times\boldsymbol{W_{i}^{T}})\odot\frac{\delta
f(\boldsymbol{Z_{i}})}{\delta\boldsymbol{Z_{i}}}$. The coefficients
$\boldsymbol{W_{i}}$ in layer $i$ are then updated as:
$\boldsymbol{W_{i}}=\boldsymbol{W_{i}}-\alpha\frac{1}{|B|}(\boldsymbol{X_{i}}\times\boldsymbol{\Delta_{i}})$.
We use $Rec$ to denote share reconstruction.

$\textsc{Hawk}_{\text{Single}}$$\textsc{Hawk}_{\text{Multi}}$
$(\epsilon_{T}=0.1)$$\textsc{Hawk}_{\text{Multi}}$
$(\epsilon_{T}=0.05)$$\textsc{Hawk}_{\text{Multi}}$
$(\epsilon_{T}=0.02)$$10^{4}$$10^{6}$$10^{8}$Lookup tables usedMNIST

$\textsc{Hawk}_{\text{Single}}$$\textsc{Hawk}_{\text{Multi}}$
$(\epsilon_{T}=0.1)$$\textsc{Hawk}_{\text{Multi}}$
$(\epsilon_{T}=0.05)$$\textsc{Hawk}_{\text{Multi}}$
$(\epsilon_{T}=0.02)$$10^{4}$$10^{5}$$10^{6}$Iris

$\textsc{Hawk}_{\text{Single}}$$\textsc{Hawk}_{\text{Multi}}$
$(\epsilon_{T}=0.1)$$\textsc{Hawk}_{\text{Multi}}$
$(\epsilon_{T}=0.05)$$\textsc{Hawk}_{\text{Multi}}$
$(\epsilon_{T}=0.02)$$10^{6}$$10^{7}$$10^{8}$Adult

Figure 11. Lookup tables required by our PPNN protocols to achieve a certain accuracy level i.e. 96% for MNIST, 85% for Adult, and 96% for Iris dataset.$(\text{r}_{\text{Multi}}\text{= 10})$. | Mode | $\mathbf{10^{0}}$ | $\mathbf{10^{1}}$ | $\mathbf{10^{2}}$ | $\mathbf{10^{3}}$ | $\mathbf{10^{4}}$ | $\mathbf{10^{5}}$
---|---|---|---|---|---|---|---
Pika | LAN | 0.0007 | 0.001 | 0.006 | 0.059 | 0.539 | 5.329
SIRNN | _ | 0.115 | 0.116 | 0.147 | 0.289 | 2.089
$\textsc{Hawk}_{\text{Single}}$ | 0.0002 | 0.0004 | 0.0004 | 0.0013 | 0.0060 | 0.0482
$\textsc{Hawk}_{\text{Multi}}$ | 0.0008 | 0.0016 | 0.0038 | 0.0209 | 0.1855 | 1.8193
Pika | WAN | 0.183 | 0.195 | 0.198 | 0.356 | 1.375 | 9.030
SIRNN | _ | 7.683 | 7.690 | 7.816 | 9.313 | 32.702
$\textsc{Hawk}_{\text{Single}}$ | 0.050 | 0.059 | 0.059 | 0.062 | 0.066 | 0.116
$\textsc{Hawk}_{\text{Multi}}$ | 0.179 | 0.180 | 0.185 | 0.192 | 0.318 | 2.160
Table 7. Comparison of Hawk with Pika and SIRNN semi-honest protocols. Time is
in seconds and the computation is a sigmoid function on a batch of
$\mathbf{10^{0}}$, $\mathbf{10^{1}}$, $\mathbf{10^{2}}$, $\mathbf{10^{3}}$,
$\mathbf{10^{4}}$, and $\mathbf{10^{5}}$ in both the LAN and WAN settings.

##  Appendix E Datasets

We use the following datasets in our experiments to compare our results with
the previous works (Mohassel and Zhang, 2017; Wagh et al., 2019) and evaluate
the scalability of our protocols.

MNIST. The MNIST dataset (LeCun et al., 2010) contains images of handwritten
digits from ‘0’ to ‘9’. The training set consists of 60,000 images, and the
test set contains 10,000 images. Each sample consists of 784 features
representing a $28\times 28$ image with pixel values ranging from 0 to 255.

Gisette. The Gisette dataset (Guyon, 2003b; Guyon et al., 2005) is constructed
from the MNIST dataset, and the task is to classify the highly confusible
digits ‘4’ and ‘9’. The dataset contains 13,500 samples, each with 5,000
features, with values ranging from 0 to 1,000.

Arcene. The Arcene dataset (Guyon, 2003a; Guyon et al., 2005) contains mass-
spectrometric data, and the task is distinguishing cancer from normal
patterns. The dataset contains 900 instances, each with 10,000 features, with
values ranging from 0 to 1000.

Fashion MNIST. The dataset contains Zalando’s article images in 10 classes
(Xiao et al., 2017). The training set consists of 60,000 images, and the test
set contains 10,000 images. Each sample consists of 784 features with values
ranging from 0 to 255. The dataset can be used as a drop-in replacement for
MNIST.

Iris. The Iris dataset (FISHER, 1936) contains 3 classes of 50 instances, each
where each class is a type of iris plant, and each instance consists of 4
features.

Adult. The dataset consists of census data with 48,842 instances, each with 14
attributes. The classification task is to predict if an individual’s income
exceeds $\$50$K/year. The dataset also contains missing values.

##  Appendix F Comparison with Related Works

Table 7 provides comparison of our $\textsc{Hawk}_{\text{Single}}$ and
$\textsc{Hawk}_{\text{Multi}}$ protocols with Pika (Wagh, 2022b) and SIRNN
(Rathee et al., 2021) for sigmoid function computation. Our protocols
outperform both Pika and SIRNN in all settings.