HyPHEN: A Hybrid Packing Method and Optimizations for Homomorphic Encryption-Based Neural Network 
Authors: Jaiyoung Park
Donghwan Kim
Jung Ho Ahn
Venue: Submitted to ICLR 2023 (2023)
Keywords: Private Inference
Homomorphic Encryption
PPML

Abstract: Private Inference (PI) enables users to enjoy secure AI inference services while companies comply with regulations. Fully Homomorphic Encryption (FHE) based Convolutional Neural Network (CNN) inference is promising as users can offload the whole computation process to the server while protecting the privacy of sensitive data. Recent advances in AI research have enabled HE-friendly deep CNN like ResNet. However, FHE-based CNN (HCNN) suffers from high computational overhead. 
Prior HCNN approaches rely on dense packing techniques that aggregate as many channels into the ciphertext to reduce element-wise operations like multiplication and bootstrapping.
However, these approaches require performing an excessive amount of homomorphic rotations to accumulate channels and maintain dense data organization, which takes up most of the runtime.
To overcome this limitation, we present HyPHEN, a deep HCNN implementation that drastically reduces the number of homomorphic rotations.
HyPHEN utilizes a novel convolution algorithm, RAConv, utilizing replication-based data organization, which leads to a significant reduction in rotation count.
Furthermore, we propose hybrid gap packing method for HyPHEN, which gathers sparse convolution results into a dense data organization with a marginal increase in the number of rotations.
HyPHEN explores the trade-off between the computational costs of rotations and other operations, and finds the optimal point minimizing the execution time.
With these optimizations, HyPHEN takes 3.8-4.9$\times$ less execution time than the state-of-the-art HCNN implementation and brings the runtimes of ResNet inference down to 1.38-14.86s using a GPU-accelerated HEAAN library.

