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_cc_2024_Conference
Published: 2024-05-06 15:40:49

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.

Main paper: 
 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 a 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. 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 [17, 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 a Client-Side Outer Product (COP) protocol to 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 to design a novel row-wise encoding scheme that achieves homomorphic matrix multiplication via the outer product. Such encoding further enhances the efficiency of homomorphic matrix multiplication and yields compact output ciphertexts for communication.• For non-linear layers, we present a 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 to 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 to fixed-point errors, allowing us to adopt a smaller ring for greater efficiency. We also propose a 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 [26] , we improve the performance of securely computing matrix multiplication (resp., GELU and Softmax) by 2.9× ∼ 12.5× (resp., 2.9× ∼ 4.0×). Combining all the optimizations, we improve the end-to-end performance of secure two-party inference by 2.7× ∼ 5.9× and reduce the communication cost by 60%. The code is available at: https://github.com/secretflow/spu. 
background: 
 We present the necessary background, including the threat model, cryptographic building blocks, and secure Transformer inference.Our protocol works in the two-party setting where the client C holds an input and the server S holds a 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 privacypreserving machine learning and has been used in most two-party protocols [18, 34, 17, 14] . As in all prior two-party inference protocols, the client is only allowed to learn the model's architecture and inference result while the server gains no information about the client's input.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 i to denote the i-th row of W and W i,j to denote the entry in the i-th row and j-th column of W. For an integer n, we write [n] = {0, 1, • • • , n -1}. For an additive secret sharing ⟨•⟩ (defined in Section 2.3), we use ⟨•⟩ c (resp., ⟨•⟩ s ) to denote a share held by a client (resp., a server). We denote by [[M] ] the homomorphic encryption (HE) ciphertexts on matrix/vector M where it may consist of multiple ciphertexts. We use Z 2 ℓ = Z ∩ [0, 2 ℓ ) to denote a ring with all entries modulo 2 ℓ . For a power-of-two integer N , we use A N,2 ℓ = Z 2 ℓ [X]/ X N + 1 to denote a set of polynomials over a ring Z 2 ℓ . Besides, we use lower-case letters with a "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 at most N elements over Z 2 ℓ .Our framework is 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-protocols used in non-linear layers can be found in Appendix B.Additive Secret Sharings. In the two-party setting, an additive secret sharing over a ring Z 2 ℓ is defined as: for a value x ∈ Z 2 ℓ , two random shares ⟨x⟩ c ∈ Z 2 ℓ and ⟨x⟩ s ∈ Z 2 ℓ are sampled uniformly such that x = ⟨x⟩ c + ⟨x⟩ s mod 2 ℓ , where ⟨x⟩ c is held by a client and ⟨x⟩ s is held by a server.Homomorphic Encryption. We adopt the lattice-based additive HE scheme [26] (building upon [33] ). 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 m ∈ (Z 2 ℓ ) N into a plaintext polynomial m ∈ A N,2 ℓ , and then m is encrypted to a ciphertext[[m]] = ( b, â) ∈ A 2 N,qwhere 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.1 for details of the HE scheme and its homomorphic operations.Conversion between Floating-point Numbers and Ring Elements. As 2PC and HE usually operate over rings, the floating-point numbers used in Transformers need to be converted into fixed-point numbers in a ring. Given a scale s ∈ N (i.e., the length of the fractional part) and a ring Z 2 ℓ , a floating-point number x ∈ R is converted to the approximated fixed-point number by computing x := ⌊x • 2 s ⌋ mod 2 ℓ , and x can be converted back to the approximated x by setting x/2 s .The details of the Transformer architecture are described in Appendix A. To securely evaluate the 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 Linear qkv , Linear o , Linear h1 , and Linear h2 . 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 [28, 26] . We do not give special optimizations and leave them as future works. 
secure computation of linear layers: 
 We first analyze the efficiency problems of the prior solution in Section 3.1. Then, Section 3.2 presents our client-side outer product (COP) protocol with row-wise encoding. In Section 3.3, we optimize the memory occupation of our COP protocol.The starting point of this work is the protocol so-called server-side inner product (SIP) [17, 14, 26] , as shown in Figure 2 (a). The inputs of the linear layer are additive secret sharings ⟨X⟩ C , ⟨X⟩ S ∈ Z k×m2 ℓheld by the client and server. The server also holds the weights W ∈ Z m×nEQUATIONThe values of two activation shares and server weights are encoded into polynomials over A N,2 ℓ using encoding functions π L : Z k×m2 ℓ → A N,2 ℓ and π R : Z m×n 2 ℓ→ A N,2 ℓ , as shown in Equation (1) . The coefficients of the polynomials x and ŵ that are not defined are set to 0. ẑ = x • ŵ ∈ A N,2 ℓ gives the result of matrix multiplication Z = X • W ∈ Z k×n 2 ℓ, as illustrated in Figure 1 . If kmn > 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 dimensions k w × m w and m w × n w , which results in multiple windows of the output matrix Z with dimension k w × n w . Therefore, we refer to this encoding approach as window encoding.Then, the client encrypts her plaintext polynomials as HE ciphertexts [[⟨X⟩ c ]], and sends them to the server. After receiving[[⟨X⟩ c ]], the server computes the HE ciphertexts [[X]] by homomorphically adding [[⟨X⟩ c ]] + ⟨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⟩ s . Finally, the server sends [[WX -R]] to the client who decrypts the HE ciphertexts into WX-R that is used as the client's shares ⟨Y⟩ c . 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(N 2 ) to O(N log N ).To simulate the inner product, the window encoding produces a sparse output (e.g. the even-degree terms of ẑ in Figure 1 ). The sparse polynomials are treated as dense after encryption, leading to inefficient communication and computation marked by the dashed boundary in Figure 2 (a). First, the computation includes unnecessary zero terms. Second, Iron shows at least 2 √ kmn √ N ciphertexts are transmitted [14] . Then, BumbleBee [26] proposes a packing approach that trades computation for less communication, but the overall latency is similar.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 a 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 C.1. [W⟨X⟩ c ]] -R to obtain HE ciphertexts [[W⟨X⟩ c -R]]which is sent to the server. Finally, the server decrypts these ciphertexts to obtain W⟨X⟩ c -R, and then sets its output shares as⟨Y⟩ s = W⟨X⟩ c -R + W⟨X⟩ s .As a result, two parties hold additive secret sharings (⟨Y⟩ c , ⟨Y⟩ s ). Below, we explain the key process for computing ⟨X⟩ c • [[W]] using the row-wise encoding approach.Row-wise Encoding. Assigning the client to perform the plaintext-ciphertext multiplication has a direct benefit in terms of saving the communication of inputs. More importantly, such saving enables us to design a new encoding approach for the weights and activations. First, we use the following function to encode each row of the weight matrix, i.e.,EQUATIONThe 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 w = 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 on 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 1 in Figure 3 . Following the spirit of the outer product, each scalar-polynomial multiplication produces a partial sum of Z 1 and their accumulation produces the final output. The scalar-polynomial 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 n 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 a ciphertext can be done by multiplying the ciphertext with a plaintext polynomial with only a s-order term. The right figure of Figure 3 shows the right shift packing. The second ciphertext is 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 1 compares the computation complexity and numbers of communicated ciphertexts. Communication: Our COP protocol eliminates the input communication, and output communication is the minimal case of prior kn kwnw when k w n w = N since values are densely arranged in the output ciphertext. Computation: The SIP protocol requires polynomial-polynomial 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(kmn). In our protocol, the NTT is only applied when the server decrypts the output ciphertext. The client's scalar-polynomial multiplication saves time spent on the NTT by directly performing the multiplication with a complexity O(kmN ), which is comparable to the previous multiplication in the NTT space, especially when n is close to N .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 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 as well as the expensive NTT cost brought about by homomorphic encryption and decryption, existing secure-inference frameworks, e.g., [17, 14, 5, 26, 29, 42] , require the client to be equipped with similar resources as the server, including a powerful CPU (e.g., 64 vCPUs) and a large memory (e.g., 128 GB) [42, 26, 29] . For clients in MPC, disk usage does not pose a significant issue as storage resources are inexpensive. The CPU usage is also not an issue as the analysis and experiments in Appendix F.2 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.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 a 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 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 a large overhead for securely computing the powers of values. Additionally, such an approximation requires computations to be conducted over a large ring Z 64 and with a large scale s = 18 [14, 5, 26] . This is 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.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
simpler piecewise polynomial and smaller rings by distribution-aware 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 nonlinear functions at the 4 th encoder. As an example, consider the input distribution of 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 to 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-aware Splitting and Fitting. Prior works typically split the input range and fit each interval based on the non-linearity of the curve. We further include the consideration of the input distribution for these two processes. For intervals with low non-linearity or input probability, we split them out and assign constant or linear polynomials to fit. The other intervals with both high non-linearity and input probability are fitted by quadratic or cubic polynomials. When fitting each piece of the non-linear function f (x) by the polynomial f ′ (x), we minimize the expected loss that integrates the inputs' probability density p(x)EQUATIONwhere l and h are the lower bound and upper bound. p(x) is the probability density function obtained by summarizing a batch of training data. Unlike prior works using fixed breakpoints l and h, we initialize each breakpoint with a starting value and search around it to 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.1. Next, we elaborate on the specific design for fitting exponential and GELU functions.Exponential. The exponential is used in the Softmax. Given an input vector x, the i-th element of Softmax is computed as exp(xi-max{x}) j exp(xj -max{x}) . 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 a sharp increase on the right. Prior works adopt a two-piece approximation by breakpoint -13. Instead, we initial breakpoints around -4 for varying depths. As the right interval spans a smaller range, it adopts a cubic polynomial P 3 (x) 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.EQUATIONGELU. The GELU curve nearing the zero exhibits pronounced non-linearity. Prior works [5, 26] assign two polynomials for intervals [-5, -1.97] and [-1.97, 3] with degree three and six. We merge these two intervals by one and shrink the range to[T 1 , T 2 ] = [-2.1, 0.2]. This is because the values beyond this interval present either less non-linearity or fewer occurrence probabilities, and using constant or linear polynomials is enough. As the middle interval becomes narrow, we find a square polynomial P 2 (x) is enough. The specific breakpoints T 1 and T 2 change for different depths. EQUATIONOur low-degree polynomials reduce the errors of operation on fixed-point numbers and potential overflow problems. This enables smaller ring Z 32 and precision s = 12 for computing Softmax and GELU functions, instead of the original standard ring Z 64 and precision of s = 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 a larger to a smaller ring can be performed locally, incurring negligible cost [31, 39] . Upcasting from a smaller to a larger ring necessitates addressing the wrap-around of shares, requiring communication among parties. Interestingly, we notice the situations demanding to upcast are always after a truncation operation that inherently computes the wrapping, which can be repurposed for the upcast to avoid additional costs. We propose a novel protocol that fuses the upcast with the truncation. We defer the protocol and the correctness proof to the Appendix E. 
performance evaluation: 
 Experimental Setup. We follow similar configurations used in prior works [26] . Except optimized non-linear functions using ring Z 2 32 and precision s = 12, other operations follow standard Z 2 64 and s = 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, 1ms) and (400Mbps, 10ms), respectively.Baselines. The baselines include Iron [14] and BumbleBee [26] . Our implementation follows the open-sourced code of BumbleBee on SecretFlow [28] . 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 [5] use piecewise polynomial approximation. BumbleBee further integrates cryptographic optimizations to make a stronger baseline. In the Appendix F.4, we also compare our 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 base [19] from HuggingFace [38] . When evaluating the performance, we use 128 as a 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 of 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 of sampled tokens yields no significant changes in the input distribution.Table 2 reports the accuracy of floating-point plaintext, BumbleBee, and our approximation across 8 tasks in the GLUE benchmark [37] . The precise approximation of BumbleBee causes small errors due to the truncation error of the fixed-point value computation. Without fine-tuning, Nimbus decreases accuracy in a small range and the average loss is around 0.6%. Such loss can be easily reduced to 0.08% through a lightweight fine-tuning Nimbus † . This demonstrates the effectiveness of our approximation. We also compare accuracy and efficiency with works that compromise accuracy in Appendix F.4, including MPCFormer [22] and BOLT [29] .Figure 5 presents the output error of exponential and GELU functions to further explain the effectiveness of our approximation. The error is summarized using a batch of test data on a certain layer. On the standard ring Z 2 64 and precision s = 18, our L2-norm errors are around 0.005 and are close to the loss-free approximation of BumbleBee. When reducing to ring Z 2 32 and s = 12, BumbleBee encounters 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 a steady fixed-point error and is not prone to overflow thanks to the low-degree polynomial. This enables moving to the smaller ring with a minor impact on the accuracy.As the main body of the Transformer model are identical Transformer blocks, we present the end-toend latency of one Transformer block under LAN and WAN network settings in Figure 6 . Besides the optimized parts of this paper, we unify the unoptimized activation matrix multiplication (QK T &P V ) and LayerNorm (LN) 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 all our optimizations, the overall runtime is 4.8× ∼ 5.9× faster than Iron and 2.7× ∼ 4.7× faster than BumbleBee. Comprehensive results on varying Transformer size and input sequence length are listed in Appendix F.1. In the following, we provide a detailed analysis of linear and non-linear layers.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, we have 7.2× ∼ 12.5× in the LAN setting and 2.9× ∼ 4.0× 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.4× faster in the LAN setting and 3.3× faster than the WAN setting. The Softmax is 4.0× faster in the LAN setting and 2.9× faster than the WAN setting.Then, we compare the communication cost and the number of rounds of linear layers, Softmax, and GELU in Table 3 . The data is summarized using BERT base and sequence length 128. For different types of linear layers, our protocol only requires half the number of communication rounds.  
