SpENCNN: Orchestrating Encoding and Sparsity for Fast Homomorphically Encrypted Neural Network Inference
Authors: Ran Ran
Xinwei Luo
Wei Wang
Tao Liu
Gang Quan
Wujie Wen
Venue: Submitted to ICLR 2023 (2023)
Keywords: Cryptographic inference
model sparsity
data encoding

Abstract: Homomorphic Encryption (HE) is a promising technology for protecting user's data privacy for Machine Learning as a Service (MLaaS) on public clouds. However, the computation overheads associated with the HE operations, which can be orders of magnitude slower than their counterparts for plaintexts, can lead to extremely high latency in neural network inference, seriously hindering its application in practice. While extensive neural network optimization techniques have been proposed, such as sparsification and pruning for plaintext domain, they cannot address this problem effectively. In this paper, we propose an HE-based CNN inference framework, i.e., SpENCNN, that can effectively exploit the single-instruction-multiple-data (SIMD) feature of the HE scheme to improve the CNN inference latency. In particular, we first develop a HE-group convolution technique that can partition channels among different groups based on the data size and ciphertext size, and then encode them into the same ciphertext in an interleaved manner, so as to dramatically reduce the bottlenecked operations in HE convolution. We further develop a sub-block weight pruning technique that can reduce more costly HE-operations for CNN convolutions. Our experiment results show that the SpENCNN-optimized CNN models can achieve overall speedups of 8.37x, 12.11x, and 19.26x for LeNet, VGG-5, and HEFNet, respectively, with negligible accuracy loss.

Under review as a conference paper at ICLR 2023
SPENCNN: ORCHESTRATING ENCODING AND SPARSITY FOR FAST HOMOMORPHICALLY ENCRYPTED NEURAL NETWORK INFERENCE
Anonymous authors Paper under double-blind review
ABSTRACT
Homomorphic Encryption (HE) is a promising technology for protecting user's data privacy for Machine Learning Service (MLaaS) public clouds. However, the computation overheads associated with the HE operations, which can be orders of magnitude slower than their counterparts for plaintexts, can lead to extremely high latency in neural network inference, seriously hindering its application in practice. While extensive neural network optimization techniques have been proposed, such as sparsification and pruning for plaintext domain, they cannot address this problem effectively. In this paper, we propose an HEE-based CNN inference framework, i.e., SpENCNN, that can effectively exploit the feature of the HE scheme to improve the CNN inference latency. In particular, we first develop HE-group convolution technique that can partition channels among different groups based on the data size and ciphertext size, and then encode them into the same ciphertext in an interleaved manner, so the bottlenecked operations in HE convolution. We further develop a sub-block weight pruning technique that reduce convolutions. Our experiment results show that the ODFNCNNN-ppiiizeee CNN models can achieve overall speedups of 8.37x, 12. Ix, and 19.26x for LeNet, VGG-5, and HEFNet, respectively, with negligible accuracy loss.
(SIMD)
dramatically reduce
costly HE-ooeraatooss for CNN
INTRODUCTION
For the past decade, we have witnessed the tremendous progress of the machine-learinng technology and the great success achieved in practical applications. Convolution Neural Network (CNN) models, for example, have been widely used for many cognitive tasks such as face recognition, medical imaging, and human action recognition. Meanwhile, there is a growing interest to deploy machine learning models on the cloud service (MLaaS). While cloud computing has been well recognized as an attractive solution, especially for computation intensive applications such as the MLaaS, outsourcing sensitive data and data processing cloud can pose severe threat user's privacy.
Homomorphic Encryption (HE) is a promising technology for protecting user's privacy when deploy- ing MLaaS on cloud. HE allows computations be performed on encrypted inputs and the decrypted output matches the corresponding results computed from the original inputs. Thus, a client can encrypt the sensitive data locally and send the encrypted ciphertexts to the cloud. All intermediate results will maintain encrypted, and the encrypted results sent from cloud can be correctly decrypted using the secret key hold by the client. Whlie HE can help to maintain the confidentiality for compu- tation process on cloud effectively, one major problem has to deal with is the excessive computational cost associated with the operations over the encrypted data: HE operations (e.g. HE multiplication, additions on encrypted data) can be several (i.e., three to seven) orders of magnitude slower than the corresponding operations on plaintexts. The tremendous computational cost of HE has been the largest bottleneck that hinders its applications cloud.
One of the most effective approaches (e.g. (Gilad-Bachracee Bachrach et al., 2016 Brutzkus et al. 2019 Dathathri et al.] [219 Kim et al. 2022) to reduce the HE computational cost is to take advantage of the dingle-instruction ceteruccioomuuiiplle.e mwwtmple-lppiiitee (SIMD) capability, supported by HE schemes, e.g. CKKS and
BFV. Smart& & Vercauteren 2000 initially proposed to pack multiple data elements in the plaintext

---

Under review as a conference paper at ICLR 2023
Inner-cclaions
Rg
Prout
Rottef
0
HEAD 1:33
R1 Re
Latenopira)
(4(A)
Bottet
M(
(4(A))
Ko
Praning
(((A)
Roslen .00
59%
Dutl
Ouz
pt/As)
Different Pruning Mathode Ptaindest domain
Convolltion Hill domain
Figure 1: (a) Comparison of different HE-ooperations latency (b) Comparison of the HE convolution latency under different pruning methods. (c) Illustration for different pruning methods for plaintext domain. (d) Multi-channel convolution process in HE domain. Notation definitions refer to section
3.1 (k;):) indicate the weight plaintext. The convolution layer used here has 64 input- and 64 output-channel, with a 3 x kernel. The input feature map size of the convolution layer is 32 x 32.
domain to different "slots" in the same ciphertext and thus computations for data elements at the same slot of two encoded messages can be performed in parallel. The challenge is how to pack data based on the characteristics of the applications so that computation can be conducted effectively in a SIMD scheme manner. In particular, the problem rises when the computation needs to be performed on data elements at different slots of the messages. To re-arrange the location of each individual data element in an encrypted message is out of question due its large overhead. A more reasonable solution is to employ the HE-rotatior pperation that can move the data element cyclically in the same message. However, HE-rotation has a high latency cost due to required permutation and key-switching operation, compared with other operratts such as the HE multiplication of ciphertext with a plaintext (Mull) and HE addition of two ciphertexts (HE-Add), as shown in Figure (a). Therefore, how judiciously encode the inputs and perform the SIMD operations plays the key role in reducing the HE computation complexity.
In this paper, we study the problem on how to improve the HE-based inference latency when deploying a privacy-preserving machine learning (PPML) platform based on CNN models on cloud. It is well-known that the major computation workload for CNN inference comes from the convolution layers. Assuming the user inputs (e.g. images) are encrypted as the ciphertexts and associated CNN models are encoded as plaintext messages, the major HE computations are therefore HU-PMult, HE-Add, and HE-rotation operations. Traditional neural network optimization techniques such as sparsification and pruning (Han et al., [2015b] Wenn et al. 2016) help to reduce the computation demand for CNN inference for plaintext domain. However, they may not be effective here as reducing the computation demand does not necessarily imply the reduction of SIMD computations. In addition, note that, shown in Figure Ia). the computation cost for an HE-rotation can be over 43x of that for an HE-Pmult or an HE-Add operation. Simply reducing the HE operations without optimizing the HE-rotations may not be effective at all in redueing the computational cost.
To this end, we develop an Ha-based CNN inference framework, i... SpENCNN, with the goal to effectively exploit the SIMD feature of the HE scheme to improve the CNN inference latency. In particular, we develop two techniques to reduce the HE computational cost. First, we develop HE-group convolution and associated irou--interleaved encoding optimize channel locations on ciphertexts based on the number of convolutional groups and ciphertext size, thus significantly reducing the number of costly HE-rotations. Second, we further optimize the model architecture by pruning and training the weights in the sub-blocks iteratively with the goal to minimize HE-rotations and accuracy loss. We have conducted extensive experiments based on three CNN models on MNIST dataset and CIFAR- 10 dataset and results show that the optimized CNN models can achieve overall speedups of 8.37x, 12. 1 1x, and 19.26x for LeNet, VGG-5, and HEFNet, respectively, with negligible accuracy loss. To our best knowledge, this is the first work to that builds optimizing framework for CNN model architecture from the aspect of structural sparsity and data packing in HE to benefit HE-based PPML inference.
Forr instance, Rot k) transforms encryption of (vo. UN)2-1) into encryption of (Miy.r 12/2-19 Nay ..., 1k-1)
2

