HyPHEN: A Hybrid Packing Method and Optimizations for Homomorphic
  Encryption-Based Neural Networks
Convolutional neural network (CNN) inference using fully homomorphic
encryption (FHE) is a promising private inference (PI) solution due to the
capability of FHE that enables offloading the whole computation process to the
server while protecting the privacy of sensitive user data. Prior FHE-based CNN
(HCNN) work has demonstrated the feasibility of constructing deep neural
network architectures such as ResNet using FHE. Despite these advancements,
HCNN still faces significant challenges in practicality due to the high
computational and memory overhead. To overcome these limitations, we present
HyPHEN, a deep HCNN construction that incorporates novel convolution algorithms
(RAConv and CAConv), data packing methods (2D gap packing and PRCR scheme), and
optimization techniques tailored to HCNN construction. Such enhancements enable
HyPHEN to substantially reduce the memory footprint and the number of expensive
homomorphic operations, such as ciphertext rotation and bootstrapping. As a
result, HyPHEN brings the latency of HCNN CIFAR-10 inference down to a
practical level at 1.4 seconds (ResNet-20) and demonstrates HCNN ImageNet
inference for the first time at 14.7 seconds (ResNet-18).
Donghwan Kim, Jaiyoung Park, Jongmin Kim, Sangpyo Kim, Jung Ho Ahn
# HyPHEN: A Hybrid Packing Method and Optimizations for Homomorphic Encryption-Based Neural Networks

###### Abstract

Convolutional neural network (CNN) inference using fully homomorphic encryption (FHE) is a promising private inference (PI) solution due to the capability of FHE that enables offloading the whole computation process to the server while protecting the privacy of sensitive user data. However, prior FHE-based CNN (HCNN) implementations are far from being practical due to the high computational and memory overheads of FHE. To overcome this limitation, we present HyPHEN, a deep HCNN construction that features an efficient FHE convolution algorithm, data packing methods (hybrid packing and image slicing), and FHE-specific optimizations. Such enhancements enable HyPHEN to substantially reduce the memory footprint and the number of expensive homomorphic operations, such as ciphertext rotation and bootstrapping. As a result, HyPHEN brings the latency of HCNN CIFAR-10 inference down to a practical level at 1.40s (ResNet20) and demonstrates HCNN imageNet inference for the first time at 16.87s (ResNet18).

 Private Inference, Fully Homomorphic Encryption

## I 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 [1] and HIPAA Act [2]. 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 a private medical diagnosis of diseases, and security companies can provide private surveillance systems without accessing client's sensitive data [3, 4].

Fully homomorphic encryption (FHE) [5] is a cryptographic primitive that enables direct evaluation of a rich set of functions on encrypted data, making it especially suited for PI among other cryptographic candidates [6, 7]. FHE-based PI 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 FHE-based PI of convolutional neural networks (HCNN) [8, 9, 10, 11, 12].

However, FHE incurs high computational and memory overheads, hindering the adoption of HCNN for real-world services. Several prior works has tried to mitigate the overheads [11, 13], but HCNN implementations still stay at a proof-of-concept level and target elementary problems such as MNIST and CIFAR-10. Gazelle [14] proposes a convolution algorithm for homomorphic encryption, which is widely adopted and by the following studies [11, 15, 16]. Gazelle and most prior PI CNN implementations have avoided the high overheads of FHE by restricting the CNN models to shallow ones [8], or mixing use of other cryptographic primitives, such as multi-party computation (MPC) [15, 17, 18]; however, MPC solutions require extra user intervention and the associated data communication overheads. The state-of-the-art FHE solution [11] modifies Gazelle's algorithm by densely mapping data into a ciphertext before entering the next convolution layer, and optimizes it for FHE circumstances. Despite such efforts, prior implementations take tens of minutes [11] to even hours [13] to perform a single HCNN inference of CIFAR-10 (ResNet20).