Under review as a conference paper at ICLR 2023
HYPHEN: A HYBRID PACKING METHOD AND OPTIMIZATIONS FOR HоMOMORPHIC ENCRYPTION BASED NEURAL NETWORK
Anonymous authors Paper under double-blind review
ABSTRACT
Private Inference (PI) enables users to enjoy secure inference services while companies comply with regulations. Fully Homomorphic Encryption (FHE) based Convolutional Neural Network (CNN) inference is promising as users can offload the whole computation process to the server while protecting the privacy sensitive data. Recent advances Al research have enabled HE- HE-friendly deep CNN like ResNet. However, FHE-based CNN (HCNN) suffers from high putational overhead. Prior HCNN approaches rely on dense packing techniques that aggregate many channels into the ciphertext reduce element-wise oper- ations like multiplication and bootstrapping. However, these approaches require performing an excessive amount of homomorphic rotations accumulate chan- nels and maintain dense data organization, which takes up most of the runtime. To overcome this limitation, we present HyPHEN, deep HCNN implementation that drastically reduces the number of homomorphic rotations. HyPHEN lever- ages two convolution algorithms, CAConv and RAConv. Alternating between two convolution algorithms leads to significant reduction in rotation count. Further- more, we propose hybrid gap packing method for HyPHEN, which gathers sparse convolution results into a dense data organization with marginal increase in the number of rotations. HyPHEN explores the trade-off between the computational costs of rotations and other operations, and finds the optimal point minimizing the execution time. With these optimizations, HyPHEN takes 3.4-4.4x less execu- tion time than the state-of-the-art HCNN implementation and brings the runtimes of ResNet on CIFARIO inference down to 1 1.44-13.37. using a GPU-accelerated HEAAN library.
INTRODUCTION
Private inference (PI) has recently gained the spotlight in the MLaaS domain as cloud companies should comply with privacy regulations such as GDPR Regulation (2016) and HIPAA Act (1996). PI enables inference services at the cloud server while protecting the privacy of the client and the intellectual properties of the service provider. For instance, hospitals can provide private medi- cal diagnosis of discases, and security companies can provide private surveillance systems without accessing client's 's sensitive data (Kumar et al., 2020 Bowditch et al., 2020).
PI can be achieved using various cryptographic primitives (Gentry 2009 Yao 1982 Costan &
Devadas 2016). Fully Homomorphic Encryption (FHE), which is set cryptographic schemes that can directly evaluate rich set of functions on encrypted data, is especially suited for PI. FHE- based Pl solution uniquely features 1) full offloading of the computation process to the server, 2) succinct data communication requirement, and 3) non-disclosure of any information about the model except the inference result. Such benefits have driven researchers to investigate convolutional neural network (CNN) PI implementations using FHE (Gilad-Bachrach
Bachrach et al. 2016 Brutzkus et al. 2019
Dathathri et al. 2020 Lee et al. 2022a Aharoni et al. (020).
To implement CNN using FHE, activation functions should be replaced with polynomials as FHE
only supports arithmetic operations of addition and multiplication. Given the constraint, two classes of polynomial activation functions have been proposed: (i) low-degree polynomials

---

Under review as a conference paper at ICLR 2023
et al. 2016 Chabanne et al. 2017) replacing the activation functions in training neural networks, and (i1) more precise high-degree approximation of ReLU (Lee et al. 2021) that replaces RELU during PI without additional training. However, both approaches lack practicality: low-degree polynomials are not applicable to deep neural networks and high-degree approximation significantly degrades the runtime of Pl. Recently, Park et al. (2022) showed that deep homomorphic CNNs (HCNNs) can be trained with low-degree polynomials even for complex image datasets with their proposal, AESPA, which utilizes orthogonal polynomial bases and fuses activation functions with batch normalization (BN) to turn them into second -egree polynomials. AESPA does not sacrifice runtime nor accuracy unlike prior approaches, thus we employ AESPA our work.
Another line of research lies in implementing an efficient convolution algorithm in FHE. Gazelle (Ju- vekar et al. 2018) proposed a convolution algorithm that can compute single Conv layer on FHE. However, Gazelle's s method cannot be directly applied to continuous convolutions as it requires ad- justing arrangement of data by re-encrypting ciphertexts after every Conv layer. [ee et al. (2022a) modified Gazelle's s convolution by densely mapping data into a ciphertext before entering the next Conv layer. However, the current state of HCNN is far from being practical. Using the convolution algorithm of Lee al. (2022a) and approximated ReLU, inference times of ResNet20 CIFAR-10 -0 are 1662/174s using a single/64 threads in our CPU environment. Despite the unique advantages of FHE--ased PI, the huge runtime overhead prevents FHE from being the go-to solution for PI.
We propose Hybrid Packing method and optimizations for Homomophic Eneryption-based neural Network (HyPHEN), which mitigates the huge overhead of HCNN with optimized convolu- tion algorithm and packing method. We observe that after AEPSA is applied, rotation operations in HCNN take up the majority of the runtime (See Appendix (A) and most of the rotations (92-99%) are spent to implement the sum of channels within the same ciphertext and maintain data organization. We design a novel convolution algorithm named RAConv that does not require rotations to accu- mulate channels. In addition, based on the observation that maintaining a single data organization necessitates massive unnecessary rotations, we design RAConv to take the new data organization based on the replication of the images. By alternating between two data organizations, we remove rotations priorly required to adjust the data organization. HyPHEN also includes a novel Hybrid Packing (HP) method that effectively handles the gap arising from strided convolution (Section 3.2) HyPHEN achieves 39.6s and 1.44s of runtime in ResNet20 for the CIFAR-10 dataset on CPU and GPU, respectively. The key contributions of the paper
follows: We propose a replication- aeplication-based convolution method, RAConv, that can effectively reduce two types of unnecessary rotations which are the major bottleneck in HCNN.
We propose a novel hybrid packing (HP) method that can utilize the entire slots of a cipher- text with a marginal increase in the number of rotations.
Our experiments show that our HCNN implementation with HyPHEN improves the infer- ence latency by 3.4-4.4x over prior state-of-the-arr HCNNs for ResNet on CIFAR-10.
BACKGROUND
2.1 FULLY HOMOMORPIIC ENCRYPTION
FHE is set of public key encryption schemes that can perform computation on encrypted data. Among several popular FHE schemes, RNS-CKKS (Cheon et al. 2018) has been broadly adopted in the PI domain as it supports fixed-point numbers and slot butching. A plaintext in RNS-CKKS is an unencrypted degree-N polynomial in a cyclotomic polynomial ring, RQ= [X](X> +1). A plaintext maps to message which is vector of N/2 real (or complex) numbers. Thus a single plaintext batches N/2 slots, which can store complex or real numbers. CKKS encrypts a plaintext into a ciphertext in R2- Q is a ring modulus which is represented by set of prime modulus obtained
from the Chinese Remainder Theorem (CRT) as II'_0 d. (1 < 1 S L). L and I denote the initial and current level of a ciphertext. The level is an HE-specific resource that determines the number of multiplications applicable to given ciphertext. We also denote the associated level of ring modulus using subscript as QL or Q:- We denote the plaintext and ciphertext of a message a as (a) and [a]. HE operations of addition, multiplication, and rotation can be described as follows:
HE. = HE, Eval((()))( = (a.
HE..ootate(a)..) = [rot(a.r))
2

---

Under review as a conference paper at ICLR 2023
fi denotes linear operations, either Hadamard addition or multiplication. rot(a.r) represents cycli- cally shifting vector by to the left. Unlike addition and rotation, multiplication in quires additional rescale operation, which consumes a level by dividing ct Ro, into ct' E Ro a ciphertext has no level left after a series of multiplications, bootstrapping (Bossuat et al.] 2022) needed reconcile the levels and allow further operation. Bootstrapping. the most costly opera- tion in HE, consists of multiple HE operations including rescale operations. After bootstrapping, the level of the resulting ciphertext becomes L' = (L Lo) where Li is the depth of rescale operations in the bootstrapping circuit. As it is beneficial to perform many operations before bootstrapping, L should be sufficiently larger than Lb. However, large L decreases the security level, which should be high enough to tolerate cryptographic attacks. The security level is roughly proportional to N/L. Considering the security requirement HE, large L. requires large (2 215). Thus prior works on
re-
FHE (Bossuat et al. 2021
Jung et al. 2021 Lee et al. 2022b) target N = 2 to 247.
Table shows the execution time of HE operations on system specified in Section [. We mea- sured the execution time of each operation at the initial level (max level) of ciphertext and thus the execution time may decrease for ciphertexts with lower levels. Bootstrapping consumes over two orders of magnitude longer runtime than other operations, but boostrapping does not occur as frequently as others. Except for bootstrapping, Rotate and MulCt are the most time-consuming operations in HE, which is due the expensive key-switching procedure.
Benchmark Time (ms)
AddPt 0.572
AddCt 0,202
MulPt
MulCt
Rescale
Rotate
Boot 2156.605
0.506
17.301
3,904
15.492
Table 1: The benchmark of HE operations averaged over 100 iterations CPU (64 threads). Pt and Ct postfixes represent ciphertext-plaintex and ciphertext-ciphertex operation, respectively.
2.2 CONVOLUTION ON HOMOMORPHIC ENCRYPTION
Ag
5x
41x
(a) Unencrypted convolution with
(b) HE SISO convolution with
(c) HE SISO convolution with
Figure 1: SISO convolution. ciphertexts and plaintexts are illustrated as 2D matrix but are actually stored in 1D manner with each matrix concatenated.
In this subsection, we describe previous convolution algorithms for FHE. We represent input and output tensors with tuples {wr, ha, ) and (Way ho, and Conv layers with [h, C.) We denote the stride of the convolution
for simplicity. Gazelle (Juvekar ct al. 2018) proposed efficient SISO (single-input and single-output channel) convolution algorithms on HE. Figures lb Ic show SISO convolutions for plaintexts. Each slot in i-th plaintext stores k; or 0 (punctured) depending on whether k; is involved in the computation of the output pixel at the same slot. SISO operates as follows: 1) rotate an encrypted input image with different indexes according to plaintext filter, 2) perform Hadamard multiplication, and 3) accumulate the multiplication results to obtain the output. Alternatively, if
and assume padding
2. Filter elements are separated into fr
3

---

Under review as a conference paper at ICLR 2023
prepare the filter plaintexts inversely rotated and directly multiply them with the input ciphertext, the rotations can be performed after MulPt operations (Zhang et al. 2021). which we dub lazy-SISO. We selectively use SISO and lazy-SISO to minimize rotations for convolution. Detailed explanation of lazy-SISO is provided in Appendix E
In more general cases of multiple channels, convolution HE is performed in SIMD manner. If the size of a channel image is smaller than the number of slots in a ciphertext, multiple channels can be placed in a ciphertext. For example, if slot 21 and an input channel is sized wy/t; 32 x 32 as in the input image of the CIFAR- 10 dataset, slot wih, 32 channels can be placed in a single ciphertext in an aligned manner (i.e. channel-ale -ainnel-alignedd. Then, the process of convolution for a channel-aligned input ciphertext storing multiple channels can be described as follows. Suppose c₁ wihy
_soo_ First,
SISO is performed on o; input channels in a SIMD manner (see Figure 2 which produces c; convolution outputs MK())) (1 S S C, S j S Co). To compute the result for the k--th output channel, Σi= M (K(AA) is accumulated by RaS (Rotate and Sum), which is repeated until all the output channels are acquired. Finally, the ciphertexts packed with output channels are realigned to match the next layer's input alignment by IR (Image Realign). Throughout this paper, we refer to this convolution that takes a channel-aligned ciphertext as the input as channel-aligned convolution (CAConv). CACony can be further optimized for the case where the input tensor is not large enough to fill all the slots in a ciphertext; wyhic; repeated copies of the input tensor are placed in a ciphertext,
sint
then slot output channels can be computed together in a single ciphertext (Lee al. 2022a
Strided convolution (s 1) using SISO algorithm creates gap between valid values (see Fig- ure Tc). A ciphertext with a gap underutilizes its slots, leading to throughput degradation. While Juvekar al. (2018) can remove the gap by client-aided re-encryption process, non-interactive PI shall remove the gap through masking and rotation, which incur additional rotation overhead and also consume more levels. Lee al. (202a)) proposed a multiplexed packing method that can be combined with CAConv
to mitigate the overheads. In the IR stage of MP-CAConv, multiplexed packing fills the gap with other channels (see Figure [3b), which we refer to as the repucking process. Other than the repacking process, MP-CAConv is very similar to CAConv. In MP-CAConv, IR collectively refers to realigning and repacking process.
Tile tensoring based convolution proposed in (Aharoni et al. 2020 is yet another convolution algorithm for FHE. While tile tensoring based convolution can be efficient alternative to SISO- based convolution when the image size is sufficiently high, our paper mainly focuses on SISO-based convolution, which can be applied more broadly.
In RNS-CKKS, the hoisting optimization allows multiple rotations to share common sub-operations composing a rotation operation. First-level hoisting shares the front decomposition sub-operations when rotating single ciphertext multiple times with different indexes. Second-level hoisting shares the rear ModDown sub-operations when rotating and summing up multiple ciphertexts. We refer the reader to Bossuat al. (2021) for further details of the hoisting optimization. First-level hoisting can be applied to SISO, whereas second-level hoisting can be applied to lazy-SISO.
2.3 POLYNOMIAL ACTIVATION FUNCTION ON HOMOMORPHIC ENCRYPTION
Non-linear activation functions, such as ReLU, cannot be used in HCNN. They must be replaced with polynomial functions as HE only supports addition and multiplication operations. To directly replace ReLU with approximate polynomials, approximation error should be negligible over a wide range to retain the original accuracy of CNN model. [ee al. (202T) designed a precise approx- imation of ReLU having an 1 norm approximation error less than 2-13 in the range of [-50, 50), obtained by a composition of {15, 15, 27) degree polynomials. This approximation- based approach has a benefit that it can be applied to pretrained neural networks. However, evaluation of high- degree polynomials imposes a significant runtime overhead in HCNN inference. Another approach is to train neural networks with low-degree polynomial activations as in Ishiyama et al. (2020): banne et al. (2017); / Obla et al. (2020); Hesamifard et al. (2019); Thaine et al. (2019). While this ap- proach requires retraining, operational cost is much cheaper compared to high-degree polynomials. Recently AESPA (Park et al., 2022) demonstrated that CNN trained with low-degree polynomials achieve equivalent accuracy to ReLU-based networks across various CNN networks and image datasets. AESPA replaces batch normalization (BN) and ReLU with the composition of orthogonal basis polynomials and basis-wise BN as follows:
4

---

Under review as a conference paper at ICLR 2023
(1(1) (,(x))-1 - i=0 o0 +e
f(x) = Σ
(I)
Here, h; are the orthogonal bases, and are the mean and variance computed from BN, and y and are trainable parameters. For d = 2, AESPA turns into second-degree polynomial with different coefficients for each channel on inference. We adopt AESPA in this paper, which leads to better runtime performance.
2.4 THREAT MODEL.
We adopt the same threat model as prior PI works. A client sends encrypted data to an untrusted server. The server performs CNN inference using HE operations and returns inference results to the client. The client decrypts the resulting ciphertext obtain the private result. The server only holds the client's public keys and cannot decrypt any intermediate ciphertexts in the inference process. The client does not know any information about the processing the server other than the result.
3 METHOD
3.1 REPLICATION-ALIONE CONVOLUTION
The main performance bottleneck of CAConv is the massive number of rotations. CAConv requires an enormous number of rotations to implement the sum of the channels within the same ciphertext (RaS) and the relocation of the channels (IR) to match the next layer's input representation. These rotations take up most of the time in CAConv. For example, when N = 216 rotations for RaS and IR account for 49% and 43% of the total number of rotations in ResNet20, respectively. Furthermore, IR consumes an additional level for masking to extract the values.
A
Spai N
RAConv with SISO
(b) RAConv with lazy-SISO
TIEN and odd
geto Joo
(c) CAConv with SISO
Figure 2: CAConv and RAConv. The single superscript denotes channel and the superscript pair denotes (input channel, output channel). We simplify the notation of M (a) ((a,b) as M (a.b)
To mitigate the performance bottleneck caused by rotations in CAConv, we design Replication- Aligned Convolution (RAConv) receive the alternative data representation. In CAConv, the output ciphertext of RaS contains replications of the channel sum (i.e. eplication-alignee) as shown in RAConv receives replication-aligned ciphertexts as input and skips IR and RaS stages. Figure 2a shows an example of performing RAConv. RAConv takes input ciphertexts each filled with replications of a single input channel and weight plaintexts aligned in output channel order. RAConv operates follows: 1) perform parallel SISO, which outputs c, ciphertexts where the i-th ciphertext contains (FJ) for all j values, and 2) accumulate the ciphertexts by simple HE ad- ditions. SISO in RAConv actually increases the number of rotations because e; input ciphertexts require cr 1) rotations during parallel SISO. Instead, we utilize lazy-SISO with RAConv. which requires much fewer (fw - 1) rotations for SISO. RAConv produces a densely-packer channcl-aligned ciphertext that complies with the CAConv input data organization, between RAConv and CAConv. RAConv-CAConv chain halves the RaS rotations previously re- quired in two CAConys to cglog(c.).
Figure 2c
alternate
5

---

Under review as a conference paper at ICLR 2023
[3]
42
4
42
42
422
131
13)
(2)
42
2
(3)
0
[3)
(2)
44
[3)
11
(1)
(1)
(2)
(2)
0
0
13)
(4)
(3)
13
133
(3)
233
12)
(a) Void packing
(b) Multiplex packing
(c) Duplicate packing
(d) Hybrid packing
Figure 3: Comparison of gap packing methods to fill gap induced by downsampling layers.
Mask Broadcast
of-1
CACces
Drandooat
wffl
k1-30.
N1TT-2231
WAT--1
(a) CAConv with hybrid packing (HP-CAConv)
RoS
Broadcast
g
eff)
4/35-32.3)
e0
elu
(b) RAConv with hybrid packing (HP-RAConv)
Figure 4: The procedure of CAConv and RACony with hybrid packing
3.2 HYBRID PACKING
SISO convolution suffers from low slot utilization in ciphertexts due to two reasons. First, strided convolution creates gap between valid values (see Figure [a). Second, the small size of input tensors creates empty slots in ciphertexts. Due to the security requirement of FHE, the number of slots in a ciphertext often larger than the size of an input tensor. Underutilization of slots in SISO leads to severe throughput degradation in HCNN.
Prior state-of-the-arr HCNN implementation (MP-CACoNv) mitigates underutilization of slots using multiplexed packing and input repetition (see Section 2.2 However, they cause a lot of additional rotation overhead to adjust the data organization. In MP-CAConv, RaS operation is used to accumu- late SISO results in a ciphertext. Under input repetition, RaS operation returns an output channel the slots where an input ciphertext stores the first channel of an input tensor. Multiplexed channels are also accumulated through RaS operation, thus values constituting an output channel exist only in non-gap slots, as shown in Figure Bal To restore the data organization of MP-CAConv, invalid values are masked off and empty slots are filled with other channels through IR process. In the pres- ence of input repetition, IR spends (cc,) rotations to relocate output channels and stat additional rotations for generating input repetition.
wah.co
To reduce the relocating overhead between convolutional layers, we propose novel image pack- ing method, hybrid packing (HP). HP fills the gap with channel duplicates of multiple channels (See Figure (d).. We design HP based on two key observations. First, applying convolution over duplicate-packer ciphertext (Figure 3c) produces multiplex-packe output ciphertext in Fig- ure 3bb Second, converting a void-packed ciphertext into a duplicate-packed ciphertext requires fewer rotations than converting it into calttplex-packeer ciphertext. Duplicate packing only needs O(lo(ggapsize)) rotations while multiplexed packing requires O(gapsise) rotations.
HP is a hybrid of duplicate packing and multiplexed packing. We represent hybrid-packed cipher- text by a pair of numbers, the number of multiplexed channels m, and the number of duplicates d. For example, Figure shows (m, d) = (2, 2) HP. Packing of the ciphertext switches between two HP settings while processing CAConv and RAConv as shown in Figure 4 We denote HP param- eter (m, d' of the input and output ciphertext as (Min, din) and (Motts dout). Input repetition is no longer required as HP with larger din can be used instead. Duplicates of HP produce different output channels within the gap (See (1)) and c(17) Figure 4b) Then, the IR process adjusts the output ciphertext's organization from (Moat: dems) (din: 1) (din, Man), which only requires Ollog m..)

---

Under review as a conference paper at ICLR 2023
Method
clus
clout
SISO
RaS
IR
Lee al.
2022a
[wyhee)
Mochao
ctin (f 1)
whdcc log G
cut log wuchan
HP-CAConv
Abmin (fufh fu 1)
coou log St
clout log Min
HP-RAConv
w.d.c.tti
etman fuud 1)
cbout log man
clout log m4n
Table 2: The rotation complexity of the convolutions. We denote the numbers of input and output ciphertexts as clin, clout. Then, clmin min(clins clout) considering SISO and lazy-SISO.
rotations, which fill the gaps. After performing a series of CAConv and RAConv, the HP organiza- tion of the output ciphertext returns to the initial (m,n, d.n). The complete procedures of RACony and CAConv with HP are described more in detail in Appendix H
Compared to MP-CAConv, HP significantly reduces the rotations in RaS and IR. The rotation com- plexities of MP-CAConv (Lee et al., 2022a) and our hybrid-packed convolutions are shown in Ta- For both HP convolution methods, the product of the numbers of input and output ciphertexts remains constant (clin chout = w.h,c,(a). Compared to MP-CACony, the number of rotations for RaS is reduced by about chin times for both HP-CAConv and HP-RAConv. IR stage of HP repacks the gap with duplicates. Rotation decreases from of MP-CAConv to mere log min rotations per output ciphertext.
2
HP convolutions require more rotations than MP-CAConv for SISO; clin of MP-CAConv is always smaller than or equal to ml of HP-CAConv or HP-RAConv. Nevertheless, hoisting can be applied to SISO which reduces the significance of the rotation cost of SISO, and the reduction of rotations in RaS and IR overwhelms the increase in SISO.
All things considered, HP reduces the overall number of rotations required for convolutions. We can also explore various combinations for the (m, d) pair to minimize the total number of rotations. The choice of (m, d) decides ctin and clout values and creates a trade-off between SISO, RaS, and IR costs, and also affects the number of ciphertexts we have to perform bootstrapping with. We provide an in-depth performance analysis with regard to the choice of (m, d) in Section 4.2
3.3 THE RESNET ARCUITECTURE ON HYPHEN
Basic Block
Shortcut (1) CAConvixt (2)
CAConN (2) Square (1)
RAConv
Bootstrap
Square (1)
Figure 5: The structure of ResNet basic block built on HyPHEN. The level consumption per block
is written in parentheses. In the downsampling block, pointwise convolution is added to the critical path. Otherwise, a simple shortcut added.
HyPHEN combines RACony and HP to build the entire CNN model. FigureB]shows the basic block of ResNet implemented on HyPHEN. There are three more considerations when deciding the order of operations. First, bootstrapping is cheaper when placed after RAConv, and not CAConv, because the number of ciphertexts is smaller the moment. Second, match the level between the shortcut path, bootstrapping should be placed either before residual
path and the main CAConv-RACon connections diverge or after they converge. Last, it is beneficial perform convolutional layers at the lowest level possible. The complexity of FHE operations such as rotation is proportional to the level I of ciphertext. Therefore, the lower the calculated level, the smaller the computational cost.
All things put together, our ResNet basic block implementation consumes a total of 6 levels. The level consumption of each layer is represented in the parenthesis of each block. CAConv and RAConv use HP and consume one level for each SISO and IR. Activation uses AESPA and con- sumes one level. AESPA is a quadratic polynomial having different coefficients for each channel while training. During inference, we fuse the coefficients into nearby layers, then the activation becomes a simple square function x². We set the initial ciphertext level L to six and perform boot- strapping when the level becomes zero
7

---

Under review as a conference paper at ICLR 2023
4 EVALUATION
4.1 EXPERIMENTAL SETUP
We HCNN inference CPU and GPU environments using the RNS-CKKS library, HEAAN. CPU instance is equipped with AMD EPYC 7452 running at 2.35GHz (64 cores) and 480GB
DRAM. GPU experiments are conducted at the same system with an additional NVIDIA A A00 GPU with 80GB HBM. Our HCNN inference experiments use the CIFAR-10 (Krizhevsky et al. 2009). We evaluate ResNet20/32/44/18 trained with AESPA on PyTorch and applied the fusion technique to all the networks. Our RNS- CKKS parameters satisfy 128-bit security level (Cheon et al. 2019) with polynomial degree N 2 and hamming weight 192. Multiplication and bootstrapping primes each occupy 48 bits and over 56 bits, respectively. The bootstrapping implementation consumes 17 levels in our setup.
4.2 OPTIMAL POINT
We explore the optimal (m, d) pair for HP to minimize the latency of ResNet 20/18. Table shows the operation count rotation and bootstrapping, which are major contributors to the runtime. Ro- tation is categorized into SISO and non-SISO. Only SISO rotations can be optimized with hoisting. Table 3 presents an instance of MP-CAConv and three (or two) instances our HP-based convo- lution. Instances of HP-based convolution consist of settings with minimal bootstrapping. minimal rotations, and optimal latency. In ResNet20, The optimal point corresponds to the minimal boot- strapping. In R8 the amount of rotations hikes following the channel increment. The optimal point sacrifices bootstrapping counts to play fewer rotations. We opt for these two settings to evalu- ate in the following section. more thorough parameter study on GPU presented in Appendix B
(m,d)
Rotations
Model
Packing
Boot
CPU Runtime(s)
L11
1.3
SISO
RaS
IR
total
MP-CAConv
152
800
1876
0.8
ResNet20
Optimal
(1.2)
(2,4)
(4.8)
152
580
187
919
11
39.6 : 0,3
Min Rot
(1,2) (1,8)
(2,16)
240
407
142
789
16
46.3 + 0.3
MP-CAConv
176
19472
4787
24435
12
558.6 1 5.6
ResNer18
Min Boot
(1,1)
(8.2)
(16,4)
184
12678
3380
16242
12
366.5 7.2
Optimal
(1,3)
(1,4)
(2,8)
(4.16)
448
3976
1131
5555
27
185.5 2.0
Min Rot
(1.1) (1.4)
(1.16)
(2,32)
672
3376
1007
5055
195.0
Table 3: Runtime for the ResNet instances with different (m,d) parameters and packing strategies.
4.3 SENSITIVITY STUDY
In Figure 6 three activation function & convo- lution algorithm pairs are evaluated. Set fol- lows the implementation of Lee et al. (2022a), using AppReLU with MP-CAConv. Set spends most of the time for bootstrapping in ResNet20 inference. Set employs the square activation of AESPA along with MP-CAConv. AESPA reduces the number of levels consumed by activation functions, thus requiring much less time for bootstrapping. Set experiences 5.1 and 2.9 reduction in bootstrapping time in ResNet20 and ResNer18, respectively. For both networks, most of the runtime spent on CACony in Set2.
RACues
150
Exccution Timeet)
100
400
200
Serl
Se12
Ser3
Seil
Sel2
Ser
ResNet-20
ResNet-18
Figure 6: The execution time of ResNer20/18 8 with three settings on our CPU environment. Set1 uses appReLU with MP-CAConv (Lee et al.) 2022a). Set2 uses AESPA with MP-CAConv and Set3 represents HyPHEN, using AESPA with our convolution method. FHE parameters used in the experiments explained in Table 11
By introducing HyPHEN in Set3, the execu- tion times spent for convolutional layers are reduced by 3.1x and 5.0x in ResNet20 and ResNet18, respectively. The impact of Hy- PHEN is amplified for more complex networks like ResNet18, 8; HyPHEN resolves the problem
8

