# Spin: An Efficient Secure Computation Framework with GPU Acceleration

Wuxuan Jiang<EMAIL_ADDRESS>Contribute equally to this paper. Tsingjiao
Information Technology Co. Ltd.  Xiangjun Song<EMAIL_ADDRESS>Contribute equally to this paper. Tsingjiao Information Technology Co. Ltd.
Shenbai Hong<EMAIL_ADDRESS>Tsingjiao Information Technology Co. Ltd.
Haijun Zhang<EMAIL_ADDRESS>Tsingjiao Information Technology Co. Ltd.
Wenxin Liu<EMAIL_ADDRESS>Tsingjiao Information Technology Co. Ltd.  Bo
Zhao<EMAIL_ADDRESS>Tsingjiao Information Technology Co. Ltd.  Wei Xu
<EMAIL_ADDRESS>Tsinghua University  Yi Li<EMAIL_ADDRESS>Tsingjiao Information Technology Co. Ltd.

###### Abstract

Accuracy and efficiency remain challenges for multi-party computation (MPC)
frameworks. Spin is a GPU-accelerated MPC framework that supports multiple
computation parties and a dishonest majority adversarial setup. We propose
optimized protocols for non-linear functions that are critical for machine
learning, as well as several novel optimizations specific to attention that is
the fundamental unit of Transformer models, allowing Spin to perform non-
trivial CNNs training and Transformer inference without sacrificing security.
At the backend level, Spin leverages GPU, CPU, and RDMA-enabled smart network
cards for acceleration. Comprehensive evaluations demonstrate that Spin can be
up to $2\times$ faster than the state-of-the-art for deep neural network
training. For inference on a Transformer model with 18.9 million parameters,
our attention-specific optimizations enable Spin to achieve better efficiency,
less communication, and better accuracy.

##  1 Introduction

As artificial intelligence keeps shaping our daily lives [55, 48, 64], data
security and privacy concerns become more important than ever, especially in
scenarios where data comes from multiple parties. A typical example is joint
training of deep neural networks, which requires lots of data from different
sources. Another example is the secure inference of pre-trained models, which
needs to protect both the data and the models. Several promising technologies
can contribute to resolving the dilemma of machine learning and security.
Multi-party computation (MPC) [68, 24, 5] enables multiple parties to compute
collaboratively using their inputs without compromising privacy. Nonetheless,
MPC incurs substantial computation and communication costs. Federated learning
[41], on the other hand, distributes a training task across multiple devices
and adjusts the joint model collectively using local gradients. Unfortunately,
this optimization diminishes the level of privacy protection, leading to
problems such as data poisoning and inference attacks [61, 46]. Differential
privacy [21, 1] is another widely used technology that regulates the privacy
level by adjusting the amount of noise, which may reduce its precision for
high privacy levels. In this paper, we focus on enhancing the efficiency of
MPC-based approaches with provable security properties.

Non-linear functions widely appear in neural networks. However, there exist
several challenges in optimizing non-linear functions for MPC: 1) As most MPC
frameworks use fixed-point numbers to represent real numbers, evaluating a
non-linear function using naïve iterative methods might lead to inaccurate
results. 2) Transformer models, such as [25, 48, 19], heavily rely on the
attention mechanism which is constructed using approximations for non-linear
functions like Exponentiation [39, 20], and there have not been solutions for
performing joint optimizations across operations within an attention block to
achieve optimal performance. 3) Some frameworks [34, 65] improve the
efficiency by exposing part of intermediate results to plaintext (e.g.,
Piranha [65] evaluates the reciprocal in plaintext when computing Softmax),
which poses potential security risks. Finding the optimal balance between
security and efficiency poses a challenging task in this particular context,
given the inherent difficulty in quantifying the impact of exposure on overall
end-to-end security.

One natural strategy to accelerate MPC is to utilize GPUs’ enormous parallel
threads to handle large inputs. However, secret sharing protocols necessitate
many rounds of communication among parties, and transferring data between GPU
memory and CPU memory incurs significant latency, pulling down the
acceleration benefit of GPUs [33]. Furthermore, some existing GPU-accelerated
frameworks such as [59, 63] use ABY3-style protocols [43], which is based on
_honest-majority_ (no two parties can collude). People require a general
multi-party computation that supports an arbitrary number of parties with a
_dishonest majority_. Piranha [65], a cutting-edge framework, though claiming
that it supports the general case theoretically, has not been implemented yet.

We design and implement Spin, an MPC framework with a dishonest majority that
enables efficient training and inference of deep neural networks. Like Piranha
[65], we concentrate on GPU-acceleration-capable protocols. Spin allows for
faster and more accurate computations for larger deep learning models. Spin
achieves these desirable properties through a collection of new designs at
both the protocol and implementation levels, We further optimize the secure
inference of Transformer models by capturing common patterns of attention
blocks.

In this study, we introduce a novel collection of non-linear function
algorithms, including Reciprocal, Exponentiation, and Logarithm. These
algorithms enhance the efficiency of neural network training in Spin. We also
use several novel attention-specific optimizations to achieve more accurate
and faster Transformer inference.

At the implementation level, we employ GPUs for acceleration and design a
double-ring buffer to enable asynchronous GPU-CPU memory copy and reduce the
latency in the computation’s critical path. We also support _remote direct
memory access_ (RDMA) [66] to accelerate communication on supported hosts
(otherwise, Spin reverts to the socket to remain compatible). For computation-
light but communication-intensive operations, we devise a CPU-GPU hybrid
computation model that avoids unnecessary GPU-CPU memory copy and only
offloads computation-intensive operations to GPUs. For multi-head attention
that employs independent matrix multiplications, we divide GPU cores into
different groups and assign matrix multiplications to core groups with a
carefully tuned group size.

We have implemented Spin on a real-world testbed and trained four deep neural
networks on real-world datasets. We show that, even delivering stronger
security, Spin may still be up to $2\times$ faster and up to 15% more accurate
than the current state-of-the-art on the same hardware.

For inference, we demonstrate that Spin outperforms neural networks of
different sizes, including a Transformer model with 18.9 million parameters
(at 3.08 samples per second).

In summary, our contributions are as follows:

  1. 1.

We propose a series of algorithms for non-linear functions, achieving better
accuracy and efficiency than existing ones.

  2. 2.

We propose a combination of implementation-level optimizations that
effectively utilize modern GPU and RDMA hardware to accelerate MPC
computation. As a by-product, we add RDMA support to Piranha [65].

  3. 3.

We design a set of novel optimizations specific to attention, reducing the
number of several key operations like secure multiplication in attention
blocks.

  4. 4.

Using Spin, we implement several non-trivial deep learning models and
demonstrate significant performance improvements in efficiency, communication,
and accuracy.

##  2 Related Work

SecureML [44] is among the pioneers linking MPC to machine learning. It uses
local shift for truncation and employs a combination ReLU s to approximate
Sigmoid and Softmax, which works well for both training and inference of
simple machine learning models such as logistic regression and simple neural
networks. Following SecureML, [52] provides more efficient protocols for
comparison and division, while [51] gives a comprehensive library of non-
linear functions for machine learning. Both of them focus on addressing secure
inference. However, SecureML-style protocols have not been proven effective
for training complex neural networks.

MPC frameworks for machine learning use different security settings.
SecureML’s line of work only supports two parties. Another line of work,
pioneered by ABY3 [43], relies on an honest-majority 3-party protocol that
adopts mixed circuit computation [17] and offers efficient protocols for basic
operations like multiplication. Recent works like [63, 59, 65, 33] are built
upon the same 3-party setting. There are also 4-party frameworks such as
Trident [11], FLASH [7], FantasticFour [14] and PrivPy [40]. Crypten [34] is
one of the few frameworks that support general multi-party secure machine
learning, i.e. supporting $n$-party dishonest majority, as Spin does. MP-SPDZ
[29] provides a variety of MPC protocols with varying levels of security,
including the Semi2k protocol that supports dishonest majority. A few works
exclusively focus on 2-party secure inference. LLAMA [26] proposes a framework
based on Function Secret Sharing (FSS) and relies on a trusted dealer. Cheetah
[28] combines several MPC protocols to support efficient neural network
inference with well-designed linear operations and non-linear operations like
ReLU and truncation, but it lacks the support for neural network training and
non-linear functions like Softmax commonly used in Transformer models.

There have been various prior attempts to use GPUs to accelerate MPC. CryptGPU
[59] is a three-party honest majority framework that uses GPUs to accelerate
neural network training. It is based on Crypten [34]. However, CryptGPU still
lacks the accuracy to train a deep neural network from scratch, as both [65]
and [33] have pointed out. Piranha [65] is a GPU-assisted secure machine
learning framework that supports two, three, and four parties by implementing
SecureML [44], Falcon [63], and FantasticFour [14]. Piranha provides cutting-
edge performance, demonstrating for the first time that training a VGG16-style
deep neural network can be completed in about a day. Piranha can also be
deployed on multiple GPUs[42]. However, Piranha does not provide accurate
enough non-linear functions, lowering overall training quality, and reveals
intermediate results in Softmax in exchange for performance.

Non-linear function evaluation plays a key role in neural network training and
inference. Secure non-linear function evaluation usually requires polynomial
approximation, and frameworks adopt different approaches. For example, Falcon
[63] proposes protocols for various non-linear functions. Some of the
protocols, however, exhibit privacy leaks. SECFLOAT [50] switches to floating-
point computation for accurate and fast evaluation. Although they produce
outstanding results for numerous non-linear functions, the high cost of
addition limits their practical application. Crypten [34] introduces simple
approximation techniques with limited accuracy. NFGen [23] proposes an auto-
fitting framework for a piece-wise polynomial approximation solution. However,
it necessitates a limited range of each function and batched comparison
operations to choose the appropriate coefficients for each evaluation.
Moreover, NFGen does not support multi-variant functions like Softmax.

Recently, some works have managed to run secure inference on Transformer
models. One of the bottlenecks they encounter is the Softmax evaluation. [32]
compares the effectiveness of different Softmax replacement strategies.
MPCFormer [39] uses an aggressive Softmax replacement strategy called _2Quad
approximation_. With the help of knowledge distillation, MPCFormer can
overcome the accuracy loss caused by the rough approximation. As the other
side of the coin, the rough approximation of MPCFormer necessitates retraining
models to fit the aggressive alteration and can hardly enable general
inference using pre-trained models. PUMA [20] modifies the Softmax-ReLU
replacement strategy and uses piecewise polynomials to approximate GeLU. PUMA
can evaluate an LLaMA-7B inference pass in 5 minutes and is the state-of-the-
art of secure inference of large language models to our knowledge. Our
evaluations will show that our optimized attention outperforms the one based
on PUMA’s Softmax in both efficiency and accuracy.

##  3 System Overview

###  3.1 Threat Model

We assume semi-honest adversaries, where each party follows the protocol but
is curious about the other parties’ sensitive information. Spin works in a
_dishonest majority_ setting, i.e., for a secure computation task with $n$
parties, Spin can tolerate up to $n-1$ parties’ collusion.

###  3.2 System Design

Fig. 1 provides an overview of Spin, and illustrates the workflow of a secure
computation task. Spin consists of several modules, and the following five
modules are key to Spin.

Figure 1: The architecture of Spin. There can exist multiple parties with
individual inputs in each task.

Module 1: Application Programming Interface (API). Similar to many extant
frameworks, Spin enables programmers to write code in a high-level language
akin to Python. The APIs are composed of three layers: a) basic operations,
including addition, multiplication, and comparison; b) derived operations,
such as non-linear functions and other operations that build on basic
operations; c) library algorithms, such as neural network training. A
programmer can either use basic operations and derived operations to implement
customized algorithms for specific applications or use the higher level Spin
library in suitable situations.

Module 2: Interpreter and Spin Instructions. Spin offers a suite of lower-
level APIs, called _Spin Instructions_ , which precisely depict the flow of a
Spin program using low-level engine-friendly operators. The interpreter reads
the user-level program and generates a sequence of Spin instructions. The
design of the interpreter is beyond the scope of this paper. Spin instructions
comprise three types:

  * •

Input/Output: Input instructions drive the engine to read input data from data
sources and secretly share the inputs with the other parties, while output
instructions tell the engine to reveal results to specified receivers.

  * •

Memory manipulation: The engine locally transforms the secret shares it holds.
Operations include _matrix reshaping_ , _memory copy_ , _array concatenation_
, and more.

  * •

Secure computation: The engine uses MPC protocols to carry out computation on
secretly shared data. The engine automatically establishes communication when
evaluating operations that require data transfer, such as multiplication,
exponentiation, etc. Applications do not need to concern themselves with when
to send or receive data.

Module 3: Scheduler.  Upon receiving the instructions for a task, the
scheduler generates the task description, which includes the instructions and
participant information. The scheduler then inserts the task description into
a task backlog. When computational resources become available, the scheduler
assigns the task to each party.

