HEPrune: Fast Private Training of Deep Neural Networks With Encrypted Data Pruning
Authors: Yancheng Zhang
Mengxin Zheng
Yuzhang Shang
Xun Chen
Qian Lou
Venue: NeurIPS 2024 poster (2024)
Keywords: Confidential Training
Privacy
Pruning
Cryptographic Computing
Primary area: privacy
TL;DR: Efficient confidential deep neural network training with encrypted data pruning

Abstract: Non-interactive cryptographic computing, Fully Homomorphic Encryption (FHE), provides a promising solution for private neural network training on encrypted data. One challenge of FHE-based private training is its large computational overhead, especially the multiple rounds of forward and backward execution on each encrypted data sample. Considering the existence of largely redundant data samples, pruning them will significantly speed up the training, as proven in plain non-FHE training. 
Executing the data pruning of encrypted data on the server side is not trivial since the knowledge calculation of data pruning needs complex and expensive executions on encrypted data. There is a lack of FHE-based data pruning protocol for efficient, private training. In this paper, we propose, \textit{HEPrune}, to construct a FHE data-pruning protocol and then design an FHE-friendly data-pruning algorithm under client-aided or non-client-aided settings, respectively. We also observed that data sample pruning may not always remove ciphertexts, leaving large empty slots and limiting the effects of data pruning. Thus, in HEPrune, we further propose ciphertext-wise pruning to reduce ciphertext computation numbers without hurting accuracy. Experimental results show that our work can achieve a $16\times$ speedup with only a $0.6\%$ accuracy drop over prior work. 
The code is publicly available at \href{https://github.com/UCF-Lou-Lab-PET/Private-Data-Prune}.

HEPrune: Fast Private Training of Deep Neural
Networks With Encrypted Data Pruning
Yancheng Zhang', Mengxin Zheng!,
Yuzhang Shang?, Xun Chen², and Qian Lou'
University of Central Florida
Illinois Institute of Technology
SSmmsung Research America
(yancheng.o zhang, mengxin. zheng, qla..iinnn.. louf edu; yshang40hawk. iit edu xunchen@ottlook..om
Abstract
Non-interactive cryptographic computing, Fully Homomorphic Encryption (FHE), provides a promising solution for private neural network training on encrypted data. One challenge of FHE-based private training is its large computational overhead, especially the multiple rounds forward and backward execution on each encrypted data sample. Considering the existence of largely redundant data samples, pruning them will significantly speed up the training, as proven in plain non-FHE training. Executing the data pruning of encrypted data the server side is not trivial since the knowledge calculation of data pruning needs complex and expensive executions on encrypted data. There lack of FHE-bbsed data pruning protocol for efficient, private training. In this paper, we propose, HEPrune, construct a FHE data-prumt tatt-pruning protocol and then design an FHE- Erie-frindly data- pruning algorithm under client-aided or non-client-aided settings, respectively. We also observed that data sample pruning may not always remove ciphertexts, leaving large empty slots and limiting the effects of data pruning. Thus, in HEPrune, we further propose ciphertext- wise pruning reduce ciphertext computation numbers without hurting accuracy. Experimental results show that our work can achieve a 16x speedup with only a 0.6% accuracy drop over prior work. The code is publicly available at https://gthubb.om/UU//LLoooo
CaarPrivatt---taaPiiii Data-Prune
1 Introduction
Machine learning, especially deep neural networks, has been widely applied in various domains, including healthcare [1, finance [2], and forth. Due the lack of expertise and computational resources, the average user often outsources the training task to the cloud servers in the machine- learning-as-a- -esv-sevvieeee (MLaaS) setting. However, the training data is often highly private and private, and it should not be directly shared because of business, legal, and ethical constraints. Private training enables the cloud server to train machine learning models on encrypted data, where strong privacy guarantees are offered by cryptographic primitives such as FHE 3
However, FHE-based private training is significantly hindered by its substantial execution time. For example, the encrypted training can be 1 3 orders of magnitudes slower than in the plaintext training [4] 5 [6) The high execution time primarily stems from the transformation of plaintext dataset into an encrypted format, along with the substitution of straightforward plaintext computations with more resource-intensive ciphertext operations. Reducing the number of data samples used for training could greatly accelerate the process. To optimize plaintext datasets, methods like dataset pruning commonly employed, where the model trainer has access both the dataset and model.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Dataset pruning involves analyzing data samples, calculating an importance score for each sample during training iterations, and discarding redundant samples streamline training. Prior research indicates that dataset pruning can enable machine learning model training on a fraction of the data sometimes as little as
minimal to no loss in accuracy
Pruning private datasets in encrypted form to accelerate training remains an open problem due to several challenges. First, calculating importance scores and sorting data samples for removal require complex encrypted computations, such as costly non-linear and sorting operations. For instance, calculating the importance score requires tracking changes in training dynamics [T] 12 such as logits, gradients, and losses-and and computing corresponding distances on encrypted data, all of which involve costly FHE operations. These high overheads that may offset- or even surpass- the potential benefits of dataset pruning. Second, plaintext-level data pruning used in the prior plaintext data does not always yield execution and eiphertext reduction benefits, as single ciphertext often contains multiple plaintext samples within its slots. Therefore, effective ciphertext pruning is critical to enable faster private training.
pruning g 9
In this paper, we propose HEPrune, the first encrypted data pruning framework for private training. We begin by constructing an encrypted data pruning method using pure FHE. To accelerate FHE- enabled data pruning, we introduce a homomorphic eneryption-friendl score (HEFS) to effectively evaluate the importance of data samples. To avoid costly FHE-based sorting, we propose client- aided masking (CAM) to identify less important samples while ensuring data privacy. To bridge the gap between sample-wise importance scores and ciphertext wise data, we develop ciphertext pruning (CWP) technique to reduce the number of ciphertexts during private training. We conduct experiments both training-front frommsccatcchh and transfer-learning settings. The proposed encrypted data pruning framework can accelerate private training by 16x with only a 0.6% accuracy drop.
2 Background
2.1 Fully Homomorphic Encryption- Private Training
Fully Homomorphic Encryption (F is a cryptographic primitive that supports arbitrary com- putation on encrypted data. An FHE workflow involves four functions: client-side KeyGen, Enc, Dec, and server-side Eval. For Eval, FHE natively supports homomorphic addition, subtraction, and multiplication between ciphertexts and plaintexts. denoted as H, E. and &, respectively. Non- linear functions such as the comparison function, max function, SoftMax function, and square root function can be approximated using polynomials. We denote these functions as HE. Cmp 13 14], HE.Maxt 14). ax and HE. respectively. FHE enables confidential training on encrypted datasets. While early works focused on training simple models on small datasets, such as linear regression and logistic regression models 17
18 19 20), recent research has advanced towards training deep neural networks (DNNs) using HE, Although HE provides theoretical data privacy guarantees, privately training DNNs on large encrypted datasets typically incurs substantial computational overhead. For example, training dense model for one step on a batch of 60 MNIST
samples can take over 1.5 days in FHESGD
line of research has been proposed to accelerate HE-enabled private training. Glyph [5] incorporates two HE schemes, TFHE and BGV, to enable private training in the transfer learning setting, allowing training of an MNIST mini-batch in only 0.04 hours. The most recent work, HETAL (6) achieves private training within 1 hour on the MNIST and CIFAR-10 10 datasets by using optimized matrix multiplication and GPU acceleration. While other cryptographic tools, such as Multi-Party Computa- tion (MPC), can also achieve private training, most existing MPC approaches 221 22 23 24 rely on a non-colluding server assumption, where multiple non-colluding servers are required to ensure security. Additionally, MPC-based methods typically incur significant communication overhead; training a LeNet model on the MNIST dataset, for instance, can generate approximately 500 GB of communication overhead [24). In contrast, FHE-enabled private training does not require the non-collusion assumption and incurs significantly less communication overhead.
2.2 Dataset Redundancy and Pruning
Not all data samples contribute equally to DNN training 25 some samples are less important and can be pruned during training. Training on only subset of data can effectively reduce computational

---

overhead while achieving generalization performance comparable to training on the full dataset [10] [T] Several methods have been proposed to identify the most informative data samples. Among g 9 10) are widely used for their simplicity and effectiveness. These
these, score-based methods 7
methods compute sample-win wise importance scores during training and select the most informative
samples based on these scores.
The importance score can be as simple as the entropy loss 8 10 for each sample. Another commonly used score is the forgetting score 77], which counts the number of "forgetting events" that occur for each sample during training, where a forgetting event defined as a change in the model's prediction for the same sample between two consecutive epochs. GraNd [9] uses the fo-norm of the sample-wiss wise gradient to represent sample importance, while ELN2 approximates GraNd by calculating the lg -n-mr of the error vector. Additional methods for identifying sample importance include submodularity-bon based methods like GraphCut (26) and gradient-matching matching-base -based methods like GradMatch [1].. These methods typically start with an empty set and gradually add samples, in contrast to score-based methods, where sample importance scores are computed simultaneously and independently.
Data pruning methods are generally divided into static and dynamic pruning methods. Static pruning refers to data pruning performed once before training 77 ( 9 26]. while dynamic pruning involves pruning data every few epochs during training [2 [0. Although these methods were designed with different motivations and target settings, they can be adapted for use in either setting. For
instance, [8] uses entropy loss in static setting, while [I] 10 apply it a dynamic setting. Similarly, dynamic pruning methods like [26] [2] can be adapted to static settings, as demonstrated by [27]. without losing effectiveness. this paper, we focus on dynamic pruning.
Test Accuracy(99)
96
HE mmmn)
10a
20
Runtime Acc
94
96
Accuracy(
#Ciphertext
150
120
Empty CT Sparse CT
94
20²
92
80
92-
Forget
ELN2
Entropy
No Pruning
10a
90
40
GraNd
90
50
70 90
Forget
Entropy
GradNd
EL2N
HEFS
1
2
3
5 6
Data Fraction(%)
#Remaining Sample
(b)
(c)
Figure I: (a). Test accuracy under various pruning fractions in plaintext dataset (ResNet-18 on CIFAR-10). (b) The encrypted training overhead and accuracy of different data pruning methods. (c) The distribution of data sample numbers in ciphertext after data pruning. Only small fraction of ciphertexts are empty with a naive sample-wise pruming.
Motivation. FHE-enabled private training provides a strong privacy guarantee for user data. However, private training remains significantly slower runtime compared unencrypted training. One primary reason for this is the large dataset size typically used for training, often comprising tens of thousands of samples. As shown in Figure [a), removing fraction of data during training has minimal impact on model accuracy: even with only 30% of the data, the accuracy drop is within 2%. However, directly applying plaintext data pruning methods to private training might not only fail to accelerate the process but could actually extend the training time. As shown in Figure [b), computing importance scores with existing methods- such as the forgetting score 77, entropy score [T] [O], GraNd [9. and EL2N [9- can introduce prohibitive overhead. This inefficiency arises because FHE natively supports only addition and multiplication, while existing data pruning methods often require range of non-linear operations. Although these non-linear operations can be implemented in FHE through lookup tables or approximations, these computations are extremely costly in FHE, potentially negating the benefits of data pruning. Furthermore, illustrated in Figure c), although existing methods can effectively prune samples from datasets, they do not necessarily reduce the number of ciphertexts in private training. This is because, during private training, single ciphertext can contain multiple samples. Naïvely applying sample-wise data pruning can lead to a large number of sparse ciphertexts that cannot be excluded from training.
Threat Model. We consider a private training scenario where client outsources model training to a cloud server. Our protocol is designed to allow a client to outsource model training while preserving the privacy of their data and model weights. The client's private dataset and model weights are treated as intellectual property that must not be disclosed to the server at any point. We assume the server is
3

---

semi-honest, meaning it will follow the protocol specifications but may attempt to gain unauthorized knowledge, such as the dataset and model weights. Sharing certain meta-information about training, such as the model architecture, dataset size, and early stopping signal, is assumed to be safe [6] Side-channel attacks are beyond the scope of this paper.
3 HEPrune Design
We begin by outlining the pipeline for private training with encrypted data pruning Section 3.1 In Section we provide details of our FHE-based data pruning algorithm. Specifically, we construct an encrypted data pruning baseline to demonstrate how sample importance evaluation and sample removal can be performed using pure FHE operations. We then enhance the efficiency of the data pruning algorithm through FHE-friendly scoring (HEFS) and client-aided masking (CAM). Finally, in Section 3.3 introduce ciphertext-wise pruning (CWP), which removes sparse ciphertexts and further accelerates the data pruning process.
Cpikereus
Eacryped
Ad
Rai
Enerypt
Bup
Treskee
Misi
Rat
Train år epechs
Suz
Madi
Adi
Sub
Rast
Max
Decrypt Model
Homomorphic Somple Scoring
Sample Masking
Ciphertext-wise Prusing
Operations
Figure 2: The overall workflow of private training with encrypted data pruning.
3.1
Pipeline of Private Training with Encrypted Data Pruning
has been widely studied how to perform the gradient descent algorithm in the encrypted state during FHE-enabled private training [4] ()). However, it remains unclear how data pruning can be incorporated into existing private training frameworks. We illustrate our FHE-based encrypted data pruning framework in Figure 2 During private training. O the client first encrypts the dataset with FHE and sends the encrypted dataset to the server. From this point forward, the dataset will never be decrypted. We refer to the encrypted data samples ciphertexts. To identify the most informative subset of samples, 2, the server first runs the forward pass algorithm on all ciphertexts to obtain the encrypted prediction vector P. 0 With P and the encrypted ground truth label Y, the server computes the sample-wise importance score S = H(x).. We propose an HE-friendly importance score in Section 3.2 @ With the importance score, the server can decide which samples prune. This is achieved by sorting the importance score and finding the threshold importance score H. corresponding to the pruning ratio (7). pruning mask is generated by comparing the importance score with the threshold as M = 1 (z) < H.). J. The unimportant samples can be masked by simply multiplying the ciphertexts with the corresponding masks. To fully reduce the number of ciphertexts, the server performs siphertextwwist pruning according to the current pruning mask. G The server performs backpropagation algorithm on the pruned ciphertexts for AT epochs, and then @ starts new round of the data pruning algorithm to update the training subset. ? At the end of private training, the server sends the encrypted model back to the client, and the client decrypts the model.
We formalize the above workflow into an encrypted data pruning protocol in Figure Sli Appendix Our protocol is the first of its kind to introduce data pruning to private training and is an enhanced private training framework with encrypted data pruning extension over existing works [4] 5 6).
Additionally, our protocol can work in both the transfer learning setting [5] 6 and training-frome scratch setting [4. Our protocol is fully compatible with the early stop techniques adopted in [6]. As in (6), sending meta information during training allowed our protocol, such as the logits, early stop signals, and importance scores. The privacy of data and models is strongly guaranteed as they are encrypted and never decrypted by the server. We first instantiate a baseline of encrypted data pruning using only FHE operations in Section 3.2 and then propose HEFS and CAM to optimize the overhead of the encrypted data pruning algorithm. In Section 33. we propose CWP to effectively reduce the number of ciphertexts involved in training and thus boost the efficiency of private training.

---

3.2 HE-enabled Data Pruning
While FHE can support arbitrary computation on encrypted data, computing non-lineal functions is typically expensive. Applying existing data pruning methods to private training can lead to additional overhead that negates or even exceeds the benefits of performing data pruning. For the entropy- -aseed methods 8
11 1Q], although the entropy loss is typically considered cost-free in the plaintext, not explicitly computed curing private training- Instead, we compute the gradient directly without calculating the loss itself, as illustrated in Figure step 3(b). Computing the entropy loss in FHE requires approximating the logarithm function, which is computationally expensive. The forgetting score 7 is simpler to compute, requiring only comparison operations between the current prediction and prediction from the last epoch. However, the forgetting score cannot be easily made dynamic, as it usually requires calculations over the full dataset for multiple epochs. The most viable existing data pruning method is the EL2N 191, which simply utilizes the prediction and label Y. Although originally proposed static pruning method, we find that EL2N also remains effective a dynamic setting, similar to the entropy score [TO]. We first instantiate an FHE-enabled data pruning algorithm, detailed in Algorithm 1 based the dynamic version of EL.NN (HE2LN). Subsequently, we demonstrate that even E1.2N remains computationally expensive in the encrypted state and propose the HE-friendly score (HEFS) and client-aided masking (CAM) accelerate the encrypted data pruning.
Algorithm I: Homomorphic Data Pruning
Input
The encrypted dataset D = {X;, Y, Y and the model M with weights W, the pruning ration p. the sample number N and the target class number
Output TThe pruned enerypted datasct D' { i Y
100--1, where C' S.
for
to C- do
P. - (M.SS W)):
// Evune.Eval
eFr: - P. Y::
// compute error vector
eFr; <- cřr; cřr;:
CrT err_šum,; = eTrs
for j 0 to log
do
Err - < Rotattatre Sum, 2'); err err_3um; + err err_ E err_ti
score; (IEESqt((err_smm))
// compute the importance score
8 score +- 0):
// Prune. Remove Remove
B + N/ C;
for + to C 1 do
for
B
s_score;ct; < HE. (sttttttt((sc)r..)))
// extract sample-wise scores
for to N do
for j f 0 to do
less +- Hm.Cmp(s scorss, s_score;);
// sort the sample-wise scores
(s_ (s_score,) t (less i score,) H ((1 Bess)) M s_oooe::):
(s_score,) (less & scooe); ((1 B less) s_score;);
Urreshold inder N p:
Ø + for i + to C do mäsk < HE. CtpcCcmmpp....... 0): (X,, Y.) (mask 00 @ ((18 mäsk) & (X., Y.));
// remove unimportant samples
return 1'' +- X Y C-
The EL2N score is defined as H(x) Ew, Ip[[;; w.) - vll2, where p(z; wa) the prediction vector for sample x and y the corresponding ground truth label. In essence, the EL2N score is the f--morm of the eтror vector, which can be computed via pure FHE operation as shown in Algorithm T We first compute the prediction vector by encrypted forward pass. The HE.SoftMax in the forward pass is evaluated by polynomial approximation [15] and domain
HEL2N Baseline.
extension technique 28). Computing the forward pass in the encrypted state the same as existing private training frameworks (6). With the encrypted prediction vector P and the ground truth label
5

---

Y, we can compute the EL2N score homomorphically. Specifically, we first compute the sum of squares over the error vector, which requires homomorphic subtraction, multiplication, and rotation. Then we take the square root of sum of squares to compute the f2-norm of the error vector. While HErtqrt can be implemented via Newton iterative algorithm [T6], the overhead is prohibitive as the Newton iterative algorithm needs ~ 10 iterations to compute an accurate square root. Additionally, the Newton iterative algorithm in FHE involves considerable ciphertext-ciphertex multiplication. This leads to a large number of additional relinearization and bootstrapping operations. A single square root over a ciphertext can take up to minutes.
HE-friendly Score. Simple as the EL2N score is, using it to evaluate the importance of data samples in the encrypted state can still incur prohibitive overhead due its complex non- non-linearity. We propose an HE-ffrienlly importance score (HEFS) to address this issue. We first derive the formulation of HEFS, and then demonstrate how it can be computed via pure FHE operation. To determine how a single data sample affects the training, we can quantify the importance of a sample by the difference of the gradient before and after removing a sample. Denote the gradient of a sample (z, y) over the weights at time gr (x, v) V.,, ((p(w;11, v). Given minibatch of B samples S (1 ) ),==0' the importance of a sample can be quantified by the difference of the time derivative of the loss function, A before and after removing the sample from the
minibatch. The difference of the derivative is bounded by the sample's gradient [9]. Specifically, let
S-k = S. {Ixx } be the set after removing a certain sample (zy, yz). For V(I,, Vt) E S and i if k. it holds that
(A,,, ((),, - - U1). S-2)ll S ell (2). 81]1
EL22N approximates the fz-norm of the gradient by the f2-norm of the error vector. We further streamline the EL2N score using the f--ormm More formally, we define the HEFS as:
Algorithm 2: Client-aided Sample Pruning
Input
:he pruning ratio p. The server holds the
enerypted dataset 5 = (X,, V:)
and encrypted score scØre and the client holds the secret key SK.
H((x)= Ew, [lp(2; w)) 8/11
(2)
Output :The pruned encrypted dataset D'= (X',, 1'' where C' S C.
HEFS can be efficiently computed during pri- vate training. Specifically, the circuit for HEFS consists of only two FHE subtractions and one max operation, which can be computed as:
Client:
score 4- HE. Dec(scurre, SK);
0 QuickSelect( (score, p);
mask t- Compare(score, 0): Sends mask to the server;
score HE. (Y P) (PE()))
(3)
In the above equation, the homomorphic subtrac- tion significantly faster than other FHE op- erations. HE.Max can be effectively computed via HE.Cmp. While the ME.Max operation has the same time complexity as HE. Cmp, the con- crete runtime of HE. is even more efficient, typically 1.5 ~ 2x faster under the same pa- rameter setting [4]. The proposed HEFS is a close approximation to the original EL2N score, which guarantees the effectiveness of the HEFS- based data pruning. We show the accuracy of return D'
Server:
D' D: for +- 0 C do if mask; == 0 then D' + D' \ ((x,, Pil // remove
empty ciphertext
else
(X,, Y) t- mask. & (X,, Yi);
// remove unimportant samples
the data pruning using HEFS in Section 4
Client-aided Masking. After evaluating the importance of each data sample, we need to remove the less informative ones from the training set. This requires the server to sort all importance scores homomorphically to determine the threshold of important scores, H. Given a dataset with N data samples, O(N2) homomorphic comparisons are needed. Since N is typically large for machine learning model training, such sorting incurs prohibitive overhead in the encrypted state, which can offset the benefits of data pruning or even prolong the total training time. To effectively identify and remove the less important data samples, we propose client-aided masking (CAM) in Algorithm 2 We offer an analysis on the computation, communication overhead, and security implications as follows.
Efficiency. In contrast to the heavy server-side homomorphic sorting, finding H. is extremely fast on the client's 's side, with only O(N) runtime via the quick select algorithm. In practice, this process takes only 15 ms on the CIFAR- 10 dataset. Additionally, the communication overhead is minimal.

---

For the CIFAR-10 10 dataset with 43, 750 training samples, only 2 CKKS ciphertexts are needed to transfer the encrypted importance scores when the slots are fully utilized. This incurs only MB of communication overhead. For comparison, the early stopping signals used to determine early stopping incur MB communication overhead when transferring the enerypted logits (6]
Security. Directly asking the client to decrypt and reveal the model weights and datasets to the server clearly breaches the client's privacy and is therefore prohibited. However, exchanging meta information about training does not directly compromise private information and is typically permitted. For instance, HETAL [6] allows the server to send the logits of the validation set to the client, who then computes the loss and determines whether to stop training early. Such exchanges of meta information are crucial ensure the effectiveness of private training. Further details can be found in Appendix B
Prumee Ciphereetts EV
Sect Sparily
Pry
Clpkerech P
Prasing Mark.M
Spandiy
Clakerest Queas
Merge Spor Ciphertests
Figure 3: Example of ciphertext wise pruning.
3.3 Ciphertext-wise Pruning
While the HEFS and CAM make the encrypted data pruning algorithm much more practical, the resulting ciphertexts remain largely sparse, thus limiting the training time acceleration. To this end, we propose ciphertext-wise pruning to effectively reduce the number of ciphertexts involved in training, as illustrated in Figure which further boosts the efficiency of the private training. We detail the steps of ciphertext pruning in Algorithm B Without loss of gen- erality, we refer to all the slots occupied by single sample within ciphertext as a sample slot. Once the server obtains the pruning mask, ciphertext-wise pruning can be performed with- out client involvement.
Algorithm 3: Ciphertext-wise Pruning
Input
:The encrypted dataset
D (X,, Y: and pruning masks
mask (M, } ==0 C-1 where
M, E {0, 1] and B is the number of samples in each ciphertexts. Output :The pruned encrypted dataset
D = (X's, 1'
C' where C' S.
D' for t C do
spasity +- B Enz MD]: // compute
the ciphertext- wise sparsity
queue + Sort(spasity,, D, mask); at queue + Trim ct_qqeue);; while at ___qqueeei_ssare
do drrrm et muequuueeppppp pro_front()):
We denote the number of samples in each ci- phertext as and M, is a Boolean array that indicates whether each of the B samples should be pruned.0 The server first computes the spar- sity of each ciphertext, which is done by simply counting the number of 0-s in each M, @ Af- ter computing the ciphertext-wise sparsity, the server can sort the ciphertexts along with their corresponding masks. We represent the sorted ciphertexts in a dequeue. To perform ciphertext- wise pruning, the server first identifies two ci- phertexts at front and ctaack from the queue. O After removing the full ciphertexts and empty ciphertexts from the queue via Trim(), we then leverage the most sparse ciphertext cttack fill in the empty slots in the least sparse ciphertexts front. The key step is to align samples in ctaack with the empty slots in front The function FZero() returns the index of the first empty sample slot slolempty in el front, sets the corresponding mask to 1, and decreases the sparsity of el front by 1. Similarly, FŌne() returns the first non-empty sample slot slotused in cloack and sets the corresponding mask and sparsity. By taking the difference of slot and slotempty. the server can
cbback t queeeepuppppppoooo pop_hock();
slotempty + FZero (ct fronr);;
slotused + FaneFFOnecacoc (ctoock);
k +- stobuaed slobempty: clatgnn t- Mask( cl florr +- -.l (I) HE. Rot(clatiin k); if ct prueue.is_emptee
V
ct front sparsity == 0 then
D' + DD fctfroos.ctf;
clse
pushh frontss_oo((ttoooon)) dt queue. push baclbbbcc((looo
return D'
7

---

determine how much the cleack should be rotated to align with front. We mask out the other slots in chack and obtain caaign and keep only the first sample slot slotused. This ensures only the empty sample slot in et front is filled and the non-empty slots in front will not be corrupted. Then, clatign rotated and added to et fromt to fill in the empty slot ef front. After merging the two eiphertexts, if et front is full or there are no remaining ciphertexts to merge, the server adds it to the final set D'. We defer the details about Trim(). FZero() FFone)) and Mask() to the Appendix D We remark the pruning mask generated by CAM is not encrypted, while enables efficient operations related the pruning mask without invoking heavy FHE computation.
4 Experiments
4.1 Experimental Setup
Models and Datasets. To demonstrate the generalizability, we evaluate the proposed encrypted data pruning methods in two settings, the transfer learning setting as in HETAL [6] and training- from-scratch setting as in FHESGD [4]. For the transfer learning setting, we adopt the same feature extractors [6], the pre-trained ViT Base [29] model and the pre-trained MPNet Base [30] model. The client first extracts samples into a 768-dimension feature and then encrypts the features. The server performs private training the encrypted features. For the training- from-scratch setting, the client encrypts the raw dataset directly, and the server performs private training on the encrypted dataset. We use 3-layer MLP, with two hidden layers of dimension 128, which is a widely used structure in the private training setting [4] 21 We perform encrypted data pruning on four widely used image datasets: MNIST (31], CIFAR-10 10 32) Face Mask Detection [3), DermaMNIST [4] for image classification and one audio dataset SNIPS (35] for sentiment analysis. We partition the datasets training, validation, and test set. The size of the training set and validation set is 7: 1. We
defer the number of samples in each set in the Appendix
System Setup and Implementation. We the RNS version of the CKKS 36 homomorphic encryption. We use the bootstrapping method for CKKS in 38 Our implementation is based on the OpenFHE [39] library. For HE parameters, we set the cyclotomic ring dimension as N = 26 and ciphertext modulus 1555 bits to guarantee a security level of 128-bit under the Homomorphic Encryption Standard [40] Each ciphertext has N/2 32768 slots and we set the multiplicative depth as T, = 12. All experiments were conducted using an AMD Ryzen Threadripper PRO 3955WX processor operating at 2.2GHz, equipped with 125GB of memory. We use the Single- (SIMD) technique [41] to fully utilize the ciphertext slots and amortize the cost of homomorphic operations. Under SIMD, multiple data samples can be coded into one ciphertext. We adopt the most efficient encoding methods proposed in 16, 42). For nonlinear operations like SoftMax and ReLU, we adopt approximation based methods. We report the CPU version of HETAL, as their GPU implementation is not publicly available.
37 scheme for
4.2 Results
End-to-end performance. As shown in Table 1 we compare the end-to-end training time and accuracy on five datasets with HETAL [6] and an unencrypted baseline. HETAL is known to be the most efficient full-data private training framework. For fair comparison, we unify the batch size as 128. For HETAL, we maintain the security parameters used in their original paper. For the proposed encrypted data pruning method, we set the pruning ratio as p 0.9, i.e., only 10% of the data remains for training in each epoch. The total training time is reduced by ~ 6.6x across datasets. The accuracy drop as small 0.25% on the Face Mask Detection dataset. With encrypted data pruning, the accuracy is even 0. 14% higher than the unencrypted baseline and HETAL.
Table 1: End end comparison across different datasets The pruning ratio is set as p = 0.9.
Method
MNIST CIFAR-10
SNIPS Face Mask Detection DermaMNIST
Unencrypted
Acc(%)
95.6910.02
96.62.0.02
95.4610.06
75.91
94.43
Acc(%)
96.27.0.02
96.57
95.4640.05
76.0620.18
95
HETAL
Runtime(h)
276.75
293.3
32.88
101.55
113.7
Acc(%)
95.54
96.31 40.06
95.21 +0.00
75.8644..1
95. 95.144a.us
Ours
Runtime(h)
41.89
44.76
5.02
15.5
17.36
8

---

Table 2: Effectiveness of the proposed method. We tested different private training methods on the CIFAR-10 dataset, with a pruning ratio = 0.9. Communication is the size of logits and importance score ciphertexts server sends to client for early stopping and data pruning.
Method
Accuracy(99) %)
Runtime(h)
Speedup
Communication(MBB)
Full Data(HETAL)
96.57
293.3
x1
18.1
Prune Baseline
90.9
488.91
x0.6
18.1
Cliient Aided
96.16.0.07
196.91
x1.49
22
+HEFS
96.31
105.57
x2.78
22
+Ciphertext-wise Pruning
96.31
44.76
x6.55
22
Effectiveness of the proposed methods. In Table we demonstrate the effectiveness of each proposed technique. We start by training on the full CIFAR-I0 dataset using the framework of HETAL. For the encrypted data pruning methods, we fix the pruning ratio as p 0.9. In the prune baseline, we naively apply plaintext data pruning method to HETAL, which prolongs the total training time. Sorting 43750 importance score in CIFAR-I0 can take more than 200 hours. which offsets the benefits of data pruning. By incorporating the client-aided masking, the server can remove the unimportant samples more effectively. The client-aided methods speed up the private training by 1.49x with a 0.41 % accuracy drop. The communication cost increases slightly by approximately 1.2x. Yet, as the EL2N score involves costly square root computation, the speed-up modest. By incorporating HEFS, we improve the overhead during importance score computation. With HEFS, the private training can be accelerated by 2.78x. The HEFS also achieves a 0.2% higher accuracy. When ciphertext-wist pruning is applied, the runtime speed-up is the most significant, achieving 6.5x speed-up over HETAL with only 0.2% accuracy drop.
Acc
No Pruning
HE Time(min)
250
96.8
250
96.6
200
0
HE Time
200
96
Accura
150
96.2
150
94
100
96.0
100
92
50
35.8
50
90
1
5
10
20
40
50
60
70
80
90
5
10
20
40
50
60
70
80
90
88
Data (raction(%)
Data Fraction(%)
(a) Different pruning ratios on CIFAR-10
(b) Different pruning ratios on MNIST
Figure 4: Private training time and accuracy with different fractions of data of (a) CIFAR-10 dataset
and (b) MNIST dataset
Ablation on the pruning ratio. In Figure we demonstrate the effectiveness of the proposed encrypted data pruning method under different data pruning ratios. In Figure 4 (a), we demonstrate the training time and accuracy achieved using different fractions of the CIFAR- 10 dataset. Surprisingly, we find that even using only 1% of the data, the accuracy drop is only around 0.6%, and the training can be sped up by 16x, Training with the 40% 70% of the data even leads to higher accuracy than training with the full dataset. The same phenomenon is observed in plaintext data pruning 19]. This is because some noisy or low-quality samples are excluded from training while retaining enough informative samples are maintained. We note that we can achieve 2.2x speed up when training with 40% of the data without any loss of accuracy on the CIFAR-IO dataset. Figure 4 (b), we experiment with the MNIST dataset and observe similar trend. On the MNIST dataset, using only 1% of the data achieves 91 01.29% accuracy with ~ 15x speed-up. Yet. using 5% of the data achieves a significantly higher accuracy of 95.2%, which only 0.5% lower than training with the full dataset.
Table 3: Privately Training an MLP from scratch under different data pruning ratios.
Method
1%
5%
10%
20%
40%
50%
60%
70%
80%
90%
Acc(%)
93.23
97.12
97.39
98.38
98.52
98.55
98.5
98.48
98.45
98.45
Acc.
Acc.
-5.26
-1.37
-1.1
-0.11
+0.03
+0.06
+0.01
-0.01
-0.04
-0.04
Time(h)
32,25
110.61
208.56
404.46
796.26
992. 16
1188.06
1383.94
1579.88
1775.72
Runtime(h)
speed up
60.8x
17.2x
9.4x
4.8x
2.5x
1.9x
1.7x
1.4x
1.2x
1.1x
Training from scratch. We show the performance of enerypted data pruning in the training from scratch setting in Table
We train 3-layer MLP on the MNIST dataset. We set the pruning

---

frequency as 10 epoch. When training with only 1% data, the end-to-ene training time could be 60.8x faster with an accuracy drop of 5.26%. Increasing the training data fraction can effectively improve the test accuracy. When using 40% and 50% fraction of data, the training accuracy is 0.03% ~ 0.06% higher than training with the full dataset. We remark that warm-start strategy can also improve the test accuracy.
5 Discussion
Broader Impact. In this paper, we propose a framework that enables encrypted data pruning during confidential training. The proposed techniques can accelerate the private training without sacrificing the model accuracy. By incorporating data homomorphic friendly data pruning techniques, our framework makes the HEö-nnalled private training more practical while ensuring the data privacy.
Limitations. (1) More Model Support. Currently, the proposed methods have only been applied to simple models like MLP. Extending the encrypted data pruning to private training larger models like CNNs and Transformers can enhance its utility. (2) More Dataset Support. In this paper. we have experimented relatively small datasets. Extending to larger datasets will enhance its utility.
6 Conclusion
The paper presents a novel framework for encrypted data pruning aimed at enhancing private training of deep neural networks. Plaintext data pruning methods offer limited benefits in encrypted settings due to their lack optimization for cryptographic processes. Our approach introduces crypto-oriented optimizations, including HE-friendly score, client-aided masking, and ciphertext wise pruning, which effectively harness the potential of data pruning, achieving up to a 16-fold acceleration in training times without compromising accuracy.
References
[1] Dinggang Shen, Guorong Wu, and Heung-ll Suk. Deep learning in medical image analysis. Annual review of biomedical engineering, 19:221-248, 2017.
[2] Matthew F Dixon, Igor Halperin, and Paul Bilokon. Machine learning in finanee, volume 1170. Springer, 2020.
[3] Craig Gentry. Fully homomorphic encryption using ideal lattices. Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 169-178, 2009.
[4] Karthik Nandakumar, Nalini Ratha, Sharath Pankanti, and Shai Halevi. Towards deep neural network training on encrypted data. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops, pages 0-0, 2019.
[5] Qian Lou, Bo Feng, Geoffrey Charles Fox, and Lei Jiang. Glyph: Fast and accurately training deep neural networks on encrypted data. Advances in neural information processing systems, 33:9193-9202, 2020.
[6] Seewoo Lee, Garam Lee, Jung Woo Kim, Junbum Shin, and Mun-Kyu Lee. Hetal: Efficient prevcccprsserving transfer learning with homomorphic encryption. In International Conference on Machine Learning, pages 19010-19035. PMLR, 2023.
[7] Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J Gordon. An empirical study of example forgetting during deep neural network learning. arXiv preprint arXiv: 182.0559, 2018.
[8] Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. arXiv preprint arXiv: 1829, 2019.
[9] Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on data diet: Finding important examples early in training. Advances in Neural Information Processing Systems, 34-20596-20677. 2021.
10

---

[10] Truong Thao Nguyen, Balazs Gerofi. Edgar Josafat Carrinez-NNoiegar François Trahay, and Mohamed Wahib. Kakurenbo: Adaptively hiding samples in deep neural network training.
Advances in Neural Information Processing Systems, 36, 2024.
[11] Ziheng Qin, Kai Wang, Zangwei Zheng, Jianyang Gu, Xiangyu Peng, Zhaopan Xu, Daquan Zhou, Lei Shang, Baigui Sun, Xuansong Xie, et al. Infobatch: Lossless training speed up by unbiased dynamic data pruning. arXiv preprint TrXiv:2303.04444 2023.
[12] Krishnateja Killamsetty, Sivasubramanian Durga, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. Grad-match: Gradient matching based data subset selection for efficient deep model training. In International Conference on Machine Learning, pages
PMLR, 2021.
[13] Jung Hee Cheon, Dongwoo Kim, and Duhyeong Kim. Efficient homomorphic comparison methods with optimal complexity. In Advances in Crypholgyy-SSAARTII national Conference the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part 26, pages 221-256, Springer, 2020.
2020: 26th Inter-
[14] Eunsang Lee, Joon- Woo Lee, Jong-Seon No, and Young- Sik Kim. Minimax approximation of sign function by composite polynomial for homomorphic comparison. IEEE Transactions on Dependable and Secure Computing. 19(6)377113772) 2021.
[15] Joon-Woo Lee, HyungChul Kang, Yongwoo Lee, Woosuk Choi, Jieun Eom, Maxim Deryabin, Eunsang Lee, Junghyun Lee, Donghoon Yoo, Young- Sik Kim, et al. Privacy-preservnn machine learning with fully homomorphic encryption for deep neural network. iEEE Access, 10:30039- 30054, 2022.
[16] Hongyuan Qu and Guangwu Xu. Improvements of root, Available SSRN 4258571.
homomorphic evaluation of inverse square
[17] Valeria Nikolaenko, Udi Weinsberg, Stratis loannidis, Mare Joye, Dan Boneh, and Nina Taft. Privacy-preserving ridge regression on hundreds of millions of records. In 2013 IEEE symposium on security and privacy, pages 334-348. IEEE, 2013.
[18] Hao Chen, Ran Kristin Lauter. Logistic regression over encrypted data from fully homomorphic encryption. BMC medical genomics, 11: 11:3-12, 2018.
Kyoohyung Han, Zhicong Huang, Amir Jalali, Kim Laine, and
[19] Andrey Kim, Yongsoo Song, Miran Kim, Keewoo Lee, and Jung Hee Cheon. Logistic regression model training based on the approximate homomorphic encryption. BMC medical genomics, 11:23-31, 2018.
[20] Miran Kim, Yongsoo Song, Shuang Wang. Yuhou Xia, Xiaoqian Jiang, et al. Secure logistic regression based on homomorphic encryption: Design and evaluation. JMIR medical informatics, 6(2)ce8805, 2018.
[21] Payman Mohassel and Yupeng Zhang. Secureml: A system for scalable privacy-preserving machine learning. In 2017 IEEE symposium on security and privacy (SP), pages 19-38. IEBE, 2017.
[22] Payman Mohassel and Peter Rindal. Aby3: A mixed protocol framework for machine learning. In Proceedings of the 2018 ACM SIGSAC conference computer and communications security, pages 35-52,20 2018
[23] Sameer Wagh, Shruti Tople, Fabrice Benhamouda, Eyal Kushilevitz, Prateek Mittal, and Tal Rabin. Falcon: majosty maliciously secure framework for private deep learning. arXiv preprint arXiv:2004.022299 2020.
[24] Jean-Luc Watson, Sameer Wagh, and Raluca Ada Popa. Piranha: A (GPU) platform for secure computation. In s1 USENIX Security Symposium (USENIX Security 22), pages 827-844, 2022.
11

