New algorithms for fully homomorphic matrix addition and multiplication
摘要
New algorithms are introduced for embedding matrices with integer or fixed-point real number entries into plaintexts and for performing matrix addition and multiplication on encrypted matrices. The encryption algorithms used for this purpose are fully homomorphic, such as BGV, BFV, and CKKS. These algorithms have the property of performing SIMD style parallel operations on plaintext values encrypted into a single ciphertext vector by a technique called “ciphertext packing” using the Chinese Remainder Theorem. This concept was introduced by Halevi and Shoup, and algorithms for homomorphic matrix operations were further improved by Jiang et al. (JKLS). Our algorithms improve both Halevi and Shoup and JKLS algorithms in terms of arithmetic and data rotation complexity. The proposed algorithms are designed on top of the BFV fully homomorphic encryption scheme. We describe our algorithms in detail step by step in this article, providing numerical examples in Appendix A. Experimental results demonstrate that our matrix multiplication algorithm achieves superior efficiency in terms of running time compared to JKLS algorithm. Real-world applications of FHE-based matrix computations often require matrix dimensions in the hundreds of thousands. Given typical FHE parameter settings (polynomial degree