Module 4: MPC Engine.  The engine is responsible for executing MPC protocols,
storing secret shares in GPU memory, receiving instructions from the
scheduler, and executing the instructions using GPU cores. Each engine
receives the same set of task descriptions and executes them synchronously and
iteratively. For each instruction, the engines invoke the corresponding MPC
protocol and communicate with one another over network channels.

Module 5: Precomputation Data Generator (PDG). To accelerate the online
computation, we implement an input-independent offline phase to precompute a
portion of data such as beaver triples [3]. We have a per-party PDG to produce
precomputation data via oblivious transfer [45] and store it in disk-based
storage.

Hardware Accelerators.  In Spin, we use GPUs for computation acceleration and
SmartNICs for efficient communication. To achieve high-bandwidth and low-
latency networking, we further employ _Remote Direct Memory Access_ (RDMA)
[66] to offload data movement among machines from CPU cores. We implement two
variants of the engine: one on CPUs and another on GPUs. The latter offloads
some lightweight but latency-sensitive computation to CPUs for acceleration.

##  4 Building Blocks

We discuss the fundamental components of our MPC operations in this section.
We first introduce basic concepts, then list all the basic operations used in
Spin.

###  4.1 Notations

The set $\mathbb{Z}_{2^{l}}$ represents the integers in
$[-2^{l-1},2^{l-1}-1]$. The arithmetic computation is in $\mathbb{Z}_{2^{l}}$
by default in this paper.

For a signed integer $x\in\mathbb{Z}_{2^{l}}$, we use $\llbracket
x\rrbracket^{\text{A}}$ to represent the $n$-out-of-$n$ arithmetic sharing of
$x$. Specifically, in a $n$-party setting, $\llbracket x\rrbracket^{\text{A}}$
means $x$ is split into $n$ shares
$x_{1},x_{2},\dots,x_{n}\in\mathbb{Z}_{2^{l}}$, such that
$x=\sum_{i=1}^{n}x_{i}$. Similarly, for a boolean number $x\in\\{0,1\\}$, the
binary sharing $\llbracket x\rrbracket^{\text{B}}$ means $x$ is split to $n$
shares $x_{1},x_{2},\dots,x_{n}\in\\{0,1\\}$ such that
$x=\bigoplus_{i=1}^{n}x_{i}$, where $\bigoplus$ stands for _exclusive OR_
(XOR). $\llbracket x_{0:l-1}\rrbracket^{\text{B}}$ is a list of $l$ binary
sharings of bits of $x$, from $\llbracket x_{0}\rrbracket^{\text{B}}$ to
$\llbracket x_{l-1}\rrbracket^{\text{B}}$.

We encode real numbers to fixed-point numbers of bit length $l$. A real number
$x$ is encoded into a signed integer $\lfloor
2^{p}x\rfloor\in\mathbb{Z}_{2^{l}}$ with precision $p$. We use $[x]_{p}$ to
represent the encoded integer of $x$. For example, $[7.7]_{p}=7.7\times
2^{p}$. We use $\llbracket x,p\rrbracket^{\text{A}}$ for the sharing of real
numbers, i.e., $\llbracket x,p\rrbracket^{\text{A}}$ =
$\llbracket[x]_{p}\rrbracket^{\text{A}}$. The operations on $\llbracket
x,p\rrbracket^{\text{A}}$ work on $\llbracket[x]_{p}\rrbracket^{\text{A}}$ by
default.

###  4.2 Precomputation Data

The engine can speed up online computation using input-independent
precomputation data. There are three main types of precomputation data in
Spin: _beaver triples_ [3], _doubly-authenticated bits_ (_daBits_) [56] and
_extended doubly-authenticated bits_ (_edaBits_) [22]. Previous approaches
[22, 4, 31, 30] use either oblivious transfer (OT) or homomorphic encryption
to generate these types of precomputation data. Spin uses OT to generate them.
The process of generating precomputation data has a different pattern compared
with online computation. In this paper, we focus on optimizing the online
phase of complex neural networks and leave the optimization for precomputation
as future work.

###  4.3 Basic Operations

We enumerate the basic operations on which our nonlinear functions algorithms
are built. These operations are implemented following the Semi2k protocol of
MP-SPDZ [29].

Addition. $\llbracket z\rrbracket^{\text{A}}\leftarrow\texttt{Add}(\llbracket
x\rrbracket^{\text{A}},\llbracket y\rrbracket^{\text{A}})$, where $z=x+y$. The
arithmetic sharing approach allows additive homomorphism in nature, and we can
conduct addition locally. Similarly, in a binary sharing scheme, the parties
can perform XOR locally.

Scaling. $\llbracket
z\rrbracket^{\text{A}}\leftarrow\texttt{Scale}(k,\llbracket
x\rrbracket^{\text{A}})$, where $k$ is a public number and $z=k\times x$.

Multiplication. $\llbracket
z\rrbracket^{\text{A}}\leftarrow\texttt{Mul}(\llbracket
x\rrbracket^{\text{A}},\llbracket y\rrbracket^{\text{A}})$, where $z=x\times
y$. The multiplication between two shared numbers $\llbracket
x\rrbracket^{\text{A}}$ and $\llbracket y\rrbracket^{\text{A}}$ demands a
beaver triple to accomplish the online phase. For the multiplication of fixed-
point numbers, Mul doubles the precision, i.e., $\llbracket
c,2p\rrbracket^{\text{A}}\leftarrow\texttt{Mul}(\llbracket
a,p\rrbracket^{\text{A}},\llbracket b,p\rrbracket^{\text{A}})$ where
$[c]_{2p}=[a]_{p}\times[b]_{p}$. Then we perform truncation on $\llbracket
c,2p\rrbracket^{\text{A}}$ to get $\llbracket c,p\rrbracket^{\text{A}}$ (we
will introduce our truncation protocol in Section 4.4). We similarly evaluate
matrix multiplication and convolution, using corresponding beaver triples.

Bit to arithmetic. $\llbracket
z\rrbracket^{\text{A}}\leftarrow\texttt{Bit2A}(\llbracket
x\rrbracket^{\text{B}})$, where $z=x$. This operation converts a secret bit to
a secret integer and requires a precomputed daBit.

Binary to arithmetic. $\llbracket
z\rrbracket^{\text{A}}\leftarrow\texttt{Compose}(\llbracket
x_{0:l-1}\rrbracket^{\text{B}})$, where $z=\sum_{i=0}^{l-1}2^{i}x_{i}$. We
construct this operation using $l$ independent Bit2A operations.

Arithmetic to binary. $\llbracket
z_{0:l-1}\rrbracket^{\text{B}}\leftarrow\texttt{Decompose}(\llbracket
x\rrbracket^{\text{A}})$, where $x=\sum_{i=0}^{l-1}2^{i}z_{i}$. We use edaBits
to implement it.

Comparison. $\llbracket z\rrbracket^{\text{B}}\leftarrow\texttt{Gt}(\llbracket
x\rrbracket^{\text{A}},\llbracket y\rrbracket^{\text{A}})$, where $x>y$
indicates $z=1$, otherwise $z=0$. We evaluate this operation by first
computing $\texttt{Decompose}(\llbracket x\rrbracket^{\text{A}},\llbracket
y\rrbracket^{\text{A}})$, then retrieving the most significant bit as the sign
of $(x-y)$. It is worth noting that this protocol may be incorrect if $(x-y)$
overflows in the ring, and we can avoid such risk using two extra Decompose
operations. In most machine learning tasks, however, we can skip the two extra
Decompose, since the number ranges of machine learning can hardly cause such
overflow.

###  4.4 Derived Operations

We can use the above basic operations to construct the following derived
operations. Here we only introduce the operations that can be constructed
naïvely and leave the introduction of non-linear functions in the next
section.

Truncation. $\llbracket
z\rrbracket^{\text{A}}\leftarrow\texttt{Truncate}(\llbracket
x\rrbracket^{\text{A}},f)$, where $z=x\cdot 2^{-f}$. Multiplication of shared
fixed-point numbers requires truncation to correct the precision. A common way
is to invoke $\texttt{Decompose}(x)$ and shift the bits, then invoke Compose
to get the result. However, Decompose involves binary addition, which requires
expensive multi-round communication. In a 2-party setting, each party can
perform bit shift locally, without any communication. But local shift causes
overflow with probability proportional to the absolute value of the shared
number [44]. For example, if we truncate the result after one multiplication
on $\mathbb{Z}_{2^{64}}$ with precision $p=26$, the failure probability will
be as high as $2^{-11}$ (or $0.5\text{\textperthousand}$).[43] also points out
that the local shift cannot work in a 3-party setting.

The authors of [13] give a solid probabilistic truncation protocol for
unsigned integers, which we denote as UnsignedTruncate. The output integer of
UnsignedTruncate probabilistically deviates from the accurate result by $1$.
This precision loss is negligible, specifically for machine learning tasks, as
deviation by $1$ in fixed-point representation only causes a precision loss of
$2^{-p}$. We extend UnsignedTruncate to a signed version for general
computation. Speficially, for a signed integer $x$, we first apply $\llbracket
y\rrbracket^{\text{A}}\leftarrow\texttt{UnsignedTruncate}(\llbracket
x\rrbracket^{\text{A}}+2^{l-2},l,f)$, then set the result as $\llbracket
y\rrbracket^{\text{A}}-2^{l-f-2}$. The correctness is direct: for
$x\in[-2^{l-2},2^{l-2}-1]$, $x+2^{l-2}$ is non-negative and can be treated as
an unsigned number, then we have $y=(x+2^{l-2})/2^{f}$, thus $y-2^{l-f-2}$ is
the result $x/2^{f}$. For $x<-2^{l-2}$ or $x>2^{l-2}-1$, $x+2^{l-2}$ may be
negative, thus cannot be treated as unsigned, making UnsignedTruncate not
work. In machine learning tasks, we can safely assume that $x$ always falls in
the range $[-2^{l-2},2^{l-2}-1]$, making sure that the output of Truncate is
correct. Our evaluations in Section 8 demonstrate that Truncate with such
assumption achieves desirable results.

Polynomial evaluation. $\llbracket
z\rrbracket^{\text{A}}\leftarrow\texttt{Evaluate}(\llbracket
f(x)\rrbracket^{\text{A}})$, with $z=f(x)$ and the coefficients of $f(x)$ are
public. As a minor optimization, we can save truncations when computing
$a_{i}x^{i}$. For instance, $f(x)=a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}$ is
evaluated by sequentially computing $x,x^{2},x^{3}$. We can skip truncations
when computing $a_{i}x^{i}$, and sum up each term directly. Then a single
truncation suffices to get the result.

Left-most one (LMO) extraction. $\llbracket
z_{0:l-1}\rrbracket^{\text{B}}\leftarrow\texttt{LMO}(\llbracket
x_{0:l-1}\rrbracket^{\text{B}})$, where there is only a bit of $1$ in
$z_{0},z_{1},\dots,z_{l-1}$ and
$\sum_{i=0}^{l-1}2^{i}z_{i}\leq\sum_{i=0}^{l-1}2^{i}x_{i}<\sum_{i=0}^{l-1}2^{i+1}z_{i}$.
A non-negative value’s LMO is the first $1$ after leading 0s. Our LMO
extraction algorithm comes from [9]: First, we scan the bit sequence and run a
pre-OR protocol to turn all bits after LMO into 1, then we shift one bit and
compute XOR with the original bit sequence, after which all bits after LMO
become 0 while LMO stands out.

##  5 Non-linear Functions Evaluation

Non-linear functions often face efficiency and accuracy issues in secure
neural network training and inference. This section presents our new
algorithms for non-linear functions. It is important to note that these
algorithms are based on the operations detailed in Section 4 and are
independent of their implementations, which implies: a) our algorithms remain
secure as long as the operations in Section 4 are universally composable; b)
optimizations or new implementations for these operations maintain the
correctness of our new algorithms. In this paper, we focus on three non-linear
functions: _reciprocal_ , _exponentiation_ , and _logarithm_ , which are
frequently used in neural networks.

Researchers have proposed various approaches to calculating or approximating
non-linear functions. For instance, the Newton-Rhapson method is a common
approach to approximate reciprocal. Such approximation methods are widely
adopted by recent frameworks, including [40, 59, 34, 44, 43]. The use of these
approaches in complex machine learning tasks, however, presents two obstacles:
a) some functions such as the exponential function $e^{x}$ output values in
vast ranges, causing polynomials to fit poorly; b) piecewise functions, while
effective in addressing accuracy issues, need expensive range detection to
select the appropriate polynomial.

In this paper, we base our methods on the ones from [10, 33, 2]. These methods
all share the concept of mapping the input value into a relatively narrow
range before applying numerical techniques. This input mapping strictly
constrains the input domain for the subsequent numerical approach, resulting
in stable numerical behavior and improved accuracy. We further optimize these
methods by reducing costly operations and using superior numerical methods.

###  5.1 Reciprocal

