Encryption-Friendly LLM Architecture
Authors: Donghwan Rho
Taeseong Kim
Minje Park
Jung Woo Kim
Hyunsik Chae
Ernest K. Ryu
Jung Hee Cheon
Venue: ICLR 2025 Poster (2025)
Keywords: Homomorphic Encryption
PPML
Encrypted Fine-tuning
Transformer Architecture
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Large language models (LLMs) offer personalized responses based on user interactions, but this use case raises serious privacy concerns. Homomorphic encryption (HE) is a cryptographic protocol supporting arithmetic computations in encrypted states and provides a potential solution for privacy-preserving machine learning (PPML). However, the computational intensity of transformers poses challenges for applying HE to LLMs. In this work, we propose a modified HE-friendly transformer architecture with an emphasis on inference following personalized (private) fine-tuning. Utilizing LoRA fine-tuning and Gaussian kernels, we achieve significant computational speedups---6.94$\times$ for fine-tuning and 2.3$\times$ for inference---while maintaining performance comparable to plaintext models. Our findings provide a viable proof of concept for offering privacy-preserving LLM services in areas where data protection is crucial. Our code is available on GitHub.

Published as a conference paper at ICLR 2025
ENCRYPTION-FRIENDEE LLM ARCHITECTURE
Donghwan Rho', Taeseong Kim ' Minje Park2, Jung Woo Kim², Hyunsik Chae', Ernest K. RyuSt, Jung Hee Cheon 121
'Seoul National University, Department of Mathematical Sciences
{ dongwhan__ro, kts1023. hsc1403, jhcheon e@nu ac kr
#CryptoLab Inc,
mmnnje, jungwoo. kim Jecryptolab. co.ke 'UCLA, Department of Mathematics eryu@math. ucla. edu
ABSTRACT
Large language models (LLMs) offer personalized responses based on user interac- tions, but this case raises serious privacy concerns. Homomorphic eneryption (HE) is a cryptographic protocol supporting arithmetic computations in encrypted states and provides potential solution for preseering machine learning (PPML). However, the computational intensity of transformers poses challenges for applying HE LLMs. this work, we propose a modified HE-friendly transformer architecture with an emphasis on inference following personalized (private) fine- tuning. Utilizing LoRA fine-tuning and Gaussian kernels, we achieve significant computational speedups-6.99 6.94x for fine-tuning and 2.3x for inference- while maintaining performance comparable plaintext models. Our findings provide viable proof of concept for offering peeeeeeippeeiiggggg LLM services in areas where data protection is crucial. Our code is available on GitHub'.
INTRODUCTION
The advent of large language models (LLMs) such as the BERT series (Devlin et al., 2019; Liu et al., 2019; Sanh et al., 2019; Lan et al., 2020; Clark al., 2020; He et al., 2021), the GPT series (Radford, 2018; Radford et al., 2019; Tom B. Brown et al., 2020; OpenAI, 2023), and ChatGPT (OpenAI, 2024) kick-started a new of natural language processing (NLP) and artificial intelligence (AI). One of the many capabilities of LLMs that has received much attention is their ability to provide personalized responses based on user interactions, especially with the use of fine-tuning. However, this use case raises serious concerns about user privacy. In response, regulations such as the GDPR (European Union, 2016) and CCPA (State of California, 2018) have been amended. In Italy, ChatGPT was even temporarily banned (McCallum, 2023), and several major corporations, including Apple and Samsung, have restricted use within their companies (Mok, 2023).
Privacy-preservin machine learning (PPML) refers to methods that use machine learning while protecting data privacy. Techniques for PPML include secure multi-party computation (MPC) (Yao, 1982). differential privacy (Dwork, 2006), and homomorphic encryption (HE) (Rivest et al., 1978; Gentry, 2009). Among these, only MPC and HE offer provable security based on cryptographic assumptions. MPC utilizes communications between parties, but these communications can make challenging to accelerate and parallelize the heavy computation of neural networks. In contrast, HE supports arithmetic computations in encrypted states without requiring communications. Since the pioneering work of Gentry (2009), several HE schemes have been developed (Brakerski, 2012: Brakerski al., 2014; 4; Ducas & Micciancio, 2015; Chillotti al., 2016; Cheon et al., 2017). Notably, the CKKS (Cheon et al., 2017) scheme is particularly efficient for evaluating large-scale real-valued (as opposed integer-valued) data parallel and widely used in the PPML literature (Han et al., 2019; Lee et al.. 2022a;b;e; 2023b).
" "Equal contribution. Order determined coin 1 Co-senioo authors. 'htpps:/ / / thub. com/ www..////w/wwooooooooooooo Rho/ hwwpaa/wwwww///eeetttto/oooooooe oneryption--riieeeee iir.

---

Published as a conference paper at ICLR 2025
In theory, homomorphic encryption (HE) presents elegant solution to the privacy concerns associ- ated with LLMs. However, despite the significant recent progress in the theory and implementation of HE operations, protecting LLMs with HE remains challenge due to their computational scale. Transformer models (Vaswani et al., 2017) famously rely on numerous matrix multiplications and various non-polynomial operations, and directly adapting these operations to HE results in significant computation time and precision loss.
In this work, we propose modified HE-friendly transformer architecture with an emphasis infer- ence following personalized (private) fine-tuning. We point out that prior work on homomorphically encrypted transformers often overlooked fine-tuning due to complexity. Our approach has two main algorithmic components: LoRA (Hu et al., 2022) fine-tuning and the replacement of softmax in attention with Gaussian kernels (GK). We show that LoRA and GK significantly accelerate the encrypted transformer computation under HE while maintaining performance levels comparable to those of the plaintext model. Experimental results of our modified BERT model on encrypted data using the CKKS scheme demonstrate its ability to securely process natural language data. Our findings show promise for offering privacy-preserving LLM services in areas where data protection is erucial.
Client
Server
Train data
Taken Lmbedding
Token Lmbedding
Fine-tunad LoRA weight
Pre-trained (frozen) LLM with GK
Plaintext
Enc
Ciphertext
Eval data
Taken Embedding
Token Embedding
Frozen weight
Enc
Classificiation
Classificiation
Inference
score
Doc
score
LLM under homomorphic encryption (HE). HE cryptographi- cally protects user's fine-tuning and inference data. We resolve two computational bottlenecks. First, we reduce the size of ciphertext-ciphereex matrix multiplication (CCMM) using LoRA fine-tuning. Second, we avoid the softmax computation, which is notoriously challenging to compute under HE, and replace it with a much simpler Gaussian kernel (GK).
Figure I: Proposed
1.1 PRIOR WORK
Transformer-basse based language models and LoRA. Since the advent of attention (Vaswani et al., 2017), the transformer has become the standard of language models. There three types of rransformer-based language models. Encoder-only models, including BERT series (Devlin et al., 2019; Liu et al., 2019; Sanh al., 2019; Lan al., 2020; Clark al., 2020; He et al., 2021) output embeddings for inputs that can be used for downstream tasks. Encoder-decode models, which use the original transformer architecture, such as MarianMT Jumezys-Dowmine et al., 2020), BART (Lewis et al., 2020), mBART (L.iu et al., 2020), and mT5 (Xue et al., 2021). are used for translation, summarizing, etc. Decoder-only models, including GPT series (Radford, 2018; Radford et al., 2019; Tom B. Brown et al., 2020; OpenAI, 2023) and Llama series (Touvron et al., 2023a;b; Dubey et al., 2024), generate sentences to the user's query. These large language models (LLMs) follow the scaling law (Kaplan et al., 2020), so the scale of LLMs tends to increase more and more. Hence, these models require a huge amount of memory capacity for inference and fine-tuning. To overcome this issue, LoRA (Hu et al., 2022) is mainly used to fine-tune a pre- trained LLM. Freezing all other weights, LoRA adapters are added to important layers of the model, such as attention layers during fine-tuning. Using LoRA, one can fine-tune I.MMs, updating only less than 1 1% of all of the parameters.
al., 2019). T5 (Raffel
frivacy-preservinn transformer using HE. Many researchers have explored preaecciree algorithms leveraging HE for transformer models. There are two main scenarios: interactive, which
2

---

Published as a conference paper at ICLR 2025
combines secure MPC with HE, and non-interactive, which relies only on HE. In interactive scenarios, encrypted computation time can reduced through communications between parties. THE-X (Chen al., 2022) proposed the first protocol for BERT-tiny inference, introducing HE-ffieendly workflows and non-polynomial evaluations via communications. Subsequent research (Hao et al., 2022; Li et al., 2023; Akimoto al., 2023; Dong et al., 2023; Pang et al., 2024) enhanced computation time and reduced communication costs.
However, interactive approaches may struggle with large-scale communication model size in- creases, and they also require data owners to be online during computation. To address these, non-interactive research is being conducted on the other side. Zimerman al. (2024) introduced the first HE- HE-friendly transformer model, replacing the original transformer with a HE-ffieedly struc- ture, minimizing the approximation domain, and obtaining pre-trained weight with the changed structure. Using these weights, they performed inference with BERT non-interactively. NEXUS (Zhang al., 2024a) further proposed con-interactive BERT inference method without re-training. using polynomial approximations for non non-polynomial operations. More recently, Park et al. (2024) proposed Powerformer, which, like our method, proposed replacing softmax in the attention with their BRP-max function for homomorphic inference.
Fine-tuning plays a crucial role in improving transformer models and providing more personalized responses. However, previous works have primarily focused secure inference, largely avoiding the challenge of fine-tuning due to the significant computational complexity involved, especially in non-interactive settings. Only a few attempts, such those by Lee et al. (2022b) and HETAL (Lee et al., 2023b), have explored fine-tuning, focusing exclusively on the classification head while leaving other key components like attention layers and feed-forward networks untouched. P3EFT (Li et al., 2024) also addresses fine-tuning of foundation models, but it concentrates more on energy consumption during fine-tuning.
1.2 CONTRIBUTIONS
We propose a homomorphic encryption (HE) friendly transformer architecture with emphasis inference following personalized (private) fine-tuning. We resolve two computational bottlenecks of the HE transformer model: (i) using LoRA, we avoid large ciphertext-ciphertext matrix multiplications (CCMMs), and (ii) we use a simpler Gaussian kemel (GK) to replace the softmax layer, which notoriously challenging compute under HE. Experiments an HE-encrypted BERT-style transformer demonstrate speedup of 6.94x for fine-tuning and 2.3x for inference.
SERVER-CLIENT COMPUTATION MODEL AND PRELIMINARIES
In this section, we first state the server-client computation model, referred to the threat model in the cryptography community. We then quickly review the relevant basic concepts and introduce the notation for homomorphic encryption and large language models.
2.1 SERVER-CLIENT COMPUTATION MODEL.
Our server-client computation model (threat model) involves client with private data, outsourcing fine-tuning and inference to the server, an LLM service provider. See Figure Specifically, the client sends encrypted token-embedded data to the server, and the server fine-tunes the model, generating customized encrypted LoRA weights. Subsequently, the server performs inference using encrypted inference data, plaintext pre-trained weights, and encrypted LoRA weights. The server returns the encrypted inference results to the client. The token embedding layer weights are not encrypted and not updated throughout fine-tuning.
Our model based on the semi-honest security model. The adversary adheres to the protocol but is allowed to collect all outputs from the model. Since the client's input data is encrypted with the CKKS ciphertext, the entire security model relies on the semantic security of the underlying CKKS.
The user data used throughout fine-tume munituning and inference is cryptographically protected, even from the LLM service provider. Both the pre- pre-trained weights of the LLM and the fine-tuned LoRA weights reside the server and are not shared with the user. However, clarify that this does not mean the
3

---

Published as a conference paper at ICLR 2025
LLM weights protected in the strict cryptographic sense, and proposed approach does not address the model weight stealing problem (Tramèr et al., 2016; Carlini et al., 2024).
2.2 HOMOMORPHIC ENCRYPTION AND CKKS
Homomorphic encryption (HE) is an encryption method that allows computations to be performed in an enerypted state without decryption. CKKS (Cheon al., 2017) is of the HE schemes that allows one to encrypt real or complex data as polynomial and perform approximate arithmetic on the enerypted data. By packing multiple real or complex data into ciphertext, CKKS supports single instruction multiple data (SIMD) operations in plain/ciphertext Plaintext denotes an unencrypted polynomial containing message vector in the context related to HE. For more detailed description, refer to Appendix B or the original reference Cheon et al. (2017).
Addition (Add): Given two ciphertexts or plaintext and ciphertext, evaluate component-wise addition.
Multiplication (Mult): Given two ciphertexts or plaintext and ciphertext, evaluate component-wise multiplication. We express the plaintext- ciihhere-iippertxtt component wise multiplcation pMult.
Rotation (Rot): Given a ciphertext ct enerypting message vector (Mo, mi,.... 1/2211), return ctrot, encrypting message vector almost same with (mz,.... m2/221: Mo, .... m;-1). We denote Rot(-;3 i) for ith left rotation. We express the same operation in plaintext as pRot.
Note that Mult and Rot require an additional key-switching operation. So, both take more computation time than other operations. For concrete time measurements, see Table 5 in Appendix E.
CKKS is one of the leveled HE schemes. A CKKS ciphertext has restricted number of (p) operations, so-called level, which is determined at the beginning of encryption. The modulus Q associated with the level, is reduced after these operations. Once we exhaust the available level budget, we cannot proceed to the next Mult operation. To recover the level budget, we can use bootstrapping (BTS) (Cheon et al., 2018). Since BTS is the most expensive HE operation, which is over 100 x slower than Mult, Rot, it is crucial to minimize its usage through effective designing of the algorithm. In fact, the time accounted for BTS constitutes a large portion of the overall computation time (Lee et al., 2022a; Zhang al., 2024a).
Matrix multiplications: PCMM and CCMM. While evaluating the transformer model under HE, we use two kinds of homomorphic matrix multiplications: plaintext-ciphertex matrix multiplication (PCMM) and ciphertext-cipherree tion requires numerous HE operations, such as Mult, Rot and Add, for each matrix, which are slower when operating on ciphertext compared to plaintext shown later in Table 5.
matrix multiplication (CCMM). Homomprhic matrix multiplica-
As result, PCMM is much faster than CCMM.
There have been several studies (Jiang et al., 2018; Jang al., 2022; Rizomiliotis & Triakosia, 2022; Zheng et al., 2023; Bae et al., 2024) to make homomorphic matrix multiplication more efficient. In this paper, we follow the JKLS (Jiang et al., 2018) algorithm, which provides the fastest known HE computation algorithm when the matrix elements can be packed in ciphertext. They also propose parallel homomorphic matrix multiplication. We use this parallel computation evaluate large-size matrix multiplication, where the size is more than available ciphertext space, by repeating block-wise matrix multiplcation. Thus, the computation time gap between PCMM and CCMM will be proportional to the number of block matrices. For more details, refer to Appendix C.
Polynomial approximations of non-polynomial functions. Since HE can only support polynomial operations, all non-polynomial operations (such as division, max function, etc.) must be replaced by their polynomial approximations. The complexity of polynomial approximation highly depends on the input range and the nature of the function being approximated.
2.3 LARGE LANGUAGE MODELS, ATTENTION LAYERS, AND LORA FINE-TUNING
Standard large language models (LLMs), such as BERT (Devlin et al., 2019), GPT-4 (OpenAI, 2023), and Llama-3 (Dubey al., 2024) constructed by stacking many transformer layers. We explain
4

---

Published as a conference paper at ICLR 2025
the standard attention mechanism in transformer (Vaswani et al., 2017) layer. We do not explain the feed-forward network (FFN), another component of the transformer, as it has not been modified in work. Suppose that L and represent sequence length and embedding dimension, respectively. Given Q, K E RR4x, the standard attention is calculated as
QK Vn
(ntentiionQQ,As V) Softmax
V E RR
(1)
The rows of Q, K, and V respectively referred to query, key, and value vectors. Here, the softmax function (Bridle, 1989) is applied row-wise, normalizing the similarity scores between each query and key vectors into probability distributions, which serve weigh the importance of each value vector. Later Section 4, we specifically discuss why the softmax function is numerically challenging compute under homomorphic encryption (HE).
Low-Rank Adaptation (LoRA) (Hu et al., 2022) of large language models has become the most widely used parameter-efficiet fine-tuning scheme for LLMs. Given weight matrix W R=xx of a linear layer, LoRA updates W with an update AW = AB, where r & n, A E Rnxr, and B E Æ"x" so that the linear layer's action becomes X X X(W + AB) for an input X e R In this LoRA fine-tuning, the pre-trained weight W is frozen while only A and B are trained.
SPEEDUP WITH LORA: AVOIDING LARGE CCMM
Bottleneck 1: Full fine-tuning incurs large CCMM. Personalized fine-tuning data is transmitted to the server encrypted, and the fine-tuning updates, which depend on the users' private data, must also be stored encrypted. Subsequently, encrypted inference data transmitted, and the transformer performs CCMM computations. Full fine-tuning updates all weights and, therefore, lead to many large CCMM calculations.
Specifically, consider a pre-trained linear layer with weight matrix W E I stored in plaintext. If we update W to W + ÁW where AW E _ then evaluating the linear layer
X(W + AW) XW + XAW, for X E g
costs (n²)) HE operations, where (--) only considers the dependence on However, while XW can be evaluated with PCMM, X must evaluated with the costly CCMM. This is because W is not encrypted, but AW must be encrypted.
Accelerating homomorphic matrix-multiplicatte with LoRA. LoRA (Hu et al., 2022) fine- tuning alleviates the cost of CCMM by reducing the size of CCMMs. We clarify that the primary benefit of LoRA in the usual plaintext application is the reduced memory footprint due to having fewer optimizer memory states. Under HE, however, the main benefit also converting large CCMMs into large PCMMs and reducing the computational cost.
Again, consider a pre-trained linear layer with weight matrix E gaxx stored in plaintext. However, consider LoRA fine-tuning updating W to W + AB, where < A RRxr and B Rx*" Then, evaluating the linear layer
X(W AB) = XW (XA)B,
for X E LR
requires an O(n")-cost PCMM to evaluate XW and two ((n))-cost CCMMs to evaluate (XA)B, where O(-) only considers the dependence on n and r. See Appendix C for further details. Since A and B encrypted, evaluating (X A) still requires CCMMs, but the CCMMs smaller than XAW by a factor of n/r. The difference in computational cost significant, as shown in Table la and Appendix G.
Finally, we mention, but without describing the details, that an analogous consideration can be applied to backpropagation. (We remind the readers that also perform fine-tuning under HE.)
Reducing optimizer states and inverse square root with LoRA. under HE using a variant of AdamW optimizer. The precise version of AdamW that we implement under HE is described in Appendix 5.2. For training and fine-tuning transformers, it is well known
We fine-tune the transformer
5

---

Published as a conference paper at ICLR 2025
that adaptive optimizers like AdamW significantly outperform non-adaptive optimizers such as SGD (Zhang et al., 2024b).
However, the inverse square root function mapping is 1/v2.. This is also non-polynomial function that tends to be difficult to use under HE. In general, due to wide input ranges for division, BTS is required for each ciphertext containing weights during evaluation. Given the large number of parameters in the transformer model, the optimizer step can create a computation time bottleneck. In fact, the optimizer's 's computation time exceeds that of the transformer block evaluation in our target model under full fine-tuning, as presented in Section 5.1.
LoRA alleviates this computational cost by substantially reducing the number of parameters being fine-tuned, thereby reducing the number of inverse square root operations needed in the AdamW optimizer. In our target 2-layer BERT model, full fine-tuning requires 368 ciphertexts containing weights, whereas LoRA only needs 15, offering clear advantage in optimizer computation time.
4 SPEEDUP WITH GAUSSIAN KERNEL: POLY-APX-FRIENDLY DESIGN
Bottleneck 2: Softmax is hard to evaluate under HE. Since HE only supports polynomial operations, polyyoooll functions must be approximated as polynomials. Traditionally, the softmax function is evaluated with
Softmax (I1, (21, T2, .. ,nn); = exp (I; a) E, exp (I, aa)
where a max {z,}. 1575n
Subtracting is crucial to avoid taking the exponential of a large positive number, which would lead to numerical instabilities. Under HE, however, the exponential, division, and max functions are non-polynomial functions that must be approximated. To clarify, the max function is conventionally evaluated using comparisons and if-statements, but these are non-polynomial functions that require polynomial approximations under HE.
While there is some recent work on efficiently approximating softmax function as polynomials (Badawi al., 2020: Jin al., 2020; Hong et al., 2022; Lee al., 2022c; 2023b), softmax still considered numerically challenging to evaluate under HE. In this section, we resolve this issue by avoiding the softmax function altogether and introducing the Gaussian kernel (GK) as an alternative.
GK attention. The standard attention layer (1) obtains the attention scores using the softmax function, which is difficult to approximate under HE. We can view the softmax as normalizing the outputs of scaled exponential kemel, where "kernel" is used the sense of RKHS kernel methods of classical machine learning (Berlinet & Thomas- 2011). However, fundamentally, there is no requirement to use the exponential kernel, nor there necessity for normalizing the scores.
We propose the alternative Gaussian kernel attention:
GK-Attention (Q, K, V) = -5Q2KKV
Kj. 12). i,j
(2)
S(Q,K), exp
1Q 2
where || ||2 is the L2 norm, the hidden dimension, and Qi. and Kj,: mean the ith and jth row of Q and K. Compared to the standard attention, the scaled exponential kernel is replaced with Gaussian kernel and we do not perform normalization. The Gaussian kernel is much easier to evaluate than the softmax function for the following reasons. First, there is no need for division. (The factor 1/(2/7) is fixed, so the reciprocal can be pre-computed and then multiplied.) Second, there is no need to compute the max function, which is difficult to approximate under HE. Third, exp(x) only needs to be approximated for x < 0, the region in which exp(x) does not blow up and therefore is much easier to approximate numerically. Specifically,
exp(x) Rs (x()) == (1
I
for
2F
which very accurate for the range polynomial approximation of exp(x)).
|-2*.0) See Appendix for further discussions on the

