Nimbus: Secure and Efficient Two-Party Inference for Transformers
Authors: Zhengyi Li
Kang Yang
Jin Tan
Wen-jie Lu
Haoqi Wu
Xiao Wang
Yu Yu
Derun Zhao
Yancheng Zheng
Minyi Guo
Jingwen Leng
Venue: NeurIPS 2024 poster (2024)
Keywords: Secure inferece
Transformer
Multi-party computation
homomorphic encryption
Primary area: privacy
TL;DR: We propose a 2-party computation framework to accelerate the secure inference of the Transformer model by optimizing the protocols of both linear and non-linear layers.

Abstract: Transformer models have gained significant attention due to their power in machine learning tasks. Their extensive deployment has raised concerns about the potential leakage of sensitive information during inference. However, when being applied to Transformers, existing approaches based on secure two-party computation (2PC) bring about efficiency limitations in two folds: (1) resource-intensive matrix multiplications in linear layers, and (2) complex non-linear activation functions like $\mathsf{GELU}$ and $\mathsf{Softmax}$. This work presents a new two-party inference framework $\mathsf{Nimbus}$ for Transformer models. Specifically, we propose a new 2PC paradigm to securely compute matrix multiplications based on an outer-product insight, which achieves $2.9\times \sim 12.5\times$ performance improvements compared to the state-of-the-art (SOTA) protocol. Furthermore, through a new observation of utilizing the input distribution, we propose an approach of low-degree polynomial approximation for $\mathsf{GELU}$ and $\mathsf{Softmax}$, which improves the performance of the SOTA polynomial approximation by $2.9\times \sim 4.0\times$, where the average accuracy loss of our approach is 0.08\% compared to the non-2PC inference without privacy. Compared with the SOTA two-party inference, $\mathsf{Nimbus}$ improves the end-to-end performance of $BERT_{base}$ inference by $2.7\times \sim 4.7\times$ across different network settings.