A commonly used approach for secure reciprocal evaluation is the Newton-
Raphson method [67]. However, this method requires a good initial guess for
convergence, which limits its application. Crypten [34] uses a heuristic
function to generate the initial guess in a specific input domain. The
heuristic function, however, does not have a demonstrable error bound, and its
evaluation is costly. Furthermore, Crypten’s solution cannot handle negative
values, and an additional comparison is needed. Falcon [63] estimates the
rough range of the input by revealing the position of LMO, leaking extra
information.

Algorithm 1 shows our algorithm for reciprocal. For the Newton-Raphson
iteration $x_{n+1}=x_{n}(2-zx_{n})$, we set initial guess $x_{0}=1$. According
to the convergence criterion, $0<x_{0}<\frac{2}{z}$ is required while
$z\in[0.5,1)$. Let $q=1-z$, then we have $x_{1}=1+q$ and
$x_{2}=x_{1}(2-zx_{1})=(1+q)(1+q^{2})$. Through induction, we can derive
$h(z)=x_{n}=\prod_{i=0}^{n-1}\Big{(}1+q^{2^{i}}\Big{)}=\prod_{i=0}^{n-1}\Big{(}1+(1-z)^{2^{i}}\Big{)}$.
The number of iteration rounds $d$ can be set flexibly according to the
tradeoff between accuracy and efficiency. Our idea is that we first obtain the
absolute value of input $x$ (line 1) and scale $|x|$ to the range $[0.5,1)$ by
finding the LMO (line 1 \- 1), then evaluate the numerical method on the
scaled value and finally scale the result back (line 1 \- 1). Note that,
despite restricting the scaling factor in $[2^{-p},2^{p-1}]$ (line 1 \- 1),
meaning we can only scale the input in range $[2^{-p},2^{p})$ to $[0.5,1)$, we
argue that the correctness is unaffected, as the reciprocal of a number
greater than $2^{p}$ underflows the fixed-point representation with precision
$p$.

Our idea is similar to [10], with several optimizations. First, the sign bit
extraction of $x$ shares the secure bit decomposition with LMO (line 1, 1 and
1), making the sign bit extraction free, while [10] invokes an extra secure
comparison between $x$ and $0$. Second, despite that, the standard way for
computing the negative value of a signed integer is to flip the bits and add
$1$, we omit the addition and only perform the bit flip when $x$ is negative
(line 1 \- 1), thus saving a binary addition. This omission only introduces an
extra error of $2^{-p}$ for fixed-point numbers, which is negligible in most
machine learning tasks.

Data: $\llbracket x,p\rrbracket^{\text{A}},x\neq 0$, bit length $l$, precision
$p$

Require: Newton-Raphson iteration function $h(z)$

Result: $\llbracket y,p\rrbracket^{\text{A}}\approx\llbracket
1/x,p\rrbracket^{\text{A}}$

1 $\llbracket
x_{0:l-1}\rrbracket^{\text{B}}\leftarrow\texttt{Decompose}(\llbracket
x,p\rrbracket^{\text{A}})$

2 for  _$i\leftarrow 0$ to $l-2$_ do

3 $\llbracket x_{i}\rrbracket^{\text{B}}\leftarrow\texttt{XOR}(\llbracket
x_{l-1}\rrbracket^{\text{B}},\llbracket x_{i}\rrbracket^{\text{B}})$

4

5 end for

6 $\llbracket s\rrbracket^{\text{A}}\leftarrow\texttt{Bit2A}(\llbracket
x_{l-1}\rrbracket^{\text{B}})$

7 $\llbracket x_{+},p\rrbracket^{\text{A}}\leftarrow\llbracket
x,p\rrbracket^{\text{A}}-2\llbracket s\rrbracket^{\text{A}}\cdot\llbracket
x,p\rrbracket^{\text{A}}$

8 $\llbracket x_{0:l-2}\rrbracket^{\text{B}}\leftarrow\texttt{LMO}(\llbracket
x_{0:l-2}\rrbracket^{\text{B}})$

9 for  _$i\leftarrow 0$ to $p-1$_ do

10 $\texttt{Swap}(\llbracket x_{i}\rrbracket^{\text{B}},\llbracket
x_{2p-1-i}\rrbracket^{\text{B}})$

11

12 end for

13 $\llbracket x_{2p}\rrbracket^{\text{B}},\llbracket
x_{2p+1}\rrbracket^{\text{B}},\dots,\llbracket
x_{l-1}\rrbracket^{\text{B}}\leftarrow 0$

14 $\llbracket t,p\rrbracket^{\text{A}}\leftarrow\texttt{Compose}(\llbracket
x_{0:2p-1}\rrbracket^{\text{B}})$

15 $\llbracket y,p\rrbracket^{\text{A}}\leftarrow\texttt{Truncate}(\llbracket
t,p\rrbracket^{\text{A}}\cdot\llbracket x_{+},p\rrbracket^{\text{A}},p)$

16 $\llbracket y,p\rrbracket^{\text{A}}\leftarrow\texttt{Evaluate}(\llbracket
h(y),p\rrbracket^{\text{A}})$

17 $\llbracket y,p\rrbracket^{\text{A}}\leftarrow\texttt{Truncate}(\llbracket
t,p\rrbracket^{\text{A}}\cdot\llbracket y,p\rrbracket^{\text{A}},p)$

18 $\llbracket y,p\rrbracket^{\text{A}}\leftarrow\llbracket
y,p\rrbracket^{\text{A}}-2\llbracket s\rrbracket^{\text{A}}\cdot\llbracket
y,p\rrbracket^{\text{A}}$

Algorithm 1 Reciprocal.

###  5.2 Exponentiation

Many activation functions in machine learning, such as Sigmoid and Softmax,
significantly rely on exponentiation. Approximation approaches techniques
based on Taylor series [60] or Remez approximation [54] work well for limited
input ranges but have accuracy issues for inputs with a wide range of
variations. Taylor’s theorem states that the approximation is only adequate
near a specific point, so [33] applies the approximation to the fractional
portion of the input rather than relying entirely on the approximation as [59]
does. For example, in deep neural network training, the inputs of Softmax may
range from $-30$ to $30$, causing the output of exponentiation to vary from
$e^{-30}$ to $e^{30}$.

The algorithm for exponentiation proposed by [33] enhances the one in [2], and
we will call this algorithm as _SOTA-exp_. Due to the page limit, we present
the pseudocode of SOTA-exp in Appendix D. The basic idea is that we can
convert the evaluation of $e^{x}$ to $2^{z}$ where $z=x\cdot\log_{2}{e}$. The
benefit is that, for a positive number $z$, we can evaluate $2^{z_{int}}$ by
invoking Compose where $z_{int}$ is the integer part of $z$, and approximate
$2^{z_{dec}}$ with a polynomial for the decimal part of $z$. In this case, we
only need to approximate the decimal portion in $[0,1]$ with polynomials. The
algorithm starts with changing the base to 2 by multiplying $\log_{2}e$ and a
truncation.

Algorithm 2 shows our algorithm. It is based on SOTA-exp but with four major
differences. The first is about how to correct the result of negative inputs.
In line 2 of Algorithm 2, we add a $p$ to $x^{\prime}$ so that values in
$[-p,0)$ become non-negative, we then use truncation to scale back the result
(line 2). If $x^{\prime}<-p$, we set the final result to 0 (line 2 \- 2),
since the result will be less than $2^{-p}$ and underflows the fixed-point
representation with precision $p$. In comparison, SOTA-exp performs a secure
comparison using binary addition, then converts the result to arithmetic
sharing for multiplication. Thus, our strategy saves a binary addition and a
Bit2A.

Second, we keep the precision of the product of line 2 as $2p$, and do the
truncation together with the bit decomposition. With this trick, this
truncation becomes free.

Third, as SOTA-exp uses a truncation of $2^{c}$ bits to correct results of
negative inputs, it sets $l=31,p=16$ to avoid underflow caused by truncation,
and thus it can only process inputs under $(l-p)\ln 2=15\ln 2$. Our algorithm,
on the contrary, exploits the full bit length $l=64$ and handles larger
inputs.

Finally, instead of the Talyor expansion used by SOTA-exp, we use the Remez
algorithm to obtain a more precise approximation. In particular, the Remez
algorithm has consistent error rates within the specified range compared to
Taylor expansion. We list the coefficients obtained by the Remez algorithm in
Appendix B.

Data: $\llbracket x,p\rrbracket^{\text{A}}$, bit length $l$, precision $p$

Require: Remez approximation $f_{1}(z)$

Result: $\llbracket y,p\rrbracket^{\text{A}}\approx\llbracket
e^{x},p\rrbracket^{\text{A}}$

1 $\llbracket x^{\prime},2p\rrbracket^{\text{A}}\leftarrow\llbracket
x,p\rrbracket^{\text{A}}\cdot[\log_{2}e]_{p}$

2 $\llbracket
x^{\prime\prime},2p\rrbracket^{\text{A}}\leftarrow[p]_{2p}+\llbracket
x^{\prime},2p\rrbracket^{\text{A}}$

3 $\llbracket x_{0:l-1}\rrbracket^{\text{B}}\leftarrow\texttt{Decompose \&
Truncate}(\llbracket x^{\prime\prime},2p\rrbracket^{\text{A}},p)$

4 $c\leftarrow\lceil\log_{2}(l-p-1)\rceil$

5 $\llbracket
x_{p:p+c-1}\rrbracket^{\text{A}}\leftarrow\texttt{Bit2A}(\llbracket
x_{p:p+c-1}\rrbracket^{\text{B}})$

6 $\llbracket
I\rrbracket^{\text{A}}\leftarrow\prod_{i=0}^{c-1}\Big{(}2^{2^{i}}\llbracket
x_{p+i}\rrbracket^{\text{A}}-\llbracket x_{p+i}\rrbracket^{\text{A}}+1\Big{)}$

7 $\llbracket t,p\rrbracket^{\text{A}}\leftarrow\texttt{Compose}(\llbracket
x_{0:p-1}\rrbracket^{\text{B}})$

8 $\llbracket y,p\rrbracket^{\text{A}}\leftarrow\llbracket
I\rrbracket^{\text{A}}\cdot\texttt{Evaluate}(\llbracket
f_{1}(t),p\rrbracket^{\text{A}})$

9 $\llbracket s\rrbracket^{\text{A}}\leftarrow 1-\texttt{Bit2A}(\llbracket
x_{l-1}\rrbracket^{\text{B}})$

$\llbracket y,p\rrbracket^{\text{A}}\leftarrow\texttt{Truncate}(\llbracket
s\rrbracket^{\text{A}}\cdot\llbracket y,p\rrbracket^{\text{A}},p)$

Algorithm 2 Exponentiation.

###  5.3 Logarithm

We follow the classic fast algorithm from Goldberg [16] and convert it into a
secure version. The procedure begins by scaling the input value to the
interval $[0.75,1.5)$ before calculating $\log_{2}x$. After that, we calculate
$\ln 2\log_{2}x$ as the result $\ln x$. Specifically, for $x\in[0.75,1.5)$, we
calculate logarithm using a 4th-degree polynomial $f_{2}(z)$. We list the
coefficients of $f_{2}(z)$ from [16] in Appendix B.

Algorithm 3 illustrates the full algorithmic. To scale $x$ to $[0.75,1.5)$, we
first map $x$ to $[0.5,1)$ (line 3, 3, and line 3 \- 3), using the scaling
technique in Algorithm 1, then verify whether $x<0.75$. If that is true, we
double $x$. Checking the following bit of LMO (line 3 \- 3) yields the bit $r$
that indicates whether $x<0.75$ or not. A quick example for $x=50$: its LMO
represents $2^{5}$ since $2^{5}<x<2^{6}$. The bit next to LMO determines
whether $x>2^{5}+2^{4}$ or not. So the scaled $x$ becomes $50/(2\times
2^{5})>0.75$. Since the scaling factor is a power of 2, we can easily
calculate its logarithm. We conclude by combining a polynomial approximation
for scaled input with the logarithm of the scaling factor.

Data: $\llbracket x,p\rrbracket^{\text{A}}$, bit length $l$, precision $p$

Require: Remez approximation $f_{2}(z)$

Result: $\llbracket y,p\rrbracket^{\text{A}}\approx\llbracket\ln
x,p\rrbracket^{\text{A}}$

1 $\llbracket
x_{0:l-1}\rrbracket^{\text{B}}\leftarrow\texttt{Decompose}(\llbracket
x,p\rrbracket^{\text{A}})$

2 $\llbracket
x^{\prime}_{0:2p-1}\rrbracket^{\text{B}}\leftarrow\texttt{LMO}(\llbracket
x_{0:2p-1}\rrbracket^{\text{B}})$

3 $\llbracket
x^{\prime\prime}_{0:2p-2}\rrbracket^{\text{B}}\leftarrow\llbracket
x^{\prime}_{1:2p-1}\rrbracket^{\text{B}},\llbracket
x^{\prime\prime}_{2p-1}\rrbracket^{\text{B}}\leftarrow 0$