---

Under review as a conference paper at ICLR 2023
of MP-CACCme showing superlinear increase in the number of rotations the number of chan- nels increases. Overall, HyPHEN achieves 3.4-4.4x speedup compared to the prior state-of-the-ar implementation of Lee et al. 2022a) (Set
4.4 EXECUTION TIME
Table shows the runtimes of various ResNet instances on CIFAR-10. We measured the execu- tion time of running inference with single CIFAR-I0 image in CPU/GPU environments. Our ResNe120/32/44 implementations on GPU take merely a few seconds to complete. Furthermore, We demonstrate running ResNet18 for the first time. As ResNet18 has 4x more channels than ResNec20/32/44, execution time largely depends on the convolutional layer. Table 4 agaai demon- strates that RAConv effectively reduces the overall runtime of the conv layer, as our operation count analysis in Table Detailed comparison with Lee et al.
2022a is provided in Appendix
Execution
CPU (64 cores)
GPU
ResNet20
ResNet32
ResNet44
ResNet18
ResNer20
ResNet44
ResNet18
HP-CACony
14.43
20.96
26.68
102.34
0.49
0.70
0.90
7.06
HP-RACony
Bootstrap
21.08
33.93
46.07
57.53
0.82
1.31
1.80
3.49
Activation
Eic
0.22
0.25
0.40
0.31
<00.01
<0.01
0.01
1.21
61.76
2.0
0.02
2.98+0002
Table 4: HyPHEN Inference time of a single CIFAR-I0 image using ResNet models on CPU and GPU. As FC layer and Pooling have tiny execution time, we gather them at Etc.
4.5 ACCURACY
In Table we measured inference accura- cies for CIFAR-10 images running ResNet model
Top-1 Acc (%)
ResNet20
ResNet32
ResNet44
ResNet18
implementa- tion. Though we found an error below the sec- ond decimal place the classifier result, did not observe deterioration in the accuracy of ResNet20/32/44. ResNet18 shows -0.08% % degradation in accuracy, which is smaller com- pared the accuracy drop in Lee et al. (2022a).
RNS-CKKS-basee
Backhone
92.18
93.36
95.1
Measured 92.17
93.35
94.08
95.02
Table 5: Comparison of the inference accuracies for the CIFAR- 10 dataset running ResNet models on our WONS-CKK-BBE based implementation.
The difference in accuracy drop can be explained by whether the original network is executed as is or an approximation has been made.
LIMITATIONS
ResNet networks the only models addressed in the paper. Broader experiments toward various models such as Liu et al. al.aa112200 (2022) would show the practicality of FHE-based PI more clearly.
CONCLUSION
In this paper, proposed an efficient convolution algorithm RAConv, and novel packing method Hybrid Packing. We showed HyPHEN, FHE-based ResNet architecture implementation applying proposed optimizations. Our experiments on real machine show 3.4-4.4x lower la- tency for ResNer20/32/44/18 compared to Lee et al. (2022a). Using GPU acceleration, HyPHEN demonstrates 1.44/2.21 33.37s execution time for running ResNer20/32/44/18 on CIFAR-10 dataset.
REFERENCES
Nvidia Nsight Systems. /ttps::/deveeooprr..wv/ miidia.iiiai. wtt.iiii...mmmiiiiiiiiioo http://wwww...aacaaaiiiiiit/s/// NVIDIA Coporation, Santa Clara, California.
2021.

---

Under review as a conference paper at ICLR 2023
Accountability Act. Health insurance portability and accountability act of 1996. Public law, 104: 191, 1996. /tthttss:://// //t:::///wwwww.. www./wwww....................... hhs hww.gg/aw.wiaaagg httpppaaaannnnnieeee html
Ehud Aharoni, Allon Adir, Moran Baruch, Nir Drucker, Gilad Ezov, Ariel Farkash, Lev Greenberg, Ramy Masalha, Guy Moshkowich, Dov Murik, et al. Helayers: A tile tensors framework for large neural networks on encrypted data. arXiv e-prinis, pp. arXiv-2011, 1, 2020.
lean-Philippe Bossuat, Christian Mouchet, Juan Ramón Proncoso-Pastoriaa and Jean-Pierre Hubaux. Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys. In Advances in Cryptology- EUROCRYPT 2021 400th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb. Croatia, October 17-21, 2021, Proceedings, Part I, 2021. URL https:: 10o../0000...00/9999555000
1007
21
Jean-Philippe Bossuat, Juan Ramón Proncoso-Paatorizaa and Jean- Hubaux. Bootstrapping for approximate homomorphic encryption with negligible probbabity by using sparse-secret encapsulation. In Applied Cryptography and Network Security 20th International Conference, ACNS 2022, Rome, Italy, June 20-23, 2022, Proceedings, 2022. URL https: / //doi org/ 10.1007/978 078
031 09234 26
William Bowditch, Will Abramson, William J. Buchanan, Nikolaos Pitropakis, and Adam J. Hall. Privacy-preserving surveillance methods using homomorphic encryption. In Proceedings of the 6th International Conference on Information Systems Security and Privacy, ICISSP 2020, Val- letta, Malta, February 25-27, 2020. SCITEPRESS, 2020. URL ltttps://oi..cr///
5220/000886992240222
Alon Brutzkus, Ran Gilad- Bachrach, and Oren Elisha. Low latency privacy preserving inference. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, 2019. WRLLhttt://rroceeeiie v97 /97/brut zkusl 19t.html
mlr pre.sssss////p////.m
Hervé Chabanne, Amaury de Wargny, Jonathan Milgram, Constance Morel, and Emmanuel Prouff. Privacy classification on deep neural network. IACR Cryptol. ePrint Arch., 2017. URL
http::/ iacr wrt.
Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. full RNS variant of approximate homomorphic encryption. In Selected Areas in Cryptography SAC 2018 25th International Conference, Calgary, AB, Canada, August 15-17, 2018, Revised Selected Papers, 2018. URLbttps: / doi. org/ 10. 1007
Jung Hee Cheon, Minki Hhan, Seungwan Hong, and Yongha Son. A hybrid of dual and meet- in-the-middle attack on sparse and ternary secret LWE. IEEE Access, 2019. URL https: //doi. ort/10. 1w111119999CSS. 201 9. 2925425
Victor Costan and Srinivas Devadas. Intel SGX Explained. IACR Cryptol. ePrint Arch., 2016. URL http://eprint.cr htt.:ppiinn......oooo/21111/111 ott.acrr.rr/2016668888888
Roshan Dathathri, Blagovesta Kostova, Olli Saarikivi, Wei Dai, Kim Laine, and Madan Musuvathi. EVA: an encrypted vector arithmetic language and compiler for efficient homomorphic compu- tation. In Proceedings of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2020, London, UK, June 15 20, 2020, 2020. doi: 10. 1111/3385412..336602 URL htttps:///// woggrlrg............
Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st Annual ACM Symposium Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 June 2, 2009, 2009. URL http::tt////dtt www.orggioo... 1tt///1..1114..1 1ee.111111111111 11333664.....11400000
Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin E. Lauter, Michael Nachrig, and John Wernsing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In Proceedings of the 33nd International Conference Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48, 2016. TRLhttp: htttt:://prrccedings..
r. www.ppressvvve aadilaadbbaae bach rach html
10

---

Under review as a conference paper at ICLR 2023
Kyoohyung Han and Dohyeong Ki. Better bootstrapping for approximate homomorphic eneryption. IACR Cryptol. ePrint Arch., 2019. URL htttt:t//tppiinnn iacr otq/ 688
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In 2016 IEEE Conference Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV. USA, June 27-30, 2016, 2016.
2016 90
Ehsan Hesamifard, Hassan Takabi, and Mehdi Ghasemi. Deep neural networks classification over encrypted data. In Proceedings of the Ninth ACM Conference on Data and Application Security and Privacy, CODASPY 2019, Richardson, TX, USA, March 25-27, 2019, 2019. URL https:
//doi. www.orgg11000.. 100.0.11113222000000 0011666330000 3300044
Geoffrey E. Hinton, Oriol Vinyals, and Jeffrey Dean. Distilling the knowledge in neural network. CoRR, 2015.
02531
Takumi Ishiyama, Takuya Suzuki, and Hayato Yamana. Highly accurate CNN inference using ap- proximate activation functions over homomorphic encryption. In 2020 IEEE International Con- ference on Big Data (IEEE BigDatt 2020), Atlanta, GA, USA, December 10-13, 2020, 2020. URL
bttps::/doos www.oorggg..... 1109 http://0.011111111aaaa5522222220
2020. 9378372
Wonkyung Jung. Sangpyo Kim, Jung Ho Ahn, Jung Hee Cheon, and Younho Lee. Over 100x faster bootstrapping in fully homomorphic encryption through memory-centric optimization with gpus. JACR Trans. Cryptogr. Hardw. Embed. Syst., 2021. URL /ttps:///6i..or//10..5555
tches. v2021 1.4.114444
Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha P. Chandrakasan. GAZELLE: A low la- tency framework for secure neural network inference. In 27th USENIX Security Symposium, USENIX Security 2018, Baltimore, MD, USA, August 15-17, 2018, 2018. URL URLhttps: //t:://wwww juvekar
usenix.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Nishant Kumar, Mayank Rathee, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma. Cryptflow: Secure tensorflow inference. In 2020 IEEE Symposium on Security and Privacy, SP 2020, San Francisco, CA, USA, May 18-21, 2020, 2020. URL httpps://doi.
org 1109/110/2000000, 2020. 00092
Eunsang Lee, Joon-Woo Lee, Junghyun Lee, Young-Si Sin Kim, Yongjune Kim, Jong-Seon No, and Woosuk Choi. Low-complexity deep convolutional neural networks on fully homomor- phic encryption using multiplexed parallel convolutions. In International Conference on Ma- chine Learning, ICMI. 2022, 17-23 July 2022, Baltimore, Maryland, USA, 2022a. URL https: //proceedings.o mlr press v 62 1ee22e html
Junghyun Lee, Eunsang Lee, Joon-Woo Lee, Yongjune Kim, Young Sik Kim, and Jong-Seon No. Precise approximation of convolutional neural networks for homomorphically encrypted data. CoRR, 0tls/2005.108777 2021. URL htt.ltttts://
10879
Yongwoo Lee. Joon-Woo Lee, Young-Sik Kim, Yongjune Kim, Jong-Seon No. and HyungChul Kang. High-precision bootstrapping for approximate homomorphic encryption by error vari- ance minimization. In Advances Cryptology EUROCRYPT 2022 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 June 3, 2022, Proceedings, Part 2022b. URL. https: /tttpp:///ci..oo .eciiorrg/11 wtt./o..g10000000.. 1007/ 378-3-031-06942
Zhuang Liu, Hanzi Mao, Chao- Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. CoRR, abs/2201.03545, 2022. URL /ettps://arxiv... /bs/
2201. 03545]
Srinath Obla, Xinghan Gong, Asma Aloufi, Peizhao Hu, and Daniel Takabi. Effective activation functions for homomorphic evaluation of deep neural networks. IEEE Access, 8, 2020. URL https: //dos wrg/oorgg....oo. 1109 ACCESS.