related work: 
 Privacy-preserving Neural Network Inference. Due to 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, 18, 32, 43, 31] . 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 [18, 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 Transformer model. For linear layers, Iron [14] 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 linear 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 a novel encoding approach that facilitates more efficient homomorphic computation and output communication. Other works [1, 5] consider 3PC inference for Transformers, which rely on 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 ≈(x[i]+c) 2 i (x[i]+c) 2 and GELU(x) ≈ x 2 8 + x 4 + 1 2. However, such aggressive approximations lead to noticeable accuracy loss, even when employing knowledge distillation to mitigate the decline in accuracy. Other methods, such as look-up tables for faithful approximation [31, 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 is inspired by insights from the input distribution used in the Transformer model [9, 10, 11, 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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: This is not the core contribution of this work. But still, we follow the standard method of prior work as we have mentioned in the Section 5.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 a 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, or as supplemental material. 
conclusion: 
 We propose a privacy-preserving, 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 a distribution-aware polynomial approximation for non-linear layers, allowing a simpler approximation with less communication and rounds. These optimizations significantly improve the performance, advancing a step towards the practical use of secure Transformer inference. Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?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, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 of compute required for each of the individual experimental runs as well as 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 or failed experiments that didn't make it into the paper). 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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-preserving inference in the Introduction section.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: The answer NA means that the paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes] Justification: We cite the original paper that produced the code package or dataset.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: We focus on Transformer [36] DNN models, such as popular models BERT [19] , GPT-2 [4] and LLaMA [35] . These models are stacked with Transformer blocks, each consisting of an attention module and a feed-forward network (FFN) module.Attention Module. The attention module starts with three independent linear layers Linear qkv 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 throughEQUATIONwhere d k is the hidden dimension of the key activation. The outputs of different heads are concatenated and fed into another linear layer Linear o , with one residue connection and one normalization layer to generate the final output of the attention module.FFN Module. The FFN module is composed of two linear layers and one activation layerEQUATIONwhere GELU [15] is the activation function. Similar to the attention module, its output needs a residue connection and a 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.We give a more detailed description of the cryptographic building blocks as a supplement to the paper. We follow those notations used in the paper.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-Error (RLWE) [27] . The RLWE scheme is defined by a set of public parameters {N, q, t}, where N is the polynomial degree, t is the modulus of the plaintext, and q is the modulus of the ciphertext.• KeyGen. Generate the RLWE key pair (sk, pk) where the secret key sk ∈ A N,q and the public key pk ∈ A 2 N,q . • Encryption. An RLWE ciphertext is given as a polynomial tuple ( b, â) ∈ A 2 N,q . Given a vector m which is encoded as m ∈ A N,t , We write [[m]] = Enc( m) to denote the encryption of m under a key pk.• Decryption. Given an RLWE ciphertext [[m]] = ( b, â) ∈ A 2N,q . We write m = Dec([[m]]) to denote the decryption under a secret key sk.0 ]] = b0 , â0 and [[m 1 ]] = b1 , â1that respectively encrypts m0 , m1 ∈ A N,t under a same key, the operation[[m 0 ]] ⊞ [[m 1 ]]computes the RLWE tuple b0 + b1 , â0 + â1 ∈ A 2 N,q which can be decrypted to m0 + m1 mod A N,t . ( b • ĉ, â • ĉ) ∈ A 2N,q which can be decrypted to negacyclicly right shift m for s terms. This can be implemented through a simple rearrange of the coefficients of the ciphertext, which is a free operation.OT lets a sender input two messages m 0 , m 1 and a receiver input a bit b, and then the receiver obtains the message m b . For security, the sender is unknown for b and the receiver does not learn m 1-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-efficient Ferret protocol [41] .Our protocol for non-linear layers calls the following functionalities in a black-box way to compute element-wise 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 2 ℓ and ⟨•⟩ B to denote Boolean additive sharings over a binary field F 2 . Secret sharing without superscript indicates using the default ring size (e.g., Z 2 64 for the linear layers and Z 2 32 for the exponetial and GELU functions).Protocols⟨X • Y⟩ = F mul (⟨X⟩, ⟨Y⟩) Element-wise multiplication [26] ⟨1{x < y}⟩ B = F less (⟨x⟩, ⟨y⟩) Less-then [28] ⟨x⟩ ℓ = F ℓ B2A (⟨x⟩ B ) Boolean to Arithmetic share [28] ⟨1{⟨x⟩ ℓ + ⟨y⟩ ℓ ≥ 2 ℓ }⟩ B = F wrap (⟨x⟩ ℓ , ⟨y⟩ ℓ ) Wrap the ring Z 2 ℓ [28]We present our detailed protocol of matrix multiplication of Section 3 in Algorithm 1. The detailed protocols of securely evaluating GELU and exponential in Section 4 are presented in Algorithm 2 and Algorithm 3.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 a brief proof idea below. The notations follow those in Algorithm 1. Specifically, the model weights are encrypted by the server and then sent to the client, where the ciphertexts are denoted by [[W] ]. According to the 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 additive secret sharing. The client samples a matrix of random shares R, and then homomorphically computes a ciphertext[[⟨X⟩ c * W-R]] = ⟨X⟩ c * [[W]]-R.Due to the circuit-privacy property of the HE scheme, in the client view, the ciphertext [[⟨X⟩ c * W-R]] does not reveal information on W. This ciphertext is sent to the server, who decrypts it to ⟨X⟩ c * W -R. Because of the random mask R, the server also learns nothing about the client share ⟨X⟩ c . 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 circuit-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 is 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 b 0 , which requires the primitive F mul , 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 a result, the client learns nothing about the piecewise polynomial. A possible improvement on the efficiency is to make b 0 public, thereby saving one round of communication. The only leakage of b 0 does not necessarily lead to leakage of the meaningful information and can provide approximately an 8% speedup. c = [[[c 0 ]], [[c 1 ]] • • • [[c k-1 ]]],wherec[α] = ⊞ β∈[m] (x α,β ⊗ [[W β ]]) . for α ∈ [k]. The c[α]denotes the α-th element of the vector c. 3: To compress the the k ciphertexts vector of c into k/⌊N/n⌋ ciphertexts, The client applies right shift on ciphertexts of c. For example EQUATION⟨b 0 ⟩ B = F less (⟨X⟩, T 1 ) ▷b 0 = 1{X < T 1 } ⟨b 1 ⟩ B = F less (T 2 , ⟨X⟩) ▷b 1 = 1{T 2 < X} .1{P } is 1 when the condition P is true and 0 otherwise. Two parties locally set⟨z 0 ⟩ B = ⟨b 0 ⟩ B , ⟨z 1 ⟩ B = ⟨b 0 ⟩ B xor ⟨b 1 ⟩ B xor l, ⟨z 2 ⟩ B = ⟨b 2 ⟩ B, where l is the party index. In this way, two parties have 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 as an example to explain. A similar algorithm can be easily generated to the GELU with two breakpoints.z 0 = 1{X < T 1 }, z 1 = 1{T 1 ≤ X < T 2 }, and z 2 = 1{T 2 ≤ X}. 3: Jointly compute the multiplexing ⟨Y⟩ = ⟨z 0 ⟩ B • 0 + ⟨z 1 ⟩ B • ⟨A 2 ⟩ + ⟨z 2 ⟩ B • ⟨X⟩The first step generates the breakpoint candidate set S given the initial breakpoint T . One can choose the search range and step according to 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(x) can be drawn from a 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.This section analyzes the computation and communication complexities listed in Partition the input range into two intervals using s.L total = 0.for each interval i do 7:Fit a polynomial of given degree using Equation 3 and obtain the corresponding loss L i .Compute total loss L total + = L i . S&C invoke F ℓ ′ -ℓ+s B2A ⟨w⟩ B and learn ⟨w⟩ ℓ ′ -ℓ+s . 3: For b ∈ {S, C}, P b outputs ⟨y⟩ ℓ ′ b = (⟨x⟩ ℓ b >> s) -2 ℓ-s * ⟨w⟩ ℓ ′ -ℓ+s b mod 2 ℓ ′ .Then, we explain the computation complexity. The server in the SIP protocol needs to apply NTT to weight O( mn mwnw N log N ) and the dyadic product kmn kwmwnw * N = kmn. In our scheme, the server only decrypts the k/⌊N/n⌋ output ciphertexts with complexity O ((k/⌊N/n⌋)N log N ). The client of the SIP protocol needs to perform NTT when encrypting the activation and INTT when decrypting the output, which requires O ( km kwmw + kn kwnw )N logN complexity. In our protocol, the client can directly multiply her activation share with the ciphertext on model weights. Our method has O(N ) complexity for each plaintext-ciphertext scalar-polynomial multiplication and km times product with total complexity O(kmN ).The protocol that computes truncation and upcast is in Algorithm 5. We show the correctness of it through the following derivation. Let ⟨x⟩ ℓ i (i ∈ 0, 1) denote the secret share held by the client and server on the ring Z 2 ℓ . The second line is drawn from the truncating secret shares on the ring 2 ℓ . w is a boolean value indicates the wrap of ⟨x⟩ ℓ i over ring size 2 ℓ and w ′ is the carry bits of the lower s bits. The carry bit w ′ is either zero or one and can be safely ignored in the inference while the w • 2 ℓ-s is a significant error that needs to be carefully handled. The third line holds since 1 i=0 ⟨x⟩ ℓ i /2 s -w • 2 ℓ-s + ŵ falls within the larger ring 2 ℓ ′ . The fourth line is the modulo expansion of the wrap w on a ring with k bits, where v is a boolean value that indicates the wrap of the ⟨w⟩ k . Through a proper choice of k ≥ ℓ ′ -ℓ + s 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⟩ k = ⟨w⟩ ℓ ′ -ℓ+s .EQUATIONF More ExperimentsWe present a comprehensive end-to-end latency comparison of a transformer block in Figure 8 , Figure 9 and Figure 10 . We present three model sizes: 768, 1024, and 2048. The input sequence lengths include 1, 32, and 128. Two network conditions are considered: 3000Gbps, 1ms (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 1 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.9× to 7.6× on sequence lengths 32 and 128. The speedup is minor on sequence 1 with 1.2× to 2.1×. For the linear layers, the speedup ranges from 2.47× to 12.09×, and the non-linear layers range from 2× to 3.9× In the following, we provide a detailed analysis of the speedup in linear and non-linear layers under varying conditions.Linear Layers. Our method is 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 is 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 4× to 10× faster than Iron and 2.0× to 3.9× faster than the stronger baseline BumbleBee. Our speedup on LAN and WAN are similar as our method improves the communication size and the communication rounds. The speedup is also similar for varying sequence lengths and hidden sizes. This is because our optimization lies in a lower degree of approximated polynomials and is not correlated with the input size.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 computation cost for our COP protocol is similar to the previous SIP protocol. This is based on a 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 ) is performed by the client when encrypting and decrypting, as listed in Table 1 . Our COP protocol makes the client perform a more efficient scalar-vector product with complexity O(kmN ). Since Linearqkv Linearo Linearh 1 Linearh 2 Softmax GELU QK T &PV LN Total Linearqkv Linearo Linearh 1 Linearh 2 Softmax GELU QK T &PV LN Total Linearqkv Linearo Linearh1 Linearh2 Linearqkv Linearo Linearh1 Linearh2 Linearqkv Linearo Linearh1 Linearh2 Linearqkv Linearo Linearh1 Linearh2 directly comparing computation complexity is hard to draw a conclusion due to the choice of the window size, we profile the client'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.7× to 2.7× compared with BumbleBee. The BumbleBee has less client computation because the compression used in BumbleBee allows the client to encrypt her activation shares to less number of ciphertexts and receive fewer output ciphertexts, thereby requiring fewer NTT operations. In the worst case of the Linear h2 , the client computation is around 5.0× longer than the BumbleBee. But still, on the total Transformer block, the extra overhead is only 2.7×. This extra computation ratio can be further shrunk given the base that the client needs to perform a large amount of computation of non-linear layers. Therefore, we believe this is acceptable for a powerful client in MPC.Asynchronous Weights Loading. For varying hidden dimensions, Table 4 lists the encrypted weight size and corresponding loading time from disk to memory, which usually takes less than 1 second. For the hidden size 768, which is the size of BERT base 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 a limited number of encrypted weights in the memory, such as weights of four linear layers of a Transformer block. Then, we swap the later weights during the execution. F.3 Amortized Overhead of the encrypted weights.Our linear protocol replaces the input communication with a one-time setup communication of sending encrypted weights. Although our method focuses on the overhead of the execution phase, we are also interested in how many queries can make the amortized setup overhead negligible. For BERT base , using our row-wise encoding, the encrypted weight size of four types of layer within a 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 to surpass the BumbleBee, leading to a speedup greater than 1. At around 40 queries, the maximal speedup is achieved.Besides BumbleBee [26] , this section compares non-linear approximation with other state-of-the-art (SOTA) works, including MPCFormer [22] and BOLT [29] .The details of the accuracy are listed in Table 5 . The accuracy of MPCFormer is reproduced using the open-sourced code of them. MPCFormer's idea is to adopt aggressive approximation to tailor the efficiency of the MPC but sacrifice the inference accuracy. For example, they let GELU (x) = 0.125x 2 + 0.25x + 0.5. MPCFormer can efficiently compute the Softmax and GELU. However, even using knowledge distillation to recover the accuracy, they still incur 2.26% accuracy on average. BOLT optimizes exponential and GELU using integer-only approximation and piecewise polynomial approximation, respectively. Similar to the BumbleBee, their approximation regards all input values as equal importance. Therefore, they require a relatively high-degree polynomial to 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.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 as its underlying cryptographic primitive instead of homomorphic encryption. To facilitate a fair comparison of the effectiveness of non-linear approximation, we 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 of 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 on a smaller ring, which makes us faster than MPCFormer's Softmax. Our method is approximately 10× faster than BOLT in all cases. In addition to the advantages of our simpler approximation, other factors also contribute to 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 a smaller ring. Since other layers still require computations on a larger ring, we also propose a truncation-upcast fusion protocol to eliminate the overhead of upcasting ring elements from a smaller ring to a larger one. In contrast, BOLT requires additional communication for this upcasting process.NeurIPS Paper Checklist 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 in 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 on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 


Decision: 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!

Reviews: review: paper_summary: paper_summary: This submission proposed secure inference protocols for Transformer-based model, involving two 
crucial components: HE-based linear operations and approximation-based no-linear operations. 
Experiments were conducted to verify the feasibility of the proposed protocols and to compare the 
performance with prior works on Transformer secure inference.
strength_weakness: strength_weakness: 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?

2. The contributions and novelty of the non-linear design are not sufficiently highlighted. It can be 
viewed as the variant of spline approximations with carefully selected coefficients, which is 
commonly applied in prior works [1].

3. Truncation in Alg. 5 discards the high-order bits rather than low-order bits. However, commonly
it is the variant of the logical right shift [2]. Please clarify the definition of such an operation.

[1] Hou, Xiaoyang et al. “CipherGPT: Secure Two-Party GPT Inference.” IACR Cryptol. ePrint 
Arch. 2023 (2023): 1147.

[2] D. Rathee et al., "SiRnn: A Math Library for Secure RNN Inference," 2021 IEEE Symposium 
on Security and Privacy (SP), San Francisco, CA, USA, 2021, pp. 1003-1020,
questions: questions: See above.
limitations: limitations: See above.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
questions: questions: Why HE + Add-SS is used for 2PC; why not directly use multi-party computing for 2PC?
limitations: limitations: No security proof for section 3.2 Client-side Outer Product Protocol
paper_summary: paper_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.
strength_weakness: strength_weakness: - The nonlinear approximation is leaking private information.
- This proposed system might require huge storage overhead on the client side.
- There is incorrect information regarding BOLT (S&P'24) and BumbleBee (NDSS'24).
- There is a gap between the authors' reported results and BumbleBee's results in their paper, which needs further explanations.
questions: 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.
- 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.
- 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.
- 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?
- 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: limitations: See my concerns in the Question section.
paper_summary: paper_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.
strength_weakness: strength_weakness: The major concerns are the accuracy and feasibility of estimating input distribution by sampling.

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

- 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?

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

- 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.
questions: questions: Please refer to the contents of the Weaknesses part.

Besides,  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: 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.

Comments: comment: We are pleased to hear that the rebuttal addresses your concerns and thank you for raising your score. We will clarify the security of the polynomial approximation protocol in the revision. We will also describe the zero-leakge version of the protocol, and provide the performance comparison. 

For the question of where the savings come from, there are three advantages in theoretical to consider. Firstly, the number of truncations called in Nimbus is the same as the number of secure multiplications called, which is two. In contrast, BOLT calls secure multiplication twice but makes four truncation calls. This is because BOLT includes additional multiplication between the public value and secret. While the multiplication between the public value and secret can be done locally, the truncation of the result sharing cannot be saved. The truncation protocol used in BOLT requires $\log \ell+3$ rounds of communication [1], where $\ell$ represents the bit length of the ring. As a result, this increases the overall communication overhead. Secondly, our low-degree approximation reduces the fixed-point error during computation, allowing computation on a smaller ring. Since other layers still require computation on a higher ring, to eliminate the overhead of upcasting ring elements from a smaller ring to a larger ring, we also propose a truncation-upcast fusion protocol. In contrast, BOLT requires $\log m+2$ rounds of communication [1] for this upcast, where $m$ is the bit length of the smaller ring. Thirdly, all computations of the Nimbus are performed on the ring, while the BOLT evaluates the linear layer on the field and the nonlinear layer on the ring. As a result, an additional conversion between the field and the ring is needed. As for the implementation, Nimbus uses HE based secure multiplication [2], while the BOLT uses OT-based secure multiplication [1]. The former saves more communication, and performances better when the network condition is bad. The underlying OT protocol also causes difference. The SOTA Ferret OT [3] used in Nimbus takes less communication than the IKNP OT [4] used by BOLT.

[1] Sirnn: A math library for secure rnn inference, SP 2021  
[2] BumbleBee: Secure Two-party Inference Framework for Large Transformers, NDSS 2021  
[3] Ferret: Fast extension for correlated ot with small communication, CCS 2020  
[4] Extending Oblivious Transfers Efficiently, CRYPTO 2003
Thanks for the authors' rebuttal. I have comments as follows:

Thanks for the clarifications on the function privacy. I think it should be clearly explained in the paper.

I still do not understand where are the savings from. In your GELU approximation, you need to evaluate 2 multiplications between secret shares and 2 comparisons, which should be the same as BOLT. Are the savings from the efficient crypto primitives used in Bumblebee?

Given that my major concern is addressed, I've slightly raised my score. I suggest the authors add a paragraph to discuss the function privacy in the revision.