  Fully homomorphic encryption (FHE) is a promising cryptographic primitive for
realizing private neural network inference (PI) services by allowing a client
to fully offload the inference task to a cloud server while keeping the client
data oblivious to the server. This work proposes NeuJeans, an FHE-based
solution for the PI of deep convolutional neural networks (CNNs). NeuJeans
tackles the critical problem of the enormous computational cost for the FHE
evaluation of convolutional layers (conv2d), mainly due to the high cost of
data reordering and bootstrapping. We first propose an encoding method
introducing nested structures inside encoded vectors for FHE, which enables us
to develop efficient conv2d algorithms with reduced data reordering costs.
However, the new encoding method also introduces additional computations for
conversion between encoding methods, which could negate its advantages. We
discover that fusing conv2d with bootstrapping eliminates such computations
while reducing the cost of bootstrapping. Then, we devise optimized execution
flows for various types of conv2d and apply them to end-to-end implementation
of CNNs. NeuJeans accelerates the performance of conv2d by up to 5.68 times
compared to state-of-the-art FHE-based PI work and performs the PI of a CNN at
the scale of ImageNet (ResNet18) within a mere few seconds
