ComplexMM: Efficient and Generic Homomorphic Matrix Multiplication via Complexification and BSGS Alignment

Fully homomorphic encryption (FHE) enables computation directly over encrypted data without decryption, offering a promising approach to privacy-preserving outsourcing computation in cloud environment. However, its high computational cost, especially for some fundamental operations such as matrix multiplication, remains a major obstacle to practical deployment. Although several homomorphic matrix multiplication schemes have been proposed for acceleration, they still suffer from excessive and costly multiplication and rotation operations. In this work, we propose an efficient and generic homomorphic matrix multiplication scheme using the matrix complexification technique and the Baby-Step Giant-Step (BSGS) strategy. Matrix complexification halving the number of multiplications by mapping matrix elements into complex numbers, allowing each homomorphic complex multiplication to process two products simultaneously. Separately, BSGS halving the number of rotation in alignment phase through a hierarchical rotation scheme involving fine-grained pre-rotations followed by coarse-grained main rotations. We implement our approach using the HEaaN library and evaluate it across a range of matrix dimensions. Results show a 34%-68% runtime reduction over prior state-of-the-art methods. Our method advances the efficiency and scalability of encrypted matrix computation, making FHE more viable for real-world applications.