We propose HyPHEN, which mitigates the huge overhead of HCNN with an optimized convolution algorithm and packing methods. We observe that, in HCNN, rotation operations take up the majority of the runtime (see Appendix A). Most of the rotations are performed to maintain the data organization inside an encrypted tensor uniformly throughout HCNN inference. _Lazy-SISO_ algorithm and _hybrid packing (HP)_ method of HyPHEN allow switching between multiple data organizations to get rid of excessive rotation operations. Also, our _image slicing_ method tackles the data expansion problem of HCNN by enhancing data reuse with only 2.5% runtime computational overhead, and saves hundreds of GBs of memory space. By these means, our GPU implementation of HyPHEN achieves 1.40s of execution time for encrypted CIFAR-10 inference with the ResNet20 model, reaching a real-time level. Also, HyPHEN shows HCNN inference for ImageNet inference with the ResNet18 model for the first time, which takes 16.87s. The key contributions of the paper are as follows:

* We devise an optimized algorithm for convolution, which alternates between two methods, _channel-aligned convolution (CAConv)_ and _replication-aligned convolution (RAConv)_, where such composition is enabled by our novel lazy-SISO algorithm.
* We propose a _hybrid packing (HP)_ method that can utilize the entire slots of a ciphertext with a marginal increase in the number of rotations.
* We show the huge memory footprint of HCNN deteriorates its performance and propose an _image slicing_ method that can save hundreds of GBs of memory space with negligible overhead.

## II Background

### _Fully Homomorphic Encryption (FHE)_

FHE is a set of public key encryption schemes that enable computation on encrypted data. Among several popular FHE schemes, RNS-CKKS [19] has been broadly adopted in the PI domain as it supports fixed-point numbers and _slot batching_. A _plaintext_ in RNS-CKKS is an unencrypted degree-\((N{-}1)\) polynomial in a cyclotomic polynomial ring, \(R_{Q}\!=\!\mathbb{Z}_{Q}[X]/(X^{N}{+}1)\). A plaintext maps to a message which is a vector of \(N/2\) real (or complex) numbers, i.e., a single plaintext batches \(N/2\)_slots_, each of which can store a complex or real number. CKKS encrypts a plaintext into a _ciphertext_ in \(R_{Q}^{2}\). \(Q\) is a ring modulus represented by a set of prime moduli obtained by the Chinese Remainder Theorem (CRT) as \(Q=\prod_{i=0}^{l}q_{i}\;(0\leq l\leq L)\). \(L\) and \(l\) denote the initial and current _level_ of a ciphertext, which is an HE-specific resource that determines the number of multiplications applicable to a given ciphertext. We also denote the associated level of ring modulus using subscript as \(Q_{L}\) or \(Q_{l}\). We denote the plaintext and ciphertext of a message **a** as \(\langle\textbf{a}\rangle\) and **[a]**. HE operations of addition, multiplication, and rotation can be described as follows:

* HE.Eval([**a**],[**b**],\(f_{l}\)) = HE.Eval([**a**],\(\langle\textbf{b}\rangle\),\(f_{l}\)) = [\(f_{l}\)(**a**,**b**)]
* HE.Rotate([**a**],\(r\)) = [rot(**a**,\(r\))]

\(f_{l}\) denotes linear operations, either addition or (Hadamard) multiplication. rot(**a**,\(r\)) represents cyclically shifting vector **a** by \(r\) to the left. Unlike addition and rotation, multiplication in RNS-CKKS requires additional rescale operation, which consumes a level by dividing \(ct\in R_{Q_{l}}\) into \(ct^{\prime}\in R_{Q_{l-1}}\). If a ciphertext has no level left after a series of multiplications, _bootstrapping_[20] is needed to reconcile the levels and allow further operation. Bootstrapping, the most costly operation in HE, consists of multiple HE operations including rescale operations. After bootstrapping, the level of the resulting ciphertext becomes \(L^{\prime}\!=\!(L-L_{b})\) where \(L_{b}\) 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 \(L_{b}\). 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 of HE, large \(L\) requires large \(N\) (\(\geq 2^{15}\)). Thus, prior works on FHE [21, 22, 23] target \(N=2^{15}\) to \(2^{17}\).

Table I shows the execution time of HE operations on a system specified in Section IV-A. We measured the execution time of each operation at the initial level (\(L^{\prime}\)) of a 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 to the expensive key-switching procedure.

### _Convolution on Homomorphic Encryption_

In this subsection, we describe the baseline HCNN algorithms. We represent input and output tensors with tuples \(\{w_{i},h_{i},c_{i}\}\) and \(\{w_{o},h_{o},c_{o}\}\), and convolution layers with \(\{f_{w},f_{h},c_{i},c_{o}\}\). We denote the stride of convolution as \(s\) and assume \(padding=1\) for simplicity.