---

[25] Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International conference on machine learning, pages 2525-2534. PMLR, 2018.
[26] Rishabh Iyer, Ninad Khargoankar, Jeff Bilmes, and Himanshu Asanani. Submodular combina- torial information measures with applications in machine learning. In Algorithmic Learning Theory, pages 722-754. PMLR, 2021.
[27] Chengeheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: A comprehensive library for coreset selection in deep learning. In International Conference on Database and Expert Systems Applications, pages 181-195. Springer, 2022.
[28] Jung Hee Cheon, Wootae Kim, and Jai Hyun Park. Efficient homomorphic evaluation on large intervals. IEEE Transactions on Information Forensics and Security, 17:2553-2568, 2022.
[29] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition scale. arXiv preprint arXiv:2010. 1929, 2020.
[30] Kaitao Song, Xu Tan, Tao Jianfeng Lu, and Tie- Yan Liu. Mpnet: Masked and permuted pre-training for language understanding. Advances in neural information processing systems, 33:16857-16867, 2020.
[31] Li Deng. The mnist database of handwritten digit images for machine learning research [best of the web]. IEEE signal processing magazine, 29(6):141-142, 2012.
[32] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[33] Larxel. Face mask detection, 2020. Accessed: May 20, 2024.
[34] Jiancheng Yang. Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni. Medmnist v2-a large-scale lightweight benchmark for 2d and 3d biomedical image classification. Scientific Data, 10(1):4) 2023.
[35] Alice Coucke, Alaa Saade, Adrien Ball, Théodore Bluche, Alexandre Caulier, David Leroy, Clément Doumouro, Thibault Gisselbrecht, Francesco Caltagirone, Thibaut Lavril, et Snips voice platform: embedded spoken language understanding system for private-by-design voice interfaces. arXiv preprint arXiv: 10190, 2018
[36] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In Advances in Crypooloy-ASIACRRI/ 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings. Part 23, pages 409-437. Springer, 2017.
[37] Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. A full mss variant of approximate homomorphic eneryption. In Selected Areas in Cryptography-SAh 2018: 25th International Conference, Calgury, AB, Canada, August 15-17, 2018, Revised Selected Pupers 25, pages 347-368. Springer, 2019.
[38] Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. Bootstrapping for approximate homomorphic encryption. In Advances in Eeypollgy-EUROCCAA Annual International Conference on the Theory and Applications of Cryplographic Techniques, Tel Aviv, Israel, April 29-May 3, 2018 Proceedings, Part 1 37, pages 360-384. Springer, 2018.
2018: 37th
[39] Ahmad Al Badawi, Jack Bates, Flavio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Micciancio, Ian Quah, Yuriy Polyakov, Saraswathy R. Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. Openfhe: Open- source fully homomorphic encryption library. Cryptology ePrint Archive, Paper 2022/915, 2022. https://eprine iacr. otgp//22//9211
12

