1
General Techniques for Reducing Key-Switching Overhead in Privacy-Preserving Two-Party Transformer Inference
arXiv:2606.25349v1 [cs.CR] 24 Jun 2026
Wenshao Yang, Zhenhua Liu and Dongdong Yao
Abstract—In secure two-party Transformer inference, linear layers are typically evaluated using Fully Homomorphic Encryption (FHE) through plaintext-ciphertext or ciphertext-ciphertext matrix multiplications, where key switching primarily occurs and dominates computational overhead in both FHE-based and hybrid FHE-MPC systems. Existing optimizations rely heavily on packing-specific algorithms, limiting their general applicability. Targeting this overhead from a packing-independent perspective, we propose a preprocessing-assisted method for secure attention computation. By decomposing attention into precomputable operations and online interactions, this method reduces online inference-phase key switching without modifying existing packing strategies. However, the first method shifting key switching offline introduces additional storage requirements. To address this, we propose storage-communication trade-off techniques that replace large precomputed ciphertexts with modest online communication, enabling flexible deployment under varying resource constraints. While ciphertext-ciphertext matrix multiplication is offloaded to the preprocessing phase in hybrid schemes and the first layer of FHE-based schemes, these operations still persist in the offline stage and subsequent FHE layers. To further optimize it, we propose a fused key-switch technique targeting the multiplication-followed-by-rotation pattern, which frequently arises in existing RNS-CKKS matrix multiplication schemes. By combining relinearization and rotation into a single procedure, this technique reduces the associated computation costs. Analytical evaluations demonstrate that our proposed techniques significantly reduce online key-switch overhead and provide flexible trade-offs between storage and communication without requiring modifications to existing packing strategies. Index Terms—Secure transformer inference, Homomorphic encryption, Secure Multi-Party Computation, Key switch.
Note: This arXiv version focuses on analytical evaluation. An updated version including end-to-end implementation results and experimental evaluation will be released in a subsequent revision. I. I NTRODUCTION Privacy-preserving Transformer inference has become an important problem in the deployment of modern large language models (LLMs). In many practical settings, inference involves two mutually distrustful parties: the client holds sensitive input data, while the server owns proprietary model parameters. The client is unwilling to reveal plaintext inputs, and the server must protect model weights from leakage or extraction. Consequently, enabling efficient two-party Transformer inference while preserving both input privacy and model confidentiality is a fundamental challenge.
Existing secure Transformer inference systems are primarily built upon FHE or hybrid FHE–MPC techniques, where ciphertext matrix computations are typically executed using FHE. Since key switching dominates the latency of homomorphic matrix multiplication [1]–[6], a common optimization strategy is to jointly design plaintext packing schemes and ciphertext matrix multiplication algorithms. As a result, keyswitching complexity has become the primary metric for aring such as BLB [3], THOR [5], BOLT [4], MOAI [7], and ARION [2]. Consequently, many existing optimizations are closely tied to specific packing schemes, which determine how tokens and embedding dimensions are mapped to plaintext slots and thereby influence the structure of homomorphic matrix multiplication. This dependency often leads systems to be tailored for particular operating regimes. For instance, BLB and THOR are optimized for small token batches, whereas MOAI and ARION target large-batch inference. While these approaches achieve strong performance in their respective settings, their optimization techniques are difficult to transfer across alternative packing schemes, limiting their applicability and deployment flexibility. In this work, we address this limitation from a different perspective. Rather than proposing a new packing method, we introduce a packing-independent method for secure attention computation in two-party Transformer inference. The key idea is to reorganize ciphertext attention computation through preprocessing so that part of the ciphertext transformation workload is shifted from the online phase to preprocessing. Since the method operates at the attention-computation level rather than the packing-layout level, it is compatible with a range of plaintext packing strategies and can be incorporated into both FHE-based and hybrid FHE–MPC inference systems. In FHE-based settings, the method reduces online key-switching operations for the first layer of multi-head selfattention. In hybrid FHE–MPC settings, it can further reduce key-switching overhead throughout all layers. The preprocessing-assisted method reduces online key switching, but it does not eliminate all key-switching costs. In particular, ciphertext multiplication followed by ciphertext rotation remains a common computation pattern in secure attention inference and appears in many existing systems, including BLB, THOR, BOLT, and ARION. To further reduce this recurring cost, we propose a fused RNS-CKKS keyswitching technique that combines relinearization and rotation into a single procedure.
2
Overall, this paper makes the following contributions. First, we propose a packing-independent preprocessing-assisted method for secure attention computation, reducing online key-switching operations without modifying existing packing strategies. Second, we introduce storage-communication tradeoff techniques that replace large precomputed ciphertexts with modest online communication, enabling flexible deployment under different resource constraints. Third, we propose a fused key-switching technique for the multiplication-followed-byrotation pattern in RNS-CKKS matrix multiplication, reducing the overhead of relinearization and rotation. II. R ELATED W ORK Privacy-preserving machine learning (PPML) has been extensively studied using cryptographic techniques such as Secure Multi-Party Computation (MPC) [8], Fully Homomorphic Encryption (FHE) [9], Differential Privacy (DP) [10], and Trusted Execution Environments (TEE) [11]. Among these approaches, MPC and FHE provide strong cryptographic guarantees and have become the foundation of secure neural network inference systems [12], [13]. Existing secure Transformer inference (STI) systems can be broadly categorized according to their underlying cryptographic primitives into MPC-based [14], [15], FHE-based [1], [5], [7], [16], and hybrid FHE-MPC approaches [3], [6]. Early efforts on encrypted Transformer inference primarily focused on adapting Transformer architectures to the constraints imposed by FHE. Systems such as PolyTransformer [17] and PowerSoftmax [18] replace nonlinear functions with low-degree polynomial approximations to reduce multiplicative depth and improve FHE efficiency. While effective, these approaches require model retraining and may introduce accuracy degradation [2]. Subsequent FHE-based systems improve secure Transformer inference through optimized plaintext packing, ciphertext encoding, and preprocessing strategies. One line of work targets compact Transformer models or scenarios with relatively short input sequences. THOR [5] exploits diagonal matrix packing to reduce the cost of homomorphic attention computation. FHEBERTTiny [19] and Tricycle [20] further improve efficiency through optimized ciphertext encodings and offline preprocessing techniques. These systems demonstrate the feasibility of efficient encrypted Transformer inference in small-scale settings, but their designs and evaluations mainly focus on compact models or inputs with a limited number of tokens. Another line of FHE-based work focuses on improving throughput in large-batch inference settings. NEXUS [16] introduces client-side preprocessing to reduce online communication and accelerate attention projections. MOAI [7], Arion [2], and Euston [21] further optimize packing layouts, preprocessing procedures, and batching strategies to amortize homomorphic computation over many inputs. These approaches are effective for high-throughput scenarios, but their optimizations are typically designed around specific packing layouts or batching assumptions. Hybrid FHE-MPC protocols have also been proposed for two-party secure Transformer inference. These systems typi-
cally employ FHE for linear layers, such as matrix multiplications in attention and feed-forward networks, while using MPC to evaluate nonlinear operations including activation functions, normalization layers, and Softmax. Representative systems include BOLT [4], BLB [3], and EncFormer [22]. More recent designs [3], [22] further extend FHE computation into linear subcomponents within nonlinear functions, reducing the number of conversions between FHE ciphertexts and MPC shares and thereby lowering communication and truncation costs. Nevertheless, FHE-based linear layers continue to account for a substantial fraction of the overall inference cost. For example, EncFormer reports that under a WAN deployment setting with NVIDIA A100 GPUs, linear-layer computation contributes more than 75% of the total execution time [22]. A common characteristic of existing FHE-based and hybrid FHE-MPC Transformer inference systems is their reliance on specialized plaintext packing schemes. In small-model or short-sequence settings, packing layouts are often tailored to reduce the number of rotations in attention computation. In large-batch settings, packing and batching strategies are designed to amortize homomorphic operations across many inputs. Although effective in their respective settings, these optimizations are usually tightly coupled with the underlying plaintext layout, making them difficult to transfer across different secure inference frameworks. Consequently, improvements developed for one packing strategy often require substantial redesign before they can be applied to another system. In contrast, this work does not introduce a new plaintext packing scheme. Instead, we propose a packing-independent approach for secure attention computation that reorganizes encrypted attention evaluation through preprocessing. The proposed method can be integrated with existing packing strategies and reduces the number of online key-switching operations in both FHE-based and hybrid FHE-MPC Transformer inference systems. Furthermore, we introduce a fused key-switching technique for the commonly occurring ciphertext multiplication-followed-by-rotation pattern. Different from conventional approaches that perform relinearization and rotation independently, the proposed technique reduces the overall key-switching overhead associated with this computation pattern. Both optimizations are orthogonal to existing packing methods and can be incorporated into current secure Transformer inference systems without modifying their underlying plaintext packing strategies. III. P RELIMINARIES A. Notations Table I summarizes the notations used throughout the paper. We use bold lowercase letters (e.g., x) to denote vectors and bold uppercase letters (e.g., X) to denote matrices. The notation [[·]] denotes CKKS ciphertexts encrypted under the client’s public key. Depending on the underlying packing strategy, the encrypted representation of a matrix may consist of one or multiple ciphertexts. The symbols h·ic and h·is denote additive secret shares held by the client and the server, respectively. Unless otherwise specified, all matrix operations are performed over the corresponding plaintext domain.
3
TABLE I C RYPTOGRAPHIC N OTATION
Notation R, Z Zq N q Rq Λ [[M]] Enc σlt , σrt P, P ′ , P ′′ p(M) ℓP (M)
Meaning Sets of real and integer numbers Integer residue space modulo q Polynomial ring degree Ciphertext modulus Polynomial ring Zq [X]/(X N + 1) plaintext polynomial space encryption of matrix M encryption Left and right slot rotations by t positions Matrix encoding layouts Encoded plaintext polynomial collection of M Number of plaintext polynomials generated by P
B. Transformer Model The Transformer architecture [23] is built upon the multihead self-attention mechanism. Given an input token matrix X ∈ Rm×d , the query, key, and value matrices are computed as Q = XWq ,
K = XWk ,
V = XWv ,
where Wq , Wk , Wv ∈ Rd×d are learnable projection matrices, m denotes the sequence length, and d denotes the hidden dimension. The matrices Q, K, and V are partitioned into H attention heads: d
Q(h) , K(h) , V(h) ∈ Rm× H ,
h ∈ {1, . . . , H}.
For each attention head, the attention output is computed as ! Q(h) K(h)⊤ p Atth (X) = Softmax V(h) . d/H
The outputs of all attention heads are concatenated and projected through the output projection matrix Wo : MHA(X) = Concat (Att1 (X), . . . , AttH (X)) Wo . The multi-head attention module is followed by residual connections, layer normalization, and a position-wise feedforward network (FFN). These components together form a standard Transformer block. Since this work focuses on secure attention computation, we omit further details of these layers. C. Threat Model We consider the standard two-party secure inference setting consisting of a client and a server. The client holds a private input token matrix X, while the server possesses the parameters of a pretrained Transformer model, including the attention and feed-forward network weights. The goal of the protocol is to enable the server to evaluate the Transformer model on the client’s input without revealing the plaintext input to the server and without exposing the model parameters to the client. At the end of the protocol, the
client obtains the inference result, while neither party learns any additional information beyond what can be inferred from its prescribed inputs and outputs. Following prior works [1]–[5], [7], [16], [21], on secure Transformer inference, we assume an honest-but-curious (semi-honest) adversarial model. Both parties correctly follow the protocol specification but may attempt to infer additional information from the intermediate messages and protocol transcripts. The communication channels between the client and the server are assumed to be secure. D. Cryptographic Primitives 1) CKKS Homomorphic Encryption Scheme: We briefly review the CKKS approximate homomorphic encryption scheme, focusing on the implementation characteristics that are relevant to the following algorithms. Detailed descriptions of CKKS and its RNS variants can be found in [24], [25]. a) Plaintexts and Ciphertexts: CKKS is an RLWE-based homomorphic encryption scheme designed for approximate arithmetic over real or complex numbers. Let Rq = Zq [X]/(X N + 1) be the polynomial ring with ring degree N and ciphertext modulus q. A plaintext vector is encoded into a polynomial in the CKKS plaintext space, which can represent up to N/2 complex slots through SIMD-style packing. A scaling factor ∆ is used to control fixed-point precision. A ciphertext encrypting a plaintext message is represented as a tuple of polynomials over Rq . In the standard twocomponent form, a ciphertext is written as ct = (c0 , c1 ) ∈ Rq2 . Throughout this paper, the notation [[M]] denotes the CKKS ciphertext representation of a matrix M. Depending on the underlying plaintext packing strategy, [[M]] may consist of one ciphertext or a collection of ciphertexts. b) Homomorphic Addition and Multiplication: CKKS supports homomorphic addition and multiplication. In this paper, the symbols + and × are used at an abstract level and may correspond to different concrete operations depending on whether the operands are plaintexts or ciphertexts. Specifically, they may denote ciphertext-ciphertext operations, ciphertextplaintext operations, or plaintext operations that appear in a particular instantiation of the proposed algorithms. For example, a homomorphic matrix multiplication procedure may consist of ciphertext additions, ciphertext-plaintext multiplications, ciphertext-ciphertext multiplications, and plaintext additions or multiplications, depending on the adopted encoding layout and secure inference protocol. Homomorphic addition is relatively inexpensive and preserves the ciphertext size. Homomorphic multiplication is more costly. In particular, ciphertext-ciphertext multiplication increases the ciphertext size and is usually followed by relinearization to reduce the ciphertext back to its standard form. In CKKS, multiplication also increases the scale, and rescaling is applied to control the scale and modulus chain. These auxiliary procedures introduce non-negligible computational overhead.
4
c) Rotation and Relinearization: CKKS supports slot rotations, which cyclically shift the packed plaintext slots inside a ciphertext. Let m be a plaintext packed a vector m. The left rotation operation (σtl (m)) shifts the slots of m cyclically to the left by t positions, while the right rotation operation (σtr (m)) shifts the slots to the right by t positions. Unless otherwise specified, rotations in this paper refer to left rotations. In RLWE-based homomorphic encryption schemes, ciphertext rotations are implemented by applying a ring automorphism followed by a key-switching procedure. CKKS also employs relinearization after ciphertext-ciphertext multiplication to transform an enlarged ciphertext back to its standard form. Similar to rotation, relinearization is realized through key switching using a public evaluation key. Therefore, both ciphertext rotations and relinearization require key-switching operations and constitute fundamental components of CKKS homomorphic computation. 2) Additive Secret Sharing: We also use 2-out-of-2 additive secret sharing as a standard primitive in hybrid FHE-MPC secure inference protocols. For an input matrix X, the client and the server hold shares
the masked input X−U in the online phase, rather than the ciphertext [[X]]. However, subsequent computations, especially ciphertext attention operations such as [[QK⊤ ]] ⊤ √ [[V]], [[QK ]] and softmax d still require a large number of ciphertext-ciphertext multiplications and key-switching operations. In RLWE-based homomorphic encryption schemes, key switching is one of the dominant computational bottlenecks. To reduce the number of online key-switching operations, we introduce a preprocessing-assisted secure attention Algorithm 1.
X = hXic + hXis ,
X = U + (X − U),
where hXic is held by the client and hXis is held by the server. Individually, neither share reveals the plaintext input. Additive sharing is commonly used to switch between encrypted computation and secret-shared computation. Linear operations can be evaluated with FHE, while nonlinear functions such as softmax, normalization, activation functions, and comparisons can be handled by MPC protocols. In our algorithms, the random matrix U serves as an additive mask for the client input. During online inference, the value X − U may be obtained by the server either directly or through an MPC-based procedure, depending on the underlying secure inference scheme. As long as U is sampled independently and remains hidden from the server, revealing X − U does not disclose the plaintext input X. This masked value enables the server to combine plaintext-side computation with precomputed encrypted intermediate values, thereby reducing online ciphertext rotations and key-switching operations. IV. T WO -PARTY S ECURE I NFERENCE A LGORITHM FOR ATTENTION M ECHANISMS Existing two-party secure Transformer inference systems, such as NEXUS [16] and Euston [21], utilize preprocessing techniques based on column-packed matrix multiplication to compute encrypted linear projections using the following decomposition: [[XW]] = [[UW]] + (X − U)W, where U is a random masking matrix generated by client. This technique enables the first linear layer of the Transformer attention module, responsible for computing Q, K, and V, to be evaluated with zero ciphertext rotations during online inference. In addition, the client only needs to transmit
A. Preprocessing-Based Attention Decomposition To facilitate the decomposition of the attention computation, we define Qu = UWq ,
Ku = UWk ,
Vu = UWv ,
where Wq , Wk , and Wv denote the query, key, and value projection matrices of a single attention head. Using the additive decomposition
the attention score matrix can be expanded as follows: [[QK⊤ ]] = [[Qu ]] × [[K⊤ u ]]
+ [[Qu ]] × ((X − U)Wk )
⊤
(1)
+ (X − U)Wq × [[K⊤ u ]]
+ (X − U)Wq Wk⊤ (X − U)⊤ . The key observation is that the expensive ciphertextciphertext multiplication [[QK⊤ ]] is decomposed into several ciphertext multiplications and offline precomputable ciphertext transformations. Consequently, a significant portion of the costly key-switching operations can be moved into the preprocessing stage.
B. Correctness and Generality We clarify that the proposed attention decomposition in Eq. (1) is both correct and compatible with a broad range of RLWE-based secure attention computation schemes. a) Abstract Encoding Model: To avoid reliance on any particular packing strategy, an encoding layout is modeled as a mapping from a matrix to a collection of plaintext polynomials: P : M 7−→ p(M),
ℓ (M)
P p(M) ∈ ΛN,q
.
The plaintext ring associated with the underlying RLWE scheme is defined as ΛN,q = Zq [X]/(X N + 1), where ℓP (M) denotes the number of plaintext polynomials generated by the encoding layout P . Depending on the packing strategy, ℓP (M) may vary and is not restricted by our algorithms.
5
Different operands and outputs may adopt different encoding layouts: P ′ : M 7−→ p′ (M), Algorithm 1 Two-Party Secure Inference for Attention Mechanism Require: Random masking matrix U ∈ Rm×d generated by the client, input token matrix X ∈ Rm×d , and server(h) (h) (h) side single-head attention weights Wq , Wk , Wv ∈ d Rd× H , where h ∈ {1, 2, · · · , H}. Ensure: Encrypted attention output [[S5 ]]. 1: Offline Preprocessing Phase 2: The client and server jointly compute the encrypted masked projections: (h) [[Q(h) u ]] = [[UWq ]]
(h)
[[K(h) u ]] = [[UWk ]]
and
The encryption of the encoded plaintext collection p(M) is denoted by [[p(M)]]. A homomorphic ciphertext-matrix multiplication algorithm is represented as ϕ : [[p(A)]] × [[p′ (B)]] −→ [[p′′ (AB)]]. The output encoding layout P ′′ is assumed to preserve additive homomorphism: p′′ (A + B) = p′′ (A) + p′′ (B),
The resulting ciphertexts are held by the server. (h)⊤ [[S1 ]] = [[Q(h) ]]. u ]] × [[Ku
4: The server precomputes transformed ciphertext sets:
CQ ,
CK ,
CV .
5: Online Inference Phase 6: The client and server obtain
and K = UWk + (X − U)Wk = Ku + (X − U)Wk , we obtain ⊤ QK⊤ = Qu + (X − U)Wq Ku + (X − U)Wk .
Applying the distributive law of matrix multiplication yields
+ Qu (X − U)Wk
either via joint computation (as in MPC-based inference) or by the client directly sending it to the server (as in FHE-based inference). The resulting value is held by the server. 7: Using ciphertexts in CQ and CK , the server computes: (h)⊤
[[S2 ]] = [[Q(h) u ]]Wk
(X − U)⊤ ,
and [[S3 ]] = (X − U)Wq(h) [[K(h)⊤ ]]. u 8: The server computes:
[[Q(h) K(h)⊤ ]] = [[S1 ]] + [[S2 ]] + [[S3 ]] + S4 . 9: Securely compute
[[Q(h) K(h)⊤ ]] √ . d 10: Using ciphertexts in CV , the server computes: hh ii [[S5 ]] = [[sf tmx]] × Vu(h) + (X − U)Wv(h) . 11: return [[S5 ]]
Q = UWq + (X − U)Wq = Qu + (X − U)Wq
QK⊤ = Qu K⊤ u
X−U
[[sf tmx]] = softmax
(2)
which is satisfied by standard RLWE packing layouts used in secure inference systems. b) Correctness: From
[[Vu(h) ]] = [[UWv(h) ]]. 3: The server computes:
P ′′ : M 7−→ p′′ (M).
+ (X − U)Wq K⊤ u
⊤
(3)
+ (X − U)Wq Wk⊤ (X − U)⊤ , which is exactly Eq. (1). Therefore, the proposed decomposition is algebraically correct. c) Generality: Since Eq. (3) is a matrix-level identity, it is independent of the underlying ciphertext representation. Applying the encoding layout P ′′ to both sides and using the additive homomorphism of P ′′ and RLWE, we obtain [[p′′ (QK⊤ )]] = ϕ [[p(Qu )]], [[p′ (K⊤ )]] u ′ + ϕ [[p(Qu )]], p (Wk⊤ (X − U)⊤ ) (4) + ϕ p((X − U)Wq ), [[p′ (K⊤ u )]] + p′′ (X − U)Wq Wk⊤ (X − U)⊤ .
Therefore, due to the additive and multiplicative homomorphism of RLWE-based ciphertexts, any RLWE-based secure attention computation scheme can directly incorporate the proposed decomposition, provided that the ciphertext encoding layout P ′′ preserves additive homomorphism. In particular, Algorithm 1 can be instantiated within existing CKKS-based secure Transformer inference systems such as NEXUS, EUSTON, Arion, and BLB. Since the purpose of introducing P , P ′ , and P ′′ are solely to establish the packing-independent correctness of the proposed decomposition, we will omit these encoding maps in the remainder of this paper for notational
6
simplicity. Accordingly, unless otherwise specified, the notation [[M]] will denote the ciphertext representation of a matrix M using any compatible plaintext encoding layout (including P , P ′ , or P ′′ ) that satisfies Eq.( 2). C. Precomputed Ciphertext Transformation Sets To further reduce online latency, the server precomputes and stores transformed ciphertext variants derived from [[Qu ]],
[[Ku ]],
[[Vu ]].
Specifically, define: CQ = {[[Qu ]]1 , [[Qu ]]2 , . . . , [[Qu ]]n }, CK = {[[Ku ]]1 , [[Ku ]]2 , . . . , [[Ku ]]n′ }, and CV = {[[Vu ]]1 , [[Vu ]]2 , . . . , [[Vu ]]n′′ }. Each transformed ciphertext may involve preprocessing operations required by downstream inference, such as ciphertext rotations, plaintext masking, ciphertext additions, ciphertext multiplications, and other auxiliary transformations. These transformed ciphertexts are generated offline and reused during online inference, thereby significantly reducing the number of online key-switching operations. The parameters n, n′ , and n′′ are not fixed and can be adjusted according to the packing strategy and system requirements. D. Secure Attention Inference We present the complete two-party secure inference protocol for Transformer attention in Algorithm 1. For clarity, the superscript (h) denotes the quantities associated with the h-th attention head throughout this section. Define: S1 = Qu(h) K(h)⊤ , u ⊤ (h) S2 = Qu(h) (X − U)Wk , S3 = (X − U)Wq(h) K(h)⊤ , u (h)⊤
S4 = (X − U)Wq(h) Wk and S5 = softmax
(X − U)⊤ ,
Q(h) K(h)⊤ √ d
V(h) .
These five terms correspond to the decomposed attention computation used in Algorithm 1. Among them, the terms involving only preprocessed or reusable encrypted operands can be prepared before the online phase, while the remaining terms are evaluated during secure inference. In particular, the computation in Line 2 of Algorithm 1 can be realized using the preprocessing techniques provided by NEXUS or EUSTON. Alternatively, with Beaver triples, the client and the server can first obtain secret shares of the target matrix. The client then encrypts its share under its public key and sends the ciphertext to the server, who completes the preprocessing step by locally adding its own share in ciphertext form.
This preprocessing strategy reduces the online latency of ciphertext attention. Plaintext rotations incur negligible cost compared with ciphertext rotations, and expensive ciphertext multiplications requiring key-switching are completed during preprocessing. Moreover, many transformed ciphertexts derived from [[Qu ]] and [[K⊤ u ]], which are required by downstream operations, can be precomputed and stored in CQ and CK . This further reduces the online key-switching overhead. The evaluation of the softmax function is abstracted in Algorithm 1. Depending on the underlying instantiation, softmax can be implemented either homomorphically in a fully FHEbased system or through a secure client-server protocol in a hybrid FHE-MPC system. V. S TORAGE -C OMMUNICATION T RADE - OFF S TRATEGY While the preprocessing strategy outlined in Section IV shifts the online key-switching computations to the preprocessing phase, it introduces substantial storage overhead in ciphertext sets CQ , CK , and CV . As the sequence length m or the number of attention heads H increases, the memory footprint of these ciphertext sets can become prohibitive, creating a significant bottleneck for resource-constrained servers. In this section, building on the proposed attentioncomputation Algorithm 1, we introduce a storage– communication trade-off strategy that replaces a large portion of ciphertext storage with a small amount of online plaintext communication. Instead of precomputing and storing all rotated ciphertext variants, part of the required linear information is generated during online inference and protected by additive masks. This trade-off preserves the main benefit of the preprocessing method, namely reducing online key-switching operations, while lowering the storage cost of the precomputed ciphertext sets. We adapt this strategy to both FHE-based Transformer inference and hybrid MPC–FHE Transformer inference, as described in the following two subsections. A. Adaptation of the Storage-Communication Trade-off Strategy to FHE-Based Transformer Inference Under FHE-based transformer inference, we apply the storage–communication trade-off strategy introduced in Algorithm 2. Instead of storing all rotated ciphertexts in CQ and CK , the client receives masked intermediate values (h)⊤
Q(h) u Wk
− R(h) s
(h)
and Wq(h) K(h)⊤ − Rs′ u
during preprocessing. When the input X is available, the client computes the plaintext matrices B1 and B2 and sends them to the server, which then reconstructs the ciphertext results [[S2 ]] and [[S3 ]] using the encrypted masks. This strategy eliminates the need to store large ciphertext sets, replacing storage with a small amount of online plaintext communication per attention head. In non-interactive FHE-based inference, the Algorithm ( 1 or 2) are applied to the first Transformer layer. By removing online key switching in this layer, the method accelerates the most expensive homomorphic computations. For deep models such as GPT-2, GPT-3, or LLaMA, optimizing only the first
7
layer provides limited overall speedup, whereas for shallow models like BERT-tiny, the reduction in key switching can yield a distinct improvement. The algorithm can also be extended to later layers if interaction is allowed, for example when ciphertexts are refreshed or bootstrapping is avoided. In such cases, the same maskingbased decomposition can be applied iteratively across layers, though the practical benefit depends on the trade-off between additional interaction latency and the cost of storage. Algorithm 2 Trade-off Strategy for Computing [[S2 ]] and [[S3 ]] under FHE (h)
(h)
Require: [[Qu ]], [[Ku ]],Wq , Wk and U in Algorithm (h) (h) 1. Random masking matrix Rs ∈ Rm×d , Rs′ ∈ (h) (h) Rd×m , Rc ∈ Rm×m , Rc′ ∈ Rm×m . Input matrix X ∈ Rm×d and server-side single-head attention weights d (h) (h) (h) Wq , Wk , Wv ∈ Rd× H , where h ∈ {1, 2, · · · , H}. Ensure: [[S2 ]] and [[S3 ]]. 1: Offline Preprocessing Phase 2: Server compute (h)⊤
[[Q(h) u ]] × Wk
B. Adaptation of the Storage-Communication Trade-off Strategy to Hybrid FHE-MPC Transformer Inference To adapt the trade-off strategy in Algorithm 2 to the hybrid FHE-MPC setting, we modify the preprocessing and online procedures while preserving the idea of replacing ciphertext transformation sets with online communication. Algorithm 3 extends the trade-off strategy of Algorithm 2. Instead of storing the ciphertext transformation sets CQ and CK required by Algorithm 1, the approach introduces masked intermediate values and encrypted correction terms during preprocessing. In the online phase, the server reconstructs [[S2 ]] and [[S3 ]] using the secret-sharing representation of X and the plaintext matrices E and F transmitted by the client. As a result, the storage overhead of CQ and CK is removed. A similar strategy applies to the computation of [[S5 ]]. Let the output of the Softmax operation be represented by secret shares hX′ ic and hX′ is , and let U′ be a random masking matrix generated during preprocessing. The ciphertext [[S5 ]] can be decomposed as [[S5 ]] = [[U′ ]][[Vu(h) ]]
− R(h) s
and
+ [[U′ ]](X − U)Wv(h) + (X′ − U′ )[[Vu(h) ]]
(h)
Wq(h) × [[K(h)⊤ ]] − Rs′ , u
+ (X′ − U′ )(X − U)Wv(h) .
then send them to client.
Let ′
3: Client decrypt ciphertext (h)⊤
[[Q(h) u × Wk
S5 = [[U′ ]](X − U)Wv(h) ,
− R(h) s ]]
and
and ′′
S5 = (X′ − U′ )[[Vu(h) ]].
(h)
− Rs′ ]], [[Wq(h) × K(h)⊤ u
′
then encrypt R(h) c
(h)
and Rc′
and send
(h)
[[R(h) c ]] and [[Rc′ ]] to server. 4: Online Inference Phase 5: The client send
X−U and (h)⊤
B1 = (Q(h) u × Wk
⊤ (h) − R(h) s ) × (X − U) − Rc
and (h)
to server 6: Server obtain ⊤ (h) [[S2 ]] = B1 + R(h) s × (X − U) + [[Rc ]]
and (h)
(h)
[[S3 ]] = B2 + (X − U) × Rs′ + [[Rc′ ]]
′′
The mixed terms S5 and S5 require the ciphertext transformation set CV in the original design. Algorithm 4 follows the same trade-off principle as Algorithm 3. With masking and correction terms generated during preprocessing, the server ′ ′′ reconstructs S5 and S5 during online inference using the plaintext matrices J and P transmitted by the client. Thus, the storage overhead of CV is replaced by the communication of J and P. Overall, Algorithms 3 and 4 extend the strategy of Algorithm 2 to the hybrid FHE-MPC setting. The ciphertext transformation sets CQ , CK , and CV are no longer required. Their storage overhead is exchanged for additional online communication incurred by transmitting the plaintext matrices E, F, J, and P, while Algorithms 3 and 4 preserve the same number of online key-switching operations.
(h)
B2 = (X − U) × (Wq(h) × K(h)⊤ − Rs′ ) − Rc′ u
7: return [[S2 ]] and [[S3 ]]
(5)
C. Security Analysis We analyze the privacy of the trade-off protocols in Algorithms 3 and 4 in the standard two-party semi-honest model using a real/ideal world simulation paradigm. The goal is to show that neither the client nor the server learns additional information beyond what is revealed by the protocol outputs. 1) Preliminaries and Notation: Let FHE denote a RLWEbased encryption scheme with IND-CPA security. Let the client’s input be X and U in the FHE-only case, or a secret share hXic in the hybrid MPC case. Let the server hold model
8
′
Algorithm 3 Trade-off Strategy for Computing [[S2 ]] and [[S3 ]] under hybrid FHE-MPC setting (h)
(h)
Require: [[Qu ]], [[Ku ]],Wq , Wk and U in Algorithm 1. (h) Random masking matrix Rt ∈ Rm×d , Rs ∈ Rm×d , (h) (h) (h) d×m m×m Rs′ ∈ R , Rc ∈ R , Rc′ ∈ Rm×m . m×d Input matrix X ∈ R and server-side single-head d (h) (h) (h) attention weights Wq , Wk , Wv ∈ Rd× H , where h ∈ {1, 2, · · · , H}. Ensure: [[S2 ]] and [[S3 ]]. 1: Offline Preprocessing Phase 2: Server compute (h)⊤
[[Q(h) u ]] × Wk and
(h)
(h) [[G]] = [[U′ ]] × (Rt Wv(h) ) + [[R̂(h) c ]] × Wv
and
(h)
[[Z]] = R̂t × [[Vu(h) ]] + [[R̂c′ ]] (h)
4: Server computes and sends [[Vu
then send them to client. 3: Client decrypt ciphertext
decrypt it after reception. (h)⊤
[[Q(h) u × Wk
(h)
− R̂s ]] to client, client
5: Online Inference Phase 6: The client adds the mask matrix −U′ to its secret share
− R(h) s ]]
and
hX′ ic , while the server adds the mask matrix −R̂t to its secret share hX′ is . Both parties then simultaneously send their masked shares to each other. 7: Client computes and sends
(h)
− Rs′ ]], [[Wq(h) × K(h)⊤ u then encrypt and send
(h)
Require: [[Vu ]], (X − U − Rt ), Wv and Rt in Algo(h) rithm 3 and Algorithm 1. Random masking matrix R̂c ∈ (h) m×d m×m m×d ′ m×m , R̂t ∈ R , R , U ∈ R , R̂s ∈ R d (h) R̂c′ ∈ Rm× H . Attention mechanism input matrix X ∈ Rm×d and the output X′ ∈ Rm×m of Softmax function. ′ ′′ Ensure: [[S5 ]] and [[S5 ]]. 1: Offline Preprocessing Phase (h) (h) and R̂c′ , then send [[U′ ]], 2: Client encrypt U′ , R̂c (h) (h) [[R̂c ]] and [[R̂c′ ]] to server. 3: Server computes
− R(h) s
(h) Wq(h) × [[K(h)⊤ ]] − Rs′ , u
R(h) c
Algorithm 4 Trade-off Strategy for Computing [[S5 ]] and ′′ [[S5 ]] under hybrid FHE-MPC setting
(h)
and Rc′
J = U′ × (X − U − Rt ) − R̂(h) c and
(h)
[[R(h) c ]] and [[Rc′ ]]
(h)
P = (X′ − U′ − R̂t ) × (Vu(h) − R̂(h) s ) − R̂c′
to server. 4: Server compute
to server.
(h)⊤ ⊤ (h) [[D]] = [[Q(h) − R(h) u × Wk s ]] × Rt + [[Rc ]]
8: Server obtain
[[S′ 5 ]] = [[G]] + J × Wv(h)
and (h)
and
(h)
[[D′ ]] = Rt × [[Wq(h) × K(h)⊤ − Rs′ ]] + [[Rc′ ]] u
[[S′′ 5 ]] = [[Z]] + P + (X′ − U′ − R̂t ) × R̂(h) s
5: Online Inference Phase 6: The client adds the mask matrix −U to its secret share
hXic , while the server adds the mask matrix −Rt to its secret share hXis . Both parties then simultaneously send their masked shares to each other. 7: Client computes and sends (h)⊤
E = (Q(h) u × Wk
⊤ (h) − R(h) s ) × (X − U − Rt ) − Rc
and (h)
(h)
F = (X − U − Rt ) × (Wq(h) × K(h)⊤ − Rs′ ) − Rc′ u to server. 8: Server obtain ⊤ [[S2 ]] = [[D]] + E + R(h) s × (X − U)
and
parameters Wq , Wk , Wv and RLWE-encrypted precomputed matrices [[Qu ]], [[Ku ]], [[Vu ]] encrypted by client’s public key. We define the view of a party as follows: viewC (client view): the client’s input, random masks, and all messages received from the server. • viewS (server view): the server’s input, random masks, and all messages received from the client. •
2) Ideal World Execution: In the ideal world, a trusted party F computes the outputs: [[S2 ]], [[S3 ]], [[S′5 ]], [[S′′5 ]]
(h)
[[S3 ]] = [[D′ ]] + F + (X − U) × Rs′ 9: return [[S2 ]] and [[S3 ]]
9: return [[S′ 5 ]] and [[S′′ 5 ]]
and returns to each party only the authorized output. No other information is leaked. 3) Real World Execution: In the real world, the parties execute the protocols in Algorithms 2, 3 or 4. All sensitive
9
matrices are either encrypted under RLWE ([[·]]) or masked by independent random matrices. Specifically: • In the FHE-only trade-off protocol (Algorithm 2), the server receives X − U, B1 , and B2 in the online phase, (h) (h) where B1 and B2 are masked by Rc , Rc′ and U. The client only decrypts masked intermediate values protected (h) (h) by Rs and Rs′ , and therefore does not learn the unmasked server-side matrices. • In the hybrid MPC protocol (Algorithms 3), both parties exchange masked shares of secret inputs. Each share is masked by independently sampled matrices (Rt , Rs , Rc , . . . ). • In the softmax hybrid protocol (Algorithms 4), similar masked shares and RLWE-encrypted matrices are exchanged. 4) Simulator Construction: We construct simulators for the semi-honest parties to show that the real-world views are computationally indistinguishable from ideal-world views. a) Server Simulator SimS : • Sample random RLWE ciphertexts with the same dimensions as the real encrypted matrices [[Qu ]], [[Ku ]], [[Vu ]]. • Sample random matrices with the same dimensions as all masked client messages (B1 , B2 , E, F, J, P ) from uniform distributions over the appropriate domains. sim • Output these as the simulated server view viewS . b) Client Simulator SimC : • Sample random masked shares or RLWE ciphertexts of the same dimensions as those received from the server (e.g., [[Qu Wk⊤ −Rs ]], [[Wq K⊤ u −Rs′ ]], and the softmax masked shares). sim • Output these as the simulated client view viewC . 5) Indistinguishability Argument: • By the IND-CPA security of RLWE encryption, any RLWE ciphertext in the real protocol is computationally indistinguishable from a ciphertext encrypting a random matrix. • By the statistical independence and uniform randomness of the additive masks, any masked linear combination of inputs or secret shares is statistically independent of the underlying private data. Therefore, for both the client and the server, the simulated view viewsim is computationally indistinguishable from the real-world view view: sim viewreal C ≈c viewC ,
sim viewreal S ≈c viewS .
6) Security: This simulation argument applies uniformly to all three algorithms: FHE-only for [[S2 ]] and [[S3 ]], hybrid FHE-MPC for [[S2 ]] and [[S3 ]], and softmax MPC-CKKS for [[S′5 ]], [[S′′5 ]]. Hence, under the standard semi-honest model and the IND-CPA assumption of RLWE, the protocols securely compute the desired outputs without leaking any additional information about either party’s private inputs. VI. F USED R ELINEARIZATION AND ROTATION The previous two sections introduced preprocessing-based techniques that shift ciphertext matrix multiplications in Transformer attention from the online phase to preprocessing,
thereby reducing the online computation cost in two-party secure inference. These techniques can be applied to all Transformer layers in hybrid FHE-MPC systems and to the first layer in fully FHE-based systems. However, ciphertext matrix multiplications remain unavoidable in two important cases: (i) the preprocessing phase itself, where these computations are performed in advance, and (ii) the subsequent layers of fully FHE-based systems, where the proposed preprocessing techniques are not directly applicable. This motivates a deeper optimization of the underlying ciphertext matrix multiplication primitive itself. In this section, we present a fused key-switching optimization that reduces the cost of ciphertext multiplication followed by rotation, a common computation pattern in secure Transformer inference systems such as BOLT [4], THOR [5], BLB [3], and ARION [2]. This optimization is independent of the proposed attention-computation algorithms and can be directly integrated into existing systems. When instantiated together with our preprocessing-based methods, it further accelerates ciphertext matrix multiplications in both preprocessing and online inference. A. Key-Switching Pipelines
Overhead
in
Multiplication-Rotation
In CKKS, ciphertext-ciphertext multiplication of ct = (c0 , c1 ) = Enc(m),
ct′ = (c′0 , c′1 ) = Enc(m′ )
produces a degree-two ciphertext (d0 , d1 , d2 ) = (c0 c′0 , c0 c′1 + c1 c′0 , c1 c′1 ), which decrypts as d0 + d1 s + d2 s2 . A conventional implementation first relinearizes this ciphertext: d0 + d1 s + d2 s2 −→ d¯0 + d¯1 s ≈ mm′ . If a rotation by t slots is then required, the implementation applies the automorphism σt (rotation left or right): (σt (d¯0 ), σt (d¯1 )). This ciphertext is encrypted under the rotated secret key τ = σt (s). Therefore, another key-switching operation is required: σt (d¯0 ) + σt (d¯1 )τ −→ c′′0 + c′′1 s ≈ σt (mm′ ). Thus, multiplication followed by rotation normally invokes two key-switching procedures: one for relinearization and one for rotation. Each key-switching operation consists of four main steps: ModUp, multiplication with the evaluation key (MulEvk), ModDown, and addition in RNS-CKKS [25]. Since polynomial multiplication is most efficiently performed in the NTT domain, ciphertext multiplications are typically maintained in the NTT representation throughout the computation. Consequently, both ModUp and ModDown involve NTT and
10
inverse NTT (INTT) transformations. Furthermore, these two steps require basis conversion between different RNS bases, making them among the most expensive components of the key-switching procedure [26]. The key idea of our fused method is to postpone relinearization until after the automorphism operation. Instead of performing separate key-switching procedures, we directly transform the ciphertext encrypted under the secret-key τ and τ 2 back to the original secret key s through a single fused key-switching pipeline.
Algorithm 5 Fused Relinearization and Rotation Require: ciphertexts RN SC (ct) and RN SC (ct′ ), C is a basis consisting of l + 1 primes. Require: Rotation step t and fused evaluation key (i) (i) evkfused = evkτ(i)→s , evkτ 2 →s , τ = σt (s)
Ensure: Ciphertext encrypting Rott (ct · ct′ ) 1: Compute the degree-two product:
RN SC (d0 , d1 , d2 ) ← RN SC (c0 c′0 , c0 c′1 + c1 c′0 , c1 c′1 ). 2: Rescale without NTT:
B. Formulation
RN SC (d˜0 , d˜1 , d˜2 ) ← Rescale(d0 , d1 , d2 )
After multiplication and rescaling, let
One prime is removed from C.
(d˜0 , d˜1 , d˜2 )
3: Apply automorphism:
be the degree-two ciphertext at the target scale and modulus level. Applying the automorphism σt gives (dˆ0 , dˆ1 , dˆ2 ) = (σt (d˜0 ), σt (d˜1 ), σt (d˜2 )).
RN SC (σt (d˜0 ), σt (d˜1 ), σt (d˜2 )) ← RN SC (d˜0 , d˜1 , d˜2 ). 4: ModUp:
RN SD (dˆ1 ) ← RN SC (σt (d˜1 )).
This ciphertext decrypts under (1, τ, τ 2 ),
RN SD (dˆ2 ) ← RN SC (σt (d˜2 )).
τ = σt (s),
because σt (d˜0 + d˜1 s + d˜2 s2 ) = dˆ0 + dˆ1 τ + dˆ2 τ 2 . The goal is to produce a standard CKKS ciphertext under the original secret key s: ctout = (c′′0 , c′′1 ),
c′′0 + c′′1 s ≈ dˆ0 + dˆ1 τ + dˆ2 τ 2 .
ˇ 5: Initialize empty ciphertext RN SD (ct). 6: for i = 0, . . . , k + l − 1 do 7:
MulEvk:
ˆ(i) (i) ˇ (i) = dˆ1(i) evk(i) ct τ →s + d2 evkτ 2 →s . 8: end for 9: Perform a single ModDown:
ˇ ← RN SD (ct). ˇ RN SC (ct)
This can be achieved if we have evaluation keys for both mappings: τ → s, τ 2 → s.
10: Output
Instead of applying two separate key switches, we define a fused evaluation key
11: return RN SC (ctout )
(i)
ˇ RN SC (ctout ) = RN SC (σt (d˜0 ), 0) + RN SC (ct).
(i)
evkfused = {evkτ(i)→s , evkτ 2 →s } i = 0, 1, · · · , k + l − 1. The RNS (Residue Number System) decomposition [25] of dˆ1 and dˆ2 is given by (0)
(1)
(k+l−1)
}D ,
(0)
(1)
(k+l−1)
}D ,
RN SD (dˆ1 ) = {dˆ1 , dˆ1 , · · · , dˆ1
RN SD (dˆ2 ) = {dˆ2 , dˆ2 , · · · , dˆ2
where D is a basis consisting of k + l primes. Then, the ciphertext-evk (evaluation key) multiplication is given by: ˇ (i) = dˆ1(i) evkτ(i)→s + dˆ2(i) evk(i)2 . ct τ →s ˇ = (ct ˇ 0 , ct ˇ 1 ) satisfyAfter one ModDown stage, ciphertext ct ing ˇ 0 + ct ˇ 1 s ≈ dˆ1 τ + dˆ2 τ 2 . ct The final ciphertext is ˇ 0 , ct ˇ 1 ), ctout = (dˆ0 + ct which decrypts to ˇ 0 + ct ˇ 1 s ≈ dˆ0 + dˆ1 τ + dˆ2 τ 2 . dˆ0 + ct
Therefore, the fused procedure jointly performs ciphertext multiplication and rotation while requiring only a single ModDown stage. The complete procedure is summarized in Algorithm 5. It is worth noting that, in RNS-CKKS, ciphertexts are represented and manipulated in their RNS-decomposed form throughout the computation. C. Correctness We denote by KSa→s (x) the key-switching operation that transforms the ciphertext component x, associated with the secret-key a, into an equivalent component under the standard secret key s. In conventional CKKS, the multiplication-thenrotation operation is equivalent to KSτ →s (σt (KSs2 →s (d2 ) + d0 + d1 s)) . By contrast, the fused procedure computes dˆ0 + KSτ →s (dˆ1 ) + KSτ 2 →s (dˆ2 ).
11
Since key switching is linear in the decomposed input component, we have KSτ →s (dˆ1 ) + KSτ 2 →s (dˆ2 ) = KSfused (dˆ1 , dˆ2 ). Thus, the fused procedure preserves the correctness of standard CKKS key switching. D. Cost Advantage A conventional multiplication followed by rotation requires approximately 2ModUp + 2MulEvk + 2ModDown, ignoring low-cost automorphism and addition operations. The fused procedure requires 2ModUp + 2MulEvk + ModDown. Therefore, one ModDown stage is eliminated. VII. E VALUATION To demonstrate the effectiveness of the proposed algorithms, we compare existing secure Transformer inference schemes with their counterparts after incorporating our algorithms. Specifically, we consider two representative schemes: Arion, a FHE-based secure inference scheme, and BLB, a hybrid FHEMPC secure inference scheme. For each scheme, we evaluate three variants. The original schemes are denoted by Arion and BLB. Arion(1) and BLB(1) denote the schemes after integrating the secure attention computation in Algorithm 1. Arion(2) denotes the FHE-based storage–communication trade-off strategy in Algorithm 2, while BLB(2) denotes the hybrid FHEMPC trade-off strategies in Algorithms 3 and 4. Table II summarizes the impact of the proposed algorithms on key-switching operations, preprocessing storage overhead, and online communication costs for the three major computations in the attention mechanism. For Arion, we apply Algorithm 1 only to the first Transformer layer during inference and do not use the baby-step giant-step method adopted in the original Arion design. For BLB, before integrating our algorithms, we adjust the position of the MPC-to-CKKS conversion protocol so that the data representation matches the inputs required by our secure attention computation. For the Q/K/V projection stage, the online key-switching operations required by the original BLB scheme, are completely eliminated. The projection matrices are instead generated through the masked preprocessing procedure described in Algorithm 1. Since Arion already performs this computation without online key switching, the algorithm does not introduce additional overhead in this stage. The largest improvements are observed in the computation of attention scores. For the original Arion scheme, evaluating Q(h) (K (h) )⊤ requires 1536 key-switching operations. After applying Algorithm 1, all of these operations are removed by precomputing ciphertext transformation sets during preprocessing. However, this optimization introduces a storage overhead of 8384 ciphertexts. Algorithm 2 further reduces this storage requirement to only 384 ciphertexts by replacing transformed ciphertexts with the online transmission of the
auxiliary values B1 and B2 . A similar trend can be observed for BLB. The original scheme requires 346 key-switching operations, which are reduced to 256 by Algorithm 1 and completely eliminated by Algorithm 3. At the same time, the preprocessing storage overhead decreases from 50 ciphertexts to only 6 ciphertexts, with the additional communication of E and F during online inference. The value aggregation stage exhibits similar behavior. For Arion, the original implementation requires 2432 keyswitching operations, while Algorithm 1 reduces this number to 64. These remaining operations are associated with ciphertext transformations required for the value matrix. In the hybrid BLB scheme, the original 128 key-switching operations are completely removed. Furthermore, Algorithm 4 reduces the preprocessing storage requirement from 257 ciphertexts to only 3 ciphertexts by replacing the stored transformed ciphertexts with the online transmission of J and P. Overall, the results demonstrate two important advantages of the proposed algorithms. First, the algorithms significantly reduces or completely eliminates online key-switching operations, which are among the most expensive operations in RLWE-based secure inference systems. Second, the proposed storage–communication trade-off strategies substantially reduce the preprocessing storage overhead introduced by ciphertext transformation sets. For both FHE and hybrid FHEMPC schemes, large transformed ciphertext collections can be replaced with a modest amount of additional online communication. Therefore, our method provides a flexible mechanism for balancing computation, storage, and communication costs according to different deployment requirements while preserving the low-latency characteristics of online secure Transformer inference. VIII. C ONCLUSION This paper presented a preprocessing-assisted method for secure attention computation in two-party Transformer inference. Unlike existing approaches that are tightly coupled with specific plaintext packing layouts, our method operates at the attention-computation level and is compatible with a broad range of RLWE-based packing strategies. By decomposing attention into precomputable ciphertext components and online ciphertext–plaintext operations, our method reduces the key switching overhead during online inference, which is one of the main bottlenecks in RLWEbased secure Transformer inference. We also proposed a fused relinearization-and-rotation algorithm for the multiplicationfollowed-by-rotation pattern commonly found in CKKS-based ciphertext matrix computations, further reducing the cost of this frequent operation without modifying existing packing strategies. The proposed method can be applied to both FHE-based and hybrid FHE–MPC secure Transformer inference. In noninteractive FHE-based inference, our algorithms can be incorporated into the first Transformer layer, while in hybrid FHE– MPC inference, they can be extended to all layers. Although preprocessing may introduce additional storage requirements, the storage–communication trade-offs discussed in this paper provide practical mechanisms for mitigating this overhead.
12
TABLE II E FFECTS OF THE PROPOSED TECHNIQUES ON KEY- SWITCHING OPERATIONS , PREPROCESSING STORAGE , AND ONLINE COMMUNICATION IN BLB AND A RION .
Operation
Q/K/V Projection (h) {XW∗ }h∈[H] m×n X ∈R n W∗ ∈ Rn× H ∗ = Q, K, V
Scheme
Slot
Key Switch
Ciphertext Storage in Preprocess Stage
Data Traffic(online)
Arion
215
0
0
X−U
Arion(1)
15
0
0
0
15
0
0
0
BLB
14
2
192
0
[[hX − Uiqc ]]
BLB(1)
214
0
0
0
BLB(2)
14
2
0
0
0
Arion
215
1536
0
0
Arion(1)
15
0
8384
X−U
15
0
384
X − U, B1 , B2
14
346
0
0
BLB(1)
14
2
256
50
hXic − U
BLB(2)
214
0
6
hXic − U, E, F
Arion
215
2432
0
0
Arion(1)
15
64
8192
Arion(2)
Attention Scores {Q(h) (K (h) )⊺ }h∈[H] n Q(h) ∈ Rm× nH (h) m× H K ∈R
Arion(2) BLB
Value Aggregation σ = sof tmax {σ(Q(h) (K (h) )⊺ )V (h) }h∈[H] σ(Q(h) (K (h) )⊺ ) ∈ Rm×m n V (h) ∈ Rm× H
2 2
2 2 2
2
0
14
128
0
[[hX − U′ ic ]]
BLB(1)
14
2
0
257
hX′ ic − U′
BLB(2)
214
0
3
hX′ ic − U′ , J, P
BLB
2
Overall, our method reduces latency-critical cryptographic operations while preserving compatibility with existing secure Transformer inference systems. This packing-independent reduction of inference-phase key switching overhead provides a complementary direction for improving the practicality of privacy-preserving Transformer inference. R EFERENCES [1] Dongjin Park, Eunsang Lee, and Joon-Woo Lee. Powerformer: Efficient and high-accuracy privacy-preserving language model with homomorphic encryption. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), pages 11090–11111, 2025. [2] Linhan Yang, Jingwei Chen, Wangchen Dai, Shuai Wang, Wenyuan Wu, and Yong Feng. ARION: Attention-optimized transformer inference on encrypted data. Cryptology ePrint Archive, Paper 2025/2271, 2025. [3] Tianshi Xu, Wen-jie Lu, Jiangrui Yu, Yi Chen, Chenqi Lin, Runsheng Wang, and Meng Li. Breaking the layer barrier: remodeling private transformer inference with hybrid CKKS and MPC. In Proceedings of the USENIX Security Symposium, pages 1–12, 2025. [4] Qi Pang, Jinhao Zhu, Helen Möllering, Wenting Zheng, and Thomas Schneider. BOLT: Privacy-preserving, accurate and efficient inference for transformers. In Proceedings of the IEEE Symposium on Security and Privacy (SP), pages 4753–4771, 2024. [5] Jungho Moon, Dongwoo Yoo, Xiaoqian Jiang, and Miran Kim. THOR: Secure transformer inference with homomorphic encryption. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 3765–3779. ACM, 2025. [6] Meng Hao, Hongwei Li, Hanxiao Chen, Pengzhi Xing, Guowen Xu, and Tianwei Zhang. Iron: Private inference on transformers. In Advances in Neural Information Processing Systems (NeurIPS), pages 15718–15731, 2022.
′
[7] Linru Zhang, Xiangning Wang, Jun Jie Sim, Zhicong Huang, Jiahao Zhong, Huaxiong Wang, Pu Duan, and Kwok-Yan Lam. MOAI: Module-optimizing architecture for non-interactive secure transformer inference. In The Fourteenth International Conference on Learning Representations, 2026. [8] Payman Mohassel and Yupeng Zhang. Secureml: A system for scalable privacy-preserving machine learning. In Proceedings of the IEEE Symposium on Security and Privacy (SP), pages 19–38, 2017. [9] Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In Proceedings of the International Conference on Machine Learning (ICML), pages 201–210, 2016. [10] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 308–318, 2016. [11] Florian Tramèr and Dan Boneh. Slalom: Fast, verifiable and private execution of neural networks in trusted enclaves. In Proceedings of the International Conference on Learning Representations (ICLR), pages 1–13, 2019. [12] Arpita Patra, Thomas Schneider, Ajith Suresh, and Hossein Yalame. ABY2.0: Improved mixed-protocol secure two-party computation. In Proceedings of the USENIX Security Symposium, pages 2165–2182, 2021. [13] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pages 169–178. ACM, 2009. [14] Dacheng Li, Hongyi Wang, Rulin Shao, Han Guo, Eric Xing, and Hao Zhang. MPCFORMER: Fast, performant and private transformer inference with MPC. In Proceedings of the International Conference on Learning Representations (ICLR), pages 1–10, 2023. [15] Wenyuan Zeng, Meng Li, Wenjie Xiong, Wen Jie Lu, Jin Tan, Runsheng Wang, and Ru Huang. MPCViT: Searching for MPC-
13
friendly vision transformer with heterogeneous attention. arXiv preprint arXiv:2211.13955, pages 1–9, 2022. [16] Jiawen Zhang, Xinpeng Yang, Lipeng He, Kejia Chen, Wen jie Lu, Yinghao Wang, Xiaoyang Hou, Jian Liu, Kui Ren, and Xiaohu Yang. Secure transformer inference made non-interactive. In Proceedings of the Network and Distributed System Security Symposium (NDSS), pages 1–16, 2024. [17] Itamar Zimerman, Moran Baruch, Nir Drucker, Gilad Ezov, Omri Soceanu, and Lior Wolf. Converting transformers to polynomial form for secure inference over homomorphic encryption. In Proceedings of the International Conference on Machine Learning (ICML), pages 1–13, 2024. [18] Itamar Zimerman, Allon Adir, Ehud Aharoni, Matan Avitan, Moran Baruch, Nir Drucker, Jenny Lerner, Ramy Masalha, Reut Meiri, and Omri Soceanu. Power-softmax: Towards secure LLM inference over encrypted data. arXiv preprint arXiv:2410.09457, pages 1–11, 2024. [19] Lorenzo Rovida and Alberto Leporati. Transformer-based language models and homomorphic encryption: An intersection with BERT-tiny. In Proceedings of the ACM International Workshop on Security and Privacy Analytics (IWSPA), pages 3–13. ACM, 2024. [20] Lawrence Lim, Vikas Kalagi, Divyakant Agrawal, and Amr El Abbadi. Tricycle: Private transformer inference with tricyclic encodings. Cryptology ePrint Archive, Paper 2025/1200, 2025. [21] Xinwen Gao, Shaojing Fu, Lin Liu, Zhuotao Liu, Yuchuan Luo, and Yongjun Wang. Euston: Efficient and user-friendly secure transformer inference with non-interactivity. Cryptology ePrint Archive, Paper 2026/046, 2026. [22] Yufan Zhu, Chao Jin, Khin Mi Mi Aung, and Xiaokui Xiao. Encformer: Secure and efficient transformer inference over encrypted data, 2026. [23] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems (NeurIPS), pages 2–8, 2017. [24] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In Advances in Cryptology – ASIACRYPT, pages 409–437. Springer, 2017. [25] Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. A full RNS variant of approximate homomorphic encryption. In Carlos Cid and Michael J. Jacobson Jr., editors, Selected Areas in Cryptography – SAC 2018, pages 347–368. Springer International Publishing, 2019. [26] Jean-Philippe Bossuat, Christian Mouchet, Juan Troncoso-Pastoriza, and Jean-Pierre Hubaux. Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 587–617. Springer, 2021.