**Single-input, single-output channel convolution (SISO):** Gazele [14] proposes efficient convolution algorithms on HE, referred to as SISO. Figure 1 shows SISO for \(s=1,2\). Filter elements are separated into \(f_{w}f_{h}\) plaintexts. Each slot in \(i\)-th plaintext stores \(k_{i}\) or 0 (punctured) depending on whether \(k_{i}\) 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 multiplication, and 3) accumulate the multiplication results to obtain the output.

**Channel-aligned convolution (CAConv):** For multiple channels, convolution is performed in a SIMD manner. If the size of a channel (\(w_{i}h_{i}\) or \(w_{o}h_{o}\)) is smaller than the number of slots in a ciphertext, multiple channels can be placed in a ciphertext. For example, if \(slot=2^{15}\) and an input channel is sized \(w_{i}h_{i}=32\times 32\) as in the input image of the CIFAR-10 dataset, \(\frac{slot}{w_{i}h_{i}}=32\) channels can be placed in a single ciphertext in an aligned manner (i.e., _channel-aligned_). Suppose we perform convolution on a channel-aligned input ciphertext with \(c_{i}=\frac{slot}{w_{i}h_{i}}\) channels. First, SISO is performed on \(c_{i}\) input

\begin{table}
\begin{tabular}{c|c c c c c c c} \hline \hline Operation & AddPt & AddCt & MulPt & MulCt & Rescale & Rotate & Boot \\ Time (ms) & 0.572 & 0.202 & 0.506 & 17.3 & 3.90 & 15.5 & 2160 \\ \hline \hline \end{tabular}
\end{table} TABLE I: Benchmark of HE operations averaged over 100 iterations on CPU (64 threads). Pt and Ct postfixes each represents ciphertext-plaintext and ciphertext-ciphertext operation, respectively.

Fig. 1: Single-input and single-output channel convolution (SISO). Ciphertexts and plaintexts are illustrated as 2D matrices, but are actually stored in 1D manner with each matrix row concatenated.
channels in a SIMD manner (see Figure 1(a)), which produces \(c_{i}c_{o}\) convolution outputs \(MK^{(i,j)}\) (\(1\leq i\leq c_{i}\), \(1\leq j\leq c_{o}\)). To compute the result for the \(k\)-th output channel, \(\sum_{i=1}^{c_{i}}MK^{(i,k)}\) is accumulated by _RaS (Rotate and Sum)_. RaS is repeated for each of \(c_{o}\) output channels. Throughout this paper, we refer to this convolution that takes a channel-aligned ciphertext as the input as _channel-aligned convolution (CAConv)_.

**Input repetition:** CAConv can be further optimized when the input tensor is smaller than the number of slots in a ciphertext. \(\frac{slot}{w_{i}h_{i}c_{i}}\) copies of the input tensor can be placed in a ciphertext, then \(\frac{slot}{w_{i}h_{i}c_{i}}\) output channels can be computed together with a single input ciphertext [11].

**Replication-aligned convolution (RAConv):** The output ciphertexts of CAConv holds multiple replications of a single output channel (i.e., _replication-aligned_). To perform another convolution, additional operations are required to realign the ciphertexts into the channel-aligned form, which we refer to as _IR (Image Realignment_). [12] constructs a framework supporting a broad scope of convolution algorithms for ciphertexts with various alignments. We build on the framework and design _replication-aligned convolution (RAConv)_. In RAConv, each replication-aligned ciphertext is multiplied with plaintexts containing filter weights for different output channels, whose results can be accumulated to produce a single channel-aligned ciphertext (see Figure 1(b)). Therefore, CAConv and RAConv can be performed in an alternative manner to get rid of costly IR computation, when performing multiple convolutions.

**Packing:** Strided convolution (\(s>1\)) using SISO creates a gap between valid values (see Figure 0(c)). A ciphertext with a gap underutilizes its slots, leading to throughput degradation. While Gazelle removes the gap by a client-aided re-encryption process, non-interactive PI should remove the gap through masking and rotation, which incur additional computation and level consumption. [11] propose a _multiplexed packing_ method that can be combined with CAConv (_MP-CAConv_) to mitigate the overheads. In the IR stage of MP-CAConv, the gap is filled with other channels (see Figure 2(b)), which we refer to as the _repacking process_. Therefore, IR incorporates both realigning and repacking processes in MP-CAConv.