---

Under review as a conference paper at ICLR 2023
2
PRELIMINARIES
2.1 CKKS HOMOMORPHIC ENCRYPTION
Homomorphic Encryption (HE) allows computations to be performed encrypted data without decryption. Among various HE schemes, the levelled HE- et al. 2 is widely adopted in the encrypted neural network inference because of supporting the fixed- point real number arithmetic and potentially avoiding the prohibitively expensive bootstrapping. The CKKSS based HE operations mainly consist of ciphertext addition HE-Add (ct, + ct2), ciphertext multiplication HE-Cmult (cl1 x cl2), scalar multiplication HE-Pmult (pl, x cl2), ciphertext roation HE-rotation Rot(e,, k), etc. For MLaaS that only encrypts clients' data, HE-Add, HE-Pmult and HE- rotation often dominate the computations of an encrypted inference. Among these three operations, HE-rotation costs much longer latency than the other two, e.g. 43x as our profiling result in Figure (a) shows, due to the complex automorphism operation and a key-switching operation. The detailed calculation process of HE-rotation can be described as:
Kim-Kim-----a (CKKS) (Cheon
Rot(ct, k) = (c(x**),0) + (a((i() eukkott
where the evaluation key (eoktod) is a public key with a larger modulus PQ, and P is greater than Q Assume et = (((X)))((X')) a(X') represents ciphertext before rotation, then the automorphism (c(X (k) and a ((x**) )) maps each polynomial coefficient index i to output polynomial coefficient index ik mod N, where N is the polynomial degree. The second term the right side of Equation| I represents the key-switching operation to ensure the final ciphertext can be still decrypted by the same secret key. It
very expensive and could take over 90% of all operations in practice (Samardzie et al. 2022)
2.2 THREAT MODEL
We assume the cloud-based machine learning service, of which a trained convolutional neural network (CNN) model with plaintext weights, is hosted in a cloud server. A client could upload his/her private and sensitive data to the public cloud for obtaining an online inference service. The cloud server is semi-honest (e.g. honest but curious). To ensue the confidentiality of clients' data against such a cloud server, the client utilizes HE to encrypt the data and then send it cloud for performing encrypted inference without decrypting the data or accessing the private key. Finally the client can decrypt the returned encrypted inference results from cloud using a private key. In this work, we focus on encrypting the client's 's data and others like model parameters, are assumed as plaintext.
2.3 MOTIVATION EXAMPLE
To identify the computation bottleneck in HE inference, we analyze the computation pattern of the convolutional layer, which often dominates CNN inference's 's memory and computational overheads, in the encryption process. Here the input and output activation feature maps are encrypted as ciphertext, while the convolutional kernels are assumed as plaintext. We also assume the state-of-the-ar ciphertext meoding-row-majoo (Dathathri et al.) 2019: Kim et al. (022) is adopted here. This allows efficient multi-chane ciphertext packing to take advantage of CPU's 's single-instruction wwatonmmllttlddddieeeee (SIMD) architecture for fast HE inference. Figure T (d) shows the typical HE convolution process of a convolution layer which consists of 2-input/output channels with 3 x 3 kernels. To compute a eiphertext output feature map, two types of cipertext rotations need to be performed sequentially. First, inner-rotation rotates each input channel's 's ciphertext feature map 8 times (or K 1, here kernel size K 3). Each rotated version will need to be multiplied with its corresponding weight plaintext, and then such results will be summed up to obtain an intermediate ciphertext from each input channel, which will further be concatenated as a whole ciphertext (e.g. Chl and Ch2 as ctl). Second, outer-rotation rotates the concatenated ciphertext multiple times (in this simple example, I time because of packing output channels as a ciphertext). Finally all ciphertext output feature maps can be obtained in parallel by the summation of these rotated copies. Apparently, compared to conneeerypted convolution, HE convolution significantly escalates the memory and computation overheads. Moreover, since the latency of HEErrotation can be much higher than other operations due to complex automorphism and key switching operations (see our profiling result in Figure a 63ms for HE-Rot v.s. 1.5ms for HE-Pmult, detailed setting in Sec. (.11). and the multi-channel convolutions in deep CNNs would involve a huge volume of HE-rotation? As a result, the long-latency HE-rotation quickly becomes a bottleneck of the encrypted inference.
"The matrix-vector multiplications follycconnected layers also require a substantial amount of HE-rotation.
3

---

Under review as a conference paper at ICLR 2023
HE Eeggroup Convolution
Sub-block Pruning
Group Convolution Subatitution
Identify sub- blocks model
Prune block weights rest
Update rest
model
sub-blocks
model recover the accuracy
CNN model
Repuat
Compile the number of groupe
(ciphertext size, daia dize)
Split the sub-blocks p. (all weights resulting ciphertex rotation)
The overall flow of SpENCNN framework for optimizing HE-based CNN inference, mainly consists of two orthogonal techniques to generate a tailored CNN model: (1) HE-group Convolution (outer-rotation optimization), and (2) the Sub-block Pruning (inner-rotation optimization).
Figure 2:
One straightforward solution to accelerating HE inference is to reduce the number of rotations through zeroing out (or pruning) the plaintext weights. As Figure [c) shows, if any weight plaintext-pl (k)) contains all zero values, then the corresponding ciphertext rotation-Roulccz,, k) and its associated multiplication and summation been proved to be effective in reducing the computation and memory overhead to speedup the nonencrypted inference without accuracy drop, we apply representative pruning methods-non- structured pruning(Han et al. 20155) (zeros appear randomly in a kernel, see Fig. [ess[((c)-) (c)-B, 75% sparsity) and structured pruning Wen al. (016)) (structured zeros in kernel, see filter pruning and channel pruning in Fig. (c)- and D. 50% sparsity). For HE operations in an example convolutional layer with 64 input/output channels, feature map size 32 x 32 and kernel size 3 x 3, as Fig. [ (d) shows, the existing pruning achieves very marginal or even no reduction of the HE-rotation latency which dominates the convolution computation. In the worst case, it even cannot remove any HE-rotation despite the high model sparsity, e.g. the non-structured pruning with 75% sparsity ratio. The underlying reason is two-fold: 1) pruning is unable to address the outer-rotation since computing output ciphertext by convolution needs to sum all channels' feature maps belonging to the same ciphertext if using the state-of-the state-of-the-ar -artth-art ciphertext encoding (see Fig. (a)); 2) existing pruning techniques are designed for non-encryted inference, and the special channel-wise ciphertext operations involved in HE convolution are ignored. This prompts the need of jointly optimizing ciphertext encoding and encryption-awen aware model sparsity accelerate HE inference.
be safely eliminated. Since existing pruning techniques have
3 THE SPENCNN FRAMEWORK
In this section, we present the technical details of our proposed SpENCNN framework. Figure 2 depicts its overall flow. The SpENCNN framework takes an initial CNN model as input and outputs a tailored CNN model after two processing (aaee-(1) HE-group Convolution is designed to reduce the outer-rotations caused by multi-channel convolution. In particular, we design and determine a theoretically optimal group number Gbese based on the size of the ciphertext and data packed in the CKKS HE scheme, to ensure that all outer-rotations can be climinated while keeping model accuracy. (2) Sub-block Pruning is further proposed to reduce the number of inner-rotations. However, this is not trivial. We observe that to reduce as many inner-rotations as possible, must precisely identify and completely prune selected sub-blocks. This, unfortunately, would result in an considerable accuracy drop. To address this issue, we develop set of sub-steps which include identifying subblocks, pruning the subblocks, updating the remaining subblocks, and retraining the model for accuracy recovery.
adjustable method
3.1 HE-GROUP CONVOLUTION
Two intuitions. Our proposed HE-group convolution is based on two intuitions. We observe that the number of required outer-rotations for ciphertext Rot = (/2x(Xxx)ppd N is the polynomial degree defined in the cryptographic parameters, h and w are the height and width of the input feature map, and pad rounds a number to the next power of two. Each ciphertext generated by the outer-rotation further requires a set of inner-rotations. The number of inner-rotations is Rotinner = K² - 1, where l is the convolutional kernel size. Apparently, increasing the number of outer-rotation Rotouter by just 1 can bring extra Rot K2 rntationns This gives us the first intuition rreuuiin- the number of outer nnttriooaaioos will fundamentally reduce the computational overhead.
1, where
4

---

Under review as a conference paper at ICLR 2023
General Convolution
HE-group Convolution
Group-Interleaved Format
d;
Ch1
Gh2
HE-rotation
O12
Gh1
di
C13
XE-olation
CM
d
d:
Chi
Group 1
Group
Syt,
X
Rod(c,, =))e)
Ki
Ki
Fn
Kis
Palls Kall
Xsc
Rac
Ch
Ch2
Chu
Ch
Ch
Ch
sigtt Ka
*9e, Ka
Ky
Kec
Ret(ffa (lgpa))
Ghi
Kzj
Resll
Ch
Nptt Ky
Xpt, Kuitt
Karth
out1
out3
outt
oud2
oudd
eut2
oui4
(e)
Figure 3: (a) an example of convolution which generates 4 output channels from the input channels with 3 x 3 kernels. By HEE-gropp convolution, we only need 2 group-interleaved encoded cts multiply with corresponding pts and sum up to get the output channels data. (b) proposed HE-group convolution by group interleaedee format.
The reason behind the outer-rotation is that multiple channels the same ciphertext are involved in the same multichannel convolution. In our study, we find that convolution (e.g., depthwise convolution (Howard et al., (017)) can be also performed individually within each single channel. We also find that the group convolution technique (Krizhevsky et al. 2012 ZZhng et al. 2018 loannou al. 2017) can reduce the number of channels involved each group. This gives us second intuition-reducing the number of channels in the group can eliminate the outer-rotation.
Based on these intuitions, we design the HE-group convolution. Given the group number G, we have the upper bound of the number of channels in the same group [(N/2-(h-w)pas) x 1/G]. Then the relationship between Rotouter and G can be expressed as:
Rotouter = ([M22((hwwppp
1/o] -1
(2)
Accordingly, we can use appropriate G value to cancel the first term, i.e., the Giase (12 in our design. Theoretically, this optimized value indicates zero outer-rotations.
Group-interleaved encoding. However, find that the traditional ciphertext encoding format is not compatible when we implement our grouping idea. This is because the row-major format mainly designed to perform convolution in the SIMD manner without considering the channel positions the ciphertext. To address this issue, we propose a group-interleaved encoding format the channel data from different groups placed the same ciphertext in interleaved manner. This new encoding facilitates fast HE-group convolution without involving any outer-rotation.
Figure 3 shows example of proposed HE--gropp convolution and group-interleaved encoding. We assume that two ciphertexts contain 4 channels of data, and each ciphertext ct, contains channels. As shown (a in general HE convolution, each ct, has to do outer-rotation to cover the different channels, i.e., {ch1, ch2) and {ch2, ch1} for ct1. Convolution will be performed individually on each outer-rotated case for all ciphertexts. The encrypted output channels {outz, outz), fouts, out,} can be generated after a summation.
For our HE group convolution, as Figure (a)-right shows, sibling channels {ch1, ch2) and (ch3, ch4) from the same ct, are in different convolution groups, which are encoded by our group- interleaved format, i.e., [ch1, ch3) ct₁ and [ch2, ch4] in ct2. Now, the outer rotation is eliminated because each et; can perform 2 groups of convolution individually without rotating the channels. The encrypted output channels after summation, i.c., {outj, outa), {out2, out4), ). are naturally group- interleaved and can immediately send to the next HE-group convolution. F (b) further shows the generalized group-interlean encoding, which a ciphertext can encrypt M channels using the adjustable convolution group number G, with constraints G < M and M%G 0.
3.2 SUB-BLOCK PRUNING
We design the sub-block pruning to further remove the remaining inner-rotation, after the HE-group convolution. Our idea is to prune (zero out) whole set of weights corresponding specific inner- rotations, so that the computational overhead of these ioneriootaiions can eliminated. This reminds us of the weight sparsity in CNN models. In HE-convolution, an inner-rotated ciphertext will be
5

---

Under review as a conference paper at ICLR 2023
Xai
Sox dl
Ki
K
fce di
K
Bg
Red(ch,
sub-block
Bot(ct
Rot
hubb-block
(4) Weight sparsity convolutional layers
Weight sparsity layers
Figure 4: (a) The weight sparse pattern in convolutional layers. For the same cl, their weight sparse patterns must be same. For different ct, the weight sparse pattern may change. (b) The weight sparse pattern FC layers is in diagonal-wise shape.
multiplied with the weights at the same position, namely "sub-block", from all relevant kernels. Therefore, our design tends to cut out the same sparse pattern these sub-blocks for all relevant kernels of the same ciphertext.
As the example in Figure (a) shows, the 4 kernels of ct shares the same sparse pattern, thus eliminating 6 inner-rotations. This pruning scheme can be also extended to the FC layer. As shown in Figure 4 (b), the multiplication of ciphertext a diagonal-win encoding method (Halevi & Shoup 2014). Multiplying with the weights in one diagonal line requires one HE-rotated copy of ciphertext. (see Appendix A.3 for more details.)
FC layer is equivalent to the convolution using
To obtain the desired sparse pattern, we propose the sub-block pruning. The more sub-blocks p; being pruned, the less inner-rotations needed. This is actually an optimization problem, in which, we need to minimize the total number of sub-blocks while maintaining the prediction accuracy concurrently:
min(P=> PP=E:: Ti} s.t. (ar( (W, 2 (z; W)) where 7, = So is pruned {1 other
We would like to find the sub-block with the minimum weight importance to the model at each iteration and prune, then, retrain the model for few epochs recover the accuracy. However, the sizes of sub-blocks are different. To measure the weight importance of each sub-block in a fair way. || |I
we define the weight importance metric as average L norm at each iteration, we would like to prune the sub-block with the least weight importance. The iterative algorithm would stop when the model accuracy is lower than the initial accuracy.
dim( (mm,),))) As described algorithm
EVALUATION
4.1 EXPERIMENT SETUP
Setup. We conduct our experiments on a workstation equipped with an AMD Ryzen Threadripper 3975WX CPU, an NVIDIA RTX 3090 GPU, and 256GB of RAM. To evaluate our proposed SpENCNN, we select three baseline CNN models that are often adopted in HE inference performance evaluation, and implement them using PyTorch GPU. This includes LeNet-like for MNIST
Model
# #Layers
Groups (Guas)
Accuracy
Algorithm 1 Sub-blocks Iterative Pruning
Conv
FC
Act
(%)
LeNet-like
Input: CNN model:f (W, P)).
VGG-5
84.06
Remark: x-Data, W-Weights, P-HE blocks
HEENet
83.67
3: Output: HE-friendly mfdel:f((z (W', P'))
Encryption Parameters
Mult
Security
Model
Level
4: P' = = P= E,
LeNet-like
8192
264
24
10
>12 bit
5: While Accuracy loss <0:
VGG-5
16384
529
31
16
80 bit
6:
i argmin dim((pp))
||w,,
HKFNet
16384
436
31
>128 bit
7:
1: =
Table 1: Three baseline Convolutional Neural Net-
8:
prune weights pa from current P
works models and corresponding Encryption Pa-
9:
update P
rameters. LeNet-like is for the MNIST dataset.
10:
retrain model with P' and update W
VGG-5 and HEFNet are for CIFAR-10 dataset.
11:
end While
12:
Return (x; (W', P))

---

Under review as a conference paper at ICLR 2023
dataset (0116) VGG-5 (Rathi et al. 2020) and the HE-frieedly Net (HEFNet) for CIFARIO dataset (Details of layer size is in Appendix (.2)). Since the non-linear activation function like ReLU cannot be evaluated in HE, replace ReLU with the adaptive quadratic polynomial function f(x) = az.² + bx + c following the related works (Dathathri et al. 2019; Kim et al. 2022), where a, a. c trainable parameters maintain the model accuracy. Table lists the specifications of these three models and the corresponding accuracy. In particular, the test accuracy for LeNet-like-MINST VGG-5-CIFARIU 10, HEFNET-CIFARIO 98.95% ,, 84.06%. and 83.67%, respectively, which consistent with their original versions.
We use Microsoft SEAL library v3.4.5 (SEAL) to implement the RNS-CKKS HE computation on these networks, Table a lists the key parameters used in our RNS-CKKS encryption, including the polynomial degree N, the total modulus in bit-length Q, the scale factor in bit-length to maintain the HE evaluation accuracy, and total multiplication level. These parameters can guarantee a security level of 80 bit for VGG-5, 128 bit for LeNet-like and HEFNet.
Methodology. We first perform an ablation study to evaluate each individual technique's effectiveness, and then compare the whole SpENCNN framework with state-of-the-art method. y We adopt the average inference latency (in seconds) as the main measurement, An image set containing 20 different samples is used to measure and report the latency for these models. A lower latency indicates better measure the left holomorphic operation count (HOC, in %). sparsity (in
performance. In addition, %), and accuracy (in %) on the tailored models. The lower HOC and lower sparsity while offering higher accuracy desired on all models.
4.2 RESULTS
4.2.1
EVALUATON ON HE-GROUP CONVOLUTION
T lists our evaluation results for the HE--grop convolution. We apply the HE group convolution alone (in ablation) to each baseline model and evaluate its effectiveness and scalability. In particular, adjust the number of groups from its default (i.e., 1-baseline) until it exceed its Gbase according to our design (i.c., the highlighted 4, 8, and 8 for LeNet-like, VGG-5, and HEFNet, respectively). For detailed analysis, breakdown HOC into "Rot" (HE-rotation) and "Others" (other operations including imuut and HE-add).
Our HE-group convolution be scaled any convolutional model. As the number of groups increases, it can effectively reduce the number of HOC and maintain the accuracy, thus reducing the latency of HE inference and improving the performance. As listed in Table 2 the number of HE-rotation is reduced from 100% to 27.27%, 85.45%, and 11.95% on LeNet-like. VGG-5, and HEFNet, respectively. Once the Gbase is reached, the number of HE-rotation does not decrease further in spite of increasing the number of groups This is because the outer-rotation is completely eliminated HE-group convolution after the group number reaches Gbase. We also find that HE group convolution can reduce other HOC such as HE-Pmult and HE-add even after exceeding Gbase- This also contributes to the performance improvement.
For example, the HE-group convolution is particularly effective on our HEFNet (i.e., 88% and 86% reduction for HE-rotation and others, respectively). This because it has the largest volume of convolution layers among the three models. Such dramatic reduction in HOC further shortens the
HOC Left (%)
Model
Groups
Accuracy (%)
Latency (s)
Speedup (x)
Rot
Others
1-baseline
98.95
1,2658
51.52
52.91
98.95
0.6806
1.86
LeNet-like
27.27
28.24
98.95
0.3807
3.32
8
27.27
16.47
98.67
0.3044
4.16
I-baseline
85.16
53.909
87.53
84.08
84.53
46.539
1.16
VGG-S
8
85.45
81.42
84.06
45.311
1.19
16
85.45
80.10
82.23
45.053
1.20
I-baseline
84.91
24.113
24.53
25.74
84.35
6.2491
3.86
HEFNet
8
11.95
13.36
83.67
3.2718
7.37
16
11.95
7.18
80.06
2.3627
10.21
Table 2: Ablation study of HE-group convolution with different number of convolution groups.
7

---

Under review as a conference paper at ICLR 2023
inference latency from 24. Is to 3.27s, which represents x speedup. In contrast, the HE group convolution is the least effective VGG-5, as it contains three large FC layers (size of 8192x,096) which cannot be substantially optimized using HE group convolution alone. There more than 85% of HE-rotations and 80% other operations that cannot be eliminated. And this number saturates as lower bound after reaching the Ghase, resulting in limited speedup of 1.19x.
We also observe that the model accuracy slightly decreases as the number of groups increases. This due the fact that fewer channels are involved in the HEEggrup convolution compared to the general convolution (see Figure 5}. Fortunately, as long as the number of groups does not exceed our suggested Gbase: the loss of accuracy marginal (i.e.. 0%. 1.1%, and 1.2% on LeNet-like, VGG-5, and HEFNet, respectively). Also, our design is adjustable, allowing a trade-off between the accuracy and the optimized number of convolution groups.
4.2.2 EVALUATION ON SUB-BLOCK PRUNING
Here, we apply the sub-block pruning alone (in ablation) and compare with other pruning methods such as Non-structural prune (Han al. 2015a), and Structural prrctural-pune (Wen et al. 2016). Table lists our evaluation results. We do not include accuracy in this evaluation since we prune each baseline model using each pruning method under the constraint of maintaining the original model accuracy. Instead, we include the sparsity (i.e., the percentage of pruned weights) for comparison.
Our sub-block pruning effectively improve the HE inference performance all baseline models (i.e., the speedup of 2.62x, 6.15x, and 2.57x on LeNet-like, VGG-5, and HEFNet, respectively). which significantly outperforms other traditional pruning methods (i.e., marginal 1.1 x speedup on most cases). The reason is obvious but significant. Our design is more HE-oriented and effective in the ciphertext domain while traditional pruning more prarstty-oriented and for the plaintext computation efficiency only. For example, although NS NS-prune can prune ~ 92% of the weights on VGG-5, cannot eliminate the HE overhead (i.e., ~ 96% HOC) caused by the remaining 8% of the weights.
Our sub-block pruning method performs the best (i.e., 16% HOC) on VGG-5 because effectively eliminates the inner-rotations caused by the large number of redundant weights in the FC layers. Together with the previous results (see Table 22), sub-block pruning can be good complement to the HE- HEE-group convolution that performs weakly the FC layers. We also note that our sub-block pruming method on LeNet-like (i.c., 35.21% Rot left) slightly outperforms HEFNet (i.c., 41.88% Rot left). This is because the larger convolutional kemnel (i.e., 5 x 5) in LeNet-like gives our pruning method more space to optimize the inner-rotations.
4.2.3 COMPARE WITH THE TFATE-OF-THE-ARY
We compare our method with the ofate-of-the-ar HE-prune method-Hunter (Cai et al. 2022). The comparison results are presented in Table 4 In this evaluation, our method combines the HE-group convolution and the sub-block pruning, and uses the proposed Gbase as the group number (i.e., highlighted data). For fair comparison, pruning is well controlled ensure that our method and Hunter have the same level of accuracy (i.e., errors #0.04% on all baseline models. We can see from Table our method outperforms the ofate-of-the-art sigiiiin in terms HOC, sparsity, and
HOC Left (%)
Network
Groups
Sparsity (%)
Latency (s)
Speedup (x)
Rot Others
Dense-Baseline
0.00
1.2658
NS-prune
96.12
96.23
91.00
1.2190
1.04
LeNet-like
S-prune (channel)
88.03
92.82
53.77
1.1202
1.13
Sub-block prune
35.21
34.07
63.83
0.4644
2.62
Basee-e
0.00
53,909
NS-prune
97.59
97.14
91.88
52.5280
1.03
VGG-5
S-prune (channel)
98.47
98.08
90.48
50,7178
1.06
Sub-block prune
15.89
16.11
89.87
8.7659
6.15
Dense-Baseling
0.00
24.113
NS-prune
85.60
88,97
72.95
21.1660
1.14
HEFNet
S-prune (channel)
94.69
95.24
51.91
22.9240
1.05
Sub-block prune
41.88
36.11
63.90
9,3709
2.57
Table 3: Ablation study of sub-block prune and comparison with other pruning methods.
8

---

Under review as a conference paper at ICLR 2023
HOC Left (%)
Sparsity (%)
Accuracy (%)
Lateney
Speedup
Network
Method
Rot
Others
(8)
(x)
Baseline
0
98,95
1.2658
LeNet-like
Hunter
40.95 8.54
39.91
59.99
98.95
0.5353
2.36
Ours-4
9.88
62.62
98.95
0.1535
8.37
Baseline
0
85.16
53,909
VGG-5
Hunter
17.86
18.93
89.81
84.03
9.9916
5,40
Ours-8
7.86
7.72
91.97
84.07
4,3830
12.11
Baseline
84.91
24.113
HEFNet
Hunter
48.27
42.20
$7.82
83.63
10,855
2.22
Ours-8
3.99
4.61
65.62
83.67
1.2520
19.26
Table 4: Comparison with Hunter model HOC left, sparsity, accuracy,latency ,nd speedup.
latency, on all baseline models. For example, our method eliminates 96% HE-rotations on HEFNet, achieving 19.26x speedup. In contrast, the Hunter-optimized model still has 51% HE-rotations left behind and achieves only x.22x speedup compared to the un-pruned baseline. This is because our method is designed eliminate both outer and inner HE-rotations by synthetically applying the HE- -rrup convolution and sub-block pruning, while the state oftte-a---e-rttttt is solely built upon the fixed structure pruning. We also print out the sparse pattern in convolutional layer of LeNet-like, included in Appendix A.1
5 RELATED WORK
CryptoNets (Gila Bachrach al. 2016) is an initial attempt realize HE-inference. After that, many subsequent works are proposed to improve the HE-inference latency from different aspects. Faster-CryptoNes (Chou et al. 2018) combines weight pruning and quantization to obtain a sparse polynomial representation to speed up the PMult operation, which achieves 6.38 latency reduction. LoLa (Brutzkus et al., 2019) successfully demonstrates the HE inference on a simple 3-layer model (1 convolutional layer and 2 FC layers) and achieves 2.2s inference latency the MNIST sample by leveraging HE schemes, data encoding format, and rotation techniques. CHET and HEAR (Dathathri ct al. 2019 Kim et al. (2022) further refine the row-major coding format achieve the same level of inference latency, but on larger network (3 convolutional layers and minimum 64 channels).
Lou & Jiang (2021) propose neural architecture search (NAS) based method reduce the encryption parameters and speed up the HE-inference. Further, Ghodsi et al.] (2020); Tha et al.] (202T): [Msshra et al. (2020); Lou et al. (2020) propose reduce the cost of non- non-linear operations in NAS based
HE-inference since operations like ReLU dominate the latency in the multi-party computation (MPC) setting. HEi-PE (Aharoni et al., 2022) and Hunter (Cai al. 2022) attempt to structurally prune the weights to accelerate the HE-inference. In Hunter, a structural pruning method is proposed to facilitate HE in the MPC setting. HE-PEx adpots Hunter's method to prune the weights in the FC layer only. It can reduce memory requirement and latency by 60% on the tested autoencoder models. Our work- SprKNN is the first to orchestrate the ciphertext encoding and model sparsity design for HE inference acceleration, significantly outperforming these works.
6 CONCLUSION
In this paper, we propose a fast LHE-based encrypted inference Sew.worr--SEENNNNNN built upon two novel techniqees-HE-gaee
convolution and sub-block weight pruning. Experimental results show that our solution can speed up the privacy-preserving inference by 8.37x, 12.1lx, and 19.26x on LeNet-like, VGG-5, and HEFNet, respectively, greatly outperforming the state-of-the-arr solutions. In the future, we would like to extend our work to deeper models and complex classification tasks in no-client-interaction setting by leveraging bootstrapping. We hope to apply our framework to these deep models. There shall exist potential optimizations for the trade-off between model sparsification, data encoding, bootstrapping, and cryptographic parameters.

---

Under review as a conference paper at ICLR 2023
REFERENCES
TensorFlow 2016. Lenet-like for convolutional mnist model example. /tt.:////.....ttttrraaaaaaaaa/// image/
https:
mnist/ mnist/conven wtt.st//ccoooouttnna........
Ehud Aharoni, Moran Baruch, Pradip Bose, Alper Buyuktosunoglu, Nir Drucker, Subhankar Pal, Tomer Pelleg, Kanthi Sarpatwar, Hayim Shaul, Omri Soceanu, al. He-pex: Efficient machine learning under homomorphic encryption using pruning, permutation and expansion. arXiv preprint 22t.:22007003844, 2022.
Alon Brutzkus, Ran Gilad Bachrach, and Oren Elisha. Low latency privacy preserving inference. In International Conference Machine Learning, pp. 812 821. PMLR, 2019.
Yifei Cai, Qiao Zhang, Rui Ning, Chunsheng Xin, and Hongyi Wu. Hunter: He-friendly structured pruning for efficient privacy-preserving deep learning. In Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security, pp. 931-945, 2022.
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In International conference on the theory and application of cryptology and information security. pp. 409-437. Springer, 2017.
Edward Chou, Josh Beal, Daniel Levy, Serena Yeung, Albert Haque, and Li Fei-Fei. Faster cryptonets: Leveraging sparsity for real-world encrypted inference. arXiv preprint 1811 1.09553, 2018.
Roshan Dathathri, Olli Saarikivi, Hao Chen, Kim Laine, Kristin Lauter, Saeed Maleki, Madanlal Musuvathi, and Todd Mytkowicz. Chet: an optimizing compiler for fully-homomorphic neural- network inferencing. In Proceedings of the 40th ACM SIGPIAN Conference on Programming Language Design and Implementation, pp. 142-156, 2019.
Zahra Ghodsi, Akshaj Kumar Veldanda, Brandon Reagen, and Siddharth Garg. Cryptonas: Private inference on a relu budget. Advances in Neural Information Processing Systems, 13:6616-11 2020.
Ran
Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Nachrig, and John Wernsing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International conference on machine learning, pp. 201-210. PMLR, 2016.
Shai Halevi and Victor Shoup. Algorithms in helib. In Annual Cryptology Conference, pp. 554-571 571. Springer, 2014.
Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510. 40149, 2015a.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015b.
Andrew Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv: htt.::/7744.0000 774.044611 2017.
Yani Ioannou, Duncan Robertson, Roberto Cipolla, and Antonio Criminisi. Deep roots: Improving cnn efficiency with hierarchical filter groups Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1231-1240, 2017.
Nandan Kumar Jha, Zahra Ghodsi, Siddharth Garg, and Brandon Reagen. Deepreduce: Relu reduction for fast private inference. In International Conference on Machine Learning, pp. 4839 484994849, PMLR, 2021.
Miran Kim, Xiaoqian Jiang, Kristin Lauter, Elkhan Ismayilzada, and Shayan Shams. Secure human action recognition by encrypted neural network inference. Nature communications, 13(1):1-13, 2022.
10

---

Under review as a conference paper at ICLR 2023
A Krizhevsky. Sutskever, and GE Hinton. Imagenet classification with deep convolutional neural networks. 2012 advances in neural information processing systems (nips). Neural Information Processing Systems Foundation, La Jolla, CA, 2012.
Qian Lou and Lei Jiang. Hemet: A iwwnoooorppii-eeeeptto-----ii-ii privacy-preserving mobile neural network architecture. In International conference on machine learning, pp. 7102-7110. PMLR, 2021.
Qian Lou, Song Bian, and Lei Jiang. Autoprivacy: Automated layer-wise parameter selection for secure neural network inference. Advances in Neural Information Processing Systems, 33: 8638-8647, 2020.
Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. Delphi: cryptographic inference service for neural networks. In 29th USENIX Security Sympo- sium (USENIX Security 20), pp. 2505-2522, 2020.
Nitin Rathi, Gopalakrishnan Srinivasan, Priyadarshini Panda, and Kaushik Roy. Enabling deep spiking neural networks with hybrid conversion and spike timing dependent backpropagation. In International Conference on Learning Representations, 2020. httpptts///opeereevi..e
net/ net/forune htt///ooumiidddaae SSSperKv
Nikola Samardzic, Axel Feldmann, Aleksandar Krastev, Nathan Manohar, Nicholas Genise, Srinivas Devadas, Karim Eldefrawy, Chris Peikert, and Daniel Sanchez. Craterlake: hardware accelerator for efficient unbounded computation on encrypted data. In ISCA, pp. 173-187, 2022.
SEAL. Microsoft SEAL (release 3.4). http::///Lthhb..co//kirrottttt/t 2019. Microsoft Research, Redmond, WA.
October
Nigel P Smart and Frederik Vercauteren. Fully homomorphic encryption with relatively small key and ciphertext sizes. In International Workshop on Public Key Cryptography, pp. 420 443. Springer, 2010.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances neural information processing systems, 29, 2016.
Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. Shufflenet: An extremely efficient convolutional neural network for mobile devices. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 9848-6856. 2018

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 SPARSE PATTERNS
We present the weights after optimized in binary representation. In each group, it contains 64 weight kernels with size 5 x 5. Kernels in same group indicate that they are associated with the same ciphertext. Within the same group, across different ciphertexts, the sparse patterns are different.
Group 1
Group 2
Figure 5: The sparse patterns for weight kernels in LeNet-like 2nd Convolutional layer.
A.2 BASELINE MODEL ARCHITECTURE IN DETAIL
The following Table contain the detailed convolutional kernels size, weight matrix size and number of channels. These three baseline models has different property. The LeNet-like model is a tiny model designed for simple classification task that the channel number and weight matrix size is small, and has the least number of layers. The VGG-5 model has much more weights in FC layers and the max number of layers. The HEFNet contain the most convolutional layers and the widest channel size.
Network
Layer Conv
Input channel
Output channel
Kernel size (Matrix size in FC)
32
5x5
Conv2
5x5
LeNet-like
FCI
64
32
64x32
FC2
32
10
32x 10
Conv1
64
3x3
Conv2
64
128
3x3
Conv3
128
128
3x3
VGG-5
FC1
8192
4096
8192x4096
FC2
4096
4096
4096x
FC3
4096
10
4096x TO
Conv1
64
3x3
Conv2
64
128
3x3
HEFNet
Conv3
128
256
3x3
Conv4
256
256
3x3
FCI
1024
10
1024x 10
Table 5: Convolutional layer and Fully-connected layer size in three baseline models.
A.3 MATRIX MUL.TIPLICATION IN FC LAYER
Halevi & Shoup (014) proposed a diagonal-wise multiplication ciphertexts on FC layers. Given a N-element ciphertext ct = {*1..N), ), the weights of FC layer can be reshaped into M x N x N tensor (W3 (will pad with zero if needed). For each N N matrix W, diagonal N elements (as plaintext) with the rotated copies of ciphertext. As the example shown in Figure 6 have et ( and x matrix W. We have pl. {a11, 022, 0g3, 444).
multiply the
12

---

Under review as a conference paper at ICLR 2023
pt, {as1. d12, d23, 034). pt2 fas1, a42, d13, 021), and pts (a21 d32. 443, 014) They will be multiplied by ot = {I1, 22, 23, xT). Rot(ct, 1) {Tg, 23, 21, 21 ). Rot(ct, 2) = { 24. 21, Ø2). and Rot(ct, 3) {oa, 22, 23), respectively and then summed.
ct copies
611
412
03
d14
2
2
3²
021
022
024
pts
x Rot(ct,,) 3)
273
22
23
22
d31
032
a33
434
pt2
x Root(ct, 2)
Σ
272
.23
27.4
21
pt1
x XRot(ct, 1)
d,2
a44
0.4
21
222
273
24
pt
xet
Matrix W
Figure 6: Ciphertext multiply with matrix.
13


Reviews:
[{"review_id": "hewA-xqteKS", "reviewer": "Reviewer_WT91", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents two techniques for speeding up convolutional neural network inference in homomorphic encryption settings.\nConceptually, the underlying RNS-CKKS homomorphic encryption provides the functionality to securely evaluate functions over a vector of encrypted data in a SIMD manner. In this specific setting, this paper proposes a novel data encoding scheme and a HE-specific pruning technique (sub-block pruning) that substantially reduce the number of homomorphic operations.", "summary_of_the_review": "Overall, I think the problem they considered is very important, and the proposed solutions are simple and effective and have a very wide application in secure neural network applications. But this paper's contribution is also limited by the lack of consideration of other aspects like bootstrapping and approximation of non-linear activation function.", "strength_and_weaknesses": "Strength:\nThey considered the problem very common and important in building homomorphic encrypted neural network applications, especially the data encoding one. Also, their solutions are simple and very effective. \n\nWeakness:\n- In the experiment setup, they didn't explicitly mention how they deal with level-zero ciphertexts. I assume that they didn't use bootstrapping and do the re-encryption.\n- Same as above, usually in applications, bootstrapping will dominate in the computational cost. Which will make this work less important than it is justified to be. However, these are two independent directions of improvement.\n- Except for bootstrapping, the choice of activation function is also questionable. Beyond quadratic polynomials, other works already adopt high-precision approximation of the non-linear ReLU function for higher accuracy (e.g. https://arxiv.org/abs/2105.10879 ). Though, it's also independent of the proposed techniques. But it's better to check in experiments if they could be combined.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "hH3cwevQCm", "reviewer": "Reviewer_CCNN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a method for privacy-preserving neural network inference using homomorphic encryption. The main contributation is optimizing the convoluational layer to fit the SIMD structure of homomorphic encryption, including reducing the number of non-zero weights and re-training.\n", "summary_of_the_review": "Interesting idea marred by editorial issues\n", "strength_and_weaknesses": "The core idea is interesting and novel to me, but I see issues with the presentation.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Bdl_EiSjEYO", "reviewer": "Reviewer_AXmR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper seeks to improve the computational efficiency of convolution layers in FHE. Since homomorphic rotations are the primary computational bottleneck of convolutions in FHE, the paper seeks to reduce the number of rotations. This is achieved in two steps, 1) adopting group convolutions, which reduces out-level rotations, and 2) weight pruning, which reduces inner-level rotations.\n\nThe efficiency of the proposed convolution is evaluated on *shallow* CNNs designed for MNIST and CIFAR-10. The proposed approach shows appreciable speed-up over *naive* implementations of convolutions in FHE.", "summary_of_the_review": "The paper proposed to use group convolutions and a weight pruning to mitigate the computational bottlenecks of convolutional layers, namely homomorphic rotations. The paper, however, does not compare to or discuss existing attempts toward HE-friendly CNNs. Furthermore, the experiments are conducted on shallow networks. The proposed approach will not provide much computational benefit for deeper networks since convolution is not the main bottleneck for such networks. Reproducibility is also limited.\n\nOverall, the paper has good ideas, but an evaluation, comparison, and discussion of the broader utility of the proposed approach are missing.\n\n**Update After Rebuttal:** The author's rebuttal does not adequately address the comments from the initial review. In theory, the method may have promise in achieving the claims in the rebuttal, but I do not believe it is straightforward and needs to be demonstrated. I will maintain the original rating.", "strength_and_weaknesses": "Strengths:\n- The paper rightly identifies the main bottleneck of *naive* implementations of convolution in FHE, namely rotations. As such, efforts to improve efficiency of convolution is necessary. Leveraging alternative convolutions, such as group convolutions or in the extreme depth-wise convolutions is interesting.\n- Adopting pruning for sparsifying the convolution and optimizing the sparsity pattern for reducing number of homomorphic rotations.\n\nWeaknesses:\n- The main drawback of the paper is the lack of comparisons to prior work that improve efficiency of convolutions. These include multiplexed convolutions [1], mobile networks explored HEMET [2].\n- The main premise of the paper is that rotations in convolutional layers are the main computational bottleneck of networks in FHE. So the paper considers shallow networks only, which are not likely to be practically useful. For instance 85% accuracy on CIFAR-10 is quite poor by the standards of the best plaintext models which achieve ~99% accuracy.\n- As networks become deeper, the main accuracy bottleneck is low-degree polynomial approximations of non-linear functions like ReLU and the main computational bottleneck is the bootstrapping operations required for evaluating high-multiplicative depth circuits. So improving efficiency of convolutional layers does not benefit deeper networks since convolution is not the main bottleneck for such networks.\n\nOther Clarification Questions:\n- The paper does not mention how pooling operations or strided convolutions are handled. Strided convolutions result in wasted slots. How  does that affect the proposed convolutions?\n\n[1] HEMET: A Homomorphic-Encryption-Friendly Privacy-Preserving Mobile Neural Network Architecture, ICML 2021\n[2] Low-Complexity Deep Convolutional Neural Networks on Fully Homomorphic Encryption Using Multiplexed Parallel Convolutions, ICML 2022\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject