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_cc_2024_Conference
Published: 2024-05-15 14:20:16

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

Main paper: 
 introduction: 
 Machine learning, especially deep neural networks, has been widely applied in various domains, including healthcare [1] , finance [2] , and so forth. Due to the lack of expertise and computational resources, the average user often outsources the training task to the cloud servers in the machinelearning-as-a-service (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 a 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 are commonly employed, where the model trainer has access to both the dataset and model. Dataset pruning involves analyzing data samples, calculating an importance score for each sample during training iterations, and discarding redundant samples to streamline training. Prior research indicates that dataset pruning can enable machine learning model training on a fraction of the data-sometimes as little as 10%-with minimal to no loss in accuracy [7, 8, 9, 10, 11] .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 [11, 12] -such as logits, gradients, and losses-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 pruning [7, 8, 9, 10, 11] does not always yield execution and ciphertext reduction benefits, as a single ciphertext often contains multiple plaintext samples within its slots. Therefore, effective ciphertext pruning is critical to enable faster private training.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 FHEenabled data pruning, we introduce a homomorphic encryption-friendly 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 a ciphertext-wise pruning (CWP) technique to reduce the number of ciphertexts during private training. We conduct experiments in both training-from-scratch and transfer-learning settings. The proposed encrypted data pruning framework can accelerate private training by 16× with only a 0.6% accuracy drop. 
fully homomorphic encryption-enabled private training: 
 Fully Homomorphic Encryption (FHE) [3] is a cryptographic primitive that supports arbitrary computation 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 ⊞, ⊟, and ⊠, respectively. Nonlinear 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.Max [14] , HE.SoftMax [6, 15] , and HE.Sqrt [16] , 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 a dense model for one step on a batch of 60 MNIST samples can take over 1.5 days in FHESGD [4] .A 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 datasets by using optimized matrix multiplication and GPU acceleration. While other cryptographic tools, such as Multi-Party Computation (MPC), can also achieve private training, most existing MPC approaches [21, 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.Not all data samples contribute equally to DNN training [25] ; some samples are less important and can be pruned during training. Training on only a subset of data can effectively reduce computational overhead while achieving generalization performance comparable to training on the full dataset [10, 11] . Several methods have been proposed to identify the most informative data samples. Among these, score-based methods [7, 8, 9, 10] are widely used for their simplicity and effectiveness. These methods compute sample-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 [7] , which counts the number of "forgetting events" that occur for each sample during training, where a forgetting event is defined as a change in the model's prediction for the same sample between two consecutive epochs. GraNd [9] uses the ℓ 2 -norm of the sample-wise gradient to represent sample importance, while ELN2 [9] approximates GraNd by calculating the ℓ 2 -norm of the error vector. Additional methods for identifying sample importance include submodularity-based methods like GraphCut [26] and gradient-matching-based methods like GradMatch [12] . 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 [7, 8, 9, 26] , while dynamic pruning involves pruning data every few epochs during training [12, 11, 10] . 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 a static setting, while [11, 10] apply it in a dynamic setting. Similarly, dynamic pruning methods like [26, 12] can be adapted to static settings, as demonstrated by [27] , without losing effectiveness. In this paper, we focus on dynamic pruning. The distribution of data sample numbers in a ciphertext after data pruning. Only a small fraction of ciphertexts are empty with a naïve sample-wise pruning.Motivation. FHE-enabled private training provides a strong privacy guarantee for user data. However, private training remains significantly slower in runtime compared to 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 1 (a), removing a 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 1 (b), computing importance scores with existing methods-such as the forgetting score [7] , entropy score [11, 10] , 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 a 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, as illustrated in Figure 1 as intellectual property that must not be disclosed to the server at any point. We assume the server is 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. 
heprune design: 
 We begin by outlining the pipeline for private training with encrypted data pruning in Section 3.1. In Section 3.2, 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, we introduce ciphertext-wise pruning (CWP), which removes sparse ciphertexts and further accelerates the data pruning process. From this point forward, the dataset will never be decrypted. We refer to the encrypted data samples as ciphertexts. To identify the most informative subset of samples, ❷, the server first runs the forward pass algorithm on all ciphertexts to obtain the encrypted prediction vector P . ❸ 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 to prune. This is achieved by sorting the importance score and finding the threshold importance score H corresponding to the pruning ratio [7] . A pruning mask is generated by comparing the importance score with the threshold as M = 1{H(x) < H t }. 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 ciphertext-wise pruning according to the current pruning mask. ❻ The server performs a backpropagation algorithm on the pruned ciphertexts for ∆τ epochs, and then ❷ starts a 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 5 in Appendix A.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-fromscratch setting [4] . Our protocol is fully compatible with the early stop techniques adopted in [6] . As in [6] , sending meta information during training is allowed in 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 3.3, we propose CWP to effectively reduce the number of ciphertexts involved in training and thus boost the efficiency of private training.While FHE can support arbitrary computation on encrypted data, computing non-linear 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-based methods [8, 11, 10] , although the entropy loss is typically considered cost-free in the plaintext, it is not explicitly computed during private training. Instead, we compute the gradient directly without calculating the loss itself, as illustrated in Figure 5 , 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 [9] , which simply utilizes the prediction P and label Y . Although originally proposed as a static pruning method, we find that EL2N also remains effective in a dynamic setting, similar to the entropy score [10] . We first instantiate an FHE-enabled data pruning algorithm, detailed in Algorithm 1, based on the dynamic version of EL2N (HE2LN). Subsequently, we demonstrate that even EL2N remains computationally expensive in the encrypted state and propose the HE-friendly score (HEFS) and client-aided masking (CAM) to accelerate the encrypted data pruning. = { X′ i, Ȳ ′ i} C ′ -1 i=0 , where C ′ ≤ C. for i ← 0 to C -1 do Pi ← HE.SoftMax(M( Xi; W )) ; // Prune.Eval ē rri ← Pi ⊟ Ȳi ; // compute the error vector ē rri ← ē rri ⊠ ē rri; ērr_sumi = ē rri; for j ← 0 to log n -1 do ērr_ti ← HE.( s_scorei) ← ( less ⊠ s_scorej) ⊞ ((1 ⊟ less) ⊠ s_scorei); ( s_scorej) ← ( less ⊠ s_scorei) ⊞ ((1 ⊟ less) ⊠ s_scorej); threshold_index ← N × p; θ ← s_score threshold_index ; for i ← 0 to C -1 do m ask ← HE.Cmp( scorei, θ); // remove unimportant samples ( Xi, Ȳi) ← ( m ask ⊠ 0) ⊞ ((1 ⊟ m ask) ⊠ ( Xi, Ȳi)); return D′ ← { X′ i, Ȳ ′ i} C-1 i=0HEL2N Baseline. The EL2N score is defined as H(x) = E wt ∥p(x; w t ) -y∥ 2 , where p(x; w t ) is the prediction vector for sample x and y the corresponding ground truth label. In essence, the EL2N score is the ℓ 2 -norm of the error vector, which can be computed via pure FHE operation as shown in Algorithm 1. We first compute the prediction vector P by encrypted forward pass. The HE.SoftMax in the forward pass is evaluated by polynomial approximation [15] and domain extension technique [28] . Computing the forward pass in the encrypted state is the same as existing private training frameworks [6] . With the encrypted prediction vector P and the ground truth label 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 ℓ 2 -norm of the error vector. While HE.Sqrt can be implemented via Newton iterative algorithm [16] , 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-ciphertext multiplication. This leads to a large number of additional relinearization and bootstrapping operations. A single square root over a ciphertext can take up to 2 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 to its complex non-linearity.We propose an HE-friendly 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 (x, y) over the weights at time t as g t (x, y) = ∇ wt ℓ(p(w t-1 , x), y). Given a minibatch of B samples S = {(x i , y i )} B-1 i=0 , the importance of a sample can be quantified by the difference of the time derivative of the loss function, ∆ t , 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 \ {(x k , y k )} be the set after removing a certain sample (x k , y k ). For ∀(x i , y i ) ∈ S and i ̸ = k, it holds that EL2N approximates the ℓ 2 -norm of the gradient by the ℓ 2 -norm of the error vector. We further streamline the EL2N score using the ℓ 1 -norm.EQUATIONMore formally, we define the HEFS as:EQUATIONHEFS can be efficiently computed during private training. Specifically, the circuit for HEFS consists of only two FHE subtractions and one max operation, which can be computed as:EQUATIONIn the above equation, the homomorphic subtraction ⊟ is significantly faster than other FHE operations. HE.Max can be effectively computed via HE.Cmp. While the HE.Max operation has the same time complexity as HE.Cmp, the concrete runtime of HE.Max is even more efficient, typically 1.5 ∼ 2× faster under the same parameter setting [14] . The proposed HEFS is a close approximation to the original EL2N score, which guarantees the effectiveness of the HEFSbased data pruning. We show the accuracy of 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(N 2 ) 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 t is extremely fast on the client'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 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 4 MB of communication overhead. For comparison, the early stopping signals used to determine early stopping incur 18 MB communication overhead when transferring the encrypted 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 to ensure the effectiveness of private training. Further details can be found in Appendix B. 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 3 , which further boosts the efficiency of the private training. We detail the steps of ciphertext-wise pruning in Algorithm 3. Without loss of generality, we refer to all the slots occupied by a single sample within a ciphertext as a sample slot. Once the server obtains the pruning mask, ciphertext-wise pruning can be performed without client involvement.We denote the number of samples in each ciphertext as B and M i is a Boolean array that indicates whether each of the B samples should be pruned.❶ The server first computes the sparsity of each ciphertext, which is done by simply counting the number of 0-s in each M i . ❷ After 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 ciphertextwise pruning, the server first identifies two ciphertexts ct f ront and ct back from the queue. ❸ After removing the full ciphertexts and empty ciphertexts from the queue via Trim(), we then leverage the most sparse ciphertext ct back to fill in the empty slots in the least sparse ciphertexts ct f ront . The key step is to align samples in ct back with the empty slots in ct f ront . The function FZero() returns the index of the first empty sample slot slot empty in ct f ront , sets the corresponding mask to 1, and decreases the sparsity of ct f ront by 1. Similarly, FOne() returns the first non-empty sample slot slot used in ct back and sets the corresponding mask and sparsity. By taking the difference of slot used and slot empty , the server can determine how much the ct back should be rotated to align with ct f ront . We mask out the other slots in ct back and obtain ct align and keep only the first sample slot slot used . This ensures only the empty sample slot in ct f ront is filled and the non-empty slots in ct f ront will not be corrupted. Then, ct align is rotated and added to ct f ront to fill in the empty slot in ct f ront . After merging the two ciphertexts, if ct f ront 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() ,Fone() and Mask() to the Appendix D. We remark the pruning mask generated by CAM is not encrypted, while enables efficient operations related to the pruning mask without invoking heavy FHE computation. 
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 trainingfrom-scratch setting as in FHESGD [4] . For the transfer learning setting, we adopt the same feature extractors as [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 on 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 a 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 [32], Face Mask Detection [33] , DermaMNIST [34] for image classification and one audio dataset SNIPS [35] for sentiment analysis. We partition the datasets as 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 C.System Setup and Implementation. We use the RNS version of the CKKS [36, 37] scheme for 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 = 2 16 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 L = 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-Instruction-MultipleData (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 [6, 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.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.6× across datasets. The accuracy drop is as small as 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. Effectiveness of the proposed methods. In Table2, we demonstrate the effectiveness of each proposed technique. We start by training on the full CIFAR-10 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-10 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.49× with a 0.41% accuracy drop. The communication cost increases slightly by approximately 1.2×. Yet, as the EL2N score involves costly square root computation, the speed-up is modest. By incorporating HEFS, we improve the overhead during importance score computation. With HEFS, the private training can be accelerated by 2.78×. The HEFS also achieves a ∼ 0.2% higher accuracy. When ciphertext-wise pruning is applied, the runtime speed-up is the most significant, achieving a 6.5× speed-up over HETAL with only 0.2% accuracy drop. Ablation on the pruning ratio. In Figure 4 , 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 ∼ 16×. 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 [9] . 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.2× speed up when training with 40% of the data without any loss of accuracy on the CIFAR-10 dataset. In Figure 4 (b), we experiment with the MNIST dataset and observe a similar trend. On the MNIST dataset, using only 1% of the data achieves 91.29% accuracy with ∼ 15× speed-up. Yet, using 5% of the data achieves a significantly higher accuracy of 95.2%, which is only 0.5% lower than training with the full dataset. Training from scratch. We show the performance of encrypted data pruning in the training from scratch setting in Table 3 . We train a 3-layer MLP on the MNIST dataset. We set the pruning frequency as 10 epoch. When training with only 1% data, the end-to-end training time could be 60.8× 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.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: In Section 4. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
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-enabled 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 on larger models like CNNs and Transformers can enhance its utility. (2) More Dataset Support. In this paper, we have experimented on relatively small datasets. Extending to larger datasets will enhance its utility.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer:[Yes] Justification: Code is released with anonymity.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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 of 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. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Section 4Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
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 4, 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, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to 
 
 Appendix: 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+ [43] . However, it operates under the assumption that the server can ask the client to decrypt specific ciphertexts. The assumption is not upheld in Algorithm 2. Since the server can 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 4 , the lower level the ciphertext is at, the smaller the ciphertext is. Therefore, the server can set the ciphertext to L = 0 to reduce the communication overhead.Table 4 : Ciphertext sizes under different levels.N = 2 16 L = 0 L = 1 L = 2 L = 3 L = 4 L = 5Ciphertext Size(MB) 1.01 2.03 3.02 4 5.02 6 0.1 and set the pruning frequency as every ∆ τ = 10 epochs. Prior works [9, 12] adopt a 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 a random start strategy and randomly choose a fraction of data samples according to the pruning ratio p. 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 crossreferenced. • 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 if they appear in the supplemental material, the authors are encouraged to provide a 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 or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: After discussion, all the reviewers provided positive feedback on this submission, therefore we recommend accepting it.

Reviews: review: paper_summary: paper_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.

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

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

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

Last, 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.
strength_weakness: strength_weakness: * The summary notes several places where definitions can be sharpened or details can be re-ordered to improve the presentation.
* There are a handful of places where some copyediting would improve the presentation, although the high-level argument structure is in general strong.
* 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.
questions: 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?
* 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?
* 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: 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.
paper_summary: paper_summary: 1. The paper introduces a Homomorphic Encryption (HE)-based confidential training framework that enhances training efficiency through encrypted data pruning.
2. The paper proposes HE-Friendly Score (HEFS), an enhancement over the existing EL2N score, to efficiently assess the importance of encrypted data samples.
3. 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.
4. The paper proposes a method for pruning at the ciphertext level to reduce sparsity in the encrypted data, thereby accelerating the training process.
5. 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.
6. The experimental results indicate that the proposed methods can accelerate confidential training by up to 16 times with minimal loss in accuracy.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
4. 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.
5. 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.
questions: 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.
In 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: limitations: They addressed it adequately.
paper_summary: paper_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: 
First, 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.
strength_weakness: strength_weakness: 1) The HE-friendly score needs more explanation. In this paper, the score is directly introduced without any theoretic proof of its effectiveness. 
2) 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.
questions: questions: 1) Is there any theoretic proof of the effectiveness of the proposed HE-friendly score?
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: Despite many strengths, there are some issues with the paper as follows:

1.	The 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).
2.	The 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.
3.	The 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.
questions: questions: 1.	Why 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?
2.	Is 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? 
3.	How 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: limitations: The authors addressed the limitations.

Comments: comment: We appreciate the reviewer's thorough reading of our response. We first explain the choice of pruning ratio in more detail. Similar to data pruning studies in plaintext, the pruning ratio is set as empirical values such as 0.5 or 0.3. Manually setting the pruning ratio does not require client-side training or expert knowledge. As shown in our previous responses and also data pruning studies in plaintext [1] (Section 3.3), a moderate pruning ratio can achieve close generalization performance compared to the full dataset. The client can choose an initial pruning ratio around 0.5, and adjust the initial pruning ratio according to the size of the training dataset, the quality of the data and the budget for the outsource training service. Moreover, the client can also adjust the pruning ratio during training according to the test accuracy. If you still have concerns about the pruning ratio, please let us know, and we will be happy to respond. We will clarify the choice of pruning ratio in our revision.

We thank the reviewer for pointing out the side channel information during the threat model. We will clarify it and discuss the potential side channel risks and declare that securing the side channel risks is out of scope for this work more explicitly in the next-version manuscript.

[1] Truong, Thao Nguyen, et al. KAKURENBO: adaptively hiding samples in deep neural network training.
I have read the response. While it addresses some of my concerns, I still struggle with some fundamental issues such as how "the client [should determine] the pruning ratio" when "The client does not have adequate resource or knowledge for training".

While it is true that the threat model can be strengthened by moving to verified outsourced computation techniques, that is a general problem with outsourced computation/FHE and wasn't my point, which was more that there's a lot of "side channel" information available to the outsourcing provider. What are the risks of this? Cryptographers have demonstrated that risks to data confidentiality can be enormous when even small channels exist. Verified computation can eliminate this by allowing the client to confirm that only desired computations are performed (during reported activities, but what about after or on the side?). If I give you ciphertext and you give me a ZKP that you did a certain computation using that ciphertext, that tells me zero information about what _else_ you did with that ciphertext. This is the problem. It's a very hard problem, and I don't mean that you have to solve it, but rather that you should acknowledge the limitation and declare it out of scope.
We sincerely appreciate the reviewer's thoughtful feedback and are grateful for the increased score. Thank you for your consideration and support.
Thank you for the detailed response. Considering the authors' new clarification and overall contribution of the paper, I am willing to improve my score.