Nimbus: Secure and Efficient Two-Party Inference for Transformers
Zhengyi Li!, Kang Yang", " Jin Tan", Wen-jie Lu Haoqi Wu', Xiao Wang', Yu Yul Derun Zhao Yancheng Zheng'. Minyi Guo! Jingwen Leng 1.2
Shanghai Jiao Tong University, "Shanghai Qizhi Institute, State Key Laboratory of Cryptology *Ant Group, ' NNotthwestern University
Abstract
Transformer models have gained significant attention due to their power in ma- chine learning tasks. Their extensive deployment has raised concerns about the potential leakage of sensitive information during inference. However, when being applied to Transformers, existing approaches based on secure two- wwo-party computa- tion (2PC) bring about efficiency limitations in two folds: (1) resturce-intensive matrix multiplications in linear layers, and (2) complex non-linear activation func- tions like GELU and Softmax. This work presents new two-party inference framework Nimbus for Transformer models. For the linear layer, we propose a new 2PC paradigm along with an encoding approach securely compute matrix multiplications based on an outer-product insight, which achieves 2.9 ~ 12.5x performance improvements compared the state-of-the-an (SOTA) protocol. For the non-linear layer, through new observation of utilizing the input distribution, we propose an approach of low-degree polynomial approximation for GELU and Softmax, which improves the performance of the SOTA polynomial approxima- tion by 2.9x 4.0x, where the average accuracy loss our approach 0.08% compared to the non-2PC inference without privacy. Compared with the SOTA two-party inference, Nimbus improves the end-to-end performance BERT base inference by 2.7x 4.7x across different network settings.
Introduction
Transformer models 36 bring about significant advancements in various machine learning tasks, such as language understanding [19] vision tasks (6, and chatting bot (21). As Transformer models handle increasingly sensitive data and tasks, privacy becomes major concern for deployment. For example, one hospital (client) wants to use the model from another organization (server) to enhance its diagnostic capabilities. This raises privacy concerns for both parties: either the hospital has to upload its private data, or the organization needs to send its proprietary model to the hospital.
16 29 building upon secure two-party computation (2PC), realize secure wwo-party inference in crivacy-preeenve way. These works proceed by having the client and server jointly execute inference over the "encrypted" input and model, using cryptographic techniques including homomorphic encryption (HE) [7]. additive secret sharing, etc. The client learns nothing about the model except for inference results and keeps the server unknown for the client's 's input.
Recently, several works 14 26
Privacy protection comes with substantial computation and communication costs due to expensive cryptographic operations. While existing secure awo-party inference for convolution neural networks could be completed in a few minutes
g 23 18
32
it is more challenging to make secure
* Email hobbit@ weaittesjjtueiiie wjw.eeuu.uuuuunnn edu.en
i Corresponding authors, email at: yangk @ wellk.o.o and leng-jw jangjw@@sju.d..cn
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

inference on Transformer models practical, due to heavy matrix multiplications in linear layers and complex non-linear layers. To amortize the overhead of HE in linear layers, many works [77 14 26]
adopt window encoding to simulate the inner product. However, such an encoding approach brings about a sparse format of HE ciphertexts, leading to redundant communication and computation. The efficiency bottleneck of non-linear layers is to securely compute GELU and exponential (included in Softmax). Prior works [5] 26] use piecewise polynomials to approximate the two non-linear functions. However, high-degree polynomials and large fixed-point precision are used to maintain the accuracy, which causes large communication costs and rounds.
This work proposes a new secure two-party inference framework Nimbus for Transformer models to address the above efficiency bottlenecks. Specifically, our contributions are summarized as follows:
We propose Client-Side Outer Product (COP) protocol facilitate linear layers. Our COP protocol incorporates two key innovations. First, the static nature of model weights allows the server to send encrypted weights to the client during the setup stage, thereby eliminating input communication during the online stage. Second, removing input communication enables us design novel row-wise encoding scheme that achieves homomorphic matrix multiplication via the outer product. Such encoding further enhances the efficiency of homo- morphic matrix multiplication and yields compact output ciphertexts for communication.
For non-linear layers, present new observation that their input distribution exhibits regular patterns. Unlike prior approximations that assumed a uniform input distribution, our approach reduces the approximation budget allocated seldom-occurring input values. This enables us to use lower-degree polynomials and fewer pieces to approximate non-linear functions. Additionally, low-degree polynomials demonstrate lower sensitivity fixed-point errors, allowing us to adopt a smaller ring for greater efficiency. We also propose new protocol that enables free conversion between the small and large rings. Consequently, our approach achieves improved performance for non-linear layers while incurring only an average accuracy loss of 0.08%.
We evaluate the performance of Nimbus using the popular Transformer model BERT base under both LAN and WAN settings. Compared with the SOTA work BumbleBee 266 we improve the performance of securely computing matrix multiplication (resp., GELU and Softmax) by 2.9x 12.5x (resp., 2.9x 4.0x). Combining all the optimizations, we im- prove the end-to-end performance of secure two-party inference by 2.7x 5.9x and reduce the communication cost by 60%. The code is available at: https:/github..oom/srrttttt/////
2
Background
We present the necessary background, including the threat model, cryptographic building blocks, and secure Transformer inference.
2.1 Threat Model
Our protocol works in the two-party setting where the client C holds input and the server S holds model. Our protocol is secure in the presence of a semi-honest adversary who could passively corrupt either the client or the server, where the adversary follows the protocol specification but may try to learn more information than allowed. Semi-honest adversary is a common assumption for privacy- preserving machine learning and has been used in most two-party protocols [18 34 14]. As in all prior two-par wo-pparty inference protocols, the client is only allowed to learn the model's is architecture and inference result while the server gains no information about the client's input.
2.2 Notation
We use upper-case bold letters to represent matrices like W for model weights and X for activations. For a matrix W, we use W, to denote the i-th row of W and W., to denote the entry the i-th row and j-th column of W. For integer n, we write [n] {0, 1.
1}. For additive
secret sharing (+) (defined in Section 2.3). we use (.)e (resp., (-)a) to denote a share held by a client (resp., server). We denote by [M] the homomorphic encryption (HE) ciphertexts
matrix/vector M where it may consist of multiple ciphertexts. We use Zze Z Znni [0, 2 to denote a ring with all

---

entries modulo 2'. For power-of-two integer N, we use AN,2 [ (X + 1) to denote set of polynomials over ring Zze. Besides, use lower-case letters with "hat" symbol such as â to represent polynomials of degree N - 1 in A N,2', where äزj] denotes the j-th coefficient of polynomial à. Note that a polynomial can encode most N elements over Paze.
2.3 Building Blocks
Our framework built upon multi-party computation (MPC) techniques, including additive secret sharings and homomorphic encryption (HE), The building block of oblivious transfer (OT) and the sub-pun sub-protocols used non- non-linear layers can be found in Appendix
Additive Secret Sharings. In the two-party setting, additive secret sharing over ring Σ2 is defined as: for a value x Ezz, two random shares (x) E Zz and (a) E En are sampled uniformly such that x = (x)) + (x)) mod 24, where (a) is held by a client and (ar). is held by a server.
Homomorphic Encryption. We adopt the lattice-based additive HE scheme (26] (building upon [3]) HE allows one party to perform computations on the encrypted data of the other party
without the need for the decryption key. The HE scheme encodes a plaintext vector E (Zze) into
E 2 and then i encrypted to a ciphertext [mm] = (6, a) E A where q is a ciphertext modulus. Given a ciphertext [[m] and a circuit f including only linear operations, one can homomorphically compute another ciphertext [f [m]]] We refer the reader to Appendix B.I for details of the HE scheme and its homomorphic operations.
a plaintext polynomial
Conversion between Floating- peatinnng-iitttaoe Numbers and Ring Elements. 2PC and HE usually operate over rings, the floating-pont point numbers used in Transformers need to be converted into fixed-point numbers in a ring. Given a scale floating
N (i.e., the length of the fractional part) and ring Ez,, noating-point point number x E R is converted to the approximated fixed-poin point number by computing = x
mod 2 and can be converted back to the approximated by setting 8/2².
2.4 Secure Two-Party Transformer Inference
The details of the Transformer architecture described in Appendix A model, the input and output of all layers are in the form of additive secret sharing, enabling the arbitrary linkage of different layers despite specific protocols. This work optimizes the protocol of the linear layers, including Lineargkv. Linearo, Linearh, and Linear We also optimize the protocols for non-linear layers Softmax and GELU, The activation multiplication in the attention and layer normalization are relatively fast following SOTA studies 288 26 optimizations and leave them as future works.
To securely evaluate the
We do not give special
Secure Computation of Linear Layers
Then, Section 3.2 presents our client-side outer product (COP) protocol with row-wise encoding. In Section 3.3 optimize the memory occupation of our COP protocol.
We first analyze the efficiency problems of the prior solution Section 3.1
3.1 Prior Solution: Server-side Inner Product Protocol
The starting point of this work is the protocol so-called server-side inner product (SIP) [1 14 26 as shown Figure 2(a) The inputs of the linear layer are additive secret sharings (X)c, (X)s 2 held by the client and server. The server also holds the weights W E E
mmxn X
f (X) Hiimn + (m 1) ý - Xij, for i E [k],] E [m]
मर. W) wijm + +] Wajs for [m],j E [n]
The values of two activation shares and server weights encoded into polynomials over A using encoding functions nL Zkxm + A and गH. Zm A as shown in Equation (I.. The coefficients of the polynomials & and d that not defined are set to 0.
3

---

00
Froedingg
Send
Back
|N Decode
Baak
OKL
mu Eplicatioon
Scalarssly ooly
Mask Sand
Decade
ncoype (RTT))
[WX
Row wibe Encoding Encrypt (ITT)
Sand
Okly
Pla rieud Matmul
Reck
ONTT;
Decryst
NTT
coson
Decoda
Decaze
(a) Server-side inner product (SIP) protocol.
(b) Client-side outer product (COP) protocol.
Figure 2: Two rows represent the client and server operations, respectively. The inefficient parts that accelerated marked by dashed boundaries. The input communication is shifted one-time setup, and the output ciphertexts are compact. The expensive NTT/INTT operations at the online stage are also reduced.
Some of coefficients polynomial 2 gives the result of matrix multiplication X. W E Z as illustrated in Figure D If kmnn > N, the encoding function would use coefficients with degrees exceeding N. The input matrices X and W need to be partitioned into smaller windows with respective dimen- sions kw mhe and ma Yhe which results in multiple windows of the output matrix with dimension kw nw- Therefore, refer to this encoding approach window encoding.
v E
Matric Multipiiationn over Eg-
Exalustion through window uncoding
P w 9
2= +- 2
7xx Be 9x* 10x t Ehr
X-W mod
2 moddss 1,29
10x2 17at 201r 2iph 20x 2ix? stot
21x" 28x 3x 3by Aug?
Figure I: An example of the window encoding of the matrix multiplication using N 16 and l 5.
Then, the client encrypts her plaintext polynomials as HE eiphertexts [(X).]. I and sends them the
server. After receiving [()),l, the server computes the HE ciphertexts [X] by homomorphically
adding [[X] (X) s- Next, the server homomorphically computes W. [X] R. to obtain HE ciphertexts [WX R. where R is randomly generated to mask Y WX and keeps as the server's output shares (Y),. Finally, the server sends [WX R.] to the client who decrypts the HE ciphertexts into WX - R that is used as the client's 's shares (Y) Note that number theoretic transform (NTT) 30 is employed to weight plaintext polynomial and activation ciphertext polynomial so that their multiplication complexity is reduced from O(N2) to O(N log N).
Analysis of Communication and Computation Costs. To simulate the inner product, the window encoding produces sparse output (e.g. the even-degree terms of Figure The sparse polyno- mials are treated as dense after encryption, leading to inefficient communication and computation marked by the dashed boundary in Figure ((a) First, the computation includes unnecessary zero terms. Second, Iron shows at least 2v/kmn ciphertexts are transmitted [14]. Then, BumbleBee (26) proposes packing approach that trades computation for less communication, but the overall latency similar.
vN
3.2 Client-side Outer Product Protocol
To solve the efficiency problems as described above, we propose an alternative client-side outer product (COP) protocol. The COP protocol includes two key insights. First, the static nature of model weights allows the server to send encrypted weights to the client at the setup stage, which can eliminate input communication at the online stage. Second, this elimination of input communication enables us to design new row-wise encoding that realizes homomorphic matrix multiplication through the outer product. Our encoding further results in compact output ciphertext for communication and enhances the efficiency of HE matrix multiplication. The formal protocol is described in Appendix [..]]
COP Protocol. In Figure 2(b) we describe the COP protocol for secure matrix multiplication, where the dashed boundary shows the optimizations of computation and communication over prior works. In the setup stage, the server encodes the model weights W in now-wise fashion and sends the HE ciphertexts [W] on these weights to the client. The client stores the HE ciphertexts [[] in the disk, which enables these ciphertexts to be reused for multiple queries by loading them into memory. In the execution stage, for additive secret sharings (X)c: (X). held by the client and server respectively, the client homomorphically computes (X). [W] to obtain HE ciphertexts [W(X), (X)el and the server
locally computes W. (X), in plaintext. Then, the client samples a random matrix R (used as its

---

63
RShift
12 RShin
Figure 3: Illustration of our matrix multiplication. Left: Functionality of the matrix multiplication using row-wise encoding, Middle: Computing the first row of the output through the scalar-poly product. Right: Packing two ciphertexts using aright shift for less number of output ciphertext.
output shares (Y)- R where Y = WX), and homomorphically computes [W(X) - R to obtain HE ciphertexts [W(X). - RJ which is sent to the server. Finally, the server decrypts these ciphertexts to obtain W (X), R, and then sets its output shares (Y)s W(X). e R + W As a result, two parties hold additive secret sharings (()): (Y).). Below, we explain the key process for computing (X) [W] using the row-wise encoding approach.
Row-wise Encoding. Assigning the client to perform the plaintext-ciphertex multiplication has direct benefit in terms of saving the communication of inputs. More importantly, such saving enables us to design new encoding approach for the weights and activations. First, we use the following function to encode each row of the weight matrix, i.e., W; for [m]]
i.j. R (;) [:] Wi.h for j [m]]
(2)
The output dimensions n of Transformers are generally less than N, so the last N n coefficients are set as zero, indicated by the blank squares in Figure 3 Row-wise encoding corresponds to an extreme case of prior window encoding (i.e., setting n n). which may cause a large number of ciphertexts on inputs. This problem is solved by eliminating the input communication in our COP protocol. Second, for the activations, the client no longer encodes his share into polynomials but directly performs multiplication between the plaintext activation shares and ciphertext weights.
Efficient Computation and Compact Output Ciphertexts. Our encoding realizes secure matrix multiplication through outer product, which achieves more efficient homomorphic computation and compact HE ciphertexts on the output. We illustrate the computation of the first row of the output matrix Z, in Figure3 Following the spirit of the outer product, each scalar-polynomial multiplication produces partial sum of Z and their accumulation produces the final output. The scalar-polynomin multiplication has same complexity as the prior poly-poly multiplication in the NTT space. But we reduce the online NTT/INTT operation, and thus reduce the computation cost. For the output communication, if is smaller than the polynomial degree N, the output ciphertext still leaves blank when communicating. The row-wise encoding makes valid coefficients and zeros separate in the output ciphertext instead of in an interleaved fashion. This enables packing the output ciphertexts through a free operation, right shift. Right shift coefficients for s steps in ciphertext can be done by multiplying the ciphertext with plaintext polynomial with only s-order term. The right figure of Figure 3 shows the right shift packing. The second ciphertext shifted to the right four slots and added with the first ciphertext. Then, all slots of the output are utilized for output communication.
Complexity Analysis. Through analysis in Appendix D Table I compares the computation complex- ity and numbers of communicated ciphertexts. Communication: Our COP protocol eliminates the input communication, and output communication is the minimal case of prior Fae Naw
kn when k. N
since values are densely arranged in the output ciphertext. Computation: The SIP protocol requires polynomial-polynoiin multiplication. It applies NTT with O(N log N) complexity to the plaintext polynomial of weights, and ciphertext polynomials of inputs and outputs. Then, the complexity of all poly-poly multiplications in the NTT space is O (kmm). In our protocol, the NTT is only applied when the server decrypts the output ciphertext. The client's scalar-polynomias multiplication saves time spent on the NTT by directly performing the multiplication with a complexity O (kmNN, which comparable the previous multiplication in the NTT space, especially when is close N.
3.3 Memory Impact of the COP Protocol
In our COP protocol, the client stores the encrypted model weights in the disk so that the ciphertexts can be reused. At the online stage, the encrypted weights are loaded into memory for secure
5

---

Table 1: Comparison of the computation and communication for multiplicattin of two matrices with dimension m and m x n. kw Mew, Thw are the window size corresponding to matrix dimensions.
SIP
COP
Communicated Ciphertexts Count
Jen Mo
k/ [N/n
Rew "ewr
Server HE Computation Complexity
O
mn Mig
N log N - kmn)
O ((k/[N/n) log N)
Client HE Computation Complexity
O
+
kn
)N log N
OkkmN)
matrix multiplication. In this way, the client executes an efficient outer product rather than the original encryption and decryption. The feasibility of such workload reallocation is due to the difference between the "client" in MPC and the traditional client. Due to the symmetric-computation characteristic of MPC well the expensive NTT cost brought about by homomorphic encryption and decryption, existing secure-inference frameworks, e.g., [1 14 to be equipped with similar resources as the server, including powerful CPU (e.g., 64 vCPUs) and For clients in MPC, disk usage does not pose significant issue as storage resources are inexpensive. The CPU usage is also not an issue as the analysis and experiments in Appendix F22 indicate that the client's computational overhead remains similar as the prior SIP protocol. However, we notice that keeping encrypted weights instead of plaintext weights may introduce additional overhead to memory usage, which we address in the next paragraph.
5 26 29 42), require the client
large memory (e.g., 128 GB) 42
26 29).
Asynchronous Weight Loading. Our COP protocol allows the weights to be encrypted at the setup stage and stored in the client disk. Different from prior SIP protocol that keeps the model weight shares in memory, loading all encrypted model weights in memory may become burden since the size of ciphertext is at least four times larger than the secret shares 26). To reduce the additional usage of memory, we let the client only keep the encrypted weights w.r.t. the current layer in memory (e.g.. either 180 MB or 720 MB for Transformer model BERT base). The encrypted weight of the subsequent layer is loaded asynchronously with the communication of output ciphertexts of the linear layer and the secure computation of the following non-linear layer, which involves large-size communication and multiple rounds of interaction. Moreover, the network bandwidth is hundreds of times smaller than the disk bandwidth. For example, as shown in Appendix F.2 loading the encrypted weights of one layer in BERT base from the disk to memory can be accomplished in tens of milliseconds, while the communication between the client and server requires several seconds. Therefore, the loading time of the encrypted weights can overlap with the communication process.
4 Secure Computation of Non-Linear Functions
4.1 Prior Solution: Piecewise Polynomial Approximation of Non-Linear Functions
For Transformers, the main efficiency bottleneck in non-linear layers is to securely compute functions exponential and GELU (5] 28 26). These works approximate the non-linear functions through piecewise polynomial approximation, which can be securely computed by executing two-party addition, multiplication, and comparison operations. To maintain the accuracy. these works adopt four-piece polynomials with degree 6 for GELU and two-piece Taylor series with Taylor expansion degree 6 for exponential. The approximation of high-degree polynomials inherently imposes large overhead for securely computing the powers of values. Additionally, such an approximation requires computations to be conducted over large ring Zes and with a large scale s = 18 [14 5 26). This brought about by the fact that computing the powers of values with high degrees leads to the accumulation of fixed-point errors and the potential overflow problem.
4.2 Simpler Piecewise Polynomial and Smaller Rings by Distribution-awan Approximation
We aim to use simpler piecewise polynomials to fit non-linear functions and reduce the size of rings without sacrificing accuracy. Inspired by the finding that activation distribution exhibits a regular pattern across training and test data 24 40 our insight for enabling simpler polynomials is to assign the approximation budget according to the input distribution instead of treating all input values with equal importance. Figure 4 illustrates patterns of the input distribution using the BERT base 's

---

1e3
1e3
2
2.5
0.0
GELU Input Value
Softmax Input Value
Figure 4: The input distribution of non-linear functions. The y-axis indicates the occurrence counts.
nonlinear functions at the 4th, encoder. As an example, consider the input distribution the GELU function. The probability peak centers around -3 and values greater than zero occur with less than 10% probability. A wise strategy should leave more budget to the high-probability ranges. Compared with prior research directly minimizing the approximation error of the original function, assuming a uniform input distribution, our strategy is supposed to generate more effective approximations. Additionally, we want note that the fitted polynomial does not leak the input distribution of the data as the client remains oblivious to the fitted polynomial during secure inference.
Distribution-awan aware Splitting and Fitting. Prior works typically split the input range and fit each interval based on the non-linenn con-litcar of the curve. We further include the consideration of the input distribution for these two processes. For intervals with low non-linews con-lincarity or input probability, we split them out and assign constant linear polynomials to fit. The other intervals with both high non-linen con-linc and input probability are fitted by quadratic or cubic polynomials. When fitting each piece of the non-linear function (1) by the polynomial f'(x), minimize the expected loss that integrates the inputs' probability density p(x)
min J. p(z)[f(x) f((x) ((
(3)
where and lo the lower bound and upper bound. p(xx) is the probability density function obtained by summarizing batch of training data. Unlike prior works using fixed breakpoints and h, we initialize each breakpoint with a starting value and search around it better fit non-linear functions at different depths. This is because although the activation distributions are broadly similar, they may shift slightly across varying model depths and the breakpoints should be adjusted accordingly. We refer to the Appendix C.2 for the splitting and fitting algorithm. The detailed protocols for securely evaluating nonlinear functions are provided in Appendix C.I Next, we elaborate on the specific design for fitting exponential and GELU functions.
Exponential. The exponential is used the Softmax. Given an input vector x, the i-th element of Softmax is computed as Σ, -maxxx= Input values subtracted from maximal values result in maximal zero. The exponential curve exhibits two distinct patterns: a long smooth tail on the left and sharp increase the right. Prior works adopt two-piece approximation by breakpoint -13. Instead, we initial breakpoints around -4 for varying depths. As the right interval spans a smaller range, adopts cubic polynomial (*xx instead of the Taylor series with expansion degree six (5) 26). Values less than -4 are less occurred and the curve is smooth, and a linear function is enough to fit.
exp(a,-max(xx
I < Texp exp(x) R (1) Texp S $
(4)
GELU. The GELU curve nearing the zero exhibits pronounced non-linearity. Prior works 5 assign two polynomials for intervals 5-5, 1.97] and 11.97, with degree three and six. We merge these two intervals by one and shrink the range to [Ti, T2. [-1., 0.2). This because the values fewer occurrence probabilities, and using
26
beyond this interval present either less non-linearity constant or linear polynomials is enough. As the middle interval becomes narrow, we find a square polynomial p2 (x) is enough. The specific breakpoints Ti and T2 change for different depths.
0
$ Ti Tj T2 I <>> T2
GELU(x)
(2)
(5)
T

---

Table 2: Accuracy comparison of (oatiig-poin (FP) baseline, BumbleBee, Nimbus (without finetun- ing), and Nimbus (with finetuning).
CoLA
SST-2
MRPC
STS-B
QQP
MNLI
QNLI
RTE
Avg.
Method
Matthews corr.
Acc.
F1
Pearson
Acc.
Acc.
Acc.
Acc.
FP baseline
58.63
92.88
90.12
88.24
91.22
84.74
91.28
67.87
83.12
Bumblebee
58.40
92.88
90.12
88.28
91.21
84.74
91.39
67.87
83.11
Nimbus
58.28
92.66
89.82
87.93
90.64
84.09
90.05
66.79
82.53
Nimbus 58.40
92.78
90.42
88.12
90.98
84.37
91.37
67.87
83.04
4.3
Free Ring Conversion by Fusion with Truncation
Our low-degree polynomials reduce the errors of operation on fixed-point numbers and potential overflow problems. This enables smaller ring Za2 and precision & 12 for computing Softmax and GELU functions, instead the original standard ring Z61 and precision of 18. However, since other operations still require the larger ring to preserve the accuracy, another challenge is to convert secret shares between differently sized rings. The process of downcasting from larger smaller ring can be performed locally, incurring negligible cost [3] 39). Upcasting from a smaller to larger ring necessitates addressing the wrap-around of shares, requiring communication among parties. Interestingly, we notice the situations demanding to upcast are always after truncation operation that inherently computes the wrapping, which can be repurposed for the upcast avoid additional costs. We propose novel protocol that fuses the upcast with the truncation. We defer the protocol and the correctness proof to the Appendix
Performance Evaluation
Experimental Setup. We follow similar configurations used in prior works (26). Except optimized non-linear functions using ring Zza2 and precision and x 18 for the secret sharing. We use N 8192 for the HE encryption. The performances are evaluated on two nodes with 64 vCPUs and 128 GB memory. We use Linux Traffic Control (tc) to simulate LAN and WAN network settings, where the bandwidth and the ping latency are (3Gbps, Ims) and (400Mbps, 10ms), respectively.
12, other operations follow standard Zze4
Baselines. The baselines include Iron 14] and BumbleBee 26]. Our implementation follows the open-sourced code of BumbleBee on SecretFlow (2 As Iron is not open-sourced, we implement Iron following their protocol using the SecretFlow library for a fair comparison. For the linear layer, Iron uses window encoding described in Section 3.1 and BumbleBee further compresses the output ciphertext. For non-linear functions, Iron evaluates them via integrating underlying protocols. Later works use piecewise polynomial approximation. BumbleBee further integrates cryptographic optimizations to make a stronger baseline. In the Appendix F.4 we also compare work with those
that use rough approximations to trade off accuracy for efficiency [22 29]
Model and Datasets. Our method is evaluated on widely used Transformer model BERT buse from HuggingFace [38] When evaluating the performance, we use 128 mild average number of the input sequence length. To evaluate the accuracy of our non-linear approximation, we test it on eight datasets from widely used GLUE benchmark (37]. To obtain the input distribution non-linear functions, we randomly sample sentences from the training dataset until the total token count reaches 512. This number is chosen because further increasing the number sampled tokens yields no significant changes in the input distribution.
19
5.1 Accuracy Comparison
Table 2 reports the accuracy of floating-pon -ponnt plaintext, BumbleBee, and our approximation across 8 tasks in the GLUE benchmark(37] The precise approximation of BumbleBee causes small emror due to the truncation error of the fixed-point value computation. Without fine-tuning, Nimbus decreases accuracy small range and the average loss around 0.6%. Such loss can be easily reduced to 0.08% % through lightweight fine-tuning Nimbust. This demonstrates the effectiveness of our
8

---

Cxp L2 Norm
Nimbus-Zga
GEL L2 Norm
0.03
Nimbus-Zz.
0.10
Nimbus-722 7
Nimbus 75
Bumblebee-Ze
0.02
Bumbllebee-zz
0.05
Bumblebec-75
Bumbleben-72
0.00
0.00
9
10
11
12
13
14
15
16
17
18
9
10
11
12
13
14
15
16
17
18
Foxed point Procislon
Flxed Precision
Figure 5: The L2-Norm of output error between oracle non-linear functions and approximations.
Vin
Vie Mimoua
Time
10-1
Sethra GELD
Satwaa CE
1N
Tabl
(a) Performance 3Gbps, Ims network.
(b) Performance on 400Mbps, 10ms network.
Figure 6: The end-to-end latency of Transformer block of BERT base and its breakdown.
approximation. We also compare accuracy and efficiency with works that compromise accuracy in Appendix F.4 including MPCFormer [22 and BOLT [29]
Figure presents presentts the output error of exponential and GELU functions to further explain the effective- ness of approximation. The error is summarized using batch of test data certain layer. On the standard ring Ezer and precision s = 18, our L2-norm errors are around 0.005 and are close to the loss-free approximation BumbleBee. When reducing to ring Ezz0 and s 12, BumbleBee en- counters higher errors. This increase is attributed to the more pronounced fixed-point errors that arise when evaluating high-degree polynomials. Moreover, the destructive overflow occurs for precision greater than 10 bits, as the sharp divergence of green and red curves of GELU function. Nimbus has steady fixed fixed-point error and not prone to overflow thanks to the low-degree polynomial. This enables moving to the smaller ring with a minor impact on the accuracy.
5.2 Efficiency Comparison
As the main body of the Transformer model are identical Transformer blocks, we present the end-to- end latency of one Transformer block under LAN and WAN network settings Figure Besides the optimized parts of this paper, we unify the unoptimized activation matrix multiplication (QKT & PV) and LayerNorm (L.) using the BumbleBee's latency. The latencies of Iron are shorter than those reported in their paper due to SecretFlow integrating many SOTA optimizations for the building blocks, such as OT [41] and inverse square root (25). Combining our optimizations, the overall runtime is 4.8% results on varying Transformer size and input sequence length are listed in Appendix In the following, provide detailed analysis of linear and non-linear layers.
5.9x faster than Iron and 2.7 2.7x 4.7x faster than BumbleBee. Comprehensive
For linear layers, our method is efficient in both computation and communication. Therefore, we achieve obvious speedup in both LAN and WAN settings. Compared with stronger BumbleBee, have 7.2x 12.5x in the L.AN setting and 2.9x 4.0x in the WAN setting. More speedup for the LAN setting indicates we accelerate the computation more than the communication. For non-linear functions, our method reduces both the communication size and rounds, so that we obtain similar speedup for both the LAN and WAN settings. Compared with stronger baseline BumbleBee, the GELU is 3.4x faster in the LAN setting and 3.3x faster than the WAN setting. The Softmax is 4.0x faster in the LAN setting and 2.9x faster than the WAN setting.
5.3 Communication Analysis
Then, we compare the communication cost and the number of rounds of línear layers, Softmax, and GELU in Table 3 The data summarized using BERT and sequence length 128. For different types of linear layers, protocol only requires half the number of communication rounds.

---

Our total communication size of lin- ear layers is reduced only 11.51% of that of Iron. Although BumbleBee takes extra "automorphism" operation to compress the output ciphertext, our communication is still only 65% com- pared with BumbleBee since we also eliminate the communication of the input ciphertext. As for the non- linear layers, compared with stronger baseline BumbleBee. we have fewer rounds and 3x less communication due simpler piecewise polynomial approximations and the smaller ring size.
Table 3: Communication cost (megabytes) and rounds com-
parison Transformer block.
Iron
BumbleBee
Nimbus
Layer
Comm.
Rd
Comm,
Rd
Comm.
Rd
Lin
74.64
14.47
2
10.35
Linear.
40.2
2
6.71
2
3.05
Linear
84.46
2
18.35
2
15.52
Linear
78.37
2
15.71
2
3.05
Softmax GELU
689,45
110
354.26
70
115.35
60
283.89
65
185.13
46
53.22
24
Related Work
crivacy-preserving Neural Network Inference. Due the rapidly growing concerns about data privacy in DNN-based applications. significant efforts have been made to design efficient cryptographic protocols for DNN models [8]
3T Early works focus on the convolutional neural network (CNN) models. Cryptonets 8 proposed one of the first protocols for 2PC HE-based private neural network inference. Later works [88
34 17 are hybrid 2PC neural network inference protocols combining HE for matrix multiplications and multi-party computation for non-linear functions.
Private Transformers. Several works have investigated two-party secure inference for the Trans- former model. For linear layers, Iron [4] builds upon Cheetah [17] by generalizing the original encoding of matrix-vector multiplication to matrix-matrix multiplication. Both Cheetah and Iron leave blanks in the input and output ciphertexts. BumbleBee (26) utilizes the "automorphism" operation to compress multiple output ciphertexts, which trades computation for communication. A recent work BOLT [29] adopts SIMD encoding to homomorphically evaluate the lincar layer, which also trades computation for the compact output ciphertext. All existing works adopt the server-side inner product protocol. In contrast, this work proposes the client-side outer product protocol that eliminates the input ciphertext communication. The proposed protocol also allows novel encoding approach that facilitates more efficient homomorphic computation and output communication. Other works [ consider 3PC inference for Transformers, which rely different settings and cryptographic primitives from this work.
For the non-linear layers, some studies, such as THE-X 3 and MPCFormer 22 evaluate transformer models using cryptographic friendly replacements for non-linear layers, such as using Softmax R
(x]+++)2 and GELU(z) $ + However, such aggressive approximations lead to noticeable Ex
accuracy loss, even when employing knowledge distillation mitigate the decline accuracy. Other methods, such as look-up tables for faithful approximation [3T 13 29]. are computationally expensive to maintain model accuracy. Later works, including PUMA 5 and BumbleBee (26), utilize piecewise polynomial approximation, which does not result in an accuracy drop but is also relatively costly to compute. In contrast, this work inspired by insights from the input distribution used in the Transformer model [9] [0 II 12 40, 24] We propose fitting the non-linear functions according to their input distribution, allowing for lower-degree polynomials and fewer polynomial pieces without sacrificing accuracy.
Conclusion
We propose a prevaccpreeerving.. accurate, and efficient two-party inference framework Nimbus for Transformers. We present an efficient protocol of secure matrix multiplication using the COP approach, achieving significantly better computation and communication efficiencies. We use distribution- polynomial approximation for non-linear layers, allowing simpler approximation with less communication and rounds. These optimizations significantly improve the performance, advancing step towards the practical use of secure Transformer inference.
10

---

Acknowledgement
This work was supported by the National Natural Science Foundation of China grants (62222210, 62102037, 61932019, 92270201, and 62125204). Yu Yu also acknowledges the support from the XPLORER PRIZE. This work was also supported by Ant Group Research Intern Program and we thank all members of the SecretFlow team for their support throughout this project.
References
[1] Yoshimasa Akimoto, Kazuto Fukuchi, Youhei Akimoto, and Jun Sakuma. Privformer: Privacy- preserving transformer with mpe. In 2023 IEEE 8th European Symposium on Security and Privacy (EuroS&P), pages 392-410. IEEE, 2023.
[2] Alon Brutzkus, Ran BaalddBBachrchh,,, and Oren Elisha. Low latency privacy preserving inference. In International Conference on Machine Learning, pages 812-821. PMLR, 2019.
[3] Tianyu Chen, Hangbo Bao, Shaohan Huang, Li Dong, Binxing Jiao, Daxin Jiang, Haoyi Zhou, Jianxin Li, and Furu Wei. The-x: encryption. arXiv preprint arXiv:2206.00216, 2022.
transformer inference with homomorphic
[4] Vanya Cohen and Aaron Gokaslan. Opengpt-2:
Open language models and implications of generated text. XRDS: Crossroads, The ACM Magazine for Students, 27(1):25 30, 2020.
[5] 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 Ilama-7b in five minutes. arXiv preprint arXiv:23007. 2tt.2233777..533., 2023.
[6] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenbom, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition scale. arXiv preprint arXiv:2010. 1929, 2020.
[7] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41th Annual ACM Symposium on Theory of Computing STOC'00, page 169-178. ACM, 2009.
[8] Ran Wernsing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International conference on machine learning, pages 201-210. PMIR, 2016.
Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Nachrig, and John
[9] Yue Guan, Zhengyi Li. Jingwen Leng, Zhouhan Lin, and Minyi Guo. Transkimmer: Transformer learns to layer-wise wise skim. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio, editors, Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume Long Papers), pages 7275-7286, Dublin, Ireland, May 2022. Association for Computational Linguistics.
[10] Yue Guan, Zhengyi Li, Zhouhan Lin, Yuhao Zhu, Jingwen Leng, and Minyi Guo. Block-skim: Efficientt question answering for transformer. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pages 10710-10719, 2022.
[11] Cong Guo, Jiaming Tang. Weiming Hu, Jingwen Leng, Chen Zhang, Fan Yang, Yunxin Liu, Minyi Guo, and Yuhao Zhu. Olive: Accelerating large language models via hardware-friends outlier-victim pair quantization. In Proceedings of the 50th Annual International Symposium on Computer Architecture, pages 1-15, 2023.
[12] Cong Guo, Chen Zhang, Jingwen Leng, Zihan Liu, Fan Yang, Yunxin Liu, Minyi Guo, and Yuhao Zhu. Ant: Exploiting adaptive numerical data type for low-bit deep neural network quantization. In 2022 55th IEEF/ACM International Symposium Microacciitecture (MICRO), pages 1414-1433, IEEE, 2022.
[13] Kanav Gupta, Neha Jawalkar, Ananta Mukherjee, Nishanth Chandran, Divya Gupta, Ashish Panwar, and Rahul Sharma. Sigma: secure gpt inference with function secret sharing. Cryptology ePrint Archive, 2023.

---

[14] Meng Hao, Hongwei Li, Hanxiao Chen, Pengzhi Xing, Guowen Xu, and Tianwei Zhang Iron: Private inference on transformers. Advances Neural Information Processing Systems, 35:15718-15733 15731,, 2022.
[15] Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). arXiv preprint arXiv:1606.08415, 2016.
[16] Xiaoyang Hou, Jian Liu, Jingyu Li, Yuhan Li, Wen-jie Lu, Cheng Hong, and Kui Ren. Ciphergpt: Secure two-party gpt inference. Cryptology ePrint Archive, 2023.
[17] 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.
[18] Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. [GAZELLE]: low latency framework for secure neural network inference. In 27th USENIX Security Symposium (USENIX Security 18), pages 1651-1669, 2018.
[19] Jacob Devlin Ming-Woi Wei Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of naacL-HILT, volume 1, page 2019.
[20] 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.
[21] Christoph Leiter, Ran Zhang, Yanran Chen, Jonas Belouadi, Daniil Larionov, Vivian Fresen, and Steffen Eger. Chatgpt: aatalaasallsss after 2.5 months. arXiv preprint a:X19:2302.13795 2023.
[22] Dacheng Li, Rulin Shao, Hongyi Wang, Han Guo, Eric P Xing, and Hao Zhang. Mpeformer: fast, performant and private transformer inference with mpc. arXiv preprint d:01::221..0155. 2022.
[23] Jian Liu, Mika Juuti, Yao Lu, and Nadarajah Asokan. Oblivious neural network predictions via minionn transformations. In Proceedings of the 2017 ACM SIGSAC conference on computer and communications security, pages 619-631, 2017.
[24] Zichang Liu, Jue Wang, Tri Dao. Tianyi Zhou, Binhang Yuan, Zhao Song, Anshumali Shrivas- tava, Ce Zhang, Yuandong Tian, Christopher Re, et al. Deja vu: Contextual sparsity for efficient Ilms at inference time. In International Conference on Machine Learning, pages 22137-22177 PMLR, 2023.
[25] Wen-jie Lu, Yixuan Fang, Zhicong Huang, Cheng Hong, Chaochao Chen, Hunter Qu, Yajin Zhou, and Kui Ren. Faster secure multiparty computation of adaptive gradient descent. In Proceedings of the 2020 Workshop on Privacy-Preserving Machine Learning in Practice, pages 47-49, 2020.
[26) Wen-jie Lu, Zhicong Huang, Zhen Gu, Jingyu Li, Jian Liu, Kui Ren, Cheng Hong, Tao Wei, and WenGuang Chen. Bumblebee: Secure two-party inference framework for large transformers. Cryptology ePrint Archive, 2023.
[27] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Advances in Crypoolgg-EUROCRYYP 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30-June 3, 2010. Proceedings 29, pages 1-23. Springer, 2010.
[28] Junming Ma Yancheng Zheng, Jun Feng, Derun Zhao, Haoqi Wu, Wenjing Fang, Jin Tan, Chaofan Yu, Benyu Zhang. and Lei Wang. (SecretFlow-SPUU) A performant and (User- Friendly) framework for Privacy-Preserving machine learning. In 2023 USENIX Annual Technical Conference (USENIX ATC 23), pages 17-33, 2023.
12

---

[29] Qi Pang, Jinhao Zhu, Helen Möllering, Wenting Zheng, and Thomas Schneider. Bolt: Privacy- preserving, accurate and efficient inference for transformers. In 2024 IEEE Symposium on Security and Privacy (SP), pages 130-130. IEFE Computer Society, 2024.
[30] John M Pollard. The fast fourier transform in finite field. Mathematics of computation, 25(114)3365-374 1971.
[31] Deevashwer Rathee, Mayank Rathee, Rahul Kranti Kiran Goli, Divya Gupta, Rahul Sharma, Nishanth Chandran, and Aseem Rastogi. Simnn: A math library for secure rnn inference. In 2021 IEEE Symposium on Security and Privacy (SP), pages 1003-1020. IEEE, 2021.
[32] 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.
[33] Deevashwer Rathee, Thomas Schneider, and K. K. Shukla. Improved multiplication triple generation over rings via RLWE-based AHE. In Cryptology and Network Security, volume 1 1822 LNCS, pages 347-359, Springer International Publishing, 2019.
[34] Wenting Zheng Srinivasan, PMRL Akshayaram, and Popa Raluca Ada. Delphi: A cryptographic inference service for neural networks. In Proc. 29th USENIX Secur. Symp, pages 2505-2522. 2019.
[35] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne I Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et Llama: Open and efficient foundation language models. arXiv preprint arX1v.2302.1397,, 2023.
[36] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[37] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. GLUE: A multi task benchmark and analysis platform for natural language understanding. arXiv preprint 10X4::8804007461 2018.
[38] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Huggingface's transform- ers: State-of-the-art natural language processing. arXiv preprint arXiv: 1910.03777 2019.
[39] Haoqi Wu, Wenjing Fang, Yancheng Zheng, Junming Ma, Jin Tan, Yinggui Wang, and Lei Wang. Ditto: Quantization-awae aware secure inference of transformers upon mpc, 2024.
[40] Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. Smoothquant: Accurate and efficient post-training quantization for large language models. In International Conference Machine Learning, pages 38087-38099, PMLR, 2023.
[41] Kang Yang, Chenkai Weng, Xiao Lan, Jiang Zhang, and Xiao Wang. Ferret: Fast extension for correlated ot with small communication. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 1607-1626, 2020.
[42] Wenxuan Zeng, Meng Li, Wenjie Xiong, Tong Tong, Wen-jie La, Jin Tan, Runsheng Wang, and Ru Huang. Mpevit: Searching for accurate and efficient mpe-friendly vision transformer with heterogeneous attention. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5052-5063, 2023.
[43] Wenting Zheng, Ryan Deng, Weikeng Chen, Raluca Ada Popa, Aurojit Panda, and Ion Stoica. Cerebro: platform for (Multi-Party) cryptographic collaborative learning. 30th USENIX Security Symposium (USENIX Security 2/), pages 2723-2740, 2021.
13

---

Input
Output
Embeading
phv
LayerNorm
N x
Encoder
Q
Linearaz
Softmax
GELU
Task
PV
Linearaa
Linear
Linear,
LayerNorm
Non-lineor
Figure 7: The illustration the Transformer-basee model and the latency breakdown its private evaluation.
A Background of Transformer Models
We focus on Transformer [36] DNN models, such as popular models BERT 19 LLaMA (35). These models stacked with Transformer blocks, each consisting of attention module and a feed-forward network (FFN) module.
GPT-2 4 and
Attention Module. The attention module starts with three independent linear layers Lineargkv that project the input to three activation tensors: Q. K, and V. The multi-head attention mechanism splits them into and computes the self-attention of all heads in parallel through
QK
Attention (Q, K, V) = Softmax
V
Vdz.
where dy is the hidden dimension of the key activation. The outputs of different heads are concatenated and fed into another linear layer Linear,, with one residue connection and one normalization layer to generate the final output of the attention module.
FFN Module. The FFN module is composed two linear layers and one activation layer
FFN(X) = Linear (GELU (GnnU(L,near,,, (X))),
where GELU [5]
the activation function. Similar attention module, its output needs a residue
connection and normalization layer.
Task Head. After all the transformer blocks are evaluated, the output is fed into a task-specific head for classification, regression, or token generation.
B More Details of Cryptographie Building Blocks
We give a more detailed description of the cryptographic building blocks as supplement to the paper. We follow those notations used the paper.
B.1 Lattice-based Additive Homomorphic Encryption
Homomorphic encryption (HE) enables computation on the encrypted data without knowing the decryption key. This work uses an HE scheme based on Ring Learning-with Beahiingwwtt-EEree Error (RLWE) [27]. The RLWE scheme is defined by of public parameters {N, q, f). where N is the polynomial degree, t the modulus of the plaintext, and is the modulus of the ciphertext.
KeyGen. Generate the RLWE key pair (sk, pk) where the secret key si E ANN. and the public key pk N.
Encryption. An RLWE ciphertext given as polynomial tuple (6,a) à) A A3 Given vector m which is encoded as E AN,, We write [m] = Enc(vi) to denote the encryption of in under a key pk.
14

---

Decryption. Given an RLWE ciphertext [m] = (6, è) E AN.. We write m = Dec( (ml]) to denote the decryption under a secret key sk.
Addition ( + Given two RLWE ciphertexts [mo]] = (00. 60) and [m1] (b. â1
that respectively encrypts me. mn E AN. under a same key, the operation [mo]] EB [m,
computes the RLWE tuple (6o + b1, āo + ā1) E AN.. which can be decrypted to mo fi mod AN
Plaintext-ciphertes polynomial Multiplication (d). Given RLWE ciphertext [m] (b, a) that encrypts in AN,. and plain polynomial AN,, the operation è X [m] computes the tuple (6- è, a c)) E Arr,, which can be decrypted to è m mod AN.--
Plaintext-ciphertes scalar-polynomial Multiplication (8). Given RLWE ciphertext [m] (6, a) that encrypts in A,,,, and scalar c, the operation e [m] computes the tuple (c b,c. E AN,, which can decrypted to c in mod AN.--
Right Shift. Given an RLWE ciphertext [m] = (6, a) that encrypts m E AN.I. and plain polynomial é AN,, with single s-order term, the right shift operation [Shift[[mm], s) computes the tuple (b ē, à â.)) E A.,. which can be decrypted to negacycliely right shift in for terms. This can be implemented through a simple rearrange of the coefficients of the ciphertext, which is a free operation.
B.2 Oblivious Transfer
OT lets a sender input two messages mo, and receiver input a bit b. and then the receiver obtains the message ma- For security, the sender is unknown b and the receiver does not learn m11-b We adopt OT to construct secure two-party computation (2PC) protocols of some non-linear operations such as comparison. We instantiate OT with the communication-efiin Ferret protocol [4
B.3
Sub-Protocols for Non-linear Layers
Our protocol for non-linear layers calls the following functionalities in black-box way to compute element-wist multiplication, comparison, Boolean to Arithmetic share (B2A), and wrap. These functionalities can be securely realized using the known protocols. We use (-) to denote arithmetic additive sharings over a ring Z.z' and (.) to denote Boolean additive sharings over a binary field F-2 Secret sharing without superscript indicates using the default ring size (e.g., Zger for the linear layers and Zzaz for the exponetial and GELU functions).
Functionalities
Protocols
(X Y) Fmuil (X)) (Y)) (1xr < k1)B Fress (1x) (y)) (x)²= = (fte((x)))
Element Element-wise wise multiplication 26
Less-then (28]
Boolean to Arithmetic share 28
(1((x)* +v) 2 2 Fwmp ((x) (
Wrap the ring Zz (28)
C Detailed Protocols and Algorithm
C.1 Protocols
We present our detailed protocol of matrix multiplication of Section in Algorithm T The detailed protocols of securely evaluating GELU and exponential in Section presented in Algorithm and Algorithm 3
Security Proof the Matrix Multiplication Protocol The proposed client-side outer product protocol directly builds upon secure building blocks. It guarantees the same security as the traditional server-side inner product protocol. In the presence of a semi-honest adversary, we provide brief proof idea below. The notations follow those in Algorithm
15

---

Specifically, the model weights are encrypted by the server and then sent to the client, where the ciphertexts are denoted by [W] According the security property the HE scheme, the ciphertexts reveal no information about these model weights. For secure matrix multiplication, the input matrix X has been shared as (())a. cs (X).) using additive secret sharing. The client samples a matrix of random
shares R. and then homomorphically computes a ciphertext [(X),* W -R] = (X) [W] - Due to the cireuit-privacy property of the HE scheme, in the client view, the ciphertext [(X) c W RJ does not reveal information on W. This ciphertext is sent to the server, who decrypts it to (X), W W--R R. Because of the random mask R, the server also learns nothing about the client share (X)e. In the proof of security, the simulator can simulate the HE ciphertexts using "dummy" ciphertexts on zero, and the adversary's 's view between the real-world execution and ideal wdeal-world execution is proven to be computationally indistinguishable by reducing it to the circuit- cireuit-privacy security of the HE scheme.
Security Proof of Non-linear Function Protocols This work does not modify the protocol for
evaluating piecewise polynomials but improves the generation method for these polynomials, ensuring that security remains consistent with previous work. We highlight the training data information that are utilized for fitting non-linear functions is not leaked. This because the secure evaluation of the piecewise polynomial prevents the client from learning the coefficients and comparison thresholds, as indicated in Algorithm 2 and Algorithm 3 Except for the usage of bo. which requires primitive Fuull all other coefficients are used through addition, which can be performed locally on the server side. For the comparison threshold, the server can subtract the threshold from its share and compare the resulting shares with zero. As result, the client learns nothing about the piccewise polynomial. A possible improvement on the efficiency is to make by public, thereby saving one round of communication. The only leakage of by does not necessarily lead to leakage of the meaningful information and can provide approximately an 8% speedup.
Algorithm Secure Matrix Multiplication Protocol of Nimbus
Parties: C' is the client. S is the server owning the model.
Input: The client holds activation share (X) E 2n2
z The server holds activation share (X)s E
znx" W Lize Znxxn and secret key sk.
Output: Sharing (Y)₂ E Zhg and (Y), E Z such that Y
WX mod 2
(Setup phase}
1: Server S partitions the matrix W into rows Wa E Z Then S encodes each row
polynomial thg = The (WB) for B e [m]. After that S sends [Wa] Enc( for [m] to
the client C.
(Execution phase]
2: The client computes the scalar- polyoo-pl multiplication to obtain a vector of output ciphertexts
c= [[Co], [c.] ... [c I]], where
c[a] B[ (Fa, @ (Wll).
for a E [k). The cfa] denotes the a-th element of the vector c.
3: To compress the the i ciphertexts vector of c into k/ [N/nn ciphertexts, The client applies right
shift on ciphertexts of c. For example
[0] RShift(c (0 [N/n]], 0) + RShift(c [0- [N/n] + k], RShift (0- [N/n] + [N/n] - 1], (LN/n) - 1))
for 0 E [k/LN [N/n]] Pad with zeros if k cannot be exactly divided by [N/n].
4: The client C' generates a random polynomial vector ciphertext. The client sends c(Ø) Br the server for all 0, which are then decrypted by server obtain W(X). R. The client keeps r, which is R z
fñ.. .. N/nj--]] i] to mask the
5: The server locally computes W (X), and outputs (Y). W(X), W(X), R. The client outputs (Y) R.
16

---

Algorithm 2 Secure GELU Protocol of Nimbus
Parties: C is the client. S the server owning the model. The polynomial (2) with coefficients {bo, bi, b2) from Equation 5
Input: The client holds activation share (X) E " and the server holds activation share (X), zkxm
Laze
Output: Sharing (Y), 2r and (Y), E žkxm such that Y = (X).
1: Two parties locally compute (A1) Fuul ((bu), (X)) bj. Then two parties jointly compute (A2) = Fma ((A1), (X)) bg. The truncations are implicitly called.
2: Jointly compute the comparisons for interval selection
(ba) B = Fless (X).T) T1)
bb 1 < Ti} bb = 1 < <
(b1) 13 = Fless (T2, (X))
I(P) is I when the condition P is true and 0 otherwise. Two parties locally set (zo) - (bo) (21) = xor (b,) xor (22) B (b2) where / the party index. this way, two
parties have 2n 1(x < J. 1[Ti X T2). and 22 1(T2 S XX].
3: Jointly compute the multiplexing (Y) = (zo) share of each party.
(1 (A2) + (22) (X) as the output
Algorithm 3 Secure Exponential Protocol of Nimbus
Parties: C' is the client. S is the server owning the model. The polynomial (3) with coefficients
(bo, bi, b2, by} from Equation 4
Input: The client holds activation share (X)a E Zhx" and the server holds activation share (X)s
zkxm
Output: Sharing (Y) E Σ z and (Y), Ey z such that Y exp(X).
1: Two parties locally compute (A1) Fmul ((bo), (X)) bi. Then two parties jointly compute
(A2) = Fmai ((Ai), (b2 and (As) = Fmul ((22), +b3) The truncations are implicitly called.
2: Jointly compute the comparisons for interval selection
(2o) B Fless( (X), Texp) D = 1(X < Texp)
((P) is I when the condition true and otherwise.
3: Jointly compute the multiplexing (Y) = (zo) () 0 (20) B (Ag) as the output share of each party.
C.2 Fitting Algorithm for Non-linear Approximation.
In this section, we present the algorithm used to search the interval breakpoint of the piecewise polynomial. We use the exponential with only one breakpoint algorithm can be easily generated to the GELU with two breakpoints.
example to explain. A similar
The first step generates the breakpoint candidate set S given the initial breakpoint T. One can choose the search range and step according the needs (Line 1). Then, for each breakpoint candidate, the input range is separated into two intervals (Lines 3-4). We fit both intervals using Equation 3 The required input distribution p(z) can be drawn from batch of data from the training dataset. The corresponding loss is accumulated for all intervals (Lines 5-9). Then, we update the optimal piecewise approximation (lines 10-13). Finally, the optimal approximation f'(x) is returned.
D Complexity Analysis of Linear-Layer Protocol of Nimbus
This section analyzes the computation and communication complexities listed in Table 1 We first analyze the number of HE ciphertexts to be communicated. The SIP protocol requires ke, m.
kmm
+ k kn
for the communication of input and output, km The scalar-polynome product produces h output removes the overhead of sending the input k. ciphertext, which pack k/ [N/]..
have explained in Section 3.1 Our COP protocol
17

---

Algorithm 4 Searching piecewise polynomial approximation of the activation function
Input: Activation function f(x), initial value of the interval breakpoint T, input distribution p(æ), and function template of (x)..
Output: The approximated function f'(z);
1: Generate breakpoint candidates set S around T.
2: Set best loss t oo and (a) < None.
3: for E S do
4: Partition the input range into two intervals using 8.
5: T-total = 0.
6: for each interval do
7: Fit polynomial of given degree using Equation 3 and obtain the corresponding loss L..
8: Compute total loss Liotal Li. end for
9:
10: if Leotal < best loss then
11:
best loss Leotal 12: f'(x) + current approximation
13:
end if
14:
end for
Output: f'(x:
Algorithm 5 Secure Fused Truncation and Upcast.
Input: Client C and server S hold input (x)
Output: Client C and server hold output (y) that y = x/22
S&C invoke Fwrap ((r)s: (x))) and learn (w)
2: S&C invoke Ff-rA+ ((w) B) and learn (w0) (o)""-tt+
3: For b {S, Po outputs (u) = ((x) > s) - - (w)b (wi -8s mod 2
Then, explain the computation complexity. The server in the SIP protocol needs to apply NTT to weight O mn . log N) and the dyadic product ku
kmm N kmnn In our scheme, the server
mornh" only decrypts the k/ [//] output ciphertexts with complexity O ((s//[N/ Jolog N). The client of the SIP protocol needs to perform NTT when encrypting the activation and INTT when decrypting the output, which requires O ((amm
( km
Nlogg complexity. our protocol, the client can + kw
directly multiply her activation share with the ciphertext on model weights. Our method has O(N) complexity for each plaintext-cipherre scalar-polynomial multiplication and km times product with total complexity (kmN).
E
Correctness of Truncation-upeast Fusion
We show the correctness of it through the following derivation. Let (a){ (i E 0, 1) denote the secret share held by the client and server on the ring Zze. The second line is drawn from the truncating secret shares on the ring 2f, w is boolean value indicates the wrap of (x)) over ring size 2 and w' is the carry bits of the lower bits. The carry bit w/ either zero or one and can be safely ignored in the inference while the 26- is significant error that needs to be carefully handled. The third line holds since 2 w falls within the larger ring 2 The fourth line is the modulo expansion of the wrap on a ring with bits, where v is boolean value that indicates the wrap of the (w)+. Through a proper choice of k 2 L' - f + to promote the boolean share (w) B its wrap can be eliminate by modulo 2"", The final line indicates the overhead of truncation and upcast is the same as truncation alone, which only requires computing the (w)* (w)''-(+>
The protocol that computes truncation and upeast is in Algorithm 5
())
18

---

8 x² 12"
Σ
10)1//2 2 -w -2 w
1=0
Σ
(2) w 20 ve mod 2
(8)
1
(z) /22 mod 2
Σ
(w) -u BBB..
.22 2/ 2'- mod 2 mod 20
R2 8+ Σ
/2) mod 2
Σ (1o) 2/-5 mod 2 + mod 2
1=0
1=0
F
More Experiments
F1
Comprehensive Performance Comparison
We present comprehensive end-to-end latency comparison of transformer block in Figure 8 Figure 9 and Figure TO We present three model sizes: 768, 1024, and 2048. The input sequence lengths include 1, 32, and 128. Two network conditions are considered: 3000Gbps, Ims (LAN) and 400Mbps, 10ms (WAN). The sequence lengths of 32 and 128 correspond to the classification Transformer model or the prefill phase of the generative Transformer model. The sequence length can be viewed as the performance during the generation phase of the generative Transformer model. Overall, for the stronger baseline BumbleBee, our method outperforms by a magnitude of 1.9x 7.6x on sequence lengths 32 and 128. The speedup is minor on sequence 1 with 1.2x to 2.1x. For the linear layers, the speedup ranges from 2.47x 12.09x, x, and the non-linear layers range from 2 3.9x In the following, we provide a detailed analysis of the speedup in linear and non-linead layers under varying conditions.
Linear Layers. Our method efficient in both computation and communication. Therefore, we achieve apparent speedup in both LAN and WAN settings. Our method obtains more speedup for large input sequences and hidden dimensions. This is because the computation time of NTT is more dominant for large-size matrix multiplication and input sequences. When the communication speedup similar, our method has more speedup when the computation time speedup is more significant. Our method has more speedup for the LAN than WAN, where latency is mainly composed by the computation. As our method computes much faster, our latency benefits more from the improved network condition.
Non-Linear Layers. Our method is 4x to 10x faster than Iron and 2.0 to 3.9x faster than the stronger baseline BumbleBee. Our speedup LAN and WAN are similar communication size and the communication rounds. The speedup is also similar for varying sequence lengths and hidden sizes. This is because our optimization lies lower degree of approximated polynomials and is not correlated with the input size.
method improves the
F.2 Detailed Client Burden Analysis
This section provides evidence to support Section 3.3 including the client computation time and the asynchronous weight loading.
Client Computation Time Comparison. The client's 's computation cost for our COP protocol is counter-intuitive similar to the previous SIP protocol. This is based on counter- intuitive workload distribution of the HE multiplication. Due to the introduction of the NTT, the server in SIP protocol only computes the dyadic product with O(N) complexity, and the more expensive NTT with complexity O(N log N) performed by the client when encrypting and decrypting, as listed in Table Our COP protocol makes the client perform more efficient vector-vector product with complexity OkkmN). Since
19

---

Marbetes Neoke
Thme ba
Nimu
Unaatty Uroe, Unean, Selina
Urid Uitea, Lhid,, Urean, Sollmax
0KTPP
(a) LAN, Sequence=1, and Hidden=766.
WAN, Sequence=l, and Hidden=768.
12
Time Il
11m
Unioa uroe, Unear, Sefirua GEU OCEYV
LA
166a
Urid Liteer, Lhtel, Unean Salmux
GEU
0KSPP
LV
(c) LAN, Sequenc==,, and Hidden=
(d) WAN, Sequence=I, and H024en=1024.
Frn
11me
10
Time
Lendl LiKos, Uniat, safbnex OAU
SKS
Toaa
Lroden Limoue Uncan,
Sorumar UBA
OKGN
LA
Telal
(c) LAN, Sequenc==1, and Hidden=2048.
(l) WAN, Sequence=1, and Hidden=2048.
Figure 8: Under sequence length 1, the end-to-end speedup and breakdown of varying hidden dimensions and network conditions.
Burt c000
Buvokose
Time
10+1
Levoffgu Uneaa, Lines, Undon,
Urokkn Linenc Uncor, Jreas,
(a) LAN, Sequence=32. and Hidden=768.
(b) WAN, Sequence=32, and H6dden=768.
Neba
Lendf Unees Lioas, Linta,, softrax
GELD OK STV
Toal
Ureafnn Linaac LiCes, Jreas, Softhoa
GEUU OKGS
(c) LAN, Sequence=32, Hidden= 1024.
(d) WAN, Sequence=32, and Hidden=1024 1024.
Outchoas
Tmeesi
Tire 50
Loe Li8M, Lnean, Sotthae GEU
Tobl
Urede: Linane Liee, Unews, Sonmar GEU OK
LN
Teall
(e) LAN, Sequence=32, and Hidden=2048.
(f) WAN, Sequence=32, and Hidden=2048.
Figure 9: Under sequence length 32, the end-to-end speedup and breakdown of varying hidden dimensions and network conditions.
20

---

10-
Teme bi
Timr
Leicaton Litee. Lioas, Lneun, Solomux GEU
OC5P
Total
Uroakn Linos Lniak, areas, Suttnaa GELL
OKGN
18
Teaal
(a) LAN, Sequence=128. and Hidden=768.
(b) WAN, Sequence=128, and Hidden=768.
Time 10-
Time
Nerbo
Lieann GEUJI
OCAN
1M
Tatal
Lioeee LINON Liiek,
Sortmaa GELL OK
LN
Teaal
(c) LAN, Sequence=128, and Hid4
(d) WAN, Sequence=128, 128, and Hidden= 1024.
120
Timeta 12
GEL
LN
16
GE
(c) LAN, Sequence=128, and Hidden=2048.
(f) WAN, Sequence=128, and Hidden=2048.
Figure 10: Under sequence length 128, the end-to-end speedup and breakdown of varying hidden dimensions and network conditions.
Iron
Bumblebee
Nimbus
Citent Comp. time
20.09
10x
Lindari number=32 Hidden=2048
Lundary
number=32
Token number=120 Hidden-766
Token number=129
Hiddenn 768
Hddonn=2488
Figure 11: Under different sequence lengths and hidden sizes, we present comprehensive experiments of client computation time of different methods.
directly comparing computation complexity is hard draw conclusion due to the choice of the window size, we profile the client's 's computation time to compare the computation workload.
Under different sequence lengths and hidden sizes, Figure 11 presents comprehensive experiments of client computation time of different methods. Across varying model sizes and input sequence lengths, Nimbus only takes around 20% to 30% compared with Iron and 0.7x to 2.7x compared with BumbleBee. The BumbleBee has less client computation because the compression used in BumbleBee allows the client to encrypt her activation shares less number of ciphertexts and receive fewer output ciphertexts, thereby requiring fewer NTT operations. the worst case of the Linear the client computation is around 5.0x longer than the BumbleBee. But still, the total Transformer block, the extra overhead only 2.7x. This extra computation ratio can be further shrunk given the base that the client needs to perform large amount of computation of non-linear layers. Therefore, we helieve this is acceptable for a powerful client in MPC.
Asynchronous Weights Loading, For varying hidden dimensions, Table lists the encrypted weight size and corresponding loading time from disk to memory, which usually takes less than second. For hidden size 768, which the size BERThee mainly considered in this paper. The loading time is only 90 ms and 370 ms. which can be easily overlapped by later communication. Therefore, we can only keep limited number of encrypted weights the memory, such as weights of four linear layers of a Transformer block. Then, swap the later weights during the exccution.
21

---

Table 4: The size of the encrypted weights measured by megabytes (MB) and the corresponding loading time measured by seconds (s).
giv
Linear,
Linearh1
Linear12
Hidden
Size
Time
Size
Time
Size
Time
Size
Time
768
180
0.09
180
0.09
180
0.09
720
0.37
1024
240
0.13
240
0.13
240
0.13
960
0.50
2048
480
0.25
480
0.25
480
0.25
1920
0.91
8
Speedup
6
4-
2-
LAN
WAN
20
40
60
80
100
Query Number
Figure 12: The execution+setup speedup over BumbleBee under different queries.
F33
Amortized Overhead of the encrypted weights.
Our linear protocol replaces the input communication with one-time setup communication of sending encrypted weights. Although our method focuses on the overhead of the execution phase, are also interested in how many queries can make the amortized setup overhead negligible. For BERT using our row-wise encoding. the encrypted weight size of four types of layer within Transformer block is 180MB, 180MB, 180MB, and 720MB. We incorporate the one-time overhead of transmitting these weights into our analysis and amortize it across the number of queries. Figure 12 shows the speedup of amortized Nimbus over BumbleBee. The dot lines indicate the speedup without considering the setup overhead. There are two critical points that we are interested in. At around three queries, the amortized overhead begins surpass the BumbleBee, leading speedup greater than 1. At around 40 queries, the maximal speedup is achieved.
F.4 More Accuracy and Efficiency Comparisons of Non-linear Approximations
Besides BumbleBee 26 this section compares non-linear approximation with other state-of-the-art
(SOTA) works, including MPCFormer [22] and BOLT
Accuracy Comparison The details of the accuracy listed in Table The accuracy of MPCFormer is reproduced using the open-sourced code of them. MPCFormer's idea is to adopt aggressive approximation tailor the efficiency the MPC but sacrifice the inference accuracy. For example, they let GELU(z) = 0.125x² + 0. 0.255 + 0.5. MPCFormer can efficiently compute the Softmax and GELU. However, even using knowledge distillation recover the accuracy, they still incur 2.26% accuracy on average. BOLT optimizes exponential and GELU using integer-only approximation and
Table 5: Accuracy comparison of floating-poin (FP) baseline, BumbleBee, MPCFormer (reproduced using Quad+2ReLU), BOLT* (accuracy relative change from the original paper), Nimbus (with finetuning). We report the relative change in accuracy.
Method
CoLA
SST-2
MRPC
STS-B
QQP
MNLI
QNLI
RTE
Avg.
Matthews corr.
Acc.
Pearson
Acc.
Acc.
Acc.
Acc.
FP baseline
58.63
92.66
90.12
88.24
91.22
84.74
91.28
67.87
83.10
Bumblebee
-0,23
0.00
0.00
0.04
-0.01
0.00
0.11
0.00
-0.01
MPCFormer
-5.88
-1.04
-0.73
-3.03
-1.91
-1.42
-0.51
-3.57
-2.26
BOLT
-0.62
0.53
-1.65
-0.02
-0.44
Nimbus
-0.23
-0.11
0.30
-0.12
-0.24
-0.37
0.09
0.00
-0.08
22

---

Table 6: Efficiency comparison of BumbleBee, MPCFormer (Quad+2Rel.U), BOLT, Nimbus
Method
LAN (3Gbps, 0.8ms)
WAN (200Mbps, 40ms)
GLUE
Softmax
GLUE
Softmax
Bumblebee 0.96
2.13
9.16
19.87
MPCFormer
0.08
0.71
1.16
7.05
BOLT
3.18
3.66
22.20
23.16
Nimbus
0.28
0.56
2.60
5.86
piecewise polynomial approximation, respectively. Similar to the BumbleBee, their approximation regards all input values as equal importance. Therefore, they require relatively high-degree polynomial approximate the original function. Since BOLT does not opensource the codes used to fine-tune the model, we use accuracy numbers reported in their paper. Their approximations are relatively accurate and incur 0.44% average accuracy loss after fine-tuning.
Efficiency Comparison The efficiency comparisons for LAN and WAN settings are listed in Table 6 We utilize the open-sourced code of BOLT to reproduce their latency. MPCFormer is originally implemented on the Crypten framework (20]. which uses secret sharing its underlying cryptographic primitive instead of homomorphic encryption. To facilitate a fair comparison of the effectiveness of non-linear approximation, re-implement their polynomial approximation using SecretFlow as the backend.
MPCFormer's GELU does not require comparison and is extremely fast. They use ReLU to replace the exponential in the Softmax, which is also fast. The same as the ReLU substitution MPCFormer, Nimbus's approximation of the exponential also has one comparison, and the additional three multiplications are relatively quick to compute. Furthermore, our approach allows for computation smaller ring, which makes faster than MPCFormer's Softmax. Our method is approximately 10x faster than BOLT in all cases. In addition to the advantages of our simpler approximation, other factors also contribute the slowness of BOLT. First, BOLT's linear layer is evaluated in the field, necessitating extra operations to convert field elements to ring elements. Second, our simpler approximation reduces the fixed-point error during computation, enabling computation on smaller ring. Since other layers still require computations on larger ring, we also propose a truncation-upcast fusion protocol eliminate the overhead of upcasting ring elements from smaller ring larger one. In contrast, BOLT requires additional communication for this upcasting process.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstraction and introduction reflect necessary contributions and experi-
ments
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The potential trade-off is discussed within the paper in a separate Section 3.3
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
The necessary assumption and proof are include in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We have listed detail configuration of experiments in Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
25

---

Answer:
[Yes]
Justification:
The code to reproduce the experimental results are provided on Github.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://niis. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips.com wttpcccpppbccccceec guwdes/dde/eeee
ssioiolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: This not the core contribution of this work. But still, we follow the standard method of prior work as have mentioned in the Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
The experiments are conducted many times and report average results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
26

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The specific configurations are included in the Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:: httpppp////aarrp.ccco//////////a
Answer: [Yes]
Justification:
We follow the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss the potential positive societal impacts of using privacy-preseree preserving inference in the Introduction section.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
27

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The answer NA means that the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite the original paper that produced the code package dataset.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
28

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "40QpWGdrFX", "reviewer": "Reviewer_dGsE", "summary": "This submission proposed secure inference protocols for Transformer-based model, involving two \ncrucial components: HE-based linear operations and approximation-based no-linear operations. \nExperiments were conducted to verify the feasibility of the proposed protocols and to compare the \nperformance with prior works on Transformer secure inference.", "questions": "See above.", "limitations": "See above.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The author focused on the critical part of designing efficient MPC protocols for Transformer, with \ndetailed analysis on drawbacks of prior works. \n\nFor the linear layer, the solution takes into consideration the different computation sources that \nthe client and server hold. As such, during the linear operations, the server side is responsible for \nthe heavy cryptographic operations.\n\nFor the non-linear layer, the protocol in the submission is based on the distribution of function input. \nConcretely, low-degree approximation was used, for the selected range.\nThe experiment in the paper is comprehensive and complete. Results indicate that it outperforms the \nbaseline.", "weaknesses": "1. One of the insights of the non-linear construction is based on the non-uniformed distribution of the input. It is not quite convincing as insufficient explanation was provided, thus limiting the feasibility of the protocol. Is it applicable to all types of input datasets or just limited to certain categories?\n\n2. The contributions and novelty of the non-linear design are not sufficiently highlighted. It can be \nviewed as the variant of spline approximations with carefully selected coefficients, which is \ncommonly applied in prior works [1].\n\n3. Truncation in Alg. 5 discards the high-order bits rather than low-order bits. However, commonly\nit is the variant of the logical right shift [2]. Please clarify the definition of such an operation.\n\n[1] Hou, Xiaoyang et al. “CipherGPT: Secure Two-Party GPT Inference.” IACR Cryptol. ePrint \nArch. 2023 (2023): 1147.\n\n[2] D. Rathee et al., \"SiRnn: A Math Library for Secure RNN Inference,\" 2021 IEEE Symposium \non Security and Privacy (SP), San Francisco, CA, USA, 2021, pp. 1003-1020,", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your insightful feedback and suggestion. We address the main concerns as follows.\n# Q1: Generalization of insight on activation distribution to other datasets\nWe supplement our study with additional experiments on the activation distribution (Figure 1 in the **supplementary PDF** of the global response) to demonstrate the generalization. Besides the eight tasks in the GLUE benchmark provided in the paper, we verify the activation distribution on additional popular datasets. Our experiments include BERT-base on the MRPC dataset (for sequence classification), SQuAD dataset (for question & answering), and SWAG dataset (for multiple choice), GPT-2 on the Wikitext-2 dataset (for causal language modeling). We observe obvious non-uniform distributions across these datasets. These distributions also exhibit similar patterns, indicating that the piece splitting strategy proposed in this paper can even be directly applied to other datasets. The non-uniform distribution of intermediate activations has also been verified by other studies as a widely applicable rule across various Transformer models and tasks [1,2], which they have utilized for quantization and sparsity.\n\nTherefore, compared to the previous strategy that treats the input distribution as uniform, our approach of fitting nonlinear functions according to the activation distribution is expected to yield better fitting results. We also conduct accuracy experiments on these datasets. As the following table shows, Nimbus only has a minor impact on the accuracy.\n| Method      | BERT-base (MRPC) | BERT-base (SQuAD) | BERT-base (SWAG) | GPT2 (wikitext-2)  |\n|-------------|------------------|-------------------|------------------|--------------------|\n|             | F1               | F1                | accuracy         | perplexity         |\n| FP baseline | 90.12            | 88.1              | 81.08            | 20.01              |\n| Nimbus      | 90.42            | 87.93             | 80.94            | 21.36              |\n\n\n[1] Deja vu: Contextual sparsity for efficient llms at inference time, ICML 2023\n\n[2] Smoothquant: Accurate and efficient post-training quantization for large language models, ICML 2023\n\n\n\n\n\n# Q2: Clarification of the contributions on nonlinear layers\nOur work on nonlinear layers has two main contributions. First, we observe that the activation distribution of the transformer model is non-uniform. Based on this observation, we allocate the approximation budget based on the input distribution when fitting the nonlinear function. This is different from prior works that directly minimize the output difference between the original function and approximated polynomials, assuming a uniform input distribution. Second, we have found that our low-degree approximation allows for efficient small ring computation. To support this, we also propose a truncation-upcast fusion protocol to avoid the cost of ring upcast. We will explain our twofold contributions in more detail in a later revision.\n\n\n# Q3: Clarification of truncation\nOur truncation in Alg. 5 also discards the low-order bits. We give a detailed derivation of Alg. 5 in Equation (8) of the Appendix. You can check the last line of Equation (8), where the low-order bits of $\\langle x \\rangle$ are discarded by division by $2^s$. We will further clarify this in the updated version of Alg. 5. We are open to further discussion if there are any remaining questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ptks7HQF5Q", "reviewer": "Reviewer_5SDb", "summary": "This paper provides a hybrid method that uses both HE and additive secret sharing (Add-SS) to perform 2PC privacy-preserving transformers. Two main contributions are discussed in this paper: (1) Client-side Outer Product Protocol and (2) Lower Degree Polynomial Approximation and Smaller Rings.", "questions": "Why HE + Add-SS is used for 2PC; why not directly use multi-party computing for 2PC?", "limitations": "No security proof for section 3.2 Client-side Outer Product Protocol", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents the complexity analysis and memory impact analysis well. These analyses help readers understand the advantages of the COP protocol.", "weaknesses": "1. Not quite sure why HE + Add-SS is used for 2PC; why not directly use multi-party computing for 2PC? Please compare the differences between these two techniques and related papers, as it is uncertain whether HE + Add-SS is a more promising technique for privacy-preserving transformers.\n2. The Client-side Outer Product Protocol is one of the main contributions. However, there is no security proof for section 3.2 Client-side Outer Product Protocol, especially for the content from lines 165 to 170.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your helpful comments, and would like to address the main concerns as follows.\n# Q1: Why HE + Add-SS is used for secure two-party inference\nHE combined with additive secret sharing (Add-SS) is one of the most promising techniques for secure two-party DNN inference. The technique of HE+Add-SS has been widely used in prior works such as Gazelle [17], Delphi [38], Cheetah [16], Iron [13], BOLT [33], and BumbleBee [29]. The rationale behind this is that HE allows the communication cost of securely computing linear layers to be independent of the model parameters. While other 2PC approaches such as GMW, Beaver, and garbled circuit (GC) require communication linear in the size of model parameters, the HE approach achieves significantly lower communication for linear layers. For non-linear layers, the 2PC protocol mainly adopts the Add-SS approach, which achieves the best efficiency for now. In particular, Add-SS, which is often combined with the oblivious transfer (OT) extension protocol, is particularly suitable for securely computing Boolean circuits, which are currently the most efficient circuit representation for non-linear functions. The Add-SS approach also obtains much lower communication than other approaches such as GC. We will clarify this in the updated version.\n\n# Q2: Security proof of the client-side outer product protocol\nWe omit the security proof since the security of our client-side outer product protocol directly builds upon a secure homomorphic encryption (HE) scheme, and thus its security proof is somewhat straightforward. In particular, our protocol guarantees the same security as the traditional server-side inner product protocol. In the presence of a semi-honest adversary, we provide a brief proof idea below, and will include a formal proof in the Appendix. \n\nSpecifically, the model weights are encrypted by the server and then sent to the client, where the ciphertexts are denoted by Enc(W). From the CPA security property of the HE scheme, the ciphertexts reveal no information about these model weights. For secure matrix multiplication, the input matrix X has been shared as $(X_c, X_s)$ using Add-SS. The client samples a matrix of random shares $Y_c$, and then homomorphically computes a ciphertext $Enc(X_c * W-Y_c)=X_c * Enc(W)-Y_c$. Due to the circuit-privacy property of the HE scheme, in the client view, the ciphertext $Enc(X_c * W-Y_c)$ does not reveal information on $X_c$ and $Y_c$. The ciphertext $Enc(X_c * W-Y_c)$ is sent to the server, who decrypts it to a matrix of shares $T_s$ such that $Y_c$ and $T_s$ constitute additive sharings of $X_c * W$. Finally, the server can locally compute its shares $Y_s=T_s+X_s * W=X * W-Y_c$, and $(Y_c, Y_s)$ constitutes the additive sharings of $X * W$. It is natural to see that the local computation is secure. In the proof of security, the simulator can simulate the HE ciphertexts using \"dummy\" ciphertexts on zero, and the adversary's view between the real-world execution and ideal-world execution is proven to be computationally indistinguishable by reducing it to the CPA and circuit-privacy security of the HE scheme.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0x7DhgGFwD", "reviewer": "Reviewer_7qmF", "summary": "This paper proposes Nimbus, a secure inference protocol for transformers in the 2pc setting. They propose distribution-aware nonlinear function approximation to use low-degree polynomials to compute GELU and softmax. They showed that their method can preserve accuracy and achieve efficient performance by comparing it with several baselines.", "questions": "- The major reason that prevents me from advocating this paper is that the nonlinear function approximations actually leak sensitive information about the training input distribution, which is not desirable in a secure inference system. For instance, the approximations polynomials are available to both parties, such that the client can easily reverse engineering the training inputs' distribution. For the GELU function, you can save one comparison and multiplication in 2PC compared to Bumblebee and BOLT but at the cost of leaking private information.\n- Additionally, the input ranges for different models, datasets, training parameters, and even different layers could be significantly different. Thus, you might need different approximations for different tasks, which will leak model information and is not friendly to use.\n- In your system, the matrix multiplication is done on the client side, which introduces a large memory overhead on the client side as they need to load the encrypted model into the memory. The encrypted model could be hundreds of times larger than the plaintext model. Considering that the client could be a normal user, such an issue should be avoided in a 2PC inference system.\n- I'm wondering why BumbleBee's performance is not as good as reported in their paper. It's about 5x faster compared to your reported numbers. Are you running their code correctly?\n- In line 308, you mentioned that BOLT uses aggressive approximation for efficiency, which is not the case. MPCFormer indeed introduces significant modifications to the nonlinear functions, but I believe BOLT's approximations are accurate, and they should be comparable to your designs. Additionally, BOLT seems to be open-sourced as BumbleBee mentioned that they obtained the results by rerunning their code.", "limitations": "See my concerns in the Question section.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Improving the efficiency of the secure inference systems is an important and timely topic.\n- Extensive experiments are conducted to demonstrate the efficiency and accuracy of the proposed system.", "weaknesses": "- The nonlinear approximation is leaking private information.\n- This proposed system might require huge storage overhead on the client side.\n- There is incorrect information regarding BOLT (S&P'24) and BumbleBee (NDSS'24).\n- There is a gap between the authors' reported results and BumbleBee's results in their paper, which needs further explanations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback on our paper. We appreciate your insights and would like to provide more clarification.\n# Q1, Q2: The leakage of the approximation polynomial\nThe secure polynomial evaluation does not allow the client to learn the polynomial coefficients and comparison thresholds, except that the coefficient on the highest degree term is known by the client to achieve slightly better efficiency. It is easy to eliminate the leakage of the high-degree coefficient by introducing an overhead of about 8%. See below for more details.\n\nWe use the GELU function as an example to show how securely computing a polynomial keeps the coefficients and thresholds secret from the client. We first discuss the coefficients. Consider the approximation polynomial $P^2(x)=b_0 x^2 + b_1 x + b_2$. The client and server hold an additive secret sharing on the input secret $x$ denoted by $\\langle x \\rangle = (x_c, x_s)$, and only the server knows $(b_0, b_1, b_2)$. To compute the additive secret sharing of $P^2(x)$, two parties first jointly compute $\\langle A_1 \\rangle = \\Pi_{mul}(\\langle b_0 \\rangle \\cdot \\langle x \\rangle)+b_1$, where $\\Pi_{mul}$ is the secure multiplication technique in BumbleBee [29]. Then two parties jointly compute $\\langle A_2 \\rangle = \\Pi_{mul}(\\langle A_1 \\rangle \\cdot \\langle x \\rangle)+b_2$ as the sharing of $P^2(x)$. During the evaluation, $b_0$ is kept secret through secret sharing, while $b_1$ and $b_2$ can be added locally at the server side using the linear property of additive secret sharings. This ensures that $b_0, b_1, b_2$ remain secret from the client. Second, for the comparison thresholds. To compare $x$ with a secret threshold $T$ known only by the server, the server can locally compute the additive secret sharing $\\langle x-T \\rangle = \\langle x \\rangle - T$ using the linear property of additive secret sharings. Then, both parties execute a secure comparison protocol on the input $\\langle x-T \\rangle$ to obtain an additive secret sharing of the bit indicating whether $x-T$ is greater than zero or not. Thus, the threshold $T$ is kept secret.\n\nIn this paper, to achieve better performance, we choose to let the server send $b_0$ to the client. As illustrated in line 1 of Alg. 3, this can eliminate one call to $\\Pi_{mul}(\\langle b_0 \\rangle \\cdot \\langle x \\rangle)$ and instead compute $b_0 \\cdot \\langle x \\rangle$ locally. This is a trade-off between security and efficiency. However, it is important to note that simply revealing the highest degree coefficient is not sufficient for the client to recover the input distribution. If the leakage is still a privacy concern, we can keep the highest-degree coefficient $b_0$ secret as the protocol in the above paragraph mentioned. We denote Nimbus* as the slightly modified protocol in the above paragraph that keeps $b_0$ secret and guarantees zero leakage on the polynomial. Following the same experimental setup, Nimbus* only increases the overhead by around 8% for secure computation of non-linear functions compared to Nimbus that reveals $b_0$. See the following table for the efficiency comparison, where the values are measured in seconds.\n|Method| GLUE (LAN) | Softmax (LAN) | GLUE (WAN)| Softmax (WAN)|\n|-|-|-|-|-|\n|Bumblebee|1.17|2.23|3.36|9.01|\n|Nimbus|0.28|0.56|1.02|3.07|\n|Nimbus*|0.30|0.61|1.10|3.29|\n\n# Q3: The memory concern of loading encrypted model into the memory\nWe discussed this concern in Section 3.3. The encrypted model weights are expanded to at least four times the size of the plaintext weights. However, our solution does not store all the ciphertexts on model weights in memory. Instead, we only load the ciphertexts for a limited number of layers into memory. This approach is based on the insight that secure inference is primarily bottlenecked by network communication. By overlapping the swapping of ciphertexts from local disk to memory with network communication, we add no extra running time to load a part of ciphertexts on model weights. See Section 3.3 for more details.\n\n# Q4: Performance gap between the reported results and BumbleBee’s results in their paper\nOur experiments are based on the open-source codes of BumbleBee and are expected to produce similar results to theirs. We have double-checked the experimental results reported in this paper against those reported in BumbleBee and find similar performance results. Note that while BumbleBee reports the performance of the whole model, we report the performance of each layer.\n\nFor example, we consider the experiment over a WAN, using almost identical settings as BumbleBee: a 400Mbps network bandwidth, the BERT-base model, and an input length of 128. In Table V of BumbleBee, they state that the 12-layer model takes 4.86 minutes, which translates to approximately 24.3 seconds per layer. This is very close to the 23 seconds per layer reported in our Table 6(b). Despite differences in hardware, the performance data from a concrete implementation is valid. We are happy to provide source codes for experimental reproduction.\n\n\n# Q5: Comparison with BOLT's nonlinear approximation\nWe say that BOLT uses aggressive approximation, meaning that the numbers reported in BOLT show an accuracy loss, as shown in Table 2 of BOLT's paper. We use the term \"aggressive\" to differentiate it from the approximation with (almost) no accuracy loss used in Iron and BumbleBee. Indeed, BOLT's approximation has a much smaller impact on accuracy, compared to MPCFormer. We will clarify it, and instead say that BOLT has a larger accuracy loss than Iron, BumbleBee and Nimbus, in the updated version.\n\nBy the time we submitted the paper, BOLT had not released their codes. Therefore, we implemented their nonlinear approximation using the backend of SecretFlow and compared the performance in Appendix G.4. Here, we also include performance comparison using their official codes, which can be found in Table 1 of the **supplementary PDF** under the \"global\" response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2NnVvyoDb4", "reviewer": "Reviewer_zib5", "summary": "This work proposes a new secure two-party computation (2PC) protocol called Nimbus for Transformer models to improve the efficiency and effectiveness of large matrix multiplication and non-linear layer approximation in Transformer inference. First, this work exploits client-side outer product and output compact to enhance layer multiplication. Second, input distributions are taken into consideration to better approximate GELU and exponential with lower-order piecewise polynomials. Comprehensive experiments and analyses are demonstrated in this work, and the results indicate Nimbus is effective and efficient.", "questions": "Please refer to the contents of the Weaknesses part.\n\nBesides,  there are some writing mistakes. For example, in Line 4 of Algorithm 1 in the appendix, it should be $\\widetilde{c} - r(\\theta)$ rather than $r(\\theta) - \\widetilde{c}$.", "limitations": "As mentioned above, the input distributions estimated by sampling when approximating non-linear functions may suffer from inaccuracy, and the description of the exact sampling process is not very clear.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Nimbus proposes client-side outer product (COP) and output compact with shift operation to reduce the computing and communication overhead.\n\n- Nimbus considers the impact of input distribution to simplify the polynomial approximation of GELU and Softmax with lower-order piecewise polynomials and small rings.\n\n- The authors provide a comprehensive discussion of Nimbus efficiency and feasibility, including client-side resources, asynchronous weight loading, free ring conversion, and more.\n\n- This work presents comprehensive complexity analyses, protocol definitions, and evaluation experiments, making the results and conclusion convincing and practical.\n\n- The evaluations prove that Nimbus significantly improves the performance and efficiency of secure 2PC for Transformer models, compared with existing works like BumbleBee, Iron, and BOLT.", "weaknesses": "The major concerns are the accuracy and feasibility of estimating input distribution by sampling.\n\n- The server samples a batch of data from the training dataset to estimate the input distribution. I notice the work lack details of this process. For example, what is the exact batch size of sampling? I think such hyper-parameter can influence the effectiveness and efficiency of sampling. Does Nimbus compute the results of all training data to get the distribution, or just sample a subset? The precise process of sampling is worth further mentioning.\n\n- It seems that Nimbus assumes that the training data and test data share the same distribution, or at least the distributions are similar. What if the two distributions are more significantly skewed?\n\n- The initial state of piecewise approximation polynomials is pre-defined empirically despite the precise split points optimized by equation (3). For example, the approximation for GELU is divided into three pieces, with the middle piece being a quadratic polynomial. However, what if the distributions of inputs differ in practical cases? Figure 4 illustrates the distribution of non-linear functions for one specific dataset. If there exists another dataset with a more uniform distribution, such pre-defined piecewise polynomials may result in unwanted inaccuracy.\n\n- In some special cases, to further protect privacy, not only the inference stage is protected by secure 2PC, but the training dataset are also protected by secure training. In such case, the server may fail to estimate the input distributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your helpful comments, and address your concerns as follows. We also appreciate the reviewer's attentive reading for pointing out the typo in the Appendix. We will rectify this in the revised version.\n# Q1: Details of the batch size for summarizing the input distribution\nFor all eight tasks in Table 2, we randomly sample sentences from the training dataset until the total token count reaches 512. This is based on the finding that the distribution of intermediate activations stabilizes when the sampled data exceeds 256 tokens. We have included figures illustrating this observation in Figure 2 of the **supplementary PDF** under the \"global\" response.\n\n# Q2: What if distribution of the test data are significantly skewed from the training data\nThe distribution skewness between the training and test data indeed exists and causes the generalization error of the model's accuracy. Nimbus is also affected by this skewness. As shown in Table 2, the skewed data contributes to the accuracy loss in the third line. However, the skewness does not have a significant impact and can be recovered through lightweight fine-tuning. The skewness is less significant for DNN models since the accuracy of DNN models relies on the independent and identically distributed (i.i.d) assumption among the training and test datasets [1], and many techniques are proposed to guarantee this assumption. For example, normalizing the training and test data using the same statistics, and using layer normalization to make the model more robust to distribution changes. Pretraining Transformers requires a large amount of data so that the model is trained to map data to the same hidden space. Many model compression techniques also utilize this assumption to design quantization [2] or pruning [3] strategies. Nimbus also builds on such a common assumption.\n\n[1] Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures, NIPS 2022\n\n[2] Deja vu: Contextual sparsity for efficient llms at inference time, ICML 2023\n\n[3] Smoothquant: Accurate and efficient post-training quantization for large language models, ICML 2023\n\n# Q3: Generalization of the insight on activation distribution to other datasets\nWe supplement our study with additional experiments on the activation distribution (Figure 1 in the **supplementary PDF** of the global response) to demonstrate the generalization. Besides the observations provided in the paper, we verify the activation distribution on additional popular datasets. Our experiments include the BERT-base model on the MRPC dataset (for sequence classification), SQuAD dataset (for question & answering), and SWAG dataset (for multiple choice), along with the GPT-2 model on the Wikitext-2 dataset (for causal language modeling). We observe obvious non-uniform distributions across these datasets. Furthermore, these distributions exhibited similar patterns, indicating that the piece splitting strategy proposed in this paper can be directly applied to other datasets. The regular distribution of intermediate activations has also been verified by prior works as a widely applicable rule across various Transformer models and tasks [1,2], where it has been utilized for quantization and sparsity in [1,2].\n\nTherefore, compared to the previous strategy of treating the input distribution as uniform, our distribution-aware fitting is expected to yield better fitting results. We also conduct accuracy experiments on these datasets. As the following table shows, Nimbus only has a minor impact on the accuracy.\n| Method      | BERT-base (MRPC) | BERT-base (SQuAD) | BERT-base (SWAG) | GPT2 (wikitext-2)  |\n|-------------|------------------|-------------------|------------------|--------------------|\n|             | F1               | F1                | accuracy         | perplexity         |\n| FP baseline | 90.12            | 88.1              | 81.08            | 20.01              |\n| Nimbus      | 90.42            | 87.93             | 80.94            | 21.36              |\n\n\n[1] Deja vu: Contextual sparsity for efficient llms at inference time, ICML 2023\n\n[2] Smoothquant: Accurate and efficient post-training quantization for large language models, ICML 2023\n\n\n# Q4: Estimation of input distribution when the training dataset is also secret for the server\nThis case poses a greater challenge for secure inference and is interesting to explore. In this scenario, the intermediate activations are invisible to the server so that he cannot directly estimate the distribution. The server can employ privacy-computing techniques such as MPC and differential privacy to estimate the activation distribution, which is feasible even though the training dataset is secret. As mentioned in question 1, our method only requires a small batch of data (e.g., 512 tokens in total) to estimate the distribution. Because the data volume is small and the estimation is a one-time setup task, the performance using a privacy-computing technique to estimate the activation distribution is acceptable. We believe that our solution will remain attractive for such a more challenging case.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Global response
Thank you for taking the time to review our work. Besides the separate response, we also include a **PDF** file under the global response that contains figures and a table related to the reviewers' comments. If you have any further questions or need more details, please don't hesitate to reach out. Your feedback is important to us, and we are ready to explain anything further. Thanks again for your comments!

Meta-review: All reviewers agreed this paper should be accepted: it addresses an important problem, the experiments are comprehensive, and the distribution-aware approximation is interesting. Authors: you've already indicated that you've updated the submission to respond to reviewer changes, if you could double check their comments for any recommendation you may have missed on accident that would be great! The paper will make a great contribution to the conference!
Decision: Accept (poster)