Paper 2024/883 Original: eprint.iacr.org/2024/883 ↗

Low-Latency Linear Transformations with Small Key Transmission for Private Neural Network on Homomorphic Encryption

Abstract

As Machine Learning as a Service expands, protecting client data has become a critical challenge. Homomorphic Encryption (HE) enables computation on encrypted data, but practical HE-based AI still suffers from high latency and large key sizes. Among neural network operations, convolution remains a central target for optimization, as it is fundamental to CNNs and increasingly used in transformers and state-space models. To realize HE convolution, various packing strategies—defining the data layout within a ciphertext—have been introduced, leading to state-of-the-art methods such as multiplexed parallel convolution (MPConv), which is implemented with multiplexed parallel packing. In this paper, we propose Rotation-Optimized Multiplexed Parallel Convolution (RO-MPConv), which enhances usability by reducing the number of rotation operations and rotation keys—major contributors to latency and key sizes in MPConv. Additionally, we introduce a small-level key system to further decrease key sizes and a parallel baby-step giant-step matrix-vector multiplication, which reduces rotations for packing strategies with multiple identical data entries, including multiplexed parallel packing. Experimental results demonstrate that RO-MPConv achieves up to an 81% reduction in convolution latency compared to MPConv. For key transmission, combining RO-MPConv with the hierarchical rotation key system and our small-level key system achieves a 29× reduction in rotation key size compared to MPConv. Furthermore, integrating RO-MPConv into existing state-of-the-art models reduces their total latency by up to 26%, and our proposed matrix-vector multiplication method reduces latency by 69%. Our code is fully available from https://github.com/byeongseomin51/RO-MPConv.git.