  Processing convolution layers remains a huge bottleneck for private deep
convolutional neural network (CNN) inference for large datasets. To solve this
issue, this paper presents a novel homomorphic convolution algorithm that
provides speedup, communication cost, and storage saving. We first note that
padded convolution provides the advantage of model storage saving, but it does
not support channel packing, thereby increasing the amount of computation and
communication. We address this limitation by proposing a novel plaintext
multiplication algorithm using the Walsh-Hadamard matrix. Furthermore, we
propose the optimization techniques to significantly reduce the latency of the
proposed convolution by selecting the optimal encryption parameters and
applying lazy reduction. It achieves 1.6-3.8x speedup and reduces the weight
storage by 2000-8000x compared to the conventional convolution. When the
proposed convolution is employed for CNNs like VGG-16, ResNet-20, and
MobileNetV1 on ImageNet, it reduces the end-to-end latency by 1.3-2.6x, the
memory usage by 2.1-7.9x and communication cost by 1.7-2.0x compared to
conventional method.