---

Under review as a conference paper at ICLR 2023
Jaiyoung Park, Michael Jaemin Kim, Wonkyung Jung, and Jung Ho Ahn. AESPA: accuracy preserving low-degree polynomial activation for fast private inference. CoRR, 2022. URL
https::/arxiv.orgg abs 2201 06699
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035. 2019. URL http:://pappeee http:/paaprs.uuu.ree.eee neur wwwpariip.ccpppppppeeeeeeepp
9015 wat--pytrrchhaac an -ecihh--n-mmmeeeee -ntirerratiieeeeeeee seeeiveeesllleeee weee-highh-eeeeee perfomanreee lerrnine Library.
pdf
Protection Regulation. Regulation (eu) 2016/679 the european of council. Reg- ulation (eu), 679:2016, 2016. URL http://data http:/a.....rr.eeeeee///////////
Patricia Thaine, Sergey Gorbunov, and Gerald Penn. Efficient evaluation of activation functions over encrypted data. In 2019 IEEE Security and Privacy Workshops, SP Workshops 2019, San Francisco, CA, USA, May 19-23, 2019, 2019, URL https:://bi..rrg////// 1109///P.....
2019 00022
Andrew Chi-Chil Yao. Protocols for secure computations (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982. IEEE Computer Society, 1982. URL
http://i.oo//1111110010000/. SFC///FC.... 982.38
Qiao Zhang, Chunsheng Xin, and Hongyi Wu. GALA: greedy computation for linear algebra in privacy-preserv neural networks. In 28th Anmual Network and Distributed System Security Symposium, NDSS 2021, virtually, February 21-25, 2021, 2021.
12

---

Under review as a conference paper at ICLR 2023
A BOTTLENECK ANALYSIS
Figure shows the runtime analysis the convolutional layer, which is conducted on actual layer instances of ResNet20. In Lee al. (022a), rotation accounts for 83-94% of the total convolution time, which reduced to 66% with our method. The optimized convolutional layer in HyPHEN G shows runtime breakdown of each operation and detailed comparison with (Lee et al.) 2022a in our CPU environment. As set both implementations due to the different packing schemes. In ResNet20, our implementation shows slight increase in activation function runtime. However, latency improvements in convolution layer leads the 1.87x lower total execution time. Similarly in ResNet18, our implementation reports increased runtime in activation function and bootstrapping time, but 5.77 lower convolution time again leads to 3.33x lower total execution execution time.
leads to smaller ratio of rotation in the total execution time. Table
AESPA with the same HE parameter set, the speedup is solely
Execation Time(m))
4000
Others Rotation
3000
2000
1000
(a) CP-CACony Lee
2022a
Execution (ime((s)
1.000
500
3
7
12
15
18
(b) HyPHEN
Figure Comparison rotation time in ResNet20 convolutional layers
ResNet
ResNet18
Execution time
Ours
Les al.
20220
Ours
Lee
20220
runtime
percent
percent
runtime
percent
runlinn
percent
CACony
14.43
36.4%
52.32
70.4%
102.33
55.2%
590.53
95.9%
RACony
2.41
6%
19.18
10.3%
Bootstrap
21.08
53,2%
21.41
28.8 %
57.53
31.0%
25.91
4.2%
Activation
1.44
3.6%
0.34
<0.01%
6.16
3.3%
0.43
<0.01
Ele
0.22
0.01%
0,22
<0.01%%
0.31
<c0.01%
0.24
<0.01 %
Total
39.58 0.3
100%
74.29 + 0.8
100%
185.52 + 2.04
100%
617.11
2.04
100%
Table 6: HyPHEN inference time of a single CIFAR-10 image using ResNet models on CPU. As FC layer and Pooling have tiny execution time, we gather them at Etc.
B PARAMETER STUDY
We present parameter study to explore the optimal HP setting which minimizes latency. Table and 8 show the rotation and bootstrapping counts with varying (m, d) available in ResNet20 and 18 and the execution time running the network on GPU. We only represent the (m, d) pair of CA- Cony, as and d are exchanged at RAConv. In ResNer20, we start with (m, d) (1,2) to remove input repetition as the size of the input tensor in the first layer (32 x 32 x 16) smaller than the ciphertext slots 12).). Nevertheless, Larger d has not been considered as it leads to more bootstrap- ping. as shown in our proposed architecture (See Figure 5) As the input ciphertexts go through the downsampling layer, d gets quadrupled and the size of the intermediate tensor gets halved. In ResNet20, HP that doubles every downsampling layer yiclds optimal performance, which re- duces rotation without increasing bootstrap. In ResNet18, the impact of bootstrapping increment
13