4 $\llbracket
r\rrbracket^{\text{B}}\leftarrow\bigoplus_{i=0}^{2p-1}(\llbracket
x_{i}\rrbracket^{\text{B}}\land\llbracket
x^{\prime\prime}_{i}\rrbracket^{\text{B}})$

5 $\llbracket
x_{0:2p-1}\rrbracket^{\text{A}}\leftarrow\texttt{Bit2A}(\llbracket
x_{0:2p-1}\rrbracket^{\text{B}})$

6 $\llbracket r\rrbracket^{\text{A}}\leftarrow\texttt{Bit2A}(\llbracket
r\rrbracket^{\text{B}})$

7 $\llbracket
y_{L}\rrbracket^{\text{A}}\leftarrow\sum_{i=0}^{2p-1}(i-l)\llbracket
x_{i}\rrbracket^{\text{A}}$

8 for  _$i\leftarrow 0$ to $p-1$_ do

9 $\texttt{Swap}(\llbracket x_{i}^{\prime}\rrbracket^{\text{B}},\llbracket
x_{2p-1-i}^{\prime}\rrbracket^{\text{B}})$

10

11 end for

12 $\llbracket m,p\rrbracket^{\text{A}}\leftarrow\texttt{Compose}(\llbracket
x_{0:2p-1}^{\prime}\rrbracket^{\text{B}})$

13 $\llbracket x,p\rrbracket^{\text{A}}\leftarrow 2\llbracket
x,p\rrbracket^{\text{A}}-\llbracket x,p\rrbracket^{\text{A}}\cdot\llbracket
r\rrbracket^{\text{A}}$

14 $\llbracket t,p\rrbracket^{\text{A}}\leftarrow\texttt{Truncate}(\llbracket
x,p\rrbracket^{\text{A}}\cdot\llbracket m,p\rrbracket^{\text{A}},p)-2^{p}$

15 $\llbracket
y_{R},p\rrbracket^{\text{A}}\leftarrow\texttt{Evaluate}(\llbracket
f_{2}(t),p\rrbracket^{\text{A}})$

16 $\llbracket y,p\rrbracket^{\text{A}}\leftarrow(\llbracket
y_{L},p\rrbracket^{\text{A}}+\llbracket
y_{R},p\rrbracket^{\text{A}}+\llbracket r\rrbracket^{\text{A}}\cdot 2^{p})[\ln
2]_{p}$

17 $\llbracket y,p\rrbracket^{\text{A}}\leftarrow\texttt{Truncate}(\llbracket
y,p\rrbracket^{\text{A}},p)$

Algorithm 3 Logarithm.

The above algorithm does not handle inputs exceeding $2^{p}$. We address this
issue with an extra comparison. When receiving an input, we truncate it by
$l-2p$ bits and apply Algorithm 3, then add $l-2p$ back to the result. The
comparison is used to distinguish the two cases. We allow users to decide
whether to perform this comparison in practice.

Prior work [2] proposes an algorithm based on scaling the input into $[0.5,1)$
and applying a division of polynomials to calculate the logarithm for values
in $[0.5,1)$. This division not only substantially increases computational
costs but also introduces inaccuracy because the division relies on
reciprocal, which are challenging to compute precisely. Errors accumulate
through two polynomial evaluations and the division. In contrast, our double
scaling technique confines the input to the range [0.75, 1.5), enabling the
subsequent polynomial approximation to be both precise and efficient in
practice.

###  5.4 Security Analysis

The above algorithms use the operations in Section 4.3 and 4.4 as building
blocks, and those operations work with proven security. Therefore, we can
formalize our algorithms using the _arithmetic black box model_
($F_{ABB}$-$Hybrid$ model) [15], and prove the security of our algorithms
under the framework of _Universal Composition_ [8]. Appendix C shows the
details of the formal proof.

##  6 Hardware Acceleration and Optimizations

Secure computation is typically much more intensive than its plaintext
counterpart. Secure comparison, for instance, requires expensive binary
additions and multi-round communication. Deep neural networks also typically
employ large-scale matrix multiplication and convolution, requiring lots of
secure 64-bit or 128-bit matrix multiplications and truncations. Spin uses
GPUs for accelerating computation, and offloads networking overhead to
SmartNICs.

###  6.1 Computation Acceleration using GPUs

GPUs are frequently used to accelerate highly parallelized computations,
particularly matrix multiplication, and convolution. A GPU contains thousands
of CUDA cores for general computation and hundreds of tensor cores for mixed-
precision computation. As secret-sharing-based protocols usually use 64-bit or
128-bit integers for fixed-point representation, CryptGPU [59] uses an
integral component of four floating-point numbers to construct a 64-bit
integer and employs tensor cores to accelerate operations on floating-point
numbers. Piranha [65], on the contrary, implements integer kernels using
CUTLASS [12],and their evaluations demonstrate that their integer kernels
perform better than those used in CryptGPU. We also use CUTLASS for matrix
multiplication and convolution but implement the GEMM kernels using the built-
in int64 t and  int128 type of CUDA11.6 [47].

In detail, we implement the integer kernel for matrix multiplication with the
following considerations:

  * •

In GPUs, the threads within a thread block can access the same shared memory,
whereas all threads from distinct blocks can only share a global memory.
Shared memory is significantly faster than global memory, but much smaller.
Thus we can use shared memory as the cache of global memory to reduce the
overall data access latency by carefully planning when and what data we need
to move from global memory data into shared memory.

  * •

As access to the shared memory of GPUs is significantly faster than access to
the global memory, we break up the matrix into blocks with a carefully chosen
size that just fits into shared memory and performs block multiplications in
parallel. In this way, each thread block has its copy of the blocks, avoiding
global memory access and contention.

  * •

We construct a pipeline for data loading and computation to exploit the
computational power of GPUs. Specifically, we carefully adjust the size of
each block so that the latency of loading block matrices from global memory
into shared memory matches the time required for the block matrix
multiplication, keeping the pipeline full most of the time.

###  6.2 Communication using SmartNICs

Communication occupies heavily in MPC. High-throughput and low-latency
communication channels are urgent for large-scale secure computation. Some
SmartNICs support _remote direct memory access_ (RDMA) [66], enabling data
copy from the memory of one computer to the memory of another, bypassing the
operating systems and CPUs. We use RDMA to accelerate communication and
introduce several optimizations to overcome the challenges of using RDMA in
practice.

Figure 2: Pipelined data transfer. The ring labeled ‘S’ represents the sending
data ring buffer, while the ring labeled ‘R’ represents the receiving data
ring buffer.

Pipelining data transfer to reduce overall latency. We can implement data
transfer to a remote GPU in a naïve manner: First, the source host gathers all
the data to be sent from the GPU and stores it in the host’s memory. Next, the
source host transmits the data over the network channel. Finally, the remote
host performs the reverse operation. The end-to-end latency consists of three
parts: two data movements between GPU memory and host memory via PCIe, and a
data transfer through the network. If the network channel is a socket channel
over TCP/IP, the data movement latency via PCIe is negligible because it is
typically much less than the socket latency. In the case of RDMA, however, the
data movement latency cannot be overlooked. Given that the bandwidth of RDMA
can reach 200 Gbps in our testbed, the throughput of the end-to-end data
transfer from one GPU to another may be roughly $3\times$ slower than RDMA’s
bandwidth.

To tackle this issue, we introduce a per-host _network agent_ to
asynchronously manage PCIe data movement and network data transfer, as
illustrated in Figure 2. When ready to transmit data, the engine divides it
into fixed-size blocks and inserts them into the sending data buffer block by
block. A network agent worker thread constantly checks and transmits new data,
while another worker thread stores newly arrived blocks and waits for the
engine to retrieve them. The entire data transfer process is thus pipelined,
making the end-to-end throughput close to the RDMA bandwidth.

Allocating ring buffers in pinned memory.  To minimize the cost of frequent
memory allocation and deallocation, a network agent features two _ring
buffers_ : one for sending data and another for receiving data. We implement
the ring buffers using _CUDA pinned memory_ to bypass the operation system’s
virtual memory system so that data can be moved directly between GPU memory
and host memory with the help of DMA. The price of pinned memory is more
initialization time and physical memory space, as pinned memory uses locked
pages and fixed physical memory addresses. However, ring buffers use fixed
memory regions in nature, without the concern of frequently allocating new
memory space, thus can fully enjoy the advantage of pinned memory.

Using sockets over TCP/IP for small data transfer. As RDMA bypasses CPUs, the
main program does not know when a transfer job finishes and usually needs an
assistant channel for notification (see [57, 53] for examples). Therefore,
RDMA cannot consistently outperform sockets over TCP/IP with an excess number
of small data transfers. For data size smaller than a given threshold, Spin
chooses a socket channel over TCP/IP, instead of an RDMA channel, for data
transfer. In our environment, we set the threshold to 0.125MB.

###  6.3 CPU-GPU Hybrid Computation

As mentioned earlier, the high latency associated with data copying between
GPU memory and host memory may offset the benefits of GPU acceleration. For
computation-intensive tasks, such as the secure multiplication of large
matrices, GPU acceleration is advantageous due to the prohibitive computation
time. However, for tasks requiring numerous communication rounds, each
involving minimal computation and only a few small data blocks for transfer,
using GPUs can reduce overall performance since the cost of data copy
dominates. For example, the Softmax function falls into this category.

We tackle this issue by employing a _CPU-GPU hybrid mode_. Spin utilizes a few
CPU cores (e.g., 20 cores) to handle operations characterized by lightweight
computation, frequent communication, and small network packets, while GPUs
manage the rest. This approach achieves improved performance without incurring
additional costs. Furthermore, since using RDMA in practice still requires a
socket for synchronization, employing RDMA for communication becomes
superfluous for frequent, small package transfers. Consequently, we utilize
sockets for communication incurred by CPU activities and RDMA for GPU
operations.

##  7 Attention-Specific Optimizations

(a) LeViT-256 inference

(b) Attention block

Figure 3: Runtime breakdown.

The attention mechanism is the fundamental building block of Transformer
models, such as LeViT [25], GPTs [49, 6] and BERT [19]. An attention block
involves a batch Softmax on an intermediate matrix that is usually of the
largest size among all the variants, making attention evaluation expensive.
Recent Transformer models even contain millions or billions of parameters,
meaning training such a model requires pretty high costs. Fig. 3 demonstrates
the runtime breakdown of secure LeViT-256 inference and an attention block
running on Semi2k. In various Transformer models, attention dominates the
evaluation time of LeViT-256 inference. For example, [39] also shows that
Softmax and matrix multiplication dominate the runtime of $BERT_{BASE}$,
indicating the domination of attention. Thus, it is essential to optimize the
evaluation of attention blocks.

Existing works such as [20, 39] focus on optimizing basic operations like
Softmax and GeLU without exploiting the characteristics of attention.
Contrarily, we treat an attention block as a whole and perform optimizations
across operations.

We normally compute $\texttt{Softmax}(X_{i})$ as
$\frac{e^{X_{i}-\texttt{Max}(X)}}{\sum_{i}e^{X_{i}-\texttt{Max}(X)}}$ in
secure computation to avoid overflow and achieve numerical stablility [20,
65]. We denote the step of finding and subtracting the maximum value as
MaxCut, as Fig. 4(a) and 4(c) illustrate. Fig. 4(b) shows the detail of a
Softmax circuit.

We propose a series of new optimizations for attention evaluation in secure
inference. To reduce arithmetic computation on 64-bit numbers, we temporarily
convert the representation to 32-bit fixed points and convert it back for free
when necessary. To optimize exponentiation in attention, we explore how the
input of exponentiation in attention differs from general exponentiation. We
also find that we can break down Softmax and integrate the operations with
other operations in attention to get better performance. We finally implement
a kernel to parallelize independent matrix multiplications for a multi-head
attention mechanism. Fig. 4(d) illustrates our optimized attention block.

(a) Original attention

(b) Softmax

(c) Secure attention

(d) Our optimized secure attention

Figure 4: Details of attention blocks.

###  7.1 Mixing Bit Lengths

To handle complex tasks, Fixed64 (i.e., a real number is mapped to a 64-bit
fixed-point number) is necessary, as secure multiplication doubles the
precision immediately, and Fixed32 multiplication would overflow with the
precision of more than 16 bits. Recent works, such as [65, 34, 20], usually
use Fixed64 throughout a task. However, we observe that some steps in secure
inference can work with 32 bits. For example, MaxCut in attention does not
require 64 bits to handle overflow so we can cast Fixed64 to Fixed32 before
MaxCut, and our carefully designed exponentiation (see Section 7.2 for
details) can receive Fixed32 as input and outputs Fixed64 without extra costs.
As casting a secret-shared value from Fixed64 to Fixed32 can be performed
locally in each party, we can nearly halve the cost of secure comparison that
dominates the cost of MaxCut, _for free_.

###  7.2 Exponentiation for Attention

We customize Algorithm 2 with several novel optimizations specific to
attention.

