Paper 2025/1957

Fast Batch Matrix Multiplication in Ciphertexts

Abstract

Encrypted matrix multiplication (MM) is a fundamental primitive in privacy-preserving machine learning and encrypted data search, but it remains a significant performance bottleneck. Recently, Bae et al.~(Crypto’24) and Park~(Eurocrypt’25) introduced novel algorithms for ciphertext–plaintext (CPMM) and ciphertext–ciphertext (CCMM) matrix multiplications. These algorithms reduce encrypted MM operations to plaintext matrix multiplications (PPMM), enabling implementation through highly optimized BLAS libraries. While these reduction-based methods offer significant improvements, their benefit is limited to scenarios where the matrix dimension $d$ is comparable to the ring dimension $N$ in RLWE-based CKKS schemes. As a result, they fall short for matrix multiplications involving small or medium-sized matrices. We extend the reduction-based CPMM/CCMM into small-sized matrix operations by batching instances. We encode a batch of matrices into a single matrix over algebraic integers, where each entry is obtained by applying the inverse Discrete Fourier Transform to the batch matrix entries at the same position. This encoding enables reductions of encrypted batch MM algorithms to a small number of batch PPMMs, which can be efficiently accelerated by BLAS libraries. Our batch encrypted MM flexibly accommodates diverse matrix dimensions and batch sizes independent of the ring dimension $N$, thereby extending its applicability to practical real-world settings. For two $d \times d$ matrices with $N/d$ batches, our batch CPMM and CCMM algorithms achieve $O(d^2N)$ cost, improving over Bae et al.'s $O(dN^2)$ and Jiang et al.'s $O(d^2N\log N)$~(CCS'18). We further extend our techniques to rectangular matrices, achieving $O(dN^2)$ for multiplying a $d \times N$ matrix by an $N \times N$ matrix, improving previous $O(N^3)$ methods. A proof-of-concept implementation validates these improvements: multiplying 128 batches of $64 \times 64$ matrices takes $0.20$s (CPMM) and $1.08$s (CCMM), yielding $240\times$ and $52\times$ speedups over previous methods. For a $64 \times 2048$ by $2048 \times 2048$ multiplication, our CCMM completes in $7.5$s, achieving a $29\times$ speedup compared to Park's algorithm.