---

Under review as a conference paper at ICLR 2023
is often smaller than the impact of rotation decrement. The optimal HP setting requires 15 more bootstrappings and 10687 fewer rotations than the minimum bootstrapping HP setting.
(m.d)
Rotations RaS
Boot
GPU Runtime(s)
L2
SISO
IR
total
(1.2)
(2,4)
(4,8)
152
580
187
919
11
1.44 0.02
(1.2)
(2,4)
(2.16)
192
539
162
893
13
1.56:t 0.02
200
813
1.59:t 0.02
(1.2)
(1.8)
(2.16)
240
407
142
789
16
1.71 0.02
(1,2)
(1.8)
01,32)
240
419
154
831
20
2.06 0.02
Table Comparison of the instances of CAConv (m,d) parameters in ResNet20.
Rotations
Boot
GPU Runtime(s)
L1
L2
L3
L4
SISO
RaS
IR
total
(1.) (4,1)
(8.2)
(16,4)
184
12678
3380
16242
12
18.5 + 0.09
(1.1) (4.1)
(8.2)
(8.8)
2793
15047
17.7
(1.) (4,1) (4.4)
(16.4)
216
9804
2786
12806
16,9 0.15
(1.1) (4,1) (4.4)
(8.8)
240
9172
2207
11619
15
=
(1.1) (4.1) (4,4)
(4.16)
288
1979
11171
15.7
(11) (2.2) (8.2)
(16.4)
216
10122
2920
13258
17.4
(1.)) (2.2) (8.2)
(8.8)
240
9490
2333
12063
15
17.0
(1.))
(4,4)
(16.4)
(L.) (2.2) (4.4)
(8.8)
272
6616
1763
8651
14.7
(1.)) (2.2) (4,4)
(4,16)
320
6348
1535
8203
19
14.9
(1.)) (2,2) (2
(L.) (2.2) (2.)
(4.16)
384
5084
1311
6779
14.1 = 0.11
(1.)) (2,2) (28
(2,32)
480
5004
1243
6727
27
14.3 0.13
(1.))
(16.4)
312
2146
8598
0.14
(L.)) (1,4) (4,4)
(8.8)
336
5508
1567
7411
14.0
(1.1) (1,4) (4,4)
(4,16)
384
5240)
1339
6963
139
(1.1)
5995
13.5
(1,1) (1,4) (2,8)
(4,16)
448
3976
1131
5555
134
(1.1) (1,4) (2.8)
(2,32)
544
3896
1063
5503
31
13.7 0.10
(1.1) (1,16)
(4,16)
S76
3456
1067
5099
1314
(1.1) (1,4)
(2,32)
672
3376
1007
5055
39
13.8 + 0.11
(1.1) (1.4) (1,16)
(1.64)
672
3432
1031
5135
14.4 0.10
Table Comparison of the instances of CAConv (m,d) parameters in ResNet18.
C RESNET ARCHITECTURE AND PARAMETERS
Figure
presents model architecture of modifed ResNet20 used in HCNN evaluation. Table
and 10
shows parameters used in convolution layer ResNet20/32/44/18, All the parameters
(Ci, Cas Whe h4, Way Boy fwu Jhg 8) are determined following the origianl ResNet paper (He et al.
2016
Image Ciphertext
RAConw
Boctstrap
Square
BasicBlock
BasicBlock
BasicBlock
Downsample BB
BasicBlock
BasicBlock
Downsample
BasicBlock
BasicBlock
AvgPool
Fully Connected
Result
Basic Block
Shortout
CAConV
Squarre
RAConw
Bootstrap
Square
Figure 8: The ResNet20 structure of HyPHEN.
14

---

Under review as a conference paper at ICLR 2023
Layerl conv
Layer2
Layer3
dsconv
peony
conv
diccnvv
peonv
conv
C2
16
32
16
32
32
64
64
h.)
32
32
32
16
16
16
hol
32
16
16
3
3
3
1
2
1
2
Table 9: Parameters used in the convolution layers of ResNet20/32/44
Layerl conv
Layer2 pcony
Layer3 pcony
Layerd peony
dsconv
conv
dsconv
conv
dscony
conv
64
64
64
128
128
128
256
256
256
512
128
128
128
256
256
256
512
512
My
ha)
32
32
32
16
16
8
8
8
4
4
ho!
32
16
8
3
3
2
2
2
2
Table 10: Parameters used in the convolution layers of ResNet18
D TRAINING DETAILS
Models used this paper is all trained using PyTorch (Paszke et al. 2019). For ResNer18 and 20, our training settings are mostly identical the AESPA; To be specific, networks are trained for 200 epochs using SGD optimizer, 0.1 initial learning rate, 100 batch size, 0.0005 weight decay and 0.9 momentum, and cosine annealing scheduler. We also use soft labels as in (Park et al. 2022 to get higher accuracy. For ResNet32 and 44, we use knowledge distillation (Hinton et al, 2015 enhance the accuracy, using pretrained ResNet32/44 with 93.4% and 94.1% accuracies as teacher models. As the FC layer of the student and teacher network is identical, teacher's FC layer is directly reused in student network. We trained the student networks by minimizing l2 loss (Lid = Il.ft fa (2). ResNet32 and 44 are trained for 200 epochs using SGD optimizer, 0.0005 weight decay and 0.9 momentum. We use 0.05 initial learning rate and learning rate scheduler decays learning rate epochs 150, 180, 200 by 0.1.
E LAZY-SISO
Unlike the original SISO convolution which rotates input ciphertexts before multiplying with filter plaintexts, lazy-SISO proposed in (Zhang et al. 202I uses inversely rotated filter plaintexts to multiply with input ciphertexts. The actual process of lazy-SISO when Ce Co = is depicted in Figure 9 After multiplying with filter plaintext, postponed rotation is performed to accumulate intermediate ciphertexts. During this process, multiple ciphertexts sharing the same rotation index grouped be accumulated first and then rotated, reducing the amount of rotations. (e.g. o ciphertexts are grouped in Figure 2b Lazy-SISO is beneficial when input channels, which are to be accumulated, are distributed in different ciphertexts as in RAConv.
F MEMORY REQUIREMENT
Memory requirement for HCNN depends on FHE parameters and data representations (packing schemes). FHE, expansion of data size occurs while encryption and encoding procedure. Result- ing ciphertexts and plaintexts are typically orders of magnitude larger than messages. The table [1] shows the actual size of the ciphertext, plaintext and evaluation key on three FHE parameter settings. dnum denotes RNS-decomposition number introduced in (Han & Ki 2019 Given N, the degree of a cyclotomic polynomial ring, large dnum increases L, max level. ParamSet 1 is used Set in Figure O to reproduce Lee al. (2022a). As Set1 uses approximated ReLU for activation, ParamSet adopts maximum dnum to have = 16. ParamSet2 set with the smallest L among three and is only used in Set2 ResNer18. ParamSet3 is the parameter used evaluate
15

---

Under review as a conference paper at ICLR 2023
1x
(a) Unencrypted convolution with
14
PP
Po
1
(b) HE lazy-SISO convolution with
Figure 9: Lazy-SISO convolution.
HyPHEN and Set2 on ResNet20 which has L Some FHE operations such MulCt, Rotate and Conjugate requires specific key switching procedure. Eval key denotes public key used at this process. The size of single Eval key is 2147, 206, 176 MB in ParamSet1, 2 and 3, respectively. To support bootstrapping operation, one relinearization key for MulCt, one conjugate key and 48 rotation keys per rotation index are required. We additionally load frequently used rotation keys to perform convolution. For instance, We load 68 unique Eval keys in ResNer20 which take up 146, 14, 12 GB in ParamSet1, 2, and
Once FHE parameter is determined, the packing scheme determines the number of ciphertext, plain- text to run each ResNet block. Table 12 and shows the required number and total memory size of ciphertexts and plaintexts. We further explain the actual computation procedure to explain how the results are obtained in Appendix
In SISO-based HCNN kernel, the size of filter plaintexts increases by factor of wyhç each filter element duplicated to the size of input image, which quires total wwwwwahccCoo slots for weight plaintexts. In consequence, weight plaintexts take up the majority of memory regardless of the ciphertext packing method. In table 12 our implementation shows up to 14.75% memory overhead compared to Lee et al. (2022a). which is primarily due to the increase in the number of ciphertexts and bias plaintext. In Table 13 implementation shows up to 36.8% memory overhead compared to Lee et al. 2022a) The larger memory overhead is caused by using different FHE parameters; ResNet18, we use ParamSet3 for our implementation and ParamSet2 for Lee et al. (022a). When using the same ParamSet3, overhead is reduced by up to 7%.
Unlike CPU, GPU memory capacity is more constrained by the current HBM technology to support high bandwidth. As the GPU memory is not capable of loading the weights of the entire model con- sidering ResNet18, weight plaintexts should be loaded separately; while one stream computes the current ResNet block, another stream is overlapped to load next block's weight plaintext. Through profiling the workloads of CPU and GPU activities through NVIDIA Nsight Systems [nvil 2021 we find that all the copy stream is completed before the end of the compute stream, meaning that loading weight plaintexts does not affect overall execution time. As such, for running large neural networks, fine-grained multi-streaming can be applied to relieve memory capacity constraint.
G IMAGENET EXPERIMENT
We conducted additional experiments to evaluate the ResNet18 model on the ImageNet dataset. The runtime is 81.85 seconds in GPU environment. We slightly modified the first pooling layer to
16

---

Under review as a conference paper at ICLR 2023
L
dnum
Ciphertext (MB)
Plaintext (MB)
Eval Key (MB)
Total Keys(GB)
ParamSetl
16
32
17.82
8.91
2147.48
146.03
ParamSet2
7.34
3.67
205.52
13.98
ParamSet3
10.48
5.24
176.16
11.98
Table 11: FHE parameter settings. dnum is tuned to support 16, 3. 6 levels required in Set Set2, Set:3. Each Ciphertext and Plaintext memory size is represented when current level = L.
Layerl
Layer2
Layer3
ResNet20
BB
DSB
BB
DSB
BB
Ours
Loe
Ours
Loc
Ours
Loc
Ours
Lec
Ours
Lec
filter pixts
144
232
144
144
232
232
144
input ctxts
1
1
1
1
peak ctxts
19
19
10
19
10
19
10
total size (GB)
0.70
0.68
1.18
1.07
0.79
0.69
1.19
1.08
0.79
0.71
memory overhead
0.3%
12.0%
Table 12: Total memory size and the number of each object in ResNet20. We abbreviated Down- sampling Block and Basic Block to DSB and BB.
average pool with kernel size 2x2 and stride As shown in Figure 10 the network receives input ciphertexts processed with modified im2col. Original im2col would transform 224x224x3 images into 147 x 12544 matrix. HCNN prefers images size to be exponential of 2, 12544 columns turns to 16384 columns. We further split 16384 columns with stride 2 (Savg in Figure I0 to per- form average pooling without rotation, resulting 4096 columns. We pack slot/4096 4096 into ciphertext. As the total number of row is faf 147, the number of input ciphertext is [147/8] x 4. After the initial convolution layer, the number of intermediate ciphertexts becomes 64 and each ciphertext stores 8 channels with (m,d) 1. Table [4 shows the runtime of ResNet18 on ImageNet. During the experiment, swap memory is used to make up the lack of CPU memory. Loading weight plaintexts from swap memory, which in SSD, incurs runtime hikes as Table shows large runtimes for Etc.
8 rows
1216
22
4006
4U2NG
224
Rv5
Figure 10: ImageNet Im2Col
H COMPLETE CONVOLUTION PROCEDURE OF HYBRID PACKED TENSOR
Figure I1 and 12 show the complete procedure of CAConv and RAConv with HP shown briefly in Figure 4 Both CAConv and RAConv perform the sequence of (SISO, RaS, IR) the input ciphertexts. As in Figure 2 single superscript represents the channel of input images, and superscript pair represents (input channel, output channel) of filters. If multiple channels are stored in a box, we represent the list of channels using & the range of channels using -. We set ea Co = 32 and w,, ht = 16 as the layer 2 of ResNet20. In HP-CACony (Figure I.. the HP setting of input ciphertext is (m,d) = (2, 4). In HP-RAConv (Figure 12.. the HP setting of input ciphertext is (m, d) = 24,
We use different brightness of color to fill the ciphertexts and plaintexts to reflect the actual com- putation process. In Figure II and 12 the intermediate ciphertexts of the CACony and input ci- phertexts of the RAConv are to and times larger than input ciphertext of the CACony, respec-
17

---

Under review as a conference paper at ICLR 2023
Layerl
Layer2
Layer3
Layerá
RosNet18
BB
DSB
BB
DSB
BB
DSB
BB
Ours
Loe
Ours
Lee
Ours
Loe
Ours
Lee
Ours
Lee
Ours
Lee
Ours
Lee
fitte plxts
3712
3712
3712
imput clats
2
2
2
4
1
4
1
4
total size (GB)
7.27
7.39
14.14
11.81
8.67
7.33
16.00
11.76
9.84
7.33
16.10
11.76
9.84
7.34
memory overhead
-0.256
19.7%
18.3%
36.8%
34.3%
36.8%
34.2%
Table 13: Total memory size and the number of each object in ResNet18. downsampling Block and basic block.
DSB and BB refers to
Im2Col
CAConv
RAConv
Bootstrap
Activation
Eic
total
runtime
3.99
5.98
2.68
28.97 35.4%
0.45 0.5%
39.78 48.60%
81.85 11.9
pereent
4.9
7.3
3.3
100%
Table 14: HyPHEN Inference time of single ImageNet image using ResNet18 models on GPU.
tively. The CACony, activation and RAConv in a ResNet block is processed at once to mitigate the huge number of intermediate ciphertexts. To avoid an increase of memory footprint, the operation on the input ciphertext continues until the ciphertext shrinks again. Thus, the tuple of operations {SISO, RaS, IR, Satuar,,SSSO, are processed to an input ciphertext and then accumulated. Blocks colored with high brightness show actual working set, which means & times larger interme- diate ciphertexts (colored with low brightness) are irrelevant with the peak memory consumption.
0
A15
0
F
h
h
A233
As2
6/2
feh
RuS
A
A1
0//4
SISO
MR
RoS
Mask and Broadcust
10-16.
g32-1230
Asge 320--0
RoS
repack
MA
Figure 11: CAConv method with HP
18

---

Under review as a conference paper at ICLR 2023
A1
F
24.9
(5-19)
Azst
100
Azd
1011-10
K A11-111177
1.5y
4/4
4/4
SISO,
MK
118-12228277
x2
(2.1117)
K 1219-13 10
RaS
Mask Broadeast e
(07-2440
(20-32.11
(177-24177
(/25-12.5)
RoS
repack
Figure 12: RACony method with HP
19


Reviews:
[{"review_id": "xVEZ3jbxDGA", "reviewer": "Reviewer_WKRX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 proposes a hybrid packing method that can speed up the Fully Homomorphic Encryption (FHE) based neural network. Experiments are performed on speeding up the CKKS implementation of ResNet on CIFAR-10 image classification. The motivation is that, in the CKKS FHE computation of convolutions, the HE computation can be speed up by a dedicated design of repacking the values such that homomorphic rotation can be avoided, thus speed up the overall pipeline. Specifically, two new conv algorithms named RAConv and CAConv are proposed. The authors further extend the design of stacking RAConv and CAConv, in building a new scheme of ResNet basic block by  combining CAConv + RAConv. And with multiplex packing, the efficiency of the FHE CKKS pipeline is further improved. The experiments show that RAConv saves more time and the number of rotations over CAConv, and the combination of CAConv + RAConv is more efficient than only using CAConv.", "summary_of_the_review": "The proposed RAConv and CAConv+RAConv Basic Block represent a contribution to the secure DNN inference research.", "strength_and_weaknesses": "Strengths\n\n- The proposed packing method using CAConv and RAConv is novel in improving the performance of the heavy computation of CKKS FHE. \n\n- RAConv has advantages over CAConv. The combination of CAConv+RAConv has advantages over only using CAConv.\n\n\nWeaknesses\n\n- Please report the information about the number of ciphertexts in your hybrid packing experiments. Also please report the amount of memory used for the comparison of pros and cons.\n\n- This paper is hard to read in the explanation of the proposed RAConv and CAConv (Fig. 2) and the hybrid packing (Fig. 4). I have to read multiple passes of the section to understand.\n\n- The details of \"lazy-SISO\" is not provided. It is mentioned multiple times in the paper but never explained how it works. What part of the computation is postponed and calculated when needed? \n\n\n3.* Clarity, Quality, Novelty And Reproducibility Can you provide an evaluation of the quality, clarity and originality of the work?", "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": {}}, {"review_id": "a4_ZTui0LN", "reviewer": "Reviewer_sH4P", "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 presents a new HCNN implementation to perform private inference (PI) called HyPHEN. It proposes a replication-based convolution method (RAConv), which is innovatively alternated with the channel-aligned convolution method (CAConv). It also proposes a hybrid packing method, which is a combination of two existing packing methods: duplicate and multiplex packing. Both these methods reduce the overall number of homomorphic rotations and lead to 3-4 times lower latency compared to the baseline, with comparable accuracy based on ResNet architectures with RNS-CKKS implementation on the CIFAR-10 dataset. ", "summary_of_the_review": "The structure of the paper is good and easy to understand. Moreover, obtained results (e.g., speedup in throughput) are better than the state-of-the-art. However,  the novelty is limited and including experiments for complex settings (e.g., larger datasets) would enhance the paper.", "strength_and_weaknesses": "Strengths: \n-\tFigures explaining convolutional operations\n-\tWell-described problem statement\n\nLimitations:\n\n1) Main contributions of the paper, namely, RAConv and hybrid packing method have limited novelty. RAConv is not entirely different from CAConv and the hybrid packing method is the mixture of two existing packing methods. The resulting HyPHEN implementation can be described as a minor/incremental improvement over existing approaches. \n\n2) Only the SISO case is considered. There is no mention about other scenarios (e.g., MIMO) and whether the proposed techniques can also be applied to other scenarios.\n\n3) Results on larger datasets with higher resolution images (say 224 x 224 x 3) must be included. This is critical to determine if the proposed methods can make real-world private inference scenarios feasible.  ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "09g3YH6IJGH", "reviewer": "Reviewer_JDDo", "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 proposes a new packing scheme for improving the efficiency of convolution layers over homomorphically encrypted data. The paper first identifies that homomorphic rotations are the computational main bottleneck. Then a new data packing scheme is proposed to minimize the number of required rotations. The network architecture is based off of AESPA and evaluation is performed on CIFAR-10 using the HEAAN library. The proposed approach is able to reduce the computational complexity of ResNet models compared to multiplexed convolutions, the current state-of-the-art.", "summary_of_the_review": "Overall, I am moderately positive about the paper; the new convolution layer certainly reduces the number of required rotations, which are computationally expensive. However, as pointed out above, there is missing information in the paper that does not allow the reader to understand the actual source of improvements, both from a performance and latency perspective.\n\n**Update after Rebuttal:** I saw the rebuttal and the updates to the paper. The comparisons to the convolution in Lee 2022a are favorable from a latency perspective but at the price of higher memory requirements. So it is not clear if the proposed convolution is strictly better. The latency improvements over AESPA seem marginal. I am discarding the accuracy improvements over Lee 2022a since they are essentially a function of better plaintext training, which is equally applicable to Lee 2022a. Given the above, I am inclined to maintain my original rating of the paper.", "strength_and_weaknesses": "Strengths:\n\n1. The paper identifies a bottleneck in implementing convolutional layers in CKKS, namely the large number of rotation operations. The paper proposes a new packing method that reduces the amount of expensive rotations.\n\n2. The proposed convolution when coupled with low-degree polynomial approximation in AESPA leads to high-performance networks with better latency in ciphertext compared to multiplexed convolution. Although the source of the latency gains are probably elsewhere as described below.\n\nWeaknesses:\n\n1. The comparison to multiplexed convolution [2] (Lee et.al. 2022a) is not entirely fair. [2] seeks to approximate ReLU functions for directly employing them in pre-trained models, as opposed to training the models from scratch as is the case for HyPHEN. As such, the goals and operational settings of the two papers are not the same. HyPHEN needs models to be trained from scratch which is not always possible. This is an important distinction and that is ignored by the paper.\n\n2. Encrypted inference in CNNs is bottlenecked in three respects,\n - (1) depth consumption of the circuit\n - (2) expense of bootstrapping operations\n - (3) cost of convolution operations.\n\nUsing low-degree polynomial approximations from AESPA mitigates (1). And, because of using low-degree approximations from AESPA, HyPHEN can use one less bootstrapping layer per residual block compared to [2], which helps mitigate (2). And since bootstrapping and polynomial approximations of ReLU consume the most levels and are the slowest parts, a majority of the latency gains in HyPHEN are probably from these two aspects as opposed to the proposed packing scheme.\n\nRebuttal Requests:\n1. As far as I understand, the main difference from AESPA [1] is a convolution layer with fewer rotations. Yet, the performance of the ResNet models considered in this paper have improved from the corresponding ones in AESPA. Can you comment on what brought about this change, since changing the implementation of convolution should not affect the performance of the model itself?\n2. In order to really understand the source of improved overall latency, can you provide a breakdown of the cost of each operation like Table 3 in [2]? Please report this for the proposed approach but with two versions of convolution, (a) multiplexed convolution, and (b) the proposed HP-CAConv+HP-RAConv? Or alternatively add another version of Table 4 where the convolution is multiplexed convolution as opposed to HP-CAConv+HP-RAConv. This should help delineate the source of latency improvements.\n4. Reporting latency and claiming latency improvements is not adequate. Latency is affected by multiple system level factors, including number of cores, type and speed of each processor, throttling, other processing that maybe running etc. Measurements for the baselines and the proposed methods have to be performed under the exact same settings, which is hard to do, and must be repeated multiple times for reliability. Are the reported latency values for HyPHEN and the baseline measured under the same settings? Can you report mean and standard deviation over multiple runs?\n5. Can you comment on the memory consumption for inference on encrypted data?\n\n[1] AESPA: Accuracy Preserving Low-degree Polynomial Activation for Fast Private Inference, arXiv:2201.06699\n\n[2] Low-Complexity Deep Convolutional Neural Networks on Fully Homomorphic Encryption Using Multiplexed Parallel Convolutions, ICML 2022", "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