Efficient Convolution Operator in FHE Using Summed Area Table

To enhance privacy in Convolutional Neural Network (CNN) based inference methods, fully homomorphic encryption (FHE) is a golden tool. However, high latency and limited multiplicative depth are major problems in building CNNs for FHE. Convolution operations dominate the inference time of CNNs in FHE schemes due to the large number of costly multiplications and accumulation operations required. All the prior works have performed convolution in either the spatial or frequency domain. Alternatively, in this paper, we propose to use a summed area table (SAT) along with kernels approximated with box filters for the computation of convolution in 1D, 2D, and 3D space. The usage of box filters allows us to reduce the number of costly multiplications required to compute convolution. We show that the proposed method computes convolution output with lower latency than the standard spatial convolution method and can be applied with arbitrary kernels. We also show that the speed-up provided by our approach increases with the size of the image or kernel. Through the usage of SATs and box filters, we reduce the number of expensive multiplication operations required in convolution by 20%-52% and latency by 15%-89%.