There are many variants of the convolution algorithm for HE [11, 13, 15, 16, 24], but most of them resort to SISO. [12] devise a convolution algorithm based on tile tensoring, and not SISO, which can be an efficient alternative to SISO for specific HE parameter settings and image sizes. However, we find that tile tensoring incurs an excessive amount of bootstrapping for FHE circumstances in general, so we exclude it from analysis and mainly focus on SISO convolution in the paper.

### _Activation Function on Homomorphic Encryption_

Non-linear activation functions, such as ReLU, cannot be used directly in HCNN. They must be replaced by polynomial functions as HE only supports addition and multiplication operations. Direct replacement of non-linear functions with approximate polynomials requires the approximation error to be kept low over a wide range, to retain the accuracy of a CNN model. [25] approximate ReLU while keeping \(l_{1}\) norm of approximation error lower than \(2^{-13}\) in the range of [-50, 50], using a composition of 15-, 15-, and 27-degree polynomials. Approximation-based approach has a benefit that it can be applied to pre-trained 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 activation functions as in [26, 27, 28, 29, 30]. While this approach requires retraining, operational cost is much cheaper compared to high-degree polynomials. Recently, AESPA [31] has demonstrated that CNN trained with low-degree polynomials can achieve equivalent accuracy to ReLU-based networks across various CNN networks and image datasets. AESPA replaces ReLU and batch normalization (BN) with the

Fig. 3: Comparison of gap packing methods to fill gap induced by downsampling layers. \(a_{i}^{(j)}\) denotes the \(i\)-th element in the \(j\)-th channel of a tensor \(a\).

Fig. 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)}K^{(a,b)}\) as \(MK^{(a,b)}\).
composition of orthogonal basis polynomials and basis-wise BN. During inference, the composition turns into a second-degree polynomial, so AESPA can drastically reduce runtime cost for activation. Therefore, we adopt AESPA for our HCNN implementation.

### _Threat Model_

We adopt the same threat model as prior PI works on HE [11, 8]. 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 to 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 at the server other than the result.

## III HyPHEN Construction

We introduce HyPHEN, our HCNN solution which focuses on reducing the memory footprint and the number of expensive homomorphic operations, including rotation and bootstrapping. We implement ResNet [32] models for CIFAR-10 and ImageNet inference tasks with HyPHEN to demonstrate its effectiveness.

### _RAConv and Lazy-SISO_

The main performance bottleneck of CAConv is the massive number of rotations. CAConv requires an enormous number of rotations for RaS and IR, which take up most of the time in CAConv. For example, rotations for RaS and IR respectively account for 49% and 43% of the total rotations in an MP-CAConv implementation of ResNet20. Furthermore, IR consumes an additional level for masking to extract the values. RAConv does not require RaS and reduces the overheads for IR when alternatively performed with CAConv, but it requires more rotations for SISO. While CAConv requires \((f_{w}f_{h}-1)\) rotations for SISO, RAConv requires \((f_{w}f_{h}-1)\) rotations for each of \(c_{i}\) input ciphertexts.

We devise lazy-SISO algorithm, which reduces the number of rotations for RAConv. With lazy-SISO, rotations are delayed to be performed after multiplications with weight plaintexts. Then, the accumulation step in RAConv transforms into an RaS step (see Figure 1(c)), which only requires \((f_{w}f_{h}-1)\) rotations. Without Lazy-SISO, simply alternating between CAConv and RAConv does not have much performance benefit due to additional SISO overheads. See Appendix A for more details of lazy-SISO.

### _Hybrid Packing_

SISO convolution suffers from low slot utilization in ciphertexts due to the gap created by strided convolutions, which leads to severe throughput degradation in HCNN. Prior state-of-the-art HCNN implementation (MP-CAConv) mitigates the underutilization of slots by packing input ciphertexts as dense as possible using multiplexed packing and input repetition (see Section II-B). However, such dense packing causes a lot of additional rotations to adjust the data organization because SISO still produces a void-packed ciphertext (see Figure 2(a)) even if the input ciphertext is densely packed. MP-CAConv has to manually restore the dense data organization by masking off invalid values and filling the gap with the values from different channels during the IR process. As a result, MP-CAConv ends up requiring additional \(c_{o}\) rotations to maintain multiplexed packing and \(\log\frac{slot}{w_{o}h_{o}c_{o}}\) rotations to maintain input repetition.