---

Published as a conference paper at ICLR 2025
Finally, we point out that in contexts unrelated to encryption or privacy, the prior work of Richter & Wattenhofer (2020) made the observation that normalizations (divisions) are not necessary for the attention layers and that the prior work of Lu et al. (2021) and Chen et al. (2021) used Gaussian kernel in place of the softmax. Specifically, Richter & Wattenhofer (2020) removed normalizations to improve the theoretical and practical characteristics of transformers, and Lu al. (2021) and Chen et al. (2021) further used low-rank approximation to the Gaussian kernel to present a linear- complexity attention layer accommodating long context lengths.
5 EXPERIMENTAL RESULTS
5.1 EXPERIMENTAL SETUP
In this subsection, we quickly describe some core aspects of the experimental setup. Some details, such the penalty training trick and hyperparameters, deferred to Appendix E.
Implementation of homomorphic encryption (HE). Our implementation is based the C++ HEaaN library (Cryptol.atl .b, 2022). All of our experiments used x Nvidia GeForce RTX 4090 24GB GPUs. We use the FGb parameter of the HEaaN library with the specific values in Table (Appendix B). Overall, we can do L = 9 (p) Mults before BTS, which means the minimum required level for BTS 3. The input range of BTS is [-1, If the input range exceeds it, we need another BTS algorithm; ExtBTS is an extended bootstrapping for having a wide input range [-220, 220), which require least 4 levels to operate. We usually use ExtBTS in our HE model except when the input range is guaranteed. For the detailed parameter information and time measurement of HE operations, refer to Table 5 in Appendix B. Note that Mult is 6x slower than pMult and Rot 24x slower than pRot. These are the main reasons for CCMM is much slower than PCMM.
Architecture. We use encoder-only transformer in the style of BERT (Devlin et al., 2019) and largely follow the setup of (Geiping & Goldstein, 2023). We remove all bias terms in the linear layers of transformer blocks and use the same tokenization in (Geiping & Goldstein, 2023). The hidden dimensions of emhedding, attention layers, and FFNs are 768. The number of attention heads is 12. In FFNs, enlarge the hidden dimension into 3072 with dense layer and reduce that to 768 using a gated linear unit (GLU) (Dauphin et al., 2017) and ReLU. In contrast to (Geiping & Goldstein, 2023), we modify the dense layer of the shape (768, 1024) in the classification head attached to the BERT into the two dense blocks of the shapes (768, 32) and (32, 1024). which allows us to use more optimized CCMMs (see Appendix D.2). We set the number of transformer layers as 2 for the practical computation time. We apply LoRA only to the query, value, and key layers applying LoRA to other layers (e.g., FFN) did not give a noticeable performance gain in our experiments. LoRA rank is 2 for all LoRA layers.
Non-polynomial approximation. Our transformer implementation under HE requires the poly- nomial approximation of several non-polynomial functions. We use the following methods for the approximation: Remez approximation (Remez, 1934), Newton's 's method (Nocedal & Wright, 2006), iterative method, and composition of minimax functions. Remez algorithm is computed using the Sollya tool (Chevillard et al., 2010). For inverse square root functions, we combine Remez approxi- mation with a few Newton's 's steps. For each non-polynomial approximation method and its precision based on input range and degree, refer to Table 13 in Appendix F, We also classify polynomials used for each downstream task through the HE experiment in the same section.
5.2 TIME MEASURMENTS
We now present the speedups provided by our proposed methods. We use input token length of 128. For further details on the optimizations of homomorphic matrix multiplication and LoRA- -fiinndiy CCMM. refer to Appendix 1. and D.2.
CCMM vs. PCMM. As explained in Appendix C and shown by the time differences between ciphertext and plaintext operations in Table 5 (Appendix E), CCMM is approximately 5x slower than PCMM for the same matrix sizes evaluation (Table la).
7

---

Published as a conference paper at ICLR 2025
Table I: Computation time comparison for homomorphic matrix multiplication and Softmax with
GK. For matrix multiplication, we assume the evaluation of matrices for 128 x 768 by 768 x 768 where 128 768 in ciphertext, and 768 768 is either in ciphertext or plaintext. PCMM and GK are much faster than their respective comparison group.
(a) CCMM vs, PCMM.
(b) Softmax vs. GK
Time (s)
Factor
Time (s)
Factor
CCMM PCMM
1,259
Softmax GK
8.99
0.275
4.58
1.44
6,24
Softmax vs. GK. In Table lb, we compare the computation time of Softmax and GK under HE, where the input range is [-2 OJ and we evaluate 12 pairs of 128 x 128 matrices row-wise for softmax and on matrices of the same size for GK. For the softmax function, we utilize the method of HETAL (Lee et al., 2023b), which approximates the maximum function, the exponential function, and the inverse function homomorphically. GK much faster than the softmax function evaluation using the HETAL (Lee et al., 2023b) approach under the same experimental setting.
Optimizer. In the experiments, we use AdamW-HE a modified version of Adam W (Loshchilov Hutter, 2019) is stated the following as Algorithm
Algorithm Adam W-HE
1: Initialize: mh +- 10 6-0
2: procedure Adam W-HEW-HHHETTT (1, B2, 0,A.00-1.m-1.110 Vo-1.9
3: 0, 4 0,-1 7201-1
4:
t 81m4-1 + (1-1))
5:
14 - 3214-1 + +(1 (1132) gi
6:
m. t m²! (1 B1)
7:
Te - v1/ (1-33) 35)
8:
Og + O2 - 7// v Uz +
(In AdamW, Og - 0. - ymii/ (Voe +
9:
Return 0,
10:
end procedure
In the original version of Adam W, the Step 8 has the form 0, + 0: ym,/ (Vin E), and this is numerically challenging to evaluate for the following two reasons:
To calculate 1/ (v De + E), we have to approximate v and 1/x, which are delicate.
Conventionally, 0 is set to sufficiently small value, such as 10-12, However, approxi- mating 1/x on the large range [e. is challenging small.
Therefore, we change Step in the Algorithm 1 into
0, +- - - +
and we choose value of e > 0 that not too small by considering both the performance and the approximation accuracy. Also, we use the maximum-dividing trick as in (3). These modifications allow AdamW-HE to be run stably under HE. Refer to Table 11 in Appendix E for hyperparameters used in AdamW-Hi for each task.
Computation time for our model and downstream tasks. Table 2 presents the execution times of each setup. We observe a speedup of 6.94x for fine-tuning and 2.3x for inference. Table compares the execution time for each downstream task with the Full+SM model. Our model consistently achieves a 4x improvement across each downstream task. For the detailed end-to-end time measurement for each block operation of our target model, Table 12 in Appendix E.
8

---

Published as a conference paper at ICLR 2025
Table Comparison of fine-tuning and inference times for full fine-tuning with Softmax (Full+SM), LoRA fine-tuning with Softmax (LoRA+SM), and LoRA fine-tuning with GK (LoRA+GK, Ours) approaches under single GPU. Our model achieves speedup both fine-tuning and inference.
Fine-tuning
Inference
Time (s)
Full+SM
LoRA+SM
LoRA+GK (Ours)
Full+SM
LoRA+SM
LoRA+GK (Ours)
2 layers
169.2
65.16
49.22
61.12
41.72
25.78
Class. head
1.52
0.72
0.72
0.72
Optimizer
252.83
10.31
10.31
Total
423.55
76.97
61.03
61.84
42.44
26.5
Factor
5.5
6.94
1.46
2.33
Table 3: Execution time analysis of fine-tuning for each downstream task, comparing method with Sull+SM. Our model shows the consistent 4x improvement for each downstream task.
Task
RTE
MRPC
STS-B
COLA
SST-2
QNLI
Ours
4.8
7.1
11.1
16.5
130
202
Time per epoch (h)
Full+SM
19.5
28.8
45.1
67.1
529
822
5.3 DOWNSTREAM TASK PERFORMANCE ON ENCRYPTED LANGUAGE MODELS
We evaluate our model the GLUE benchmark (Wang al., 2018). However, exclude WMNI (Devlin et al., 2019) as in Geiping & Goldstein (2023), and MNLI (Williams et al., 2018) and QQP (Wang al., 2018) due their size and our computational constraints. We fine-tune using the cross-entropy loss for tasks including CoLA (Warstadt et al., 2019), MRPC (Dolan & Brockett, 2005), al., 2007), QNLI (Wang al., 2018), and SST-2 (Socher et al., 2013), and MSE loss for STSB (Cer et al., 2017). We fine-tune SST-2 and QNLJ only for epoch and 5 epochs for others since the former are more computationally heavy. One can see the scores for Full+SM, LoRA+GK under plaintext, and LoRA+GK under HE (ours) in Table 4. We set s = 10 10 in the optimizer for all plaintext settings. For plaintext experiments, we repeat 10 times for each task and choose the best score. For experiments under HE, different & values are chosen for each task. The results in Table 4 indicate that using LoRA, Gaussian kernel, and homomorphic encryption results in only a minimal reduction in model accuracy compared to using full fine-tuning, softmax, and no encryption.
RTE (Giampiccolo
Table 4: GLUE results on our homomorphically encrypted language model. "Matthews corr." means Matthews correlation. "Full+GK" denotes full fine-tuning with GK. For all metrics, higher values mean better performance. Our model performs comparably to plaintext models.
Plaintext Fine-tuning
LoRA+GK under HE (Ours)
Task
Full+SM
Full+GK
LoRA+GK
Eval under Plaintext
Eval under HE
CoLA
0.2688
0.2640
0.1883
0.1512
0.1575
(Matthews com. 1)
MRPC
0.8304
0.8431
0.8258
0.8147
0.8147
(F
RTE
0,5884
0.6101
0,5776
0.5957
0,5993
(Accuracy t)
STSB
0.8164
0.8215
0.8107
0.8002
0.7997
(Pearson ?1
SST-2 (Accurncy
0.8991
0.8911
0.8567
0.8188
0.8188
QNLI
0.8375
0.8287
0.8040
0.7827
0.7827
(Accuracy
Average
0.7068
0.7098
0.6772
0.6606
0.6621

---

Published as a conference paper at ICLR 2025
6 CONCLUSION
In this work, we present a homomorphic encryption (HE) friendly transformer architecture and experimentally demonstrate that an encrypted BERT-style transformer exhibits significant speedups in both fine-tuning and inference under HE. Our architecture specifically resolves two computational bottlenecks using LoRA and Gaussian kernel (GK).
The field of
machine learning using large neural networks will advance through research on (i) training small, efficient language models with considcrations unrelated to encryption, (ii) improving the computational efficiincy of fundamental computational primitives under HE with considerations unrelated to machine learning, and (iii) developing machine learning models tailored toward the encrypted usage. This work represents the first steps of progress in the direction (iii).
ACKNOWLEDGEMENTS
This work has been supported by the National Research Foundation of Korea (NRF) under a grant funded by the Korea government (MSIT) (No. 2022RIA5A60008A00 Jung Hee Cheon and Taeseong Kim have been supported by Samsung Electronics Co., Ltd
REFERENCES
Yoshimasa Akimoto, Kazuto Fukuchi, Youhei Akimoto, and Jun Sakuma. Privformer: Privacy- preserving transformer with MPC. IEEE European Symposium on Security and Privacy, pp. 392-410, 2023.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. 1rXiv:160.006450. 2016.
Ahmad Al Badawi, Louic Hoang, Chan Fook Mun, Kim Laine, and Khin Mi Mi Aung. PrivFT: Private and fast text classification with homomorphic encryption. IEEE Access, 0226544-226555 2020.
Youngjin Bae, Jung Hee Cheon, Guillaume Hanrot, Jai Hyun Park, and Damien Stehlé. Plaintext- ciphertext matrix multiplication and fhe bootstrapping: Fast and fused. CRYPTO, 2024.
Moran Baruch, Nir Drucker, Gilad Ezov, Eyal Kushnir, Jenny Lerner, Omri Soceanu, and Itamar Zimerman. Training large scale polynomial CNNs for E2E inference over homomorphic encryption. WrXiv:2304.14883 2023.
Alain Berlinet and Christine Thomas-Agnan Reproducing Kernel Hilbert Spaces in Probability and Staristics. Springer Science & Business Media, 2011.
Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical GapSVP. CRYPTO, 2012.
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory, 6:1-36, 2014.
John Bridle. Training stochastic model recognition algorithms as networks can lead to maximum mutual information estimation of parameters. Neural Information Processing Systems, 1989.
Nicholas Carlini, Daniel Paleka, Krishnamurthy Dj Dvijotham, Thomas Steinke, Jonathan Hayase, A. Feder Cooper, Katherine Lee, Matthew Jagielski, Milad Nasr, Arthur Conmy, Eric Wallace, David Rolnick, and Florian Tramèr. Stealing part of production language model. International Conference on Machine Learning, 2024.
Daniel Cer, Mona Diab, Eneko Agirre, Iñigo Lopez-Gazpin and Lucia Specia. Semeval-2017 task I: Semantic textual similarity multilingual and crosslingual focused evaluation. International Workshop Semantic Evaluation, 2017.
10

---

Published as a conference paper at ICLR 2025
Tianyu Chen, Hangbo Bao, Shaohan Huang, Li Dong, Binxing Jiao, Daxin Jiang, Haoyi Zhou, Jianxin Li, and Furu Wei. THE-X: Privacy-preserving transformer inference with homomorphic encryption. Findings of the Association for Computational Linguistics, pp. 3510-3520, 2022.
Yifan Chen, Qi Zeng, Heng Ji, and Yun Yang. Skyformer: Remodel self-attention with gaussian
kernel and nyström method. Neural Information Processing Systems, 2021.
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic encryption for arithmetic of approximate numbers. ASIACRYPT, 2017.
Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. Bootstrapping for approximate homomorphic encryption. EUROCRYPT, 2018.
Sylvain Chevillard, Mioara Joldes, and Christoph Lauter. Sollya: An environment for the development of numerical codes. International Congress on Mathematical Software, 2010.
Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachene. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. ASIACRYPT, 2016.
Kevin Clark, Thang Luong, Quoc V. Le, and Christopher D. Manning, ELECTRA: Pre-training text encoders as discriminators rather than generators. International Conference on Learning Representations, 2020.
HEaaN. Cryptol.ab. Lab. HEaaN 2022.
n/heaan-he/, 2022.
Yann N Dauphin, Angela Fan, Michael Auli, and David Grangier. Language modeling with gated convolutional networks. International Conference Machine Learning, 2017.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre- Pre-training of deep bidirectional transformers for language understanding. Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2019.
William B. Dolan and Chris Brockett. Automatically constructing corpus of sentential paraphrases. International Workshop on Paraphrasing, 2005.
Ye Dong, Wen jie Lu, Yancheng Zheng, Haoqi Wu, Derun Zhao, Jin Tan, Zhicong Huang, Cheng Hong, Tao Wei, and Wenguang Chen. PUMA: Secure inference of Llama-7b in five minutes. arXiv:2307. /2533, 2023.
Abhimanyu Dubey, Abhinav Jauhri, Abhishek Kadian, et al. The Llama 3 herd of models. arXiv:2407.21783, 2024.
Léo Ducas and Daniele Micciancio. FHEW: : Bootstrapping homomorphic encryption in less than second. EUROCRYPT, 2015.
Cynthia Dwork. Differential privacy. International Colloquium on Automata, Languages, and Programming, 2006.
European Union. Regulation (EU) 2016/679 of the european parliament and of the council of 27 april 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing directive 95/46/ec (general data protection regulation).
https://eurr lex. www.eurr........................ www.urpp....ee..eee.eeeeeet.eeee wwtp://eeeeeeeee////e11/
679/07 oj. 2016.
Jonas Geiping and Tom Goldstein. Cramming: Training a language model on single gpu in one day. International Conference on Machine Learning, 2023.
Craig Gentry. Fully homomorphic encryption using ideal lattices. ACM Symposium on Theory of Computing, 2009.
Danilo Giampiccolo, Bernardo Magnini, Ido Dagan, and Bill Dolan. The third pascal recognizing textual entailment challenge. ACL-PASCAL Workshop on Textual Entailment and Paraphrasing, 2007.
Shai Halevi and Victor Shoup. Faster homomorphic linear transformations in HElib. CRYPTO, 2018.

---

Published as a conference paper at ICLR 2025
Kyoohyung Han, Seungwan Hong, Jung Hee Cheon, and Daejun Park. Logistic regression homomorphic encrypted data at scale. AAAI Conference on Artificial Intelligence, 2019.
Meng Hao, Hongwei Li, Hanxiao Chen, Pengzhi Xing, Guowen Xu, and Tianwei Zhang. Iron: Private inference transformers. Neural Information Processing Systems, 2022.
Pengcheng Hc, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. DcBERTa: Decoding-enhaneee BERT with disentangled attention. International Conference on Learning Representations, 2021.
Seungwan Hong, Jai Park, Wonhee Cho, Hyeongmin Choe, and Jung Cheon. Secure tumor clas- sification by shallow neural network using homomorphic encryption. BMC Genomics, 23:284, 2022.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang. Lu Wang. and Weizhu Chen. LoRA: Low-rank adaptation of large language models. International Conference on Learning Representations, 2022.
Jaehee Jang, Younho Lee, Andrey Kim, Byunggook Na, Donggeon Yhee, Byounghan Lee, Jung Hee Cheon, and Sungroh Yoon. pwracc-preserving deep sequential model with matrix homomorphic encryption. ACM Asia Conference on Computer and Communications Security, 2022.
Xiaoqian Jiang, Miran Kim, Kristin Lauter, and Yongsoo Song. Secure outsourced matrix computation and application neural networks. ACM SIGSAC Conference Computer and Communications Security, 2018.
Chao Jin, Mohamed Ragab, and Khin Mi Mi Aung. Secure transfer learning for machine fault diagnosis under different operating conditions. International Conference on Provable Security, 2020.
Marcin Junczys-Dommunt, Roman Grundkiewicz, Tomasz Dwojak, Hieu Hoang, Kenneth Heafield, Tom Neckermann, Frank Seide, Uirich Germann, Alham Fikri Aji, Nikolay Bogoychev, al. Marian: Fast neural machine translation in C++. Association for Computational Linguistics: System Demonstrations, 2019.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. vrXiv:2001.083611 2020.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. ALBERT: A lite BERT for self supervisdd learning of language representations. International Conference on Learning Representations, 2020.
Eunsang Lee, Joon-Woo Lee, Junghyun Lee, Young-Sir Sik Kim, Yongjune Kim, Jong-Scon No. and Woosuk Choi. Low-complexity deep convolutional neural networks on fully homomorphic en- cryption using multiplexed parallel convolutions. International Conference on Machine Learning. 2022a.
Garam Lee, Minsoo Kim, Jai Hyun Park, Seung-won Hwang, and Jung Hee Cheon. Privacy- preserving text classification on BERT embeddings with homomorphic eneryption. Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, 2022b.
Joon-Wont Woo Lee, HyungChul Kang, Yongwoo Lee, Woosuk Choi, Jieun Eom, Maxim Deryabin, Eunsang Lee, Junghyun Lee, Donghoon Yoo, Young-Sik Kim, and Jong-Seor No. Privacy- preserving machine learning with fully homomorphic encryption for deep neural network. IEEE Access, 10:30039-30000 -0054,, 2022c.
Junghyun Lee, Eunsang Lee, Joon-Wor Woo Lee, Yongjune Kim, Young Sik Kim, and Jong-Seon No. Precise approximation of convolutional neural networks for homomorphically encrypted data. IEEE Access, 11 11:62062-62076, 2023a.
Seewoo Lee, Garam Lee, Jung Woo Kim, Junbum Shin, and Mun-Kyu Lee. HETAL: Efficient srivacy-preserving transfer learning with homomorphic encryption. International Conference on Machine Learning, 2023b.
12

---

Published as a conference paper at ICLR 2025
Mike Lewis. Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. BART: Denoising sequence-to peneence-to-sqqucee sequence pre-training for natural language generation, translation, and comprehension. Association for Computational Linguistics, 2020.
Dacheng Li, Rulin Shao, Hongyi Wang, Han Guo, Eric P Xing, and Hao Zhang. MPCFormer: Fast, performant and private transformer inference with MPC. International Conference on Learning Representations, 2023.
Yang Li, Wenhan Yu, and Jun Zhao. Privtuner with homomorphic encryption and lora: A P3EFT scheme for privacy-preserving purameter-effiiien fine-tuning of ai foundation models. 3xXi:241100004333 2024.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A robustly optimized BERT pretraining approach. arXiv:/907.11030 1692, 2019.
Yinhan Liu, Jiatao Gu, Naman Goyal, Xian Li, Sergey Edunov, Marjan Ghazvininejad, Mike Lewis, and Luke Zeutleoyer. Multilingual denoising pre-training for neural machine translation. Transactions of the Association for Computational Linguistics, 8:726 742, 2020.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. International Conference on Learning Representations, 2019.
Jiachen Lu, Jinghan Yao, Junge Zhang, Xiatian Zhu, Hang Xu, Weiguo Gao, Chunjing Xu, Tao Xiang, and Li Zhang. SOFT: Softmax-free transformer with linear complexity. Neural Information Processing Systems, 2021.
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. EUROCRYPT,
Shiona McCallum. ChatGPT banned in Italy over privacy concerns. https: wwww wbw. com/ 2023.
newss/tech:ooog--513333
Aaron Mok. Amazon, Apple, and 12 other major companies that have restricted employees from com/ cttptptttttttteecc compa ieeaaaiisiieeee eeseesiss iss
using ChatGPT, heelbaass-tsttiiiciooo--ooos---s wawp::aaaaaaaaaaaa-a-a-oaaoooo-a 202--22222110 2023.
Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer, 2006.
OpenAl. GPT-4 technical report. arXivv2303.088: 2023.
OpenAl. ChatGPT. https:
httt//chappt.... 2024.
Qi Pang, Jinhao Zhu, Helen Möllering, Wenting Zheng, and Thomas Schneider. BOLT: Privacy- preserving, accurate and efficient inference for transformers. IEEE Symposium on Security and Privacy, 2024.
Dongjin Park, Eunsang Lee, and Joon-Wor Lee. Powerformer: Efficient preeaccireeervinggg trans- former with batch rectifier- power max function and optimized homomorphic attention. Cryptology ePrint Archive, 2024.
Alec Radford.
Improving language understanding by generative pre- mre-training. OpenAl blog, 2018.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl blog, 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21:1-67, 2020.
Eugene Y Remez. Sur la détermination des polynômes d' approximationn de degré donnée. Communi- cations of the Mathematical Society of Kharkov, 10:41-63, 1934.
13

---

Published as a conference paper at ICLR 2025
Oliver Richter and Roger Wattenhofer. arXiv:2005.09561, 2020.
Normalized attention without probability cage.
Ronald L Rivest, Len Adleman, and Michael L Dertouzos. On data banks and privacy homomor- phisms. Foundations of Secure Computation, 4:169-180, 1978.
Panagiotis Rizomiliotis and Aikaterini Triakosia. On matrix multiplication with homomorphic encryption. Cloud Computing Security Workshop, 2022.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. DistilBERT, distilled version of BERT: Smaller, faster, cheaper and lighter. NeurIPS Workshop on Energy Efficient Machine Learning and Cognitive Computing, 2019.
Richard Socher, Alex Perelygin, Jean Y Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. Conference on Empirical Methods in Natural Language Processing, 2013.
State of California. California consumer privacy act of 2018. https://oag.. ca. http://aaa....../.......a.o govvariy /ecpa, 2018.
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient public key encryption based ideal lattices. ASIACRYPT, 2009.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss. Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler. Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alee Radford, llya Sutskever, and Dario Amodei. Language models are few-shot learners. Neural Information Processing Systems, 2020.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv:2302. 13971, 2023a.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et Ilama 2: Open foundation and fine-tuned chat models. arXiv:2307.09288, 2023b.
Florian Tramèr, Fan Zhang, Ari Juels, Michael K. Reiter, and Thomas Ristenpart. Stealing machine learning models via prediction APIs. USENIX Security Symposium, 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Neural Information Processing Systems, 2017.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding. EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, 2018.
Alex Warstadt, Amanpreet Singh, and Samuel R. Bowman. Neural network acceptability judgments. Transactions of the Association for Computational Linguistics, 7:625-641, 2019.
Adina Williams, Nikita Nangia, and Samuel R Bowman. A broad-coverage challenge corpus for sentence understanding through inference. Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2018.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the natural language processing. Conference on Empirical Methods in Natural Language Processing: System Demonstrations, 2020.
14

---

Published as a conference paper at ICLR 2025
Linting Xue, Noah Constant, Adam Roberts, Mihir Kale, Rami Al-Rfou, Aditya Siddhant, Aditya Barua, and Colin Raffel. mT3: A massively multilingual pre-trained text-to-text transformer. Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2021.
Andrew C. Yao. Protocols for secure computations. IEEE Annual Symposium on Foundations of Computer Science, 1982.
Jiawen Zhang, Jian Liu, Xinpeng Yang, Yinghao Wang, Kejia Chen, Xiaoyang Hou, Kui Ren, and Xiaohu Yang. Secure transformer inference made non-interactive. Cryptology ePrint Archive, 2024a.
Yushun Zhang, Congliang Chen, Tian Ding, Ziniu Li, Ruoyu Sun, and Zhi-Quan Luo. Why trans- formers need Adam: A Hessian perspective. Workshop on Efficient Systems for Foundation Models at ICML, 2024b.
Xiaopeng Zheng, Hongbo Li, and Dingkang Wang. A new framework for fast homomorphic matrix multiplication. Cryptology ePrint Archive, 2023.
Itamar Zimerman, Moran Baruch, Nir Drucker, Gilad Ezov, Omri Soceanu, and Lior Wolf. Converting transformers to polynomial form for secure inference over homomorphic encryption. International Conference on Machine Learning, 2024.
15

---

Published as a conference paper at ICLR 2025
A DIAGRAM: FULL FINE-TUNING VS. LORA FINE-TUNING IN BERT
Figure 2, 3 illustrate the complete diagram our target model with respect to full fine-tuning and LoRA suee-tunig, respectively. Orange boxes indicate where updates occur during fine-tuning, and in the classification head layer denotes the number of classes. In full fine-tuning, large-size weight matrices are updated and transformed from plaintexts to ciphertexts, which means the large-size CCMMs must be processed during both fine-tuning and inference. In contrast, only small-size weight matrices are transformed into ciphertexts in LoRA fine-tuning.
Input
128 x 768
Laye Norm
Layenhorm
128 x 768
120
LoRA
LoRA
LoRA
COMM
CCMM w/
CCMM
PCMM W
SCWN
PCMM W
PCMM W!
DoMB
w
128 x 768
128 x 788
+ 128 768
Spltt
Spilt
Spiit
Add
Add
Add
v
128
708
Splt
Splft
Transpose
128
128
128
Transpose
Atti
Kernel
X
Gauestor Kornel
X 12
128
OCMM
[ 1228
128
Concat
COMM
PCMM
120 788
X 2
128 x 788
X 2
Leyerromm
128 788
Laye
128 x
CCMM
PCMM
128 9072
Spil
Spltt
+ ReLU
SplRt
FEN
28 1536
+
ReLU
128 1538
120 x 1535
CCMM
128 768
128
LayerNorm
Layer Norm
8.768
CCMM
CCMM
Classification head
1
+
CCMM
CCMM
Tanh
Tanh
1x
CCMM
COMM
1
Loss
Loss
Figure 2: Full fine-tuning.
Figure 3: LoRA fine-tuning.
16

---

Published as a conference paper at ICLR 2025
B CKKS FUNCTIONALITES
The CKKS (Cheon et al., 2017) a homomorphic encryption scheme that allows one to encrypt real complex data as message polynomial and perform approximate arithmetic on the enerypted message. More precisely, CKKS scheme supports a mingle-intruction-mmlln
(SIMD) property from encoding /decoding (Dcd) map: given power-of positive integer ring degree N, encoding map is defined as Ecd C + RQ [gl=\/(>" + 1). where is positive integer. The decoding map Dcd can be interpreted as an inverse process of Ecd. Ecd/Do represents conversion between (CN/2, (D, @) and (Rq. where ① and @ are component-we wise addition and multiplication, respectively. In the CKKS scheme, each of Ecd and Dcd is processed before eneryption or after decryption, respectively. Eneryption (Encpk) and Decryption (Dec.)) ) are ring learning with errors (RLWE) (Stehlé et al., 2009; Lyubashevsky et al., 2010) eneryption and those vectors via polynomial
decryption, respectively. We operate addition/mulliplicaatee operations from the ring isomorphism. Here, we use notation to indicate approximate equality, as the CKKS scheme evaluates approximately (for more details, refer to Cheon et al. (2017));
Key generation: Given security parameter À and subset S (1, ,N/2), return public key pk, a secret key sk, relinearization key rlk, and rotation keys {rki
Eneryption: Given pk and a message m, return a ciphertext ct = Encpk(m) = Enc(Ecd(mm) pk).
Decryption: Given sk and a ciphertext ct, return a message m' (ct) = Dcd(Dec(ct,sk)) where m' R m.
Addition: Given two ciphertexts ct₁ and ct2, return ctadd = Add(ct ct2), satisfying Dec,x (ctædd) = Dec,((ct1) @ (ec2)(ct2). Addition also can be evaluated between plaintext and ciphertext.
Multiplication: Given two ciphertexts ct and ct2 and linearization key rik, return ctmmute Mult(ct,, ct2). satisfying Decsk(Ctmull (ec,(cct) Dec (ct2).
Multiplication by Plaintext: Given plaintext pt and ciphertext ct, return Chymult. pMult(pt, ct), satisfying Decau(Clyman 2 Dcd(pt) @ (ecau(Clpmutt).
Rotation: Given a rotation key rk; for i E S and a ciphertext ct with Decx((et) 20 (mo, m1, ...,, x))2-1), return ciphertext ctrot, = Rot(ct, i) satisfying Dec,((ctro)/ 2 (m,, ................................ 1/1-11 Mo. .... m4-1). The rotation index i acts modulo N/2, so Rot(:, -i) Rot(-, N/2 i). pRot is the same operation on the plaintext side.
HE parameter and its time measurement. During HE implementation, we use the FGb parameter, one of the HEEaaN-providing parameters. For the detailed value of the FGb parameter, refer to Table 5. We also list the time measurement HE operations under a single GPU. We know that Mult and Rot, operated in ciphertext, are slower than pMult and pRot, which are related to plaintext operations, respectively.
Table 5: The FGb parameter and time measurement for each HE operation under the single GPU. The terms log(QP), N, L, À denote the bit lengths of the largest modulus, ring degree, multiplicative depth, and security parameter.
FGb parameter
Time measurement of each homomorphic operation (ms)
log(QP) (PP)
N
L
h
À
Add
pRot
Rot
BTS
ExtBTS
pMult
Mult
1555
2
9
192
128
0.02
0.02
0.49
60
137
0.1
0.6
C HOMOMORPHIC MATRIX MULTIPLICATION ALGORITHM
Consider d x d homomorphic matrix multiplication. JKLS (Jiang et al., 2018) suggests the fastest known HE square matrix multiplication algorithm with (d) HE computational complexity (for more precise number of each operation, refer to Table 6) when the matrix elements can be packed in cipher- text, specifically when d' < N/2. The required HE operations include Add, (p Rot, and Multu... The computation time of Rot and Mult operations differ between plaintext and ciphertext (see Table
17

---

Published as a conference paper at ICLR 2025
5), with operations in ciphertext being significantly slower. Consequently, CCMM is much slower than PCMM; the number of different message space operations is exactly + 2vd for one homomor- phic matrix multiplication. For precise time difference between two kinds of homomorphic matrix multiplication, see Section 5.2.
When > N/2, where we cannot encrypt the matrix into one ciphertext, we can also utilize the JKLS algorithm by computing block-wise matrix multiplication. For example, if we take N 2 for the base ring degree, we can pack two 128 x 128 matrices into one ciphertext. When d = 768, require 18 ciphertexts pack d x d matrix. After packing each block matrices into eiphertexts, we repeat the corresponding block-wise matrix multiplication to all the weights. Thus, for large-size matrix multiplications, the computation time gap between CCMM and PCMM will be proportional to the number of ciphertexts required for packing.
In addition, JKLS introduced a homomorphic rectangular matrix multiplcation of size x by d x or vice-versa, with < d and êd < N/2. We can use this method to evaluate LoRA CCMMs, where we need to evaluate the homomorphic rectangular matrix multiplication sequentially. For more detailed HE operations numbers, see Table 7.
Table 6: The number of each HE operation for x homomorphic matrix multiplication required by JKLS (Jiang et al., 2) algorithm.
Operations
Add
pMult
Rot
Mult
Depth
JKLS (Jiang et al., 2018)
6d
4d
3d + 5.
Table The number of each HE operation for rectangular homomorphic matrix multiplication é x by d x d required by JKLS (Jiang et al., 2018) rectangular matrix algorithm.
Operations
Add
pMult
Rot
Mult
Depth
JKLS (Jiang al., 2018)
3d + 28 log(d/f) 3d + 26 36 + 5 log(d/E)
3
D OPTIMIZATIONS FOR HOMOMORPHIC MATRIX MULTIPLICATION
The CKKS scheme packs all input data into a polynomial from encoding (Ecd). The packed data are assigned to fixed positions within the polynomial, and to change these positions, we have to use the Rot operation. the homomorphic matrix multiplication algorithm, several Rot operations required. Our target model has sequential matrix multiplications, packing structure. Among various packing methods, we use row-wise packing (see Figure 4a) for all packed data except for LoRA weights. which will be explained in the next subsection. Because using the FGb parameter can pack a total 2 data in one message space, we consider one plain/ciphertext having 2 data, which corresponds the size either 128 256 256 128 in implementation. Thus, during our model computation, we will assume one plain/ciphertext is packed 128 x 256 matrix row-wise.
it is more efficient to fix the
D.1 HOMOMORPHIC MATRIX MULTIPLICATION
Here, we introduce the optimization techniques used in our homomorphic matrix multiplication implementation. We adopt three optimization techniques improve the speed of homomorphic matrix multiplication:
Evalation in lower level: Because homomorphic matrix multiplication contains numerous HE operations and its speed depends the current level, the ciphertexts containing matrix values are brought down to the minimum required level before performing the evaluation (Bae et al., 2024; Park al., 2024), even if BTS may be needed for the next block evaluation. We adhere to this strategy in our homomorphic matrix multiplication by taking the JLKS (Jiang et al.. 2018) algorithm, which requires 3 levels. Consequently, evaluating the bottom-level level) PCMM is
18

---

Published as a conference paper at ICLR 2025
2 faster than the top-level (12 level) PCMM (refer Table of size 128 256 by 256 128. This difference even more pronounced in CCMM.
Pre-computation and reuse for left-matrix: When we perform homomorphic matrix multi- plication of size 128 x 768 by 768 x 768, we need to split the matrices as three and eighteen block matrices (see Figure 4c), respectively. And we go through each block matrix multiplication to get corresponding result. From the property of block matrix multiplication, we know the same left matrices are used several times to multiply by the right block matrices. Thus, we do pre-computation using JKLS (Jiang et al., 2018) and save these objects for left- Using this strategy, we can reduce the total number JKLS algorithm calls, which require numerous HE operations (as shown in Table 6), from 36 to 21. This is trade-off between memory and computation time.
Lazy weyyswwichhing/rscalnnggg When a ciphertext is evaluated by an automorphism, we need do a key-switching operation. This is expensive process. If the result ciphertext is made from several ciphertexts resulting in same automorphism, we are used to take lazy key-switching (hoisting) (Halevi & Shoup, 2018); that is, go through only key-switching after collecting all results instead of doing key-switching for each automorphism. By taking lazy key-switching, we can speed up the required computation time. Lazy rescaling is also similar strategy for reducing computation time and added errors when doing a rescaling operation, which is an operation contained in Mult.
Table 8: Computation time comparison between PCMMs according the different levels. The lower-level homomorphic matrix multiplcation is faster than the top-level evaluation.
PCMM
Time (s)
Factor
12 level
0.242
7 level
0.103
2.35
(a) Row-wise packing
(b) Zero-padding packing
3
14 15
14
(c) Block-wise matrix multiplication
768
Wi
Wio
128
C
X
W21
W26
128 rest
rCSe
128
128
Wai
W36
res1
Ax W B W21 C Wai
128
res: A x Wio + B x W2 + Wao
Figure 4:
Row-wise packing method for matrix representation, utilizing zero-padding for non-square matrices, followed by block-wise matrix multiplication for efficient processing of large matrices.
D.2 LORA STYLE CCMM
LoRA fine-tuning consists of two CCMMs. Because the LoRA weights are rectangular matrices, we need do cero-padding (see Figure 4b) for the second weight to make it square matrix. After that, we can follow the optimized homomorphic rectangular matrix multiplication algorithm sequentially, which call the Rectangular MM algorithm in the following. However, when consider that
19

---

Published as a conference paper at ICLR 2025
target LoRA rank(=2) is quite small, this Rectangular MM approach generates inefficiency since there are many non-usable spaces in the ciphertext from sero-padding. Thus, we make a more efficient algorithm for LoRA CCMMs than following the Rectangular MM. Our optimized algorithm can be applied in cases similar to LoRA CCMMs, which involve sequential matrix multiplication where one dimension is significantly smaller than the other. In model, we also these optimized CCMMs during classification head layer evaluation, where we have to perform homomorphic rectangular matrix multiplications of size 768 by 768 32 and 1 32 by 32 x 1024. For convenience, this subsection will describe the case regarding LoRA CCMMs with rank 2: 128 x 768 by 768 x 2 and 128 x by X 768, sequentially.
(a) A-RAeniiy packing
768
128
128
128
128
rank
a
rank
0
128
(b) Split & repeat row-wise
128
128
128
81
128
128
4r
b
128
rank
128
C
ct1
clir
61
fi
fr
ctu1
clar
Figure 5: LoRA-friendly packing is used when the given matrix has one long and one short size. Split repeat row-wise divides and copies each row into ciphertexts, which is used during LoRA CCMMs and a, denotes i-th row of matrix The shaded block matrices represent zero eero-padded blocks.
D.2.1 LORA-FRIENDLY PACKING
In our target model, the LoRA weights are either 768 x rank rank 768. Both weights have one long and one short dimension. Instead of directly following row-wise packing used entire message packing, pack LoRA weights with another approach. Figure 5a represents the packing method, called LoRA-friendly packing, used in LoRA weights. Even if 768 x rank is column rectangular matrix shape, we follow the LoRA-friendly packing by considering the transposed column rectangular matrix. This does not mean we evaluate homomorphic transposition, where we use an algorithm in JKLS (Jiang et al., 2018) that also has numerous HE operations. But treat its column rectangular matrix with the corresponding order in row-wise packed structure:
(Ar hiii + (BeheksN/2= = {{
AAi
A it 768 (j - 1) otherwise
By following this, remove the required evaluations of transposition during backpropagation computation.
D.2.2 OPTIMIZED HOMOMORPHIC LoRA MATRIX MUL.TIPLICATION ALGORITHM
We optimize the sequential LoRA CCMMs in Algorithm 5. This algorithm consists of several HE operations and three operation blocks: (i) Split & repeat row-wise (Algorithm 2) for weights, (ii)
repeat column-wise (Algorithm 3), and (iii) collect into the first column (Algorithm 4).
20

---

Published as a conference paper at ICLR 2025
Algorithm 2 Split & repeat row-wise (Figure 5b)
1: Input: A ciphertext che having LoRA weight, LoRA rank r, plaintext Mrow encoding 128 x 256 matrix where all entries are zero except for the first row, which entirely ones.
2: Output: Ciphertexts (et.)).ee....3..........
3: procedure SplitRepeat Tú Mrow)
4: for i (1 3) do
5: imp + ctw
6: if is not then tmp + Rot(tmp, (i - 1) x r x 256)
7:
8: end if
9:
for j E [1, . do then tmp < Rot(ump, (j 1) x 256)
if
11:
end if
13:
cliy pMult(Mrow: tmp)
for k E (0.... ... log,( (128) - 1
15:
tmp Rot(ctt) -2 256)
16:
ctaj Add(ctyy. tmp)
17:
end for end for
18:
19:
end for
20:
Return (cl.:)ee122330410...
21:
end procedure
Algorithm 3 Repeat column-wise
1: Input: Ciphertexts fct, (et, .r. LoRA rank
2: Output: Ciphertexts (Et,))
3: procedure RopeatCol((ct)))edll...
4: for i {1.... ... ,r} do
5: for l E (0.... ... log, (256) - 1) do tmp + Rot(ct, -2*)
6:
7: end for
ct,- +- Add (t,,
(dd( tmp)
8:
9: end for
10: Return {ct.)ee(1,-..r))
11:
end procedure
Algorithm 4 Collect into the first column
1: Input: A ciphertext (a. je ... LoRA rank r, plaintext Moot, encoding 128 x 256 matrix where all entries are zero except for the first column, which is entirely ones.
2: Output: Ciphertexts je,,))
3: procedure CollectFinstColctt,, Mool) Mcot)
4: for j E (1,...,7) do
5: Ctj +- aij
6: for i (2,3) do
7:
ct, t Add(cty,
8: end for
9:
for A E {0, (O..... log, (256) 1} do tmp + Rot(ct,, 2*) ct, + Add(ct,, tmp)
10:
12: end for
Clj + pMult(Mosts clj) end for
14:
15: Return {ct, bet
16:
end procedure
21

---

Published as a conference paper at ICLR 2025
Algorithm 5 LoRA CCMMs
1: Input: Ciphertexts (1.23)) LoRA weight ciphertexts ct and ct&, LoRA rank r, plain-
texts Mrow Mcot-
2: Output: Result ciphertexts (res; (E of LoRA CCMMs.
3: procedure LORA CCMMs((ct,)ef11.. cta, ctp, Mrow Mcot)
4: {Aij} <- SplitRepeat T, Mrow)
5: for i E (1, 2, 3) do
6: for E {1,... (1....,r] .r) do
7:
W < Mult(Ary,tt, ct,)
8:
end for
9:
end for
10:
{ump; <- FolstctFFirstCol
Meat)
11:
{ump,) +
[Bij] SplitRepeat(clB Frow)
13:
for i [1, [1,2,3] 3) do
res; f- Mult(B,1, tmp,)
15:
for j E [2, , do
Bi f- Mult( Big, tmp,)
res; Add( 13. res;)
18:
end for end for
19:
20:
Return {res; (
21:
end procedure
D.2.3 COMPARISON RECTANGULAR MM AND OPTIMIZED LORA CCMMS
We compare two approaches, Rectangular MM and our optimized LoRA CCMMs (Algorithm 5). We list up the required number of each HE operation for each method (Table 9) based on the given number of JKLS (Jiang et al., 2018) algorithm (Table 7) and the computation time comparison in implementation (Table 10). Our optimized LoRA CCMMs are 4.45 faster than Rectangular MM. In addition, using LoRA-friendly packing, can reduce the required number of homomorphic transposition evaluations.
Table 9: The total required number of HE operations for 128 x by r and 128 r by r homomorphic matrix multiplications where denotes the LoRA rank. Rectangular MM denote method that takes homomorphic rectangular matrix multiplication sequentially. Algorithm requires much smaller HE operations than following Rectangular MM algorithms.
Operations
Add
pMult
Rot
Mult
Depth
Rectangular MM 18d 12r 6 (lg(d//r)
18d
12r
18r
30
6 log(d/r)
6r
6
Algorithm 5
42r
4r
40r
6r 3
Table 10: Comparison of execution times between Rectangular MM and Algorithm 5. In the figure, MM denotes implementing our homomorphic matrix multiplication, Tr denotes homomorphic transpose. Algorithm 5 is about 4.45x faster than Rectangular MM.
Forward eval.
Backprop.
MM
BTS
MM
BTS
Tr
Total
Factor
Rectangular MM (s)
0.65
1.3
2.84
0.42
0.71
5.92
Algorithm (s)
0.12
0.76
0.29
0
0.16
1.33
4.45
E EXPERIMENTAL DETAILS UNDER HE
In this section, we provide experimental details used in experiments under HE.
22

---

Published as a conference paper at ICLR 2025
Penalty training In the experiments, approximate non-polynomials such inverse square root in LayerNorm (Ba et al., 2016). However, we cannot assure that the inputs of each non-polyn non-polynomial lie in the approximation domain. To address this, charge a penalty in Baruch et al. (2023) in the pre-training stage. For example, when we approximate ReLU the ith transformer layer on [-50, 50), for an input X of model, let the input of this ReLU be X N.LLL Then we add the term 1 [IIX, 250} to the pre-training loss Lpre where À > 0. If we let
J (U The approximation range of f [- Ly]}
be the set of all con-polynomials and their approximation domains in our model, then the original loss function is modified into
Epenally (X:0) = (p:e + E (1x)1)=01)()))
(1.L))E
where X is the input of the model, 0 is the parameters of the model, and X is the input of F for the initial input X. We change the original Trre to /peeaaly in the last & (100 in our setting) steps of the pre-training. In this way, we can narrow the input range of non-polynomial functions and are able to approximate them.
Hyperparameters. We summarize the hyperparameters used in HE experiments. We first experi- mented on the plaintext and chose the best hyperparameters for HE experiments.
Table Hyperparameters used for HE experiments. Epsilon means of AdamW-HHE in section 5.1. Warmup steps, Number of cycles are used in transformers (Wolf et al., 2020) cosine scheduler, and betas are used in AdamW-HE.
Learning Rate
Epsilon
Warmup Steps
Number of Cycles
Betas
CoLA
4.0e 3
8.0e
MRPC
5.0e 4
6.0e
RTE
2.0c 4
2,0e
0.5
0.9.0.999)
STSB
2.5e 2
4.0e 1
SST-2
8.5e 3
8.0e
QNLI
6.5e 3
8.0e
End-fo-end runtime of 1 layer forward evaluation and backpropagation. Here, we list all the required block operations runtime in 1 layer case with respect to forward evaluation and backpropa- gation of LoAR fine-tuning in Table 12. In forward evaluation, the softmax function evaluation is the most tome-consuming part in LoRA with Softmax, on the other hand, BTS is the part in LoRA with GK. In both cases of backpropagation, the matrix multiplication time is the most time-consuming part. Thus, replacing the softmax function efficiently and reducing the required number of CCMM key factors, adopt LoRA fine-tuning and the Gaussian Kernel.
23

---

Published as a conference paper at ICLR 2025
Table 12: Lists the end-to-end runtime for each individual operation using single GPU. Tr denotes transposition, and Save is the saving time for backpropagation or optimizer. Softmax evaluation occupies 43%, which is the most time-consuming forward evaluation; however, GK is just 8%.
Forward eval.
Time (s)
Ratio (%)
Backprop.
Time
Ratio (%)
PCMM
1.35
6.47
PCMM
2.29
19.54
CCMM
1.87
8.96
CCMM
3.79
32.34
LayerNorm
0.48
2.3
LayerNorm
0.32
2.73
BTS
5.74
27.53
BTS
4.45
37.97
Softmax
8.99
43.1
Softmax
0.02
0.17
ReLU
1.35
6.47
ReLU
0.02
0.17
LoRA
0.85
LoRA
0.26
2.22
Tr & Save
0.23
1.1
Tr & Save
0.57
4.86
Total
20.86
100
total
11.72
100
Forward eval.
Time (s)
Ratio (%)
Backprop.
Time
Ratio (%)
PCMM
1.35
10.47
PCMM
2.29
19.54
CCMM
1.87
14.51
CCMM
3.79
32.34
LayerNorm
0.48
3.72
LayerNorm
0.32
2.73
BTS
5.74
44.53
BTS
4.45
37.97
GK
1.02
7.91
GK
0.02
0.17
ReLU
1.35
10.47
ReLU
0.02
0.17
LoRA
0.85
6.59
LoRA
0.26
Tr & Save
0.23
1.78
Tr & Save
0.57
4.86
Total
12.89
100
total
11.72
100
Multi-GPU implementation that simulates a batch scenario. For the LoRA finettuning for the downstream tasks, we use 8 GPUs. We follow the same plain model parameters (refer to Appendix E), where the batch size is 16. Because packing multiple datasets to mimic the batch scenario itself has some restrictions (such as large-size weights, long token lengths, and restricted message spaces), we get to use multiple GPUs to make our algorithm keep following batch scenarios. Here, we assign one datum one GPU. When the weights are updated, the communications between GPUs are raised, and an average of each gradient can be obtained. This speeds the runtime per epoch, even with slight communication delay, which is negligible compared the overall runtime.
F UTILIZED POLYNOMIALS FOR EACH DOWNSTREAM TASK
F.1 OVERVIEW OF POLYNOMIAL APPROXIMATIONS USED IN OUR TARGET MODEL.
Table 13 shows the overview of polynomial approximation utilized our target model experiments. According the input range, the optimized approximation method is different. For the inverse square root, we additionally employ a few iterations of Newton's method for the following reason. While minimax approximation optimizes multiplicative depth in polynomial evaluation, it requires numerous multiplications. To mitigate this, we integrate a few Newton iterations, which provide a faster approximation of the inverse square root, though at the cost of additional multiplicative depth.
24

---

Published as a conference paper at ICLR 2025
Table 13: Overview of polynomial approximation methods for various non-polynomial functions with specific usages. "Worst prec." refers to the maximum value of []) (z))(=)]l across the input range, while "Avg prec." denotes the average (mean) value. Although we replace the softmax with the Gaussian kernel in attention layers, the softmax function is still used once in computing the cross-entropy loss. Non-polynomials require different polynomial approximations according to input range.
1/vz
1/a
tanh
exp
ReLUU
Input range
10.0005. 1I
[0.04.1]
[0.8.3.0]
[-5,5]
[-16,16]
[-2,2]
[-13,1]
[-2*%.0]
[-1.1]
Degree Worst proc. (bits)
127
127
15
15/15/27
11.1
19.8
23.7
24.7
18.6
21.2
21.2
15
10
Avg prec. (hits)
24.6
24.6
26.5
26.6
19.6
25.8
Minimax composition
Method
Remez
Remez Classification head
(Lee al.. 2023a)
LayerNorm Adam H-
Usage
(Softmax)
(Softmax)
F.2 POLYNOMIALS FOR EACH DOWNSTREAM TASK
In the previous subsection F.1, we give our polynomial approximation of each non-polynomial. Since the input ranges for non-polynomial functions vary across downstream tasks, appropriate polynomial approximations are required for each task, Below, we list the polynomials used for each task, with Table 14 categorizing them based on their input domains.
Inverse square root with additional three Netwon steps: sqrtInv ([0.0005, 1J)
Inverse: inv1 ([0.04, 1J). inv2 ([0.8, 3.0])
Exponential: expl (I-2, 2)), exp2 ([-13, 1J)
Exponential with iterative algorithm: explter ([-214.0)) (p14 in section 4)
ReLU: relu (l-50, 50])
Tanh: tanhl ([-5, 5)), tanh2 ([-16, 16])
Table 14: Types of polynomials used in the block operations for each task.
LayerNorm
Attn
FFN
Class. head
Loss (Softmax)
AdE
CoLA
MRPC
tanh1
expl, invl
RTE STSB
sqrtInv
explter
relu
sqrtInv
SST-2
tamh2
exp2, inv2
QNLI
We plot some polynomial functions used in work: explter, sqrtInv, and relu. See Figure 6 and 7. For ReLU and 1/ II, we slightly modify to use approximations these functions the fixed input range. When we approximate 1/ if the input range lies outside the interval [0.0005, 1]. we divide a predetermined number M for the inputs to belong in [0.0005, 1]: for an input x, we calculate
1
V V
VM
For ReLU, we set K and for an input æ calculate as
ReLU(z) = KReLU
K
using the homogeneity of ReLU. In the experiments, we set = 50. You can see in Figure the comparison of these functions and their approximations.
25

---

Published as a conference paper at ICLR 2025
10.
exponential
exconential
P14
5.-
0.5
y
0.
0.4
-50
-100
-14
Figure 6: The graph of approximation pıa(= explter) on [-214, 0] of the exponential.
1/X
Rell
sqrtinv
relu (approximated)
y
0.4
0-
Q,1
0.6
0.8
-3.00
-3.30
-B.23
0.00
0.23
0.73
1.40
Figure 7: The graphs of approximated inverse square root and ReLU on [0.0005, 1] and [-1, 11. respectively.
G COMPUTATION ADVANTAGE OF LORA AND GAUSSIAN KERNEL FOR LARGER MODELS
In section 5.2, we saw that CCMM is approximately 4.58 x slower than PCMM when performing matrix multiplication with dimensions 128 x 768 and 768x768, where 768 is the embedding size. Also, calculating attention scores using softmax is approximately 6.24 x slower than using GK. However, when the embedding dimension and sequence length become larger, as in GPT-4 (OpenAI, 2023), the gain in computational time by LoRA and GK is amplified. In this section, we calculate the time required perform PCMM and CCMM and to obtain attention score through softmax and GK as the embedding dimension and the sequence length increase. See the Table 15 for the results.
Table 15: Computation times for performing PCMM and CCMM with 128 by matrices, and evaluating Softmax and GK on n-dimensional input. Factor in each table represents the ratio of computation times between two operations. As the dimension increases, the performance gains become larger.
(a) Comp. time for PCMM vs. CCMM.
(b) Comp. time for GK vs. Softmax.
Dim. (rt)
256
512
768
Dim. (a)
128
256
512
PCMM (8)
0.138
0.139
0.275
GK (s)
0.17
0.34
1.36
CCMM (s)
0,297
0.463
1.259
Softmax (s)
1.3
2.86
13.04
Factor
2.15
3.33
4.58
Factor
7.65
8.41
9.59
26

---

Published as a conference paper at ICLR 2025
CCMM
4,5
Factor
PCMM
Computation time (s)
4.0
Factor
3.5
3.0
2.5
0.2
256
512
768
256
512 n
768
Figure 8: Computation time comparison between PCMM with CCMM for 128 x matrix by X matrix multiplications according input dimension n. As the input dimension increases, CCMM becomes progressively slower compared to PCMM.
Softmax
9.50
Factor
12
GK
9.25
Computation time (s)
10
9.00
8
Factor
8.75
6
8.50
8.25
8.00
7.75
0
128
256
512
128
256
512
Figure 9: Computation time comparison between Softmax and GK according to input dimension n. As the input dimension increases, Softmax becomes progressively slower compared GK.
H CLASSIFICATION ACCURACY AND PRECISION
Here, we present the classification accuracy and average precision our HE model during inference with fine-tuned weights, comparing the results with evaluation under plaintext. Based on these figures, we can conclude that the inference results under HE are closely aligned with those plaintext.
Table 16: Classification accuracy and average precision, compared with plaintext inference results. Since STSB not a classification task, we could not calculate the precision. Ace indicates how closely the class obtained from HE evaluation matches the class predicted in plaintext evaluation. HE inference results are similar to the results plaintext inference.
COLA
RTE
MRPC
STSB
SST2
QNLI
0.99
0.99
1.00
1.00
0.99
Avg prec. (bits)
-9.32
-13.48
-10977
-8.03
-11.15
-9.59
27


Reviews:
[{"review_id": "EVfJurbM9L", "reviewer": "Reviewer_YQ2M", "summary": "This paper presents optimizations to LLM architectures to make them more friendly towards Homomorphic Encryption evaluation. Concretely, first they propose to use LoRA for fine-tuning, where the data used for fine-tuning is given in encrypted form. This is useful to avoid re-training a lot of parameters, since LoRA focuses on updating only a few weights. This minimizes the amount of homomorphic operations w.r.t. plain fine-tuning. They also observe that LoRA is useful for reducing the dimension of homomorphic matrix multiplications. Secondly, they replace Softmax-based with Gaussian Kernel attention. They show that this is a simpler function to evaluate in HE, leading to significant savings with little impact in accuracy.", "questions": "For reproducibility, can the authors comment on the source code? Whether they intend to make it public for validation?\n\nAlso for reproducibility (and in lack of code), I am interested in understanding better the polynomial approximations used. In Section E the authors talk about penalizing the model in a \"pre-training stage\". I am not sure I understand how this would work, especially in the context of secure inference (no fine-tuning). What do the authors mean exactly? The model owner retrains the model using this new loss function? Most prior works take a pre-trained model, changing only its non-linearities by polynomial while keeping its weights. What are the authors proposing to do here? Does this require changing the model's weights? Re-training?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The problem statement is well motivated. Several works are currently exploring evaluation of LLMs under FHE, and the potential applications are also quite compelling. This is an extremely difficult task in terms of achieving viable efficiency, and any method that advances the state-of-the-art in this direction is welcome. The results achieved here show that several optimizations in other domains, that is, LoRA and the use of Gaussian Kernels, turn out to be useful for the evaluation of LLMs in FHE. I am not aware of this observation being made and explored in this depth in other papers (it is worth mentioning https://arxiv.org/pdf/2410.00433, which appeared after the submission deadline).", "weaknesses": "I am not particularly impressed by the novelty of this paper. It uses existing FHE tools with existing ML optimizations. This may not be a weakness on its own given the positive results of combining these techniques, but I still think the improvement factors may not be big enough for these techniques to become \"enablers\" of private LLM applications in practice. Put differently, I am not convinced that the gains here are a significant enough to overcome the blockers that prevent LLMs + FHE from becoming more widely spread.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sUu7CaFHyh", "reviewer": "Reviewer_f3Ds", "summary": "As LLMs surge, privacy issue becomes important considering government-level regulations. Among methods in privacy-preserving machine learning, homomorphic encryption (HE) can provide cryptographic security by computing over encrypted data directly without extra communication like MPC. However, HE is not efficient to compute matmul or non-poly operations in the transformer-level scale. This work focus on fine-tuning stage with LoRA and softmax variant to create HE-friendly transformer architecture.", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Compared to MPC approaches, n on-interactive property helps HE to be feasible to compute over large-scale LLMs without including considerable communication overhead among computing parties.\n2. This work has a great focus on the fine-tuning stage to make LLMs secure for users, which also concentrates on the key components like attention layers in the transformer, and it is also combined with SoTA techniques like LoRA to make the process more efficient.\n3. Writing with bottleneck-improvement pattern for LoRA and GK looks good for readers to figure out key ideas.", "weaknesses": "1. When you mentioned SoTA LLMs, you should notice that decoder-based models have been proved very powerful in generative tasks. After iteration of the recent few years, BERT series is not as useful and prevalent as decoder models. Hence, the significance to protect BERT-based model is less essential in the current LLMs.\n2. Although this work introduces how HE and CKKS work in the secure way, this work does not specify adversary model, such ability of adversaries, type of adversaries (e.g., semi-honest or malicious) and kind of attacks (e.g., member inference attack) this architecture counters with.\n3. In the conclusion, this work is too vague on the future work. For example, how cryptographic community develops helps the improvement of this work (e.g., any change on HE). Also, how LLMs itself evolve may change security issue based on this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "17OnMr2zVi", "reviewer": "Reviewer_EsSP", "summary": "This paper starts from the poor performance problem of homomorphic encryption (HE) in transformer architecture and focuses on optimizing the speed of HE in it. Specifically, the scheme tries to avoid CCMM computations to solve the poor performance brought by full fine-tuning. In addition, this paper aims to address the difficulty of evaluating under HE with Softmax, the core idea of which is to replace Softmax with a Gaussian kernel. Finally, this paper carried out many experiments, and the results show that their scheme is comparable to existing schemes in terms of modeling performance, while at the same time, the computational speed has been significantly improved. The overall narrative of the paper is clear, and has good logic.", "questions": "1.\tOne core idea of this paper to solve the difficulty of evaluating Softmax under HE is to replace it with Gaussian kernel, however, this method is very similar to that in the literature “Chen, Yifan, et al. Skyformer: Remodel self-attention with gaussian kernel and nystr\\\" om method. Advances in Neural Information Processing Systems 34 (2021): 2122-2135”. However, this paper does not describe the difference with this paper or even cite this literature. Is there a difference in the performance of the two? Furthermore, the polynomial approximation method of this paper seems to be very common way.\n2.\tIn Section 3, is the author's approach in solving Bottleneck 1 just an application of some existing methods? If not, please clarify the differences and improvements.\n3.\tDoes the use of LoRA and Gaussian Kernel affect the interpretability of the model? How does the author balance efficiency and explainability?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper is oriented to the problem of inefficiency of transformer architecture under HE, although the existing research has produced richer results. The main contribution of this paper is to enhance the speed of transformer architecture under HE, and the authors have carried out many experiments to verify the rationality and advantages of the scheme. I think the experiments in this paper are full, and the advantages of this paper are elaborated in terms of speed and model performance, which speed is emphasized in this paper. The experimental results are thorough and well-analyzed. Overall, this paper seems to incorporate some of the SOTA approaches in the current field and apply them to a widely researched topic.", "weaknesses": "1. Insufficient innovation. First, the topic chosen for this paper is a more widely studied one. Second, the solutions in this paper seem to be a direct combination and application of existing advanced schemes, and it is not intuitively obvious in the paper that the authors have improved on existing methods.\n2. The description in 2.1 does not seem to be consistent with Figure 1. Furthermore, why does the statement “LLM weights are protected in the strict cryptographic sense (line 149)” hold?\n3. Although the paper proposes a privacy-protecting LLM architecture, the security considerations of the model, especially against attacks and model theft, is insufficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)