Moving scaling to plaintext. In secure inference, the model handler can
perform any plaintext processing on model parameters beforehand. At the
attention block level, the model parameters include the weight $W$ and bias
$b$ of Linear (see Fig. 4(d)). As the scaling step (line 2) of Algorithm 2
uses a constant number $\log_{2}e$, we can actually move the scaling to
Linear, that is, we use $W^{\prime}=\log_{2}e\cdot W$ and
$b^{\prime}=\log_{2}e\cdot b$ to replace $W$ and $b$ respectively and do not
need scaling in exponentiation anymore. It is easy to see that this
replacement does not hurt the correctness. Furthermore, due to the elimination
of the scaling, the input of line 2 is of precision $p$, so we do not need
truncation in the next step (line 2). We thus eliminate a scaling and a
truncation for exponentiation.

Casting from Fixed32 to Fixed64 for free. Unlike casting from Fixed64 to
Fixed32 that can be performed locally in each party, the normal way to cast
from Fixed32 to Fixed64 is to extract the sign bit and extend the number with
it. However, sign bit extraction is usually a costly operation [29, 40, 43].
In Algorithm 2, as there is an inherent bit decomposition (line 2), we only
need to perform the Bit2A conversion from binary representation to 64-bit
arithmetic representation as usual, irrespective of whether the input is of
bit length 32 or 64. That is, we successfully _convert Fixed32 to Fixed64
without extra costs_.

Completing the square to save secure multiplications. We use Remez
approximation to evaluate exponentiation on decimal fractions (line 2 of
Algorithm 2). Specifically, we use a 4-degree polynomial (Eq.(1)), which
requires three secure multiplications and four scalings. We reduce the number
of secure multiplications by _completing the square_.

$\displaystyle f(x)$
$\displaystyle=k_{4}x^{4}+k_{3}x^{3}+k_{2}x^{2}+k_{1}x+k_{0}\ \ $
$\displaystyle(1)$
$\displaystyle=k_{4}(((x+t_{3})^{2}+t_{2})^{2}+t_{1}x+t_{0})\ \ $
$\displaystyle(2)$ $\displaystyle f^{\prime}(x)$
$\displaystyle=k_{4}^{\prime}(((x+t_{3})^{2}+t_{2})^{2}+t_{1}x+t_{0})\ \ $
$\displaystyle(3)$
$\displaystyle=k_{4}^{\prime}((x+t_{3})^{2}+t_{2})^{2}+(k_{4}^{\prime}t_{1})x+k_{4}^{\prime}t_{0}$
$\displaystyle(4)$

Eq.(2) shows the result of completing the square. It requires two secure
multiplications and two scalings. We further observe that $k_{4}$ is a common
factor shared by the outputs of exponentiation on different inputs (see line 2
\- 2 of Algorithm 2). It will be eliminated in Softmax, thus the concrete
value of $k_{4}$ does not affect the output of Softmax. However, ignoring
$k_{4}$, though saving a scaling, may make the outputs of exponentiation too
large or too small, which may increase the relative error of the following
steps. We address this issue by replacing $k_{4}$ with the nearest power of 2
so that the output range remains similar, then using truncation to replace the
scaling.

Notably, this truncation can be free, as we can fuse it with the subsequent
secure multiplications. For example, we can replace the $k_{4}=0.0135$ of
$f_{1}(x)$ in Algorithm 2 with $k_{4}^{\prime}=2^{-6}$, then truncate the
second square $p+6$ bits instead of $p$ bits. Finally, we get Eq.(4), which
needs two secure multiplications and a scaling, _saving one secure
multiplication and three scalings_ compared to Eq.(1). Note that the
coefficients $k_{4}^{\prime}t_{0}$ and $k_{4}^{\prime}t_{1}$ can be pre-
calculated in plaintext. Appendix B shows the values of these newly introduced
parameters.

Ignoring unnecessary bits of the integer part. Remember that we evaluate
exponentiation as $e^{x}=2^{x\cdot\log_{2}e}=2^{x^{\prime}_{int}}\cdot
f_{1}(x^{\prime}_{dec})$, where $x^{\prime}$ is $x\cdot\log_{2}e$,
$x^{\prime}_{int}$ is the integer part of $x^{\prime}$, $x^{\prime}_{dec}$ is
the decimal part of $x^{\prime}$, and $f_{1}(x^{\prime}_{dec})$ is the Remez
approximation of $2^{x^{\prime}_{dec}}$. In Algorithm 2, we use a bias $p$ to
ensure a correct output for $x^{\prime}\in[-p,0)$, and line 2 determines the
maximum number of bits for calculating $2^{(x^{\prime}+p)_{int}}$. In the
general case, $l=64$ and $p=14$, thus $c=6$. However, for Softmax, we have
$x^{\prime}\leq 0$ after MaxCut, and if we adjust the evaluation of Softmax
from $\frac{e^{X_{i}-\texttt{Max}(X)}}{\sum_{i}e^{X_{i}-\texttt{Max}(X)}}$ to
$\frac{e^{X_{i}-\texttt{Max}(X)-\epsilon}}{\sum_{i}e^{X_{i}-\texttt{Max}(X)-\epsilon}}$
where $\epsilon$ is a negligible number (e.g., $\epsilon=2^{-14}$), we can get
$x^{\prime}<0$, indicating $x^{\prime}+p<p$. Furthermore, since the result
would underflow and would be set to $0$ when $x^{\prime}<-p$, we only need to
consider the case $x^{\prime}+p\in[0,p)$. Therefore, in the Softmax case, we
can set $c=\log_{2}p=4$. In this way, we further _save two secure
multiplications_.

Based on the above optimizations, we save 3 secure multiplications, 4
scalings, and 1 truncation for attention-specific exponentiation in total. We
summarize this variant of exponentiation in Appendix E.

###  7.3 Downsizing Batch Multiplication.

The last step of Softmax is to multiply
$\frac{1}{\sum_{i}e^{X_{i}-\texttt{Max}(X_{i})}}$ and
$e^{X_{i}-\texttt{Max}(X_{i})}$ for all $i$, which is a batch multiplication,
namely the element-wise multiplication of two arrays of the same size. In an
attention block, the size of the input of Softmax is usually larger than the
size of other operations, thus moving this batch multiplication elsewhere can
downsize it.

Fig. 4(b) illustrates the Softmax circuit. The operation Mul denotes batch
multiplication, and we use the symbol $*$ to denote this operation. Now let us
assume the outputs of Exp, Sum and Reciprocal in Fig. 4(b) are $E$, $S$ and
$R$ respectively, then if the size of $E$ is $D_{1}\times D_{2}$, it is easy
to deduce that the size of $R$, as well as the size of $S$, is $1\times
D_{2}$. Of course, we should first tile the elements of $R$ for $D_{1}$ times
to get a new array of size $D_{1}\times D_{2}$ before evaluating Mul. Here we
assume the notation $E*R$ implies this tiling. Then if we put Softmax and the
final matrix multiplication together, the output of an attention block can be
written as $(E*R)@V$ (see Fig. 4(c)), where $V$ is of size $D_{2}\times D_{3}$
and the symbol $@$ here stands for matrix multiplication.

On the other hand, we observe that $(E*R)@V=E@(R*V)$. The size of MatMul
remains, whereas the size of Mul changes from $D_{1}\times D_{2}$ to
$D_{2}\times D_{3}$. In attention blocks, we usually have $D_{1}=D_{2}$ and
$D_{2}$ is multiple times larger than $D_{3}$. For example, in the original
paper of attention [62], we have $D_{1}=D_{2}=512$ and $D_{3}=64$, so we can
downsize Mul by $8\times$, as $\frac{D_{1}\times D_{2}}{D_{2}\times D_{3}}=8$,
while in LeViT-256 [25], we have $D_{1}=D_{2}=196$ and $D_{3}=64$, indicating
a benefit of more than $3\times$.

###  7.4 Parallelizing Matrix Multiplications

Transformer models rely on multi-head attention to better amplify key elements
and filter less important ones. Multi-head attention mechanism involves
multiple independent matrix multiplications, and matrix multiplication in
attention blocks usually works on matrices of size hundreds $\times$ hundreds.
Such a matrix multiplication can hardly fully utilize the computation
resources of a GPU like A100 with thousands of cores, as allocating too few
computation tasks to each core cannot balance the time of communication,
scheduling, and computation. Thus if we calculate independent matrix
multiplications in series, the GPU resources cannot be fully utilized.

We address this issue by implementing a CUDA kernel that receives two arrays
of matrices as input and calculates matrix multiplications in parallel. This
operation can be formalized as
$\llbracket\textbf{Z}\rrbracket^{\text{A}}\leftarrow\texttt{PMatMul}(\llbracket\textbf{X}\rrbracket^{\text{A}},\llbracket\textbf{Y}\rrbracket^{\text{A}})$,
where X, Y and Z are arrays of matrices and $Z_{i}=X_{i}@Y_{i}$. At the
implementation level, we divide the GPU cores into several groups and feed
independent tasks to different groups. Each group handles several matrix
multiplications so that the GPU cores do not wait too long for scheduling and
communication. We set the number of core groups to $8$ in our paper.

##  8 Experiments

We run four types of experiments. The first one includes several
microbenchmarks demonstrating the benefits of our optimization ideas of
utilizing hardware. The second is a function-level comparison among
implementations from [34], state-of-the-art approaches from [10, 33, 2], and
the novel algorithms of Spin. The third is the performance of neural network
training and inference, compared with Piranha [65], the state-of-the-art GPU-
assisted framework. In the last one, we report the performance of secure
inference of a pre-trained Transformer model with 18.9 million parameters.

###  8.1 Experiment Setup

Each party uses a machine with 512 GB RAM and uses AMD EPYC 7H12 CPU (2.6 GHz,
64 cores with 128 threads). The engine of each party runs on an Nvidia A100
GPU with 80 GB memory and uses a Mellanox ConnectX-6 for networking. Both A100
and ConnectX-6 interact with the host through PCIe 4.0. The machines are
connected by a Mellanox Quantum QM8790 200 Gbps InfiniBand switch. With the
QM8790 and ConnectX-6, the parties can communicate using both socket and RDMA,
achieving bandwidths of up to 25 Gbps for socket channels and 200 Gbps for
RDMA.

We implement Spin using C++ 17 and use CUDA toolkit 11.6 for GPU-related
operations. We offer a flag that allows users to choose between CPU, GPU, and
hybrid mode. We use the RDMA-core library [53] to implement our RDMA-based
network components. In total, there are 31k lines of C++ code, including all
components and algorithms.

###  8.2 Microbenchmarks