To reduce the repacking overhead between convolutional layers, we propose a novel _hybrid packing (HP)_ method. HP fills the gap with duplicates of multiple channels (See Figure 2(d)). We design HP based on two key observations. First, applying convolution over a duplicate-packed ciphertext (Figure 2(c)) produces a multiplex-packed output ciphertext as in Figure 2(b). Second, converting a void-packed ciphertext into a duplicate-packed ciphertext requires fewer rotations than converting it into a multiplex-packed ciphertext. Duplicate packing only needs O(log(\(gap_{size}\))) rotations while multiplexed packing requires O(\(gap_{size}\)) rotations.

We represent a hybrid-packed ciphertext by a pair of \((m,d)\), where \(m\) is the number of multiplexed channels, and \(d\) is the number of duplicates. For example, Figure 2(d) shows \((m,d)\!=\!(2,2)\) HP. Data organization for HP can differ even for the same \((m,d)\) parameter, and depends on the convolution algorithm. HP parameter \((m,d)\) changes when CAConv or RAConv is performed as shown in Figure 4. We denote \((m,d)\) of the input and output ciphertexts as (\(m_{\text{in}}\), \(d_{\text{in}}\)) and (\(m_{\text{out}}\), \(d_{\text{out}}\)). Input repetition is no longer required as HP with larger \(d_{\text{in}}\) can be used instead. During convolution, duplicates of the same element produce output elements in different channels (\(c^{(1)}\)-\(c^{(4)}\) in Figure 3(a), and \(c^{(1)}\) and \(c^{(17)}\) in Figure 3(b)). Therefore, after the IR process, we get output ciphertexts with the HP parameter set to \((m_{out},d_{out})\!=\!(d_{in},m_{in})\). So, after a series of CAConv and RAConv, the HP parameter returns to the initial \((m_{in},d_{in})\). The complete procedures of RAConv and CAConv with HP are described more in detail in Appendix A.

Compared to MP-CAConv, HP significantly reduces the rotations in RaS and IR. The rotation counts of MP-CAConv [11] and our HP convolutions are shown in Table II. For both HP convolution methods, the product of the numbers of input and output ciphertexts remains constant (\(ct_{in}\cdot ct_{out}=\frac{vt_{in}c_{c}c_{o}}{slot_{o}}\)). Compared to MP-CAConv, the number of rotations for RaS is reduced by about \(ct_{in}\) times for both HP-CAConv and HP-RAConv. Also, the number of rotations required for repacking decreases from \(c_{o}\) of MP-CAConv to mere \(\log m_{in}\) per output ciphertext in our HP convolutions. Although HP requires slightly more rotations for SISO (\(ct_{min}\) of HP convolutions are usually higher than \(ct_{in}\) of MP-CAConv), HP reduces the overall number of rotations required for convolution. We also explore various combinations for the \((m,d)\) pair to minimize the total number of rotations. The choice of \((m,d)\) decides \(ct_{in}\) and \(ct_{out}\) 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 Appendix A.
### _Image Slicing_

In HCNN inference, weight plaintexts take the majority of the memory footprint. In the ResNet models in our experiment, plaintexts take tens to hundreds of GBs of memory space, occupying the majority of the memory footprint. The plaintext packing method of SISO replicates each filter element \(w_{i}h_{i}\) times to form a weight plaintext (see Figure 0(b)), which requires a total of \(w_{i}h_{i}f_{w}f_{h}c_{i}c_{o}\) plaintext slots for a weight tensor. Such plaintext data expansion increases the cost of HCNN inference in terms of storage capacity and memory bandwidth. For instance, plaintexts for running ResNet18 on ImageNet take up 379GB of memory space (see Table III), which even exceeds the memory capacity of the latest GPUs, limited by the current HBM technology.