---

[40] Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, et al. Homomorphic encryption standard. Protecting privacy through homomorphic encryption, pages 31-62, 2021.
[41] Nigel P Smart and Frederik Vercauteren. Fully homomorphic simd operations. Designs, codes and cryptography, 71: 2014.
[42] Eric Crockett, A low-depth homomorphic circuit for logistic regression model training. Cryp- tology ePrint Archive, 2020.
[43] Baiyu Li and Daniele Micciancio. On the security of homomorphic encryption on approximate numbers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 648-677. Springer, 2021.
13

---

Appendix
A Encrypted data pruning protocol
In this section, detail the proposed encrypted data pruning protocol. The main overhead associated with performing performing encrypted data pruning is determined by Step 3.(d) in Figure 5
Parties:
Client C, Server S.
Input: C' holds private dataset D, with N samples and labels {(X,, ! Output: C' learns a trained model M and learns nothing.
Protocol:
1: enccyypi the dataset with HE. Enc, and sends encrypted dataset Y.) to server.
2: S initializes M with random parameters Wo and chooses the hyperparamerters for training: the learning rate y,. pruning ratio and the pruning frequency Ar.
3: For each epoch r, repeat the following:
(a) S performs forward pass homomorphically: P HE.SoftMax(M((X ())
(b) S computes gradients and updates model:
W++1 W, V/ where Lw (P (P-
(c) S sends P to C, C determines early stop.
(d) If (T mod Ât = 0), S performs data pruning follows:
(i) 9 computes the importance score: score Prune.Evall P, Y)
S sends score C, can C computes pruning mask mask.
(iii) S removes unimportant samples: D' Prune. Remove D, mask)
(iv) Continue step 3(a) train the model the pruned dataset 5' (X', y'
4: S sends the trained model M with encrypted optimal weights W to C. C decrypts the model with
HE. Dec and obtain the final model M with optimal plaintext weights W"
Figure 5: Private Data Pruning Protocol.
B Analysis of Client-aided Masking
In this section, we offer more details about the proposed Client-aided Masking (CAM).
The main privacy issue is that (1) the server may learn private information based on the meta information, (2) the server may crack the secret key. Exposing the pruning mask mask to the server only reveals the location of unimportant data samples, while all samples are still encrypted by HE, hence the server still learns nothing about the data sample itself, which avoids the security issue (1). One of the most recent and well-known attacks is the IND-CPA+ [33. However, it operates under the assumption that the server can ask the client to decrypt specific ciphertexts. The assumption not upheld in Algorithm 2 Since the server not specify the ciphertext to be decrypted and that the client only sends the server the resulting mask, rather than the decrypted scores.
The communication depends on the level of ciphertexts. As shown in Table the lower level the ciphertext is at, the smaller the ciphertext is. Therefore, the server can set the ciphertext to L to reduce the communication overhead.
Table 4: Ciphertext sizes under different levels.
N N=24 2
L=0
L
=
L
Ciphertext Size(MB)
1.01
2.03
3.02
4
5,02
14

---

Algorithm 4: Ciphertext-wise Pruning
Input
The encrypted dataset (X;, Y; ) and pruning masks mask = {M: [C-1 where M, E {0, 1 and B is the number of samples in each eiphertexts.
Output TTee pruned enerypted dataset D' (X', Y ) where C' S.
D'
for i c t C do spasily; +- -5 M:
// compute the ciphertext-wise sparsity
ct_queue Sort(spasity, D, mask); while ct ct__qeueeis__nn ciaiiis__tteetty((l do
ct_front + li_queue.poo-frottee // The Trim() removes full and empty ciphertexts from the cl_queue
if ct front.sporsity 0 then
D'+ D'U fct_front.ct):
continue;
break;
hile et siueue.s__ot_emppeee of et_back + ot rd_queue.pop. :: if cl back.spersil = B then
do
continue;
clse
pwwhhuushhhhhhpkcooe break:
while et queue.is _no emplyy( do
diroont et queue.pop rom_o
clbuck + ct__ueueeppppbeeee slotempty t 0;
// The FZero() returns index of the first 0 in of front
for slot + + B do
if ct fr_ffott.mmsssllol = 0 then
slotempty slot;
at fr_ooot.mashi [slot] +- 1;
ct donoront.parar
1:
slobuced 0:
// The FOne() returns index the first cleack
for slot <- to do if ct ba..o..mmssssssoo = 1 then
stot.sed slot;
ct_ dt_back.mar meae.mmskksslll slot +- 0:
ct_ d__back.spar sparsity += 1:
slotused 1a.FFOnecctaan (ctaacc))) k + slotused slotemptyi
M. < [0]
11 The Mask() keep only the sample at slubused in clanck
Mi Mi(stobused] +-
ctalign t ctbock 8 M.;
frott front + HE.HE.RRR NHE.Rot(ctaalgn k);
if ct wtt__queeesssse_ee (euepe.sseeppt(() V sporrsiiitittt then
D' D D'U (cl else pusqueue.puhh_ ctt.cpuuussoooo(ttooa)))
queue. push back back(clsaa (claack);
return D'
C
Datasets and Hyperparameters
We detail how we divide the training set, validation set and test set in Table For all tasks, we use batch size 128. For the transfer learning setting, we use learning rate 0.5 and set the pruning frequency every A, epochs. For the training from scratch setting, we use leaning rate of
15

---

0.1 and set the pruning frequency every A, 10 epochs. Prior works [9 12 adopt warm start strategy, which trains the model for 10 20 epochs on the full dataset. The warm start period is computation intensive as it uses the whole dataset. Therefore, we use random start strategy and randomly choose a fraction of data samples according to the pruning ratio p.
Table Dataset Distribution for Various Machine Learning Challenges
Dataset
Total
Train
Validation
Test
MNIST
70000
52500
7500
10000
CIFAR-10
60000
43750
6250
10000
Face Mask Detection
4072
2849
408
815
DermaMNIST
10015
7007
1003
2005
SNIPS
14484
13084
700
700
D Ciphertext-wise pruning
In Algorithm 4 we detail the Trim(). FZero(), Fone() and Mask() functions, which are used during ciphertext-wise pruning. When k >> 0, the server perform left rotation on claock by [k] sample slot. If K' O, right rotation performed.
16

---

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

---

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

---

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

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section 4 System Setup.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp::/ h/tpprips///rrpp...co http://pp....pppooooctccccccaaaa
Answer: [Yes]
Justification:
The authors have reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We report Broader Impact in Section
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
20

---

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

---

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


Reviews:
[{"review_id": "jP3pHSAtPF", "reviewer": "Reviewer_98ig", "summary": "This paper presents a method for pruning data in a utility-preserving way under homomorphic encryption, evaluating the method to demonstrate that the savings from training on pruned data outweighs the costs of encrypted data pruning computations. The methods for determining how relevant data items are to improving training performance are similar in spirit to those in the active/few-shot learning literature, but the paper does not explicitly draw this parallel.\n\nAlthough the paper offers a concrete threat model related to \"private training\" (where model training is outsourced to a third party), several aspects of the threat model seem not to achieve the stated goal of limiting the outsourcing party/vendor's ability to learn useful facts about the data. As the current state-of-the-art is to bind third-party infrastructure providers contractually, I'd like to see a map from how the approach in this paper, in a threat model that is weak, could be strengthened to a threat model that would obviate these purely contractual limitations. For example, there are standard constructions to move from honest-but-curious models to models where the third party is more adversarial (although some reliance must always be assumed in the case of outsourced computation). More difficult are the problems of separating data flows from inferences about the content of training data through various sorts of indirect leakage (training time, ciphertext size, dependence of the presence/absence of the allowed \"early stop\" signal, etc). Although this problem is difficult in general, I suspect there are ways to organize the threat model here so that it can make stronger claims around solving them. At a minimum the threat model should declare indirect data flow out of scope while recognizing that it can leak data items to the outsourcing partner.\n\nA few structural aspects of the paper confuse an otherwise solid presentation: a core assumption in the setup of the model in which the protocol is used is that the outsourcing partner will compare the sorted data items (under encryption) to a threshold importance score determined by the utility loss of pruning, but how this threshold is set/computed is left open (an experiment uses an ex vacuo value of 0.9 for this parameter, but why is not explained even in this concrete context!); although it is clear that the goal is only to outsource training, it is not clear that an organization without the infrastructure capability for training will have infrastructure capability for things like serving - this should be declared out of scope or unpacked/discussed a bit; approximations made to simplify computation under encryption, such as the replacement of $\\ell_2$ with $\\ell_1$ norm at 204-205, are not directly evaluated or justified; in general, the grouping of samples into batch ciphertexts is assumed but not explained - the paper should explain its necessity and the benefits it provides vs. the simple solution of putting each sample in its own ciphertext.\n\nAlthough the evaluation is valuable in supporting the core claims of the paper, there are some structural issues there as well: although the experiments characterize the tradeoff between utility and pruning ratio, this tradeoff is very different for the two example datasets. How general ought a tradeoff curve for this be? How data dependent might it be? Relatedly, might pruning affect performance for different classes differentially, especially in situations where class balance is poor? Much of the \"fairness\" literature focuses on ways that aggregate analysis breaks down when distinct classes might or ought to be treated differently by the model. Does this affect the analysis? Could it in some cases?\n\nLast, I observe that 4MB of communication overhead for a tiny database (CIFAR-10, 43750 samples) is manageable but there is no discussion of scaling here. Are the proposed applications small like this? If not, at what point is the overhead too much? Does scale cause this to break down? I here recognize that the paper inherits the inherent inefficiency of FHE constructions.", "questions": "* How does the pruning ratio get determined in practice? Is it necessary to do many private training runs and measure utility on the resultant models? How does this cost compare to the cost of non-private training?\n* Is the scale problem being swept under the rug at 237-240 an issue for larger data sets, or is the idea that this should only apply to data sets at the scale demonstrated? How does communication overhead scale as the training runs become larger?\n* Can the issue of indirect data leakage be managed somehow, or must it simply be assumed away in the security model? It's a hard problem, so solving it may well be out of scope here, but also past computation-on-encrypted-data methods have failed catastrophically due to indirect leakage problems so it's necessary to say something about it. What can or should the paper say?", "limitations": "As noted in the summary, there are places where limitations could be more clearly expressed, for example with regard to indirect data leakage, with regard to the determination of the critical pruning ratio parameter, and also with regard to aggregated analysis and generality of the pruning/utility tradeoff.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The research question is well motivated and the solution a useful tool to making private outsourced training a more realistic option. I am not well versed enough in the FHE training literature to evaluate the novelty of this specific approach, but the core idea is sound.\n* Evaluations justify the theoretical claims nicely, even where improvements are available.\n* The overall argumentation is strong, even if some details are never defined or explained as noted in the summary.", "weaknesses": "* The summary notes several places where definitions can be sharpened or details can be re-ordered to improve the presentation.\n* There are a handful of places where some copyediting would improve the presentation, although the high-level argument structure is in general strong.\n* The key question of how the pruning ratio is determined must be explained, since it is an input to most of the provided private training algorithms and also a key determinant of the model in which the protocol is meant to be used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 98ig for his/her careful reading of the manuscript and constructive comments.\n\nQ1 Deciding the pruning ratio.\n\nIn practice, the pruning ratio should be determined by the client during the client aided masking process. As shown in Figure 1 (in rebuttal pdf), a moderate pruning ratio around 0.5 has close accuracy to training with the full dataset across different datasets. Therefore, like the plaintext data pruning works, one straightforward strategy can be choosing a fixed pruning ratio [1]. Recent works show that one can also choose a set of pruning ratios for different epochs [2]. Moreover, the server can store checkpoints after each data pruning. Since the client can observe the test accuracy, the client can also roll back to certain checkpoint if needed. One should avoid running private training multiple times. This is because private training is orders of magnitudes more expensive than the non-private training.\n\nQ2 The communication scalability.\n\nThe proposed data pruning methods are scalable to large datasets. The communication complexity of the proposed method is linear with respect to the number of total data samples and the frequency of the pruning. For the ImageNet, performing one encrypted data pruning over 1,281,167 training samples would only incur around 40MB communication overhead. Note that data pruning is performed every $\\Delta_{\\tau}$ epochs, so the overall communication are few multiples of 40MB.\n\nThe major challenge of scaling to larger datasets is the inefficiency of the HE constructions. As far as we know, the latest HE-based private training works still focus on small datasets like CIFAR-10 and MNIST [3]. Securely training on ImageNet can still take years even with GPU acceleration and more efficient cryptographic tools [4].\n\nQ3 Threat model and indirect data leakage.\n\nThe threat model can be strengthened via additional integrity techniques like zero-knowledge proofs (ZKP). HE alone cannot ensure the integrity of the computation on the server side and we can introduce ZKP to verify the correct execution on the server side. Making HE verifiable via ZKP is an active research topic that is currently being explored [5]. In addition to ZKP, other integrity techniques such as Message Authentication Codes and Trusted Execution Environments can also be utilized to defend against malicious adversaries.\n\nProtecting the indirect information, such as the training time and the size of the dataset and ciphertext, is indeed out of scope for this work. In the meantime, we believe the security risk of such indirect information leakage is limited, since all data and model weights are strictly encrypted during the whole training phase. In this work, we focus on protecting client’s data privacy and model privacy in the semi-honest setting, like prior works on private training [3]. Such a setting is reasonable because as a service provider, the server is motivated to adhere to the protocols to guarantee the quality of service. We will make more explicit declarations for better clarity.\n\nQ4 Generality issue\n\nWe show the pruning/utility tradeoff on more datasets in Figure 1 (rebuttal pdf). The accuracy does differ for different datasets. We notice that extremely high pruning ratios like 0.99 only work for CIFAR-10 dataset and do not generalize well. On the other hand, moderate pruning ratios demonstrate reasonable pruning/utility tradeoff across all datasets. When we keep more than 10% data, the accuracy is only 0.05%~0.31% lower than training with full dataset. When we keep around 50% data, the accuracy can be even higher.\n\nQ5 Explanations on details\n\nWe thank the reviewer’s thorough reading and constructive advice on the copyediting.\n\n(1) The client's capability. The client does not have adequate resource or knowledge for training but has basic computation resource for at least encryption and decryption. The encryption and decryption algorithms are lightweight in HE, taking only 86ms and 49ms for one ciphertext respectively. Accordingly, it is reasonable to assume that the client can compute the pruning mask, which takes as little as 15ms for the CIFAR-10 dataset. Similarly, the client should be capable of computing the early stop signal [3].\n\n(2) The effectiveness of the HEFS score. A sample's importance can be quantified by the $\\ell_2$-norm of its gradients, which can be approximated by the $\\ell_2$-norm of the error vector [1]. The more similar a sample's prediction vector is to the label vector, the smaller EL2N score will a sample have. This means the sample is easier to learn and less informative for the training process. From this perspective, HEFS has identical properties as EL2N. Additionally, HEFS can be computed in HE more efficiently.\n\n(3) Batching data samples in ciphertext. Single Instruction-Multiple Data (SIMD) is a commonly used technique in HE. With SIMD, a single ciphertext has many slots, i.e., 32,768 slots in our setting. On the other hand, a single data sample can only occupy 768 slots in the transfer learning setting, and 784 slots for the MNIST dataset, 3,027 slots for the CIFAR-10 dataset. Packing multiple samples in one ciphertext is a commonly used strategy to reduce the number of ciphertexts as well as the number of HE operations [3,6].\n\nWe will incorporate the reviewer's suggestions into the future versions for better clarity.\n\n[1] Paul, Mansheej, et al. Deep learning on a data diet: Finding important examples early in training.\n\n[2] Truong, Thao Nguyen, et al. KAKURENBO: adaptively hiding samples in deep neural network training.\n\n[3] Lee, Seewoo, et al. HETAL: efficient privacy-preserving transfer learning with homomorphic encryption.\n\n[4] Jawalkar, et al. Orca: FSS-based Secure Training and Inference with GPUs.\n\n[5] Viand, Alexander, et al. Verifiable fully homomorphic encryption.\n\n[6] Crockett, Eric. A low-depth homomorphic circuit for logistic regression model training.", "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": "CsAyNselKx", "reviewer": "Reviewer_FEVE", "summary": "1. The paper introduces a Homomorphic Encryption (HE)-based confidential training framework that enhances training efficiency through encrypted data pruning.\n2. The paper proposes HE-Friendly Score (HEFS), an enhancement over the existing EL2N score, to efficiently assess the importance of encrypted data samples.\n3. Due to the high complexity of sorting scores and calculating the pruning mask on the server, the paper introduces a method that generates data pruning masks with the assistance of the client, enabling the server to perform pruning.\n4. The paper proposes a method for pruning at the ciphertext level to reduce sparsity in the encrypted data, thereby accelerating the training process.\n5. The performance of HEFS, CAM, and CWP is evaluated on diverse datasets such as MNIST, CIFAR-10, Face Mask Detection, DermaMNIST, and SNIPS. The results are compared with the previous method, HETAL (ICML2023), to demonstrate improvements in training speed and accuracy.\n6. The experimental results indicate that the proposed methods can accelerate confidential training by up to 16 times with minimal loss in accuracy.", "questions": "Is it true that the pruning mask is also encrypted? The distinction between encrypted and non-encrypted elements in the algorithm is not entirely clear. While an overline appears to indicate encrypted values, there are instances where this is not consistently applied.\nIn scenarios where the server does not send scores to the client, the mask would presumably remain encrypted. If this is the case, how does the server determine which parts to prune, and how does it use rotation to merge ciphertexts and create pruned ciphertexts? Is it assumed that the client must decrypt the data and create the mask in plaintext? If so, the paper should explicitly state this assumption.", "limitations": "They addressed it adequately.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper tackles the novel problem of accelerating confidential training through encrypted data pruning, a topic that appears to have not been previously explored in existing research.\n2. The methodologies and experimental procedures are clearly explained, ensuring the reproducibility of the results by providing their code (although I have not tested the code yet).\n3. Considering that HE training is a very challenging subject due to the computational complexity of operations on homomorphically encrypted data, it is noteworthy that the authors have implemented detailed techniques such as pruning within the homomorphic encryption framework for the first time. However, it is crucial that the design carefully considers both security and performance limitations.", "weaknesses": "1. There are concerns regarding the privacy threat setting in this paper. The focus is solely on the importance of the client's data privacy, without explicitly considering the server's model privacy. In other words, the server's model is assumed to be publicly available information. This assumption is reflected in the final step, where the client recovers the weights of the trained model and sends them back to the server.\n2. If the server's model is publicly available, it would be more efficient for the client to process the data in plaintext after receiving the pretrained model. If the scenario involves a massive pretrained model, such as a large language model (LLM), which individual clients cannot train, then training such an LLM in an encrypted state would require at least 1000 times more computation on the server due to the difference in computational overhead between homomorphic encryption and plaintext operations. This level of computation may be unmanageable, and the final decryption of the model by the client would also be infeasible due to the enormous size (100 trillion parameters) of the model.\n3. If the primary concern is the client's privacy, it would be significantly more efficient to have the client train on a pretrained model in plaintext, use federated learning, or adopt other methods rather than struggling with encrypted training on the server, as proposed in this paper. The bottom line is that if the server's model privacy is not considered in the security threat model, it is questionable whether this approach is practical or appropriate.\n4. The HE.cmp operation does not yield a precise 1 or 0; rather, it produces a fractional value when the two compared values are similar. During the sorting process in Algorithm 1, swapping based on HE.cmp might introduce noise if the score differences are not substantial. This could affect performance. To avoid this, HE.cmp would need a high-degree approximation. The paper does not provide sufficient information on HE.cmp, and additional explanation would be beneficial.\n5. Due to the overhead of homomorphic encryption operations, involving the client in the training process because of the complexity of sorting diminishes the method's utility. While the paper does not consider the server's model privacy, allowing the client to access intermediate values during training does not pose an additional security risk. However, in scenarios where the server's model privacy is a concern, this method could enable the client to gain critical information about the model. Increasing the client's role in plaintext processing during training could significantly reduce the server's burden and enhance overall performance. In extreme cases, the client could potentially handle the entire training process in plaintext. The paper needs to explain why the client should only assist with sorting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1 Clarification on the threat model\n\nWe would like to clarify some misunderstandings about the privacy threats this paper focuses on. The proposed method protects both the data privacy and the model privacy. In our threat model, both training data and the model weights belong to the client. The client does not have adequate resource or knowledge for training and outsources the training task to the server. Neither the training data nor the model weights are revealed to the server at any time. All the intermediate features and gradients are also encrypted and protected by HE. This threat model is commonly used in private training works [1]. \n\nWeakness 1. Since the model belongs to the client, it is reasonable that the client can decrypt the model. Additionally, we note that the client does not need to send the decrypted model to the server. Since the model is already well-trained, the client can keep it for local use. Alternatively, if the client requires the server to provide private inference service on the trained model, it is possible to store the encrypted final model on the server side.\n\nWeakness 2.  As mentioned above, the model does not belong to the server and is not publicly available.\n\nWeakness 3. As mentioned above, the goal and privacy threats are different from those in federal leaning. In our threat model, the client outsources the training task to the server because the client does not have enough resource or knowledge for training. In the meantime, the gradients are encrypted and not revealed to the server. Federal learning typically needs local training on the client side and does not directly protect the gradients. \n\nQ2 The security of the pruning mask\n\n(1) Unencrypted mask. In response to weakness 5, we explain why client aided masking is secure and reasonable. As explained above, the both the data and the model belong to the client. Therefore, revealing the mask to the client does not pose security risk against the data privacy or model privacy. In our client aided masking algorithm, the importance score is revealed to the client. The client performs a quick selection algorithm to find the score threshold and generate a pruning mask. This happens in the unencrypted state on the client side. \n\nDuring the client aided masking and ciphertext-wise pruning, the plaintext pruning mask is revealed to the server to enhance the efficiency of data pruning on the server side. The server does learn the sparsity information of the training dataset implied by the pruning mask. However, since all the training data and model weights are strictly encrypted on the server side, the privacy of client's data and model is still protected. Similar to prior works [1], we allow revealing necessary meta information about training like the the size of the dataset or ciphertexts, the early stop signal and the pruning mask. Sharing these information does not pose direct security risk against the client’s data privacy or model privacy.\n\n(2) Encrypted mask. We explain how the server can remove unimportant samples using encrypted mask without client aided masking. Performing data pruning without the client's aid and via an encrypted mask is possible. The server can first compute the importance score in the encrypted state and generate the encrypted pruning mask as shown in Algorithm 1. With the encrypted pruning mask, the serve can make the slots of unimportant samples empty via homomorphic multiplication and generate sparse ciphertexts. However, since the mask is encrypted, the server cannot learn which samples should be pruned. The server cannot merge the sparse ciphertexts via rotation either. This is because the sparsity of each ciphertext remains unknown to the server, and the server can not determine how to rotate each ciphertext to create pruned ciphertexts. Therefore, while data pruning with encrypted mask is possible, it incurs prohibitive overhead during homomorphic sorting in practice and is barely useful.\n\nOur experiments are indeed based on the client aided masking and the unencrypted pruning mask. We will state this more explicitly for better clarity.\n\nQ3 The approximated comparison in CKKS\n\nThe comparison function in the CKKS scheme is approximated and not accurate. We approximate the sign function to compute the comparison function and the max function in equation (3). Both the max and the comparison function can be constructed via the sign function and have similar complexity [3]. Specifically, the max function can be defined as $max(a,b) \\approx \\frac{(a+b)-(a-b)sign(a-b)}{2}$, where $sign(x)$ returns 1 if $x>0$, 0 if $x==0$ and $-1$ if $x<0$. We use a composition of polynomials to approximate the sign function, i.e., $sign(x) \\approx f(g(x))$, where $f(x)=f(x) = 8.83133072x - 46.45750399x^3 + 83.02822347x^5 - 44.99284778x^7$ and $g(x)= 3.94881885x - 12.91030110x^3 + 28.08653622x^5 - 35.59691490x^7 + 26.51593709x^9 - 11.41848894x^{11} + 2.62558444x^{13} - 0.24917230x^{15}$. The approximation error of the max function $e = \\left| \\max(a,b) - \\frac{(a+b) - (a-b)\\text{sign}(a-b)}{2} \\right|$ is bounded by $2^{-8}$ [3]. While increasing the number of compositions and the degree of each polynomial can lead to an even smaller bound, we find that above approximation is precise enough for computing the HEFS score. Prior works [1] find that polynomials of even lower degree is enough for private training.\n\nWe hope our responses address the reviewer's concerns. We will add the details about the max and comparison function to Appendix in future version for better clarity.\n\n[1] Lee, Seewoo, et al. HETAL: efficient privacy-preserving transfer learning with homomorphic encryption.\n\n[2] Lee, Eunsang, et al. Minimax approximation of sign function by composite polynomial for homomorphic comparison.", "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": "ZOq1NO0ZdX", "reviewer": "Reviewer_LFsM", "summary": "This paper focuses on the scenario where the client encrypts the model and dataset with homomorphic encryption and outsources them to the server for training. It accelerates the training process through dynamic data pruning. This paper makes the following three contributions: \nFirst, this paper is the first to use dynamic data pruning to accelerate model training in homomorphic encryption (HE) scenarios. Second, because using the plaintext data pruning method in the HE scenario incurs significant overhead, this paper proposes an HE-friendly method for evaluating the importance of data samples. Lastly, because of the high cost of sorting in HE, this paper proposes that the client undertake this part of the computation. Additionally, since a single SIMD ciphertext can contain multiple data samples, pruning may not reduce the number of ciphertexts, even though the samples within each ciphertext become more sparse. To address this issue, the paper proposes to combine several sparse ciphertexts to reduce HE computation.", "questions": "1) Is there any theoretic proof of the effectiveness of the proposed HE-friendly score?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) This paper is the first to apply dynamic data pruning to accelerate model training in HE scenarios.\n2) It introduces a HE-friendly important score to make data pruning more efficient.\n3) This paper uses ciphertext-wise pruning to reduce the number of ciphertexts while keeping detailed information.", "weaknesses": "1) The HE-friendly score needs more explanation. In this paper, the score is directly introduced without any theoretic proof of its effectiveness. \n2) The work is a bit incremental. Applying data pruning in the HE scenario doesn't seem very challenging, and there is no significant difference between data pruning in plaintext and ciphertext.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer ADwT for his/her thorough reading of the manuscript and constructive comments.\n\nQ1 The effectiveness of HEFS\n\nThe proposed HE-friendly score relies on the observation that the importance of a data sample can be quantified by its gradients [1]. We denote the input vector as $x\\in\\mathbb{R}^d$ where $d$ is the input dimension and the one-hot label as $y\\in \\{0,1\\}^K$ where $K$ is the number of class. We denote the logit outputs of the model as $f(x;w)$ and the prediction vector as $p(x;w)=\\sigma(f(x;w))$, where $\\sigma(\\cdot)$ is the SoftMax function. We denote the cross-entropy loss as $\\ell(p,y)=\\sum_{i=0}^{K-1}y^{(i)}\\log p^{(i)}$.\n\nWe denote a minibatch of $B$ samples as $S=\\{(x_i,y_i)\\}_{i=0}^{B-1}$.\n\nWe denote a single sample's gradient to the weights at time $t$ as $g_t(x,y)=\\nabla_{w_t}\\ell(p,y)$. The change of a sample's contribution to training at time $t$ can be quantified by the time derivative of the loss on the sample, i.e., $\\Delta_t((x,y), S)= -\\frac{d \\ell(p,y)}{dt}$. Accordingly, we can evaluate the importance of some data sample $(x_k,y_k) \\in S$ by investigating how removing the $(x_k,y_k)$ from the minibatch change the loss of other samples. The impact of removing the sample $(x_k,y_k)$ is bounded by its gradients. More formally, for $\\forall (x_i,y_i)\\in S$ where $i\\neq k$, we have:\n$\\| \\Delta_t((x_i, y_i), S) - \\Delta_t((x_i, y_i), S_{\\neg k}) \\|_2 \\leq c \\| g_t(x_k, y_k) \\|_2 \\cdots (1)$\n\nWe provide a proof of the correctness of the Equation (1) as follows. By the chain rule, we have $\\Delta_t((x_i, y_i), S) =  -\\frac{d \\ell(p,y_i)}{dt} = -\\frac{d \\ell(p,y_i)}{dw_t}\\frac{dw_t}{dt}$. When the weights are updated via SGD, we have $\\frac{dw_t}{dt}=-\\eta\\sum_{(x_j,y_j)\\in S}g_t(x_j,y_j)$ where $\\eta$ is the learning rate. Accordingly, the change of the loss of the sample $(x_i,y_i)$ is $-\\frac{d \\ell(p,y_i)}{dw_t}\\cdot\\eta\\sum_{(x_j,y_j)\\in S}g_t(x_j,y_j) + \\frac{d \\ell(p,y_i)}{dw_t}\\cdot\\eta\\sum_{(x_j,y_j)\\in S_{\\neg k}}g_t(x_j,y_j) = \\eta\\frac{d \\ell(p,y_i)}{dw_t}g_t(x_k, y_k)$. By the submultiplicative property of norms, we have $\\| \\Delta_t((x_i, y_i), S) - \\Delta_t((x_i, y_i), S_{\\neg k}) \\|_2 \\leq \\eta \\| \\frac{d \\ell(p,y_i)}{dw_t} \\|_2 \\| g_t(x_k, y_k) \\|_2$. Since $\\eta$ and $\\frac{d \\ell(p,y_i)}{dw_t}$ is independent of $k$, we can set $\\eta \\| \\frac{d \\ell(p,y_i)}{dw_t} \\|_2$ as a constant $c$. Thus, we have proved the correctness of the Equation (1).\n\nThe above bound can be simplified. Specifically, by the chain rule, we have $g_t(x,y)=\\frac{d \\ell(p,y)}{d f}\\frac{d f}{d w_t}$. Given the number of class $K$, the bound can be written in the logit-wise form as $\\sum_{i=0}^{K-1}\\| \\nabla_{f^{(i)}}\\ell(p,y)^T\\nabla_{w_t}f^{(i)}(x;w_t) \\|_2$.\n\nUnder the cross entropy loss, the derivative with respect to the $i$-th logit is $p(x;w_t)^{(i)}-y$. It was observed that logit gradients $\\{\\nabla_{w_t}f^{(i)}(x;w_t)\\}_{i=0}^{K-1}$ are generally orthogonal among classes [2,3]. Thus, the bound can be simplified as $\\| p(x;w_t)-y \\|_2$, which is the EL2N score.\n\nThe proposed HEFS further simplifies the computation as the $\\ell_1$-norm of the error vector. We observe that the $\\ell_1$-norm of the error vector has identical properties as the $\\ell_2$-norm. If a sample's prediction vector is largely similar to the label vector, it will have both a small EL2N score and a HEFS score. This indicates that the sample is easier to learn and less informative for the training process. Our experiments also supports our analysis. HEFS can effectively select informative data samples to accelerate training without compromising the accuracy. Additionally, while computing the square root in EL2N is expensive in HE, HEFS can be computed in HE much more efficiently.\n\nQ2 Why encrypted data pruning is challenging\n\nWhile the idea of leveraging data pruning to accelerate the private training seems straightforward, we note that encrypted data pruning differs from data pruning in the plaintext in several key aspects.\n\nComputing these metrics such as the entropy loss and the $\\ell_2$-norm is considered as free in the plaintext. However, evaluating the complex non-linear functions in HE is non-trivial. Evaluating a single square root function on a ciphertext can take up to 2 minutes. This implies that simple metrics like EL2N could negate the benefits of data pruning. We highlight that HEFS rely solely on the prediction vector and the label vector, which are directly available from the private training process. Evaluating the HEFS score only requires subtraction, max and the rotation operation, which takes only 1.72~1.84s for one ciphertext.\n\nAnother key difference is that removing the less important data samples directly reduce the computation overhead of training in the plaintext. However, merely excluding the less important data samples does not effectively reduce the overhead of private training. This is because the runtime of private training is determined by the number of ciphertexts, and one ciphertext can contain multiple data samples. Performing sample-wise data pruning leads to a large number of sparse ciphertext. We introduce ciphertext-wise data pruning to effectively reduce the number of ciphertext and boost the efficiency of private training.\n\nThe proposed data pruning methods are lightweight, taking only as little as 0.4%~2.5% total runtime, while effectively accelerating private training. We believe this work enables more practical private training in real-world. We thank the reviewer's suggestions and will incorporate the detailed analysis of HEFS in the future version for better clarity.\n\nReference\n\n[1] Paul, Mansheej, et al. Deep learning on a data diet: Finding important examples early in training.\n\n[2] Fort, Stanislav, et al. Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel.\n\n[3] Fort, Stanislav, et al. Emergent properties of the local geometry of neural loss landscapes.", "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": "TaJgDqeCs8", "reviewer": "Reviewer_ADwT", "summary": "This paper proposes a data pruning algorithm for the training of Homomorphic Encryption (HE)-based neural networks. The authors introduce an HE-friendly importance score and client-aided masking to prune samples in the dataset. The authors further propose ciphertext-wise pruning to merge ciphertexts with empty slots, thereby reducing computational costs during training. Finally, the paper presents empirical studies to validate the effectiveness of the proposed data pruning method.", "questions": "1.\tWhy not directly compute the square of the EL2N score, which would avoid the need for computing the square root or the maximum value and is a simpler process?\n2.\tIs the running time for HE-based data pruning included in the total running time reported in the Tables in Section 4.2? If so, what proportion of the total running time does the HE-based data pruning constitute? \n3.\tHow does the proposed method compare to a baseline that directly randomly samples a subset of ciphertext at each epoch, instead of computing importance score and merging ciphertext? I think this baseline is simpler and more efficient.", "limitations": "The authors addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The main advantages can be listed as follows:\n\n1.\tThe paper provides a new data pruning method for data encrypted by HE scheme. The authors propose the HEL2N score, which substitutes the $\\ell_2$-norm in the EL2N score with $\\ell_1$-norm, and the client will select important samples based on the score computed by server.\n2.\tThe paper proposes the ciphertext-wise pruning, enabling the server to merge ciphertexts with empty slots with the communication of the client.\n3.\tThe paper conducted experiments on five datasets and compares the proposed method with the HETAL method to demonstrate its effectiveness.", "weaknesses": "Despite many strengths, there are some issues with the paper as follows:\n\n1.\tThe submission requires further revisions for clarity and consistency. At line 43 “methds” should be “methods”; At line 74 and Figure 1 “CIFAR10” should be “CIFAR-10” as in Section 4; At line 326 “Table2” should be “Table 2”; At line 340 “Figure 4(4)” should be “Figure 4(a)”; Figure 1 and 4 should have sub-captions denoting which subgraph is (a) or (b).\n2.\tThe computation costs associated with data pruning raise concerns. As given by Eqn. (1), computing the HEL2N score involves multiple gradient computations for each sample, which is computationally intensive. Moreover, ciphertext-wise pruning seems to require a large number of rotations, which is also a very slow HE operation. If the data pruning process is time-consuming, it may negate the benefits, making it more efficient to train directly without pruning.\n3.\tThe novelty of the paper is questionable. The HEL2N score primarily modifies the $\\ell_2$-norm in the EL2N score to an $\\ell_1$-norm, and directly computing the square of EL2N score seems to be faster than HEL2N score. The trick of masking is also common place in HE literature. Moreover, one advantage of HE-based method is that they do not require any communications between server and client. The requirement for client-server communication in client-aided masking and ciphertext-wise pruning could diminish the significance of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer ADwT for his/her thorough reading of the manuscript and constructive comments.\n\nQ1 Clarity and consistency\n\nWe thank the reviewer for the thorough reading. We will fix the typos in the future version.\n\nQ2 The overhead of the proposed methods\n\nThe results in Section 4.2 include the running time for HE-based data pruning. The proposed data pruning mainly contains (1) computing the HEFS score and (2) performing ciphertext-wise pruning. We show the proportion of the proposed methods of total runtime in Table 2(rebuttal pdf).\n\nWe first benchmark the runtime of basic HE operations in our environment: addition:8ms, ciphertext-plaintext multiplication (cpMult):17ms, rotation:116ms, ciphertext-ciphertext multiplication (ccMult):146ms, max:1.37s and bootstrapping:35.89s.\n\n**HEFS.** The proposed HEFS does not rely on the gradients. Instead, HEFS can be computed via the error vector as shown in the Equation (2). To compute HEFS, we only need subtraction, max and the rotation operation. Computing HEFS on a single ciphertext takes 1.72~1.84s.\n\n**Ciphertext-wise Pruning.**\nWhile rotation is not fast compared with addition and cpMult, it is still faster than the ccMult in the CKKS scheme. Moreover, the rotation barely consumes the noise budget [1]. We remark that the non-linear SoftMax function is computed via approximation, which also relies on ccMult. The intensive evaluation of the ccMult in the forward pass and back propagation leads to frequent bootstrapping, which is the most expensive operation in practice.\n\nIn the worst case, the ciphertext-wise pruning needs $O(p(1-p)N)$ rotations, where $N$ is the number of total data samples and $p$ the pruning ratio. Take the CIFAR-10 dataset for an example. We choose a batch size of 128, and the 43750 training data samples are encrypted in 342 ciphertext blocks. When the pruning ratio is 99\\%, the ciphertext-wise pruning needs at most 430 rotations to combine the 342 sparse ciphertext blocks into 4 dense ones, which takes 0.04h. In contrast, evaluating one epoch without pruning takes more than 20h.\n\nWe remark that the main bottleneck of private training remains to be the evaluation of complex non-linear functions like the SoftMax function and the bootstrapping. We believe that optimizing these operations could further accelerate private training. This is orthogonal to the optimizations discussed in this paper.\n\n\nQ3 The effectiveness of the proposed HEFS.\n\nIn Figure 2(rebuttal pdf), we compare HEFS with (1) the square of the EL2N score; (2) randomly dropping ciphertexts. However, these two methods yield inferior efficiency / utility trade off compared with the proposed HEFS.\n\n**The square of EL2N.**\nThe HEFS generally has a better accuracy than the squared EL2N. HEFS outperforms the squared EL2N by a noticeable margin when the pruning ratio is high, i.e., the remaining data is below 0.2. This is because the squared EL2N score enlarges the importance of samples that are predicted wrong. These samples can be noisy samples [2]. Emphasizing these samples too much makes the selected data less informative, which leads to an inferior accuracy. As the pruning ratio goes down, the proportion of such noisy samples decreases. Accordingly, the performance of the squared EL2N becomes closer to HEFS. In Table 1(rebuttal pdf), we show that computing the score is not the bottleneck and the savings from using the squared EL2N is marginal.\n\n**Random pruning.** While random pruning strategy is simple, it ignores the importance of data samples. This leads to significant deterioration of accuracy, especially when the remaining fraction is low.\n\nQ4 The novelty and the significance.\n\nTo the best of our knowledge, we are the first to explore encrypted data pruning to accelerate private training. Performing data pruning in the encrypted state is non-trivial. Directly adapting plaintext pruning methods is not viable. To start with, the importance score in the plaintext often involves complex nonlinear functions that are expensive in HE. Moreover, sorting samples are considered free in plaintext, but sorting in the encrypted state is expensive. Most importantly, the sample-wise pruning in plaintext leads to sparse ciphertexts and fails to effectively accelerate private training. We propose a series of HE-aware optimizations including HEFS, client aided masking and ciphertext-wise pruning. Our methods boost the efficiency of private training significantly without sacrificing accuracy.\n\nMoreover, we would like to remark that EL2N has been treated as a static data pruning method. Prior works have assumed either that it remains unclear if EL2N reduces the total training time [3] or that EL2N cannot be used to accelerate training [4]. In this work, we innovatively adapt it to the dynamic data pruning setting and show its effectiveness.\n\nQ5 The non-interactivity of HE\n\nPrivate training with the proposed encrypted data pruning remains largely non-interactive compared with the MPC-based methods. This is because all HE computation is performed solely by the server. The client is only required to be online for less than 0.1% of the total training time, to handle the early stop signal and pruning mask. As shown in prior works like HETAL, these communications are both secure and necessary.\n\nTo sum up, we show that the squared EL2N and randomly pruning are less effective than the proposed HEFS. Additionally, the proposed HEFS and ciphertext-wise pruning are efficient at runtime. We sincerely hope our responses have addressed the reviewer's concerns.\n\nReference\n\n[1] Bossuat, Jean-Philippe, et al. Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys.\n\n[2] Paul, Mansheej, et al. Deep learning on a data diet: Finding important examples early in training.\n\n[3] Truong, Thao Nguyen, et al. KAKURENBO: adaptively hiding samples in deep neural network training.\n\n[4] Qin, Ziheng, et al. Infobatch: Lossless training speed up by unbiased dynamic data pruning.", "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:
We thank all reviewers for their constructive and insightful feedback.

We are glad that all reviewers unanimously agree that our encrypted data pruning methods are of great significance for improving private training. We appreciate the reviewers recognizing the novelty of our work as the first framework that enables data pruning in private training (FEVE, LFsM). Reviewers find our work and evaluation effective, and our presentation clear (98ig, FEVE, LFsM). The reviewers also find that our work successfully boosts the efficiency of private training without compromising either accuracy or privacy. This paper makes private training more practical in real-world applications.

Performing data pruning in the encrypted state is non-trivial. Directly adapting plaintext pruning methods is not viable. To start with, the importance score in the plaintext often involves complex nonlinear functions that are prohibitive in HE. Moreover, sorting samples are considered free in plaintext, but sorting in the encrypted state is expensive. Most importantly, the sample-wise pruning in plaintext leads to sparse ciphertexts and fails to effectively accelerate private training. We propose a series of HE-aware optimizations including HEFS, client-aided masking, and ciphertext-wise pruning. Our methods boost the efficiency of private training significantly without sacrificing accuracy.

We thank the reviewers for their interest in many aspects of our work. 
**(1) Generality and scalability:** We have shown that the proposed encrypted data pruning methods are highly general and scalable for different datasets and pruning ratios. 
**(2) Lightweight design:** We present a more detailed runtime breakdown to show the proposed methods are extremely efficient at runtime, taking as little as 0.4% to 2.5% of the total runtime of private training. 
**(3) Analysis on Privacy and Efficiency:** We present an in-depth analysis of the privacy and efficiency of the proposed methods. We guarantee data privacy and model privacy simultaneously via HE throughout training and address security issues related to the pruning mask. We demonstrate the mechanism of using the proposed HEFS score to identify the most informative samples in the encrypted state. Meanwhile, we leverage HE-friendly scores, efficient sorting, and ciphertext-wise pruning techniques to construct lightweight yet effective strategies that significantly enhance the efficiency of private training.

Meta-review: After discussion, all the reviewers provided positive feedback on this submission, therefore we recommend accepting it.
Decision: Accept (poster)