Paper 2025/448

Ciphertext-Ciphertext Matrix Multiplication: Fast for Large Matrices

Abstract

Matrix multiplication of two encrypted matrices (CC-MM) is a key challenge for privacy-preserving machine learning applications. As modern machine learning models focus on scalability, fast CC-MM on large datasets is increasingly in demand. In this work, we present a CC-MM algorithm for large matrices. The algorithm consists of plaintext matrix multiplications (PP-MM) and ciphertext matrix transpose algorithms (C-MT). We propose a fast C-MT algorithm, which is computationally inexpensive compared to PP-MM. By leveraging high-performance BLAS libraries to optimize PP-MM, we implement large-scale CC-MM with substantial performance improvements. Furthermore, we propose lightweight algorithms, significantly reducing the key size from $$ MB to $$ MB for CC-MM with comparable efficiency. In a single-thread implementation, the C-MT algorithm takes $$ seconds to transpose a $$ encrypted matrix. The CC-MM algorithm requires $$ seconds to multiply two $$ encrypted matrices. For large matrices, our algorithm outperforms the state-of-the-art CC-MM method from Jiang-Kim-Lauter-Song [CCS'18] by a factor of over $$.