Port bicyclic encodings for matrix multiplication

[j2kun]

https://eprint.iacr.org/2024/1762

Homomorphic Matrix Operations under Bicyclic Encoding
Jingwei Chen, Chongqing Institute of Green and Intelligent Technology, CAS
Linhan Yang, Chongqing Jiaotong University
Wenyuan Wu, Chongqing Institute of Green and Intelligent Technology, CAS
Yang Liu, Chongqing Jiaotong University
Yong Feng, Chongqing Institute of Green and Intelligent Technology, CAS

Abstract
Homomorphically encrypted matrix operations are extensively used in various privacy-preserving applications. Consequently, reducing the cost of encrypted matrix operations is a crucial topic on which numerous studies have been conducted. In this paper, we introduce a novel matrix encoding method, named bicyclic encoding, under which we propose two new algorithms BMM-I and BMM-II for encrypted matrix multiplication. BMM-II outperforms the stat-of-the-art algorithms in theory, while BMM-I, combined with the segmented strategy, performs well in practice, particularly for matrices with high dimensions. Another noteworthy advantage of bicyclic encoding is that it allows for transposing an encrypted matrix entirely free. A comprehensive experimental study based on our proof-of-concept implementation shows that each algorithm introduced in this paper has specific scenarios outperforming existing algorithms, achieving speedups ranging from 2x to 38x.