Integer kernel. We compare the performance of our 64-bit integer kernel for
matrix multiplication in Spin with Piranha’s CUTLASS implementation
(https://github.com/jlwatson/piranha-cutlass, commit id e4f6c42). We employ an
Nvidia A100 to run plaintext matrix multiplication of different matrix sizes.
Fig. LABEL:fig:gemm shows that for matrix size smaller than $1000\times 1000$,
Spin is about 2.4$\times$ faster than Piranha-CUTLASS, and for larger
matrices, the performance of Spin is close to Piranha-CUTLASS.

(a)

(b)

(c)

Figure 5: The performance of our integer kernel and pipelined communication
solution.

Pipelined data transfer. As mentioned in Section 6.2, we use a _network agent_
on each host to pipeline the data transfer so that the data copy between hosts
and GPUs would not hinder the end-to-end performance. We record the latency of
transferring data of different sizes from a GPU to a remote one, using RDMA
and socket, respectively. For comparison, we also record the latency of pure
RDMA/socket channels (i.e., the time for transferring data with pure
RDMA/socket channels, without the latency of data copy between GPUs and
hosts), and the latency of the naïve method mentioned in Section 6.2. As Fig.
LABEL:fig:channel_rdma and Fig. LABEL:fig:channel_socket show, our pipelined
solution nearly eliminates the influence of data copy between hosts and GPUs,
while achieving about $2\times$ performance improvement compared to the naïve
method.

###  8.3 Non-linear Functions

We conduct benchmarks on three non-linear functions: reciprocal,
exponentiation, and logarithm. We compare our algorithms to both naïve and
state-of-the-art (SOTA) approaches. To our knowledge, the SOTAs are:
reciprocal in [10], exponentiation in [33], and logarithm in [2]. We refer to
them as _SOTA-rec, SOTA-exp, SOTA-log_ , respectively. Crypten [34] presents
_naïve_ approaches for these functions: Newton-Raphson method for reciprocal,
limit approximation for exponentiation, and Householder method for logarithm.

Fig. 6 shows the comparison of accuracy and running time. The left column
records the accuracy, while the right column is for running time. The
parameters are all from the default settings in the articles or related codes.
Compared with the naïve implementations, both our algorithms and SOTAs have
remarkable advantages in accuracy. Compared to SOTAs, our algorithms for
exponentiation and logarithm are more accurate and stable. For $x>10$, SOTA-
exp even overflows. Note that our reciprocal algorithm is based on SOTA-rec
with several optimizations so that the accuracy curves overlap.

As the accuracy of the naïve implementations is not practical enough, we only
compare the running time of our algorithms with SOTAs. We run them on Spin
backend in a two-party setting. Each party uses 20 CPU cores for computation,
and the two parties communicate using RDMA. We run the evaluation 10 times and
take the average running time. Compared to SOTAs, the advantage of our
algorithms increases as the input scale grows. When the input scale reaches
$10^{6}$ elements, the advantage of our algorithms can be up to about $15\%$
on reciprocal/exponentiation and $100\%$ on logarithm.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 6: Accuracy and running time of non-linear functions. The segments
colored yellow mean overflows.

###  8.4 Neural Network Training and Inference

We compare our empirical performance on real neural networks with Piranha
[65], the framework with state-of-the-art performance, to the best of our
knowledge. We compare Spin in a 2-party setting with two protocols from
Piranha: _P-SecureML_ , a 2-party protocol, and _P-Falcon_ , which is based on
a 3-party protocol with the assumption of honest majority.

We use the same set of neural network models utilized in Piranha’s evaluation
[65], including: a Simple model from SecureML [44], LeNet [38], AlexNet [36],
VGG16 [58]. The first two models use MNIST [37] as the dataset, and others use
CIFAR10 [35]. MNIST has 60,000 / 10,000 training/test samples, each of which
has a size of $28\times 28$. CIFAR10 has 50,000 / 10,000 samples, each of
which is $32\times 32$ with RGB channels. Following Piranha’s setting, we
modify the models by replacing the max-pooling layer with the average pooling
layer. In our experiments, we remove a few layers in VGG16, as we observe that
these layers have minimal impact on the final accuracy. We denote the modified
version as _VGG16m_. We use the same Kaiming initialization [27], learning
rate, and mini-batch size as Piranha. We list the detailed structure for all
neural networks in Appendix A.

We run Piranha and Spin in the same testbed mentioned above. The built-in
network module of Piranha only supports sockets over TCP/IP. To make a fair
comparison, we further optimize the socket with pipelining and implement an
RDMA-based network module for Piranha. Spin can run in three modes: CPU, GPU,
and hybrid mode. Both CPU mode and GPU mode can run with sockets or RDMA,
while the hybrid mode can use both (as Section 6.3 details).

Neural network training time. Table 1 displays the running time of one _epoch_
(one epoch consists of training on all data samples once). Consistent with
Piranha’s setting, we only report online time here. We have the following
observations:

  * •

RDMA in the Simple model is slower. This is because the computation time is so
small that the overhead of moving data in RDMA dominates the total time.

  * •

For large neural networks, RDMA has clear advantages in all three protocols.

  * •

For all the models other than the Simple model, the hybrid mode of Spin
outperforms all the other settings, achieving up to $2\times$ faster than the
RDMA-enhanced P-Falcon.

As a side note, Spin offers stronger security than P-Falcon. Piranha computes
reciprocal in plaintext to accelerate Softmax for accuracy and efficiency. The
code of Piranha offers a fully secure softmax version
(https://github.com/ucbrise/piranha, commit id dfbcb59), using a quadratic
polynomial to approximate reciprocal, but the training fails (the accuracy
converges to about 10%) when using this rough approximation. That is, even
with stronger security, Spin-hybrid still outperforms P-Falcon.

| Channel | Simple | LeNet | AlexNet | VGG16m
---|---|---|---|---|---
Spin-CPU | socket | 26.6 | 539.6 | 552.7 | 21160.6
RDMA | 34.0 | 510.5 | 546.7 | 20651.1
Spin-GPU | socket | 57.0 | 187.1 | 188.8 | 1432.8
RDMA | 59.1 | 158.0 | 141.5 | 835.3
Spin-hybrid | hybrid | 32.0 | 120.5 | 119.4 | 804.4
P-SecureML | socket | 65.8 | 271.9 | 385.0 | 1847.3
RDMA | 73.8 | 185.7 | 274.3 | 1442.5
P-Falcon | socket | 48.0 | 266.4 | 345.6 | 1692.4
RDMA | 49.0 | 162.9 | 265.8 | 1686.8
Table 1: Neural network training time for one epoch.

Accuracy of trained models. The accuracy results are obtained by training 10
epochs on the training set and evaluating the test set. The precisions (i.e.,
the precision parameter $p$ as defined in Section 5) are 23/23/23/26 bits for
Simple/LeNet/AlexNet/VGG16m. We train the models from scratch by initialing
all parameters randomly, to better demonstrate Spin’s capabilities. Table 2
demonstrates that Spin produces better accuracy for all neural networks. This
is mainly thanks to our optimized algorithms for non-linear functions,
compared to Piranha’s simple polynomial approximation.

We also train and test the model in a plaintext version using double-precision
floating points, and the result shows that Spin achieves results _closed to
the plaintext version_ , while P-SecureML and P-Falcon result in much lower
accuracy in AlexNet. In total, we can see that Spin outperforms Piranha in
both efficiency and accuracy.

| DataType | Simple | LeNet | AlexNet | VGG16m
---|---|---|---|---|---
Spin | Fixed64 | 97.48 | 98.89 | 54.79 | 63.17
P-SecureML | Fixed64 | 96.56 | 97.13 | 37.01 | 53.08
P-Falcon | Fixed64 | 97.10 | 97.13 | 38.97 | 53.08
Plaintext | double | 97.83 | 99.08 | 55.16 | 64.41
Table 2: Neural network accuracy on the test set.

Inference performance.  We also display the inference performance (measured by
images per second) for all neural networks in Table 3. We run Piranha using
our RDMA implementation, and we set Spin to operate in the hybrid mode. The
results show an improvement up to $2.6\times$ over P-Falcon.

| Simple | LeNet | AlexNet | VGG16m
---|---|---|---|---
Spin | 13485.81 | 3288.98 | 2999.40 | 166.30
P-SecureML | 12241.10 | 1598.32 | 1472.42 | 44.65
P-Falcon | 12025.87 | 2149.20 | 1767.94 | 62.88
Table 3: Inference performance (images per second).

Scalablility with number of parties Spin can theoretically work on any number
of parties with a dishonest majority. We evaluate the performance of Spin over
the Simple model with 2-5 parties, using RDMA for communication. Table 4 shows
the results, where $Rate=\frac{\text{running time}}{\text{2-party running
time}}$. As the number of parties increases, the communication complexity of
online computation grows linearly. We observe a stable running time that
increases linearly with the number of parties.

Parties | 2 | 3 | 4 | 5
---|---|---|---|---
Time | 37.24 | 54.90 | 82.22 | 102.88
Rate | 1.00 | 1.47 | 2.21 | 2.76
Table 4: Scalability of Spin with different numbers of parties.

###  8.5 Transformer Inference

The goal of this experiment is to demonstrate the benefits of our novel
optimizations in Section 7. We first test the running time and communication
incurred by the first attention block of LeViT-256 with the whole validation
set and additionally collect _mean squared error (MSE)_ values. This
evaluation can show the performance of different solutions on an attention
block with the same input. We then use LeViT-256 inference as an example of
Transformer models and record the throughput and accuracy. LeViT [25] is a
Vision Transformer for fast inference of image classification. We choose
LeViT-256 with 18.9 million parameters and use the ImageNet [18] dataset,
which has images of size $224\times 224$ with RGB channels.

Performance of Spin. Piranha, the state-of-the-art GPU-assisted MPC framework,
has not supported Transformer models yet. MPCFormer [39] is one of the latest
frameworks for secure Transformer inference. An important issue of MPCFormer
is that it does not support pre-trained models, and requires models to be
retrained using _2Quad approximation_ for non-linear functions. PUMA [20], to
our knowledge, is the state-of-the-art of secure inference of large pre-
trained models. The key contributions of PUMA are new approximations for GeLU,
Softmax, and LayerNorm. However, it currently only supports running on CPUs.
So we only report the performance of Spin, in line 1 of Table 5.

Ablation study. We demonstrate the benefits of our attention-specific
optimizations by replacing the attention implementation with other approaches:

  * •

Spin w/P-softmax: Spin backend with all the optimizations except those in
Section 7, while Softmax is replaced with PUMA’s.

  * •

Spin w/S-nonlinear: Spin backend with all the optimizations except those in
Section 7, while the non-linear functions are implemented using SOTAs as in
Section 8.3.

A notable thing is that, LeViT uses Hardswish to replace GeLU and fuses
LayerNorm to Linear, so we only borrow Softmax from PUMA. But as both Fig. 3
and [39] show, Softmax and MatMul dominate the performance of Transformer
inference, hence replacing Softmax solely is enough to demonstrate the
advantages of our optimizations compared to PUMA. The results are reported in
line 2-3 of Table 5.

For attention evaluation, we can see that our solution outperforms the others
in both efficiency and communication cost while achieving the best precision.
For secure inference, Spin also gets the best efficiency and better accuracy
than PUMA’s Softmax. In conclusion, our attention-specific optimizations
enable Spin to achieve advantages in efficiency, communication, and accuracy.

| Attention Block | LeViT-256
---|---|---
Time | Comm. | MSE | Thro. | Accu.
Spin | 23.50 | 56.04 | 4.10e-6 | 3.08 | 80.0
Spin w/P-softmax | 28.85 | 61.43 | 4.82e-3 | 2.57 | 79.2
Spin w/S-nonlinear | 34.20 | 82.06 | 2.72e-5 | 2.38 | 80.0
Table 5: Performance on attention blocks and LeViT-256 inference (time in ms,
communication in MB, throughput in img/s). The accuracy of plaintext inference
is 81.6%.

##  9 Conclusions and Future Work

Implementing machine learning on MPC frameworks necessitates numerous subtle
optimizations to enhance both efficiency and accuracy. At the MPC protocol
level, it is crucial to trade-off between bits utilization and the associated
costs. At the neural network level, it is helpful to exploit the
characteristics of high-level components instead of basic operations.
Additionally, new generation of hardware and networks, including GPUs and
RDMA, significantly speed up computation. However, managing memory and data
movements among these devices requires considerable effort.

Our optimizations in Spin prove to be highly effective. Compared to existing
highly-optimized solutions, Spin simultaneously achieves superior security,
performance, and accuracy. Spin paves the way for several future advancements.
Firstly, we plan to utilize a GPU cluster for each party and design
heterogeneous computing scheduling specific to MPC tasks. Additionally, we aim
to support larger inputs exceeding GPU memory capacity by transparently
caching data in host memory and disks, which is vital for accommodating larger
models. Lastly, we will explore more optimizations for secure training of
large models.

## References

  * [1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016.
  * [2] Abdelrahaman Aly and Nigel P Smart.  Benchmarking privacy preserving scientific operations.  In Applied Cryptography and Network Security: 17th International Conference, ACNS 2019, Bogota, Colombia, June 5–7, 2019, Proceedings, pages 509–529. Springer, 2019.
  * [3] Donald Beaver.  Efficient multiparty protocols using circuit randomization.  In Advances in Cryptology—CRYPTO’91: Proceedings 11, pages 420–432. Springer, 1992.
  * [4] Donald Beaver.  Precomputing oblivious transfer.  In Advances in Cryptology—CRYPT0’95: 15th Annual International Cryptology Conference Santa Barbara, California, USA, August 27–31, 1995 Proceedings, pages 97–109. Springer, 2001.
  * [5] Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson.  Completeness theorems for non-cryptographic fault-tolerant distributed computation.  In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 1–10, 1988.
  * [6] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901, 2020.
  * [7] Megha Byali, Harsh Chaudhari, Arpita Patra, and Ajith Suresh.  Flash: fast and robust framework for privacy-preserving machine learning.  Cryptology ePrint Archive, 2019.
  * [8] Ran Canetti.  Universally composable security: A new paradigm for cryptographic protocols.  In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 136–145. IEEE, 2001.
  * [9] Octavian Catrina and Sebastiaan De Hoogh.  Improved primitives for secure multiparty integer computation.  In Security and Cryptography for Networks: 7th International Conference, SCN 2010, Amalfi, Italy, September 13-15, 2010. Proceedings 7, pages 182–199. Springer, 2010.
  * [10] Octavian Catrina and Amitabh Saxena.  Secure computation with fixed-point numbers.  In Financial Cryptography and Data Security: 14th International Conference, FC 2010, Tenerife, Canary Islands, January 25-28, 2010, Revised Selected Papers 14, pages 35–50. Springer, 2010.
  * [11] Harsh Chaudhari, Rahul Rachuri, and Ajith Suresh.  Trident: Efficient 4pc framework for privacy preserving machine learning.  arXiv preprint arXiv:1912.02631, 2019.
  * [12] CUTLASS contributors.  CUTLASS: Cuda templates for linear algebra subroutines.  https://github.com/NVIDIA/cutlass, 2023.
  * [13] Anders Dalskov, Daniel Escudero, and Marcel Keller.  Secure evaluation of quantized neural networks.  Proceedings on Privacy Enhancing Technologies, 4:355–375, 2020\.
  * [14] Anders PK Dalskov, Daniel Escudero, and Marcel Keller.  Fantastic four: Honest-majority four-party secure computation with malicious security.  In USENIX Security Symposium, pages 2183–2200, 2021.
  * [15] Ivan Damgård and Jesper Buus Nielsen.  Universally composable efficient multiparty computation from threshold homomorphic encryption.  In Advances in Cryptology-CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003. Proceedings 23, pages 247–264. Springer, 2003.
  * [16] David Goldberg.  Fast approximate logarithms, part iii: The formulas, 2015.  https://tech.ebayinc.com/engineering/fast-approximate-logarithms-part-iii-the-formulas/, Last accessed on 2023-03-01.
  * [17] Daniel Demmler, Thomas Schneider, and Michael Zohner.  Aby-a framework for efficient mixed-protocol secure two-party computation.  In NDSS, 2015.
  * [18] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [19] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [20] Ye Dong, Wen-jie Lu, Yancheng Zheng, Haoqi Wu, Derun Zhao, Jin Tan, Zhicong Huang, Cheng Hong, Tao Wei, and Wenguang Cheng.  Puma: Secure inference of llama-7b in five minutes.  arXiv preprint arXiv:2307.12533, 2023.
  * [21] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014.
  * [22] Daniel Escudero, Satrajit Ghosh, Marcel Keller, Rahul Rachuri, and Peter Scholl.  Improved primitives for mpc over mixed arithmetic-binary circuits.  In Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II 40, pages 823–852. Springer, 2020\.
  * [23] Xiaoyu Fan, Kun Chen, Guosai Wang, Mingchun Zhuang, Yi Li, and Wei Xu.  Nfgen: Automatic non-linear function evaluation code generator for general-purpose mpc platforms.  In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 995–1008, 2022.
  * [24] O Goldreich, S Micali, and A Wigderson.  How to play any mental game.  In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 218–229, 1987.
  * [25] Benjamin Graham, Alaaeldin El-Nouby, Hugo Touvron, Pierre Stock, Armand Joulin, Hervé Jégou, and Matthijs Douze.  Levit: A vision transformer in convnet’s clothing for faster inference.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 12259–12269, 2021.
  * [26] Kanav Gupta, Deepak Kumaraswamy, Nishanth Chandran, and Divya Gupta.  Llama: A low latency math library for secure inference.  Cryptology ePrint Archive, 2022.
  * [27] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In Proceedings of the IEEE international conference on computer vision, pages 1026–1034, 2015.
  * [28] Zhicong Huang, Wen-jie Lu, Cheng Hong, and Jiansheng Ding.  Cheetah: Lean and fast secure $\\{$two-party$\\}$ deep neural network inference.  In 31st USENIX Security Symposium (USENIX Security 22), pages 809–826, 2022.
  * [29] Marcel Keller.  Mp-spdz: A versatile framework for multi-party computation.  In Proceedings of the 2020 ACM SIGSAC conference on computer and communications security, pages 1575–1590, 2020.
  * [30] Marcel Keller, Emmanuela Orsini, and Peter Scholl.  Mascot: faster malicious arithmetic secure computation with oblivious transfer.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 830–842, 2016.
  * [31] Marcel Keller, Valerio Pastro, and Dragos Rotaru.  Overdrive: making spdz great again.  In Advances in Cryptology–EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29-May 3, 2018 Proceedings, Part III, pages 158–189. Springer, 2018.
  * [32] Marcel Keller and Ke Sun.  Effectiveness of mpc-friendly softmax replacement.  arXiv preprint arXiv:2011.11202, 2020.
  * [33] Marcel Keller and Ke Sun.  Secure quantized training for deep learning.  In International Conference on Machine Learning, pages 10912–10938. PMLR, 2022.
  * [34] Brian Knott, Shobha Venkataraman, Awni Hannun, Shubho Sengupta, Mark Ibrahim, and Laurens van der Maaten.  Crypten: Secure multi-party computation meets machine learning.  Advances in Neural Information Processing Systems, 34:4961–4973, 2021.
  * [35] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [36] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Communications of the ACM, 60(6):84–90, 2017.
  * [37] Yann LeCun.  The mnist database of handwritten digits.  http://yann. lecun. com/exdb/mnist/, 1998.
  * [38] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [39] Dacheng Li, Hongyi Wang, Rulin Shao, Han Guo, Eric Xing, and Hao Zhang.  Mpcformer: Fast, performant and private transformer inference with mpc.  In The Eleventh International Conference on Learning Representations, 2022.
  * [40] Yi Li and Wei Xu.  Privpy: General and scalable privacy-preserving data mining.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1299–1307, 2019.
  * [41] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017.
  * [42] Yibai Meng, Shuxian Wang, and Alex Schedel.  Multi-gpu for piranha, a multiparty computation framework.
  * [43] Payman Mohassel and Peter Rindal.  Aby3: A mixed protocol framework for machine learning.  In Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pages 35–52, 2018.
  * [44] Payman Mohassel and Yupeng Zhang.  Secureml: A system for scalable privacy-preserving machine learning.  In 2017 IEEE symposium on security and privacy (SP), pages 19–38. IEEE, 2017.
  * [45] Moni Naor and Benny Pinkas.  Efficient oblivious transfer protocols.  In SODA, volume 1, pages 448–457, 2001.
  * [46] Milad Nasr, Reza Shokri, and Amir Houmansadr.  Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning.  In 2019 IEEE symposium on security and privacy (SP), pages 739–753. IEEE, 2019.
  * [47] NVIDIA.  https://developer.nvidia.com/blog/cuda-11-6-toolkit-new-release-revealed-2/, 2022\.
  * [48] OpenAI.  GPT-4 technical report.  arXiv preprint arXiv:2303.08774, 2023.
  * [49] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  OpenAI blog, 1(8):9, 2019.
  * [50] Deevashwer Rathee, Anwesh Bhattacharya, Rahul Sharma, Divya Gupta, Nishanth Chandran, and Aseem Rastogi.  Secfloat: Accurate floating-point meets secure 2-party computation.  In 2022 IEEE Symposium on Security and Privacy (SP), pages 576–595. IEEE, 2022.
  * [51] Deevashwer Rathee, Mayank Rathee, Rahul Kranti Kiran Goli, Divya Gupta, Rahul Sharma, Nishanth Chandran, and Aseem Rastogi.  Sirnn: A math library for secure rnn inference.  In 2021 IEEE Symposium on Security and Privacy (SP), pages 1003–1020. IEEE, 2021.
  * [52] Deevashwer Rathee, Mayank Rathee, Nishant Kumar, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma.  Cryptflow2: Practical 2-party secure inference.  In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 325–342, 2020.
  * [53] RDMA-core contributors.  RDMA-core.  https://github.com/linux-rdma/rdma-core, 2023.
  * [54] Eugene Y Remez.  Sur la détermination des polynômes d’approximation de degré donnée.  Comm. Soc. Math. Kharkov, 10(196):41–63, 1934.
  * [55] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10684–10695, 2022.
  * [56] Dragos Rotaru and Tim Wood.  Marbled circuits: Mixing arithmetic and boolean circuits with active security.  In Progress in Cryptology–INDOCRYPT 2019: 20th International Conference on Cryptology in India, Hyderabad, India, December 15–18, 2019, Proceedings, pages 227–249. Springer, 2019.
  * [57] Rong Shi, Sreeram Potluri, Khaled Hamidouche, Jonathan Perkins, Mingzhe Li, Davide Rossetti, and Dhabaleswar K DK Panda.  Designing efficient small message transfer mechanism for inter-node mpi communication on infiniband gpu clusters.  In 2014 21st International Conference on High Performance Computing (HiPC), pages 1–10. IEEE, 2014.
  * [58] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [59] Sijun Tan, Brian Knott, Yuan Tian, and David J Wu.  Cryptgpu: Fast privacy-preserving machine learning on the gpu.  In 2021 IEEE Symposium on Security and Privacy (SP), pages 1021–1038. IEEE, 2021.
  * [60] Brook Taylor.  Methodus incrementorum directa & inversa.  Inny, 1717.
  * [61] Vale Tolpegin, Stacey Truex, Mehmet Emre Gursoy, and Ling Liu.  Data poisoning attacks against federated learning systems.  In Computer Security–ESORICS 2020: 25th European Symposium on Research in Computer Security, ESORICS 2020, Guildford, UK, September 14–18, 2020, Proceedings, Part I 25, pages 480–501. Springer, 2020.
  * [62] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [63] Sameer Wagh, Shruti Tople, Fabrice Benhamouda, Eyal Kushilevitz, Prateek Mittal, and Tal Rabin.  Falcon: Honest-majority maliciously secure framework for private deep learning.  Proceedings on Privacy Enhancing Technologies, 1:188–208, 2021\.
  * [64] Chengyi Wang, Sanyuan Chen, Yu Wu, Ziqiang Zhang, Long Zhou, Shujie Liu, Zhuo Chen, Yanqing Liu, Huaming Wang, Jinyu Li, et al.  Neural codec language models are zero-shot text to speech synthesizers.  arXiv preprint arXiv:2301.02111, 2023.
  * [65] Jean-Luc Watson, Sameer Wagh, and Raluca Ada Popa.  Piranha: A GPU platform for secure computation.  In 31st USENIX Security Symposium (USENIX Security 22), pages 827–844, 2022.
  * [66] Wikipedia contributors.  Remote direct memory access — Wikipedia, the free encyclopedia, 2022\.  [Online; accessed 23-March-2023].
  * [67] Wikipedia contributors.  Newton’s method — Wikipedia, the free encyclopedia, 2023.
  * [68] Andrew C Yao.  Protocols for secure computations.  In 23rd annual symposium on foundations of computer science (sfcs 1982), pages 160–164. IEEE, 1982.

##  Appendix A Neural Network Structure

For the configuration of a convolution layer, we use a format of (filter
channel, filter size, stride, padding). For the configuration of an average
pooling layer, the format is (window size, stride).

Layer $\\#$ | Layer type | Configuration
---|---|---
1 | Fully-connected | $784\times 128$
2 | ReLU | NA
3 | Fully-connected | $128\times 128$
4 | ReLU | NA
5 | Fully-connected | $128\times 10$
Table 6: Simple network with 722,848 parameters. Layer $\\#$ | Layer type | Configuration
---|---|---
1 | Convolution | $(20,5\times 5,1,0)$
2 | Average pooling | $(2\times 2,2)$
3 | ReLU | NA
4 | Convolution | $(50,5\times 5,1,0)$
5 | Average pooling | $(2\times 2,2)$
6 | ReLU | NA
7 | Fully-connected | $800\times 500$
8 | ReLU | NA
9 | Fully-connected | $500\times 10$
Table 7: LeNet with 430,500 parameters. Layer $\\#$ | Layer type | Configuration
---|---|---
1 | Convolution | $(96,11\times 11,4,9)$
2 | Average pooling | $(3\times 3,2)$
3 | ReLU | NA
4 | Convolution | $(256,5\times 5,1,1)$
5 | Average pooling | $(2\times 2,1)$
6 | ReLU | NA
7 | Convolution | $(384,3\times 3,1,1)$
8 | ReLU | NA
9 | Convolution | $(256,3\times 3,1,1)$
10 | ReLU | NA
11 | Fully-connected | $256\times 256$
12 | ReLU | NA
13 | Fully-connected | $256\times 256$
14 | ReLU | NA
15 | Fully-connected | $256\times 10$
Table 8: AlexNet with 2,552,874 parameters. Layer $\\#$ | Layer type | Configuration
---|---|---
1 | Convolution | $(64,3\times 3,1,1)$
2 | ReLU | NA
3 | Convolution | $(64,3\times 3,1,1)$
4 | Average pooling | $(2\times 2,2)$
5 | ReLU | NA
6 | Convolution | $(128,3\times 3,1,1)$
7 | ReLU | NA
8 | Convolution | $(128,3\times 3,1,1)$
9 | Average pooling | $(2\times 2,2)$
10 | ReLU | NA
11 | Convolution | $(256,3\times 3,1,1)$
12 | ReLU | NA
13 | Convolution | $(256,3\times 3,1,1)$
14 | Average pooling | $(2\times 2,2)$
15 | ReLU | NA
16 | Convolution | $(512,3\times 3,1,1)$
17 | ReLU | NA
18 | Convolution | $(512,3\times 3,1,1)$
19 | Average pooling | $(2\times 2,2)$
20 | ReLU | NA
21 | Convolution | $(512,3\times 3,1,1)$
22 | Average pooling | $(2\times 2,2)$
23 | ReLU | NA
24 | Fully-connected | $512\times 256$
25 | ReLU | NA
26 | Fully-connected | $256\times 256$
27 | ReLU | NA
28 | Fully-connected | $256\times 10$
Table 9: Modified VGG16 (VGG16m) with 7,439,306 parameters.

##  Appendix B Polynomial Coefficients

We give the coefficients of $f_{1}(z),f_{2}(z)$ in Table 10, where each
polynomial is denoted as $k_{4}\cdot z^{4}+k_{3}\cdot z^{3}+k_{2}\cdot
z^{2}+k_{1}\cdot z+k_{0}$.

Coefficient | $f_{1}(z)$ | $f_{2}(z)$
---|---|---
$k_{4}$ | 0.01353417 | -0.268344
$k_{3}$ | 0.05201146 | 0.496404
$k_{2}$ | 0.24144276 | -0.726980
$k_{1}$ | 0.69300383 | 1.442547
$k_{0}$ | 1.00000259 | 0
$k_{4}^{\prime}$ | 0.015625 | -0.25
$t_{3}$ | 0.96074360 | -0.46246981
$t_{2}$ | 6.15066406 | 0.712932283
$t_{1}$ | 24.02000383 | -0.366125013
$t_{0}$ | 23.85013773 | -0.858977912
Table 10: Coefficients of Polynomial Approximation

##  Appendix C Security Analysis of Algorithms

We assume a semi-honest adversary $\mathcal{A}$ who can corrupt any subset of
the parties (no more than $n-1$, where $n$ is the number of parties) before
the protocol begins. We say that a protocol $\pi$ securely implements a
functionality $F$ if any adversary $\mathcal{A}$ with probabilistic polynomial
time cannot distinguish between a protocol $\pi$ and a functionality $F$
attached to a simulator $\mathcal{S}$.

Security definition. Security is defined by comparing a _real_ and _ideal_
interaction. We denote $\text{Real}_{\pi,\mathcal{Z}(\mathcal{A},\lambda)}$
the bit output by environment $\mathcal{Z}$ after the execution of protocol
$\pi$ on security parameter $\lambda$, which is a real interaction involving
protocol $\pi$. We denote $\text{Ideal}_{F,\mathcal{Z}(S)}$ the bit output by
$\mathcal{Z}$ after the execution of trusted functionality. As an interface,
$\mathcal{S}$, also known as a simulator, can access $F$ and simulate a run of
$\pi$ with the same input-output behavior. $\mathcal{Z}$ can observe the
inputs of $\mathcal{A}$.

We say that $\pi$ realizes $F$ if there exists a simulator $\mathcal{Z}$ s.t.
for all environment $\mathcal{Z}$ holds that

$|\Pr[\text{Real}_{\pi,\mathcal{Z}(\mathcal{A},\lambda)}]-\Pr[\text{Ideal}_{F,\mathcal{Z}(S)}]|\leq
2^{-\lambda}$

The $F_{\text{ABB}}$-Hybrid model is the real-world model where the parties
have access to an ideal functionality $F_{\text{ABB}}$. We say that $\pi$
realizes $F$ in the $F_{\text{ABB}}$-Hybrid model if there exists a simulator
$\mathcal{Z}$ s.t. for all environment $\mathcal{Z}$ holds that

$|\Pr[\text{Hybrid}^{F_{\text{ABB}}}_{\pi,\mathcal{Z}(\mathcal{A},\lambda)}]-\Pr[\text{Ideal}_{F,\mathcal{Z}(S)}]|\leq
2^{-\lambda},$

where $\text{Hybrid}^{F_{\text{ABB}}}_{\pi,\mathcal{Z}(\mathcal{A},\lambda)}$
is the bit output by environment $\mathcal{Z}$ after the execution of protocol
$\pi$ based on $F_{\text{ABB}}$-Hybrid model on security parameter $\lambda$.
In this paper, we only give the proof for security of the Reciprocal algorithm
based on the $F_{\text{ABB}}$-Hybrid model, and the security proofs for the
other algorithms are similar.

Functionality $F_{\text{Reciprocal}}$

$\textbf{INPUT: }\llbracket x,p\rrbracket^{\text{A}},x\neq 0,\text{bit length
}l,\text{precision }p\\\ \textbf{OUTPUT: }\llbracket
y,p\rrbracket^{\text{A}},y\approx\frac{1}{x}$

######  Theorem C.1.

In the $F_{\text{ABB}}$-Hybrid model, our reciprocal algorithm 1 realizes the
ideal functionality $F_{\text{Reciprocal}}$ in presence of a semi-honest
adversary.

###### Proof.

Consider the worst-case scenario: except for an honest party $P_{h}$, all the
other $n-1$ parties are corrupted.

Initialize. Now we construct a simulator $S$ for adversary $\mathcal{A}$ and
any environment $\mathcal{Z}$ who chooses all parties’ inputs and sees all
intermediate results and outputs obtained by an adversary. In an ideal world,
$S$ simulates the honest $P_{h}$’s input share with uniformly random values
$r$. Note that $S$ does not need to alter the input of the corrupted
adversary. Now the actual input changes from $[x]$ to $[x^{\prime}]$.
$x^{\prime}$ is from a uniform distribution.

Indistinguishability. We now argue the indistinguishability of the real and
ideal executions to an environment $\mathcal{Z}$. Recall that $\mathcal{Z}$
can choose the inputs for all parties. The view of $\mathcal{Z}$ then consists
of these inputs ($\llbracket x,p\rrbracket^{\text{A}}$, $\llbracket
x^{\prime},p\rrbracket^{\text{A}}$), the messages received by the adversary
(namely shares of intermediate results obtained by the adversary), and output
($\llbracket y,p\rrbracket^{\text{A}}$) shares obtained by the adversary.

For line 1 of Algorithm 1, we use Decompose primitive by $F_{\text{ABB}}$.
From the security of the arithmetic secret sharing, $\mathcal{Z}$ can only see
uniformly random strings of bits. In an ideal world, the original input
$[x^{\prime}]$ is uniformly random. Thus, in $\mathcal{Z}$’s view, the
$\llbracket x_{0:l-1}\rrbracket^{\text{B}}$ in the real world is
indistinguishable from the $\llbracket
x^{\prime}_{0:l-1}\rrbracket^{\text{B}}$ of the ideal world.

For line 1 \- 1, in the real world, all messages received by the adversary are
output by series of $F_{\text{ABB}}$ primitives. So $\llbracket
x_{0:l-1}\rrbracket^{\text{B}}$ and $\llbracket
x^{\prime}_{0:l-1}\rrbracket^{\text{B}}$ are indistinguishable, which leads to
the indistinguishability of $\llbracket x_{0:l-2}\rrbracket^{\text{B}}$ and
$\llbracket x^{\prime}_{0:l-2}\rrbracket^{\text{B}}$. In both the real world
and ideal world, in $\mathcal{Z}$’s view, these strings of bits are uniformly
random.

For line 1 \- 1, since the output of the previous step is indistinguishable
and the bit strings are uniformly random, the operation of swapping their
order and setting them to zero is indistinguishable.

For line 1 \- 1, we again use the primitives by $F_{\text{ABB}}$ and this
process is indistinguishable. ∎

##  Appendix D Baseline Exponentiation Algorithm

Algorithm 4 shows the exponentiation algorithm in [33].

Data: $\llbracket x,p\rrbracket^{\text{A}}$, bit length $l$, precision $p$

Require: Taylor approximation $g(z)$

Result: $\llbracket y,p\rrbracket^{\text{A}}\approx\llbracket
e^{x},p\rrbracket^{\text{A}}$

1 $\llbracket
x^{\prime},p\rrbracket^{\text{A}}\leftarrow\texttt{Truncate}(\llbracket
x,p\rrbracket^{\text{A}}\cdot[\log_{2}e]_{p}$

2 $\llbracket
x_{0:l-1}\rrbracket^{\text{B}}\leftarrow\texttt{Decompose}(\llbracket
x^{\prime},p\rrbracket^{\text{A}})$

3 $\llbracket b\rrbracket^{\text{B}}\leftarrow\llbracket
x_{0:l-1}\rrbracket^{\text{B}}+\llbracket l-p-1\rrbracket^{\text{B}}>0$

4 $c\leftarrow\lceil\log_{2}(l-p)\rceil$

5 $\llbracket
x_{p,p+c-1}\rrbracket^{\text{A}}\leftarrow\texttt{Bit2A}(\llbracket
x_{p,p+c-1}\rrbracket^{\text{B}}$

6 $\llbracket
I\rrbracket^{\text{A}}\leftarrow\prod_{i=0}^{c-1}\Big{(}2^{2^{i}}\llbracket
x_{p+i}\rrbracket^{\text{A}}-\llbracket x_{p+i}\rrbracket^{\text{A}}+1\Big{)}$

7 $\llbracket t,p\rrbracket^{\text{A}}\leftarrow\texttt{Compose}(\llbracket
x_{0:p-1}\rrbracket^{\text{B}}$

8 $\llbracket D,p\rrbracket^{\text{A}}\leftarrow\texttt{Evaluate}(\llbracket
g(t),p\rrbracket^{\text{A}})$

9 $\llbracket y_{+},p\rrbracket^{\text{A}}\leftarrow\llbracket
I\rrbracket^{\text{A}}\cdot\llbracket D,p\rrbracket^{\text{A}}$

10 $\llbracket
y_{-},p\rrbracket^{\text{A}}\leftarrow\texttt{Truncate}(\llbracket
y_{+},p\rrbracket^{\text{A}},2^{c})$

11 $\llbracket s\rrbracket^{\text{A}}\leftarrow\texttt{Bit2A}(\llbracket
x_{l-1}\rrbracket^{\text{B}})$

12 $\llbracket y,p\rrbracket^{\text{A}}\leftarrow\llbracket
s\rrbracket^{\text{A}}(\llbracket y_{-},p\rrbracket^{\text{A}}-\llbracket
y_{+},p\rrbracket^{\text{A}})+\llbracket y_{+},p\rrbracket^{\text{A}}$

$\llbracket y,p\rrbracket^{\text{A}}\leftarrow(1-\texttt{Bit2A}(\llbracket
b\rrbracket^{\text{B}}))\cdot\llbracket y,p\rrbracket^{\text{A}}$

Algorithm 4 Exponentiation of [33].

##  Appendix E Attention-Specific Exponentiation

Algorithm 5 details how we evaluate exponentiation in an attention block when
we perform Transformer-based model inference. Note that, line 5 \- 5 work with
bitlength $l/2$, while line 5 and the following work with bitlength $l$. That
is, in the case $l=64$, we convert the Fixed32 input to a Fixed64 output for
free. Line 5 uses $\llbracket x_{l/2-1}\rrbracket^{\text{B}}$ as the sign bit,
due to the fact that $\llbracket x_{l/2-1}\rrbracket^{\text{B}}$ equals
$\llbracket x_{l-1}\rrbracket^{\text{B}}$ when $l/2$ bits are enough to
represent the input.

Data: Bit length $l$, precision $p$, $\llbracket
x^{\prime},p\rrbracket^{\text{A}}$ where $x^{\prime}$ equals $\log_{2}e\cdot
x$ and is of bitlength $l/2$

Require: Remez approximation $f_{1}^{\prime}(z)$ (the completing square
version of $f_{1}(z)$)

Result: $\llbracket y,p\rrbracket^{\text{A}}\approx\llbracket
e^{x},p\rrbracket^{\text{A}}$ of bitlength $l$

1 $\llbracket
x^{\prime\prime},p\rrbracket^{\text{A}}\leftarrow[p]_{p}+\llbracket
x^{\prime},p\rrbracket^{\text{A}}$

2 $\llbracket
x_{0:l/2-1}\rrbracket^{\text{B}}\leftarrow\texttt{Decompose}(\llbracket
x^{\prime\prime},p\rrbracket^{\text{A}})$

3 $c\leftarrow\lceil\log_{2}p\rceil$

4 $\llbracket
x_{p:p+c-1}\rrbracket^{\text{A}}\leftarrow\texttt{Bit2A}(\llbracket
x_{p:p+c-1}\rrbracket^{\text{B}})$

5 $\llbracket
I\rrbracket^{\text{A}}\leftarrow\prod_{i=0}^{c-1}\Big{(}2^{2^{i}}\llbracket
x_{p+i}\rrbracket^{\text{A}}-\llbracket x_{p+i}\rrbracket^{\text{A}}+1\Big{)}$

6 $\llbracket t,p\rrbracket^{\text{A}}\leftarrow\texttt{Compose}(\llbracket
x_{0:p-1}\rrbracket^{\text{B}})$

7 $\llbracket y,p\rrbracket^{\text{A}}\leftarrow\llbracket
I\rrbracket^{\text{A}}\cdot\texttt{Evaluate}(\llbracket
f_{1}^{\prime}(t),p\rrbracket^{\text{A}})$

8 $\llbracket s\rrbracket^{\text{A}}\leftarrow 1-\texttt{Bit2A}(\llbracket
x_{l/2-1}\rrbracket^{\text{B}})$

$\llbracket y,p\rrbracket^{\text{A}}\leftarrow\texttt{Truncate}(\llbracket
s\rrbracket^{\text{A}}\cdot\llbracket y,p\rrbracket^{\text{A}},p)$

Algorithm 5 Exponentiation in attention.