We find a method to reduce data expansion of plaintexts, by organizing the weights in a circular way such that they can be permuted at runtime when being multiplied with the input ciphertexts. This results in a packing method for ciphertexts shown in Figure 5, which we refer to as _image slicing_. In CAConv, the input image is divided into \(s_{i}\) (2 in the figure) slices, and different slices are chosen from each channel to be placed in a single ciphertext. This organization enables each plaintext to be reused by \(s_{i}-1\) permutations. After accumulation, the output ciphertext follows a simple replication-aligned organization. After modified RAConv with image slicing shown in Figure 4(b), the organization returns to the image-sliced one.

Image slicing can be orthogonally applied along with HP, and reduce the memory footprint for plaintexts roughly by a factor of \(s_{i}\). Extra computation of plaintext permutation during imageliced convolution is not significant to the overall performance because plaintext permutation is much less complex than other homomorphic operations; plaintext permutation only involves moving data elements. We use \(s_{i}=8\) for ImageNet implementations of HyPHEN, but do not apply image slicing to CIFAR-10. Image slicing requires an explicit zero padding inside a ciphertext, to which the small image size of CIFAR-10 (e.g., 16\(\times\)16 space is required for a 8\(\times\)8 feature map) is not well suited. Zero padding overhead outweighs the benefit of image slicing, so it is not applied to CIFAR-10.

\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Method** & \(ct_{in}\) & \(ct_{out}\) & **SISO** & **RaS** & **IR** \\ \hline
**[11]** & \(\frac{\pi i_{h}c_{i}}{slot}\) & \(\frac{\pi w_{h}aca_{i}}{slot}\) & \(ct_{in}(f_{w}f_{h}-1)\) & \(\frac{w_{i}h_{i}c_{i}}{slot}\log c_{i}\) & \(c_{o}\)+\(\log\frac{slot}{w_{o}hc_{o}}\) \\ \hline
**HP-CAConv** & \(\frac{w_{h}c_{i}d_{i}}{slot}\) & \(\frac{c_{o}}{slot}\) & \(ct_{min}(f_{w}f_{h}-1)\) & \(ct_{out}\log\frac{c_{i}}{ct_{in}}\) & \(c_{out}\log m_{in}\) \\ \hline
**HP-RAConv** & \(\frac{c_{i}}{m_{in}}\) & \(\frac{w_{i}h_{i}c_{i}m_{in}}{slot}\) & \(ct_{min}(f_{w}f_{h}-1)\) & \(ct_{out}\log m_{in}\) & \(c_{out}\log m_{in}\) \\ \hline \hline \end{tabular}
\end{table} TABLE II: The rotation complexity of the convolutions. We denote the numbers of input and output ciphertexts as \(ct_{in},ct_{out}\). Then, \(ct_{min}=\min(ct_{in},ct_{out})\) considering SISO and lazy-SISO.

Fig. 4: The procedure of CAConv and RAConv with hybrid packing

Fig. 5: Simplified convolution processes with image slicing. Ciphertexts are filled with image slices each represented with a channel number and a postfix: upper half of image as \(a\) and lower half as \(b\) (e.g. _3b_ represents the lower half of the 3\({}^{\text{rd}}\) channel). Ciphertexts are multiplied with plaintexts holding weight values, where \(i,j\) on each slice represents weight values for \(i\)-th input channel, and \(j\)-th output channel. Black arrow represents plaintext permutation.
### _ResNet Construction with HyPHEN_

HyPHEN combines RAConv, HP and Image Slicing to build the entire CNN model. Figure 6 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 for the former. Second, to match the level between the shortcut path and the main CAConv-RAConv path, bootstrapping should be placed either before residual connections diverge or after they converge. Last, it is beneficial to perform convolutional layers at the lowest level possible because the complexity of FHE operations such as rotation is proportional to the level \(l\) of the ciphertext.

All things put together, our ResNet basic block 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 of SISO and IR. Activation uses AESPA and consumes 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^{2}\). We set the ciphertext level after bootstrapping (\(L^{\prime}\) in Section II-A) to six and perform bootstrapping when the level becomes zero.

## IV Evaluation

### _Experimental Setup_

We ran HCNN inference on CPU and GPU environments using the RNS-CKKS library, HEaaN [33]. The CPU system is equipped with two AMD EPYC 7452 CPUs running at 2.35GHz (32 cores per socket) and 480GB DRAM. GPU experiments were conducted at the same system with an additional NVIDIA A100 GPU with 80GB HBM. Our HCNN inference experiments used the CIFAR-10 [34] and ImageNet [35] datasets. We evaluated 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 [36] with polynomial degree \(N\!=\!2^{16}\) and hamming weight 192. The bootstrapping implementation consumes 17 levels.

