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