### _Performance_

We first compare HyPHEN against Cheetah [18], one of the state-of-the-art HE-MPC hybrid PI protocol. As it is hard to make a fair comparison between the HCNN and HE-MPC as the preferred system settings are different, we set out to use the best result presented in the paper. Here, HyPHEN is 11.3\(\times\) faster than Cheetah on ResNet32 considering the end-to-end runtime and 5.5\(\times\) efficient than Cheetah in terms of communication. Although the HE-MPC hybrid PI protocol is generally accepted as faster than HCNN, equipped with efficent packing scheme and hardware acceleration, we show that the performance of HCNN inference is comparable.

In FHE domain, [11, 13] has priorly shown ResNet on CIFAR-10, while [11] reported single thread implementation of ResNet20 in 2271s. HyPHEN shows significant latency reduction on image classification. Our work conduct the same task in 37.6 seconds in 64 thread CPU environment, and further reduces within 1.4 seconds in GPU.

### _Sensitivity Study_

To analyze the effectiveness of each component of HyPHEN, we started from the HCNN implementation of [11] augmented with AESPA (Baseline), and gradually applied alternation between CAConv and RAConv with lazy-SISO (+ L-SISO), HP (+ HP), and image slicing (HyPHEN). We tested with CPU/GPU implementations of ResNet18 for ImageNet. The results are shown in Figure 7.
weight plaintexts by roughly \(s_{i}=8\) times, it does not lead to reduction in latency for our CPU system. However, for the GPU system, image slicing enables the whole working set to fit in the 80GB GPU memory, so also reduces the latency by removing the runtime overhead of copying data from the host to the GPU (Memory). Overall, image slicing has benefits of substantial memory footprint reduction and also latency reduction for memory-constrained systems.

### _Execution Time Breakdown_

Table IV shows the runtimes of ResNet20/32/44 for the inference of a single CIFAR-10 image and ResNet18 for a single ImageNet image. Our ResNet20/32/44 implementations on GPU take merely a few seconds to complete. While the majority of inference time for ResNet20/32/44 is spent on bootstrapping, for ResNet18, 51.1% to 57.0% of inference time is spent on convolution as ResNet18 has four times more channels than ResNet20/32/44. Table IV also demonstrates that RAConv effectively reduces the overall runtime of the convolution layers, following the operation count analysis in Table VIII. We provide more detailed comparison with [11] in Appendix A.

### _Accuracy_

In Table V, we measured inference accuracies for CIFAR-10 running ResNet models with HyPHEN.1 Near-zero accuracy degradation (\(\leq\) 0.01%) is observed for ResNet20/32/44. HyPHEN is more robust to accuracy degradation than [11], which shows 0.09% to 0.21% accuracy degradation for ResNet20/32/44 on CIFAR-10. The difference in accuracy drop can be explained by whether the original network is executed as is (using AESPA) or an approximation has been made (using ReLU approximation).

Footnote 1: We are still experimenting on the ImageNet accuracy, and will report the accuracy of the ResNet18 model for ImageNet in the revised version.

## V Future Work

We have shown the effectiveness of HyPHEN on HCNN using ResNet as representative CNN models. Exploring application of HyPHEN to a broader scope, such as application to various models as in [37], is needed as future work.

## VI Conclusion

In this paper, we proposed HyPHEN, an efficient private inference construction of FHE-based CNN (HCNN). Mixing two convolution methods with lazy-SISO and hybrid packing (HP) enables fast inference by significantly reducing the number of homomorphic rotations in convolution. Also, image slicing enables HyPHEN to reduce the memory footprint for high resolution image classification tasks, which is especially beneficial for memory-constrained devices. Our experiments with HyPHEN on CPU systems show 1.87\(\times\) lower latency compared to the prior state-of-the-art implementation. Using GPU acceleration, HyPHEN achieves 1.40s/2.17s/2.96s execution time for running ResNet20/32/44 for CIFAR-10, and we also showed HCNN inference of ResNet18 for ImageNet in 16.87s for the first time.
