Welcome to the resource topic for 2025/1425
Title:
Lodia: Towards Optimal Sparse Matrix-Vector Multiplication for Batched Fully Homomorphic Encryption
Authors: Jiping Yu, Kun Chen, Xiaoyu Fan, Yunyi Chen, Xiaowei Zhu, Wenguang Chen
Abstract:Encrypted matrix-vector multiplication is a fundamental component of a variety of applications that involve data privacy concerns. Current algorithms utilizing fully homomorphic encryption (FHE) generally use batching to enhance computational efficiency while neglecting the sparsity of the matrices, a characteristic that exists naturally in many practical situations. Alternatively, porting plaintext algorithms that address sparsity may fail to utilize batching and introduce additional privacy concerns.
We propose Lodia, an efficient outsourced SpMV algorithm for batched FHE schemes without sacrificing privacy. It only requires \Theta((n+m)\log(n+m)/s) FHE operations, where n is the number of rows/columns, m is the number of non-zero elements of the matrix, and s is the batch size of the FHE scheme. This is optimal for m=\Omega(n) and m=O(n^\rho) for some \rho<2 (i.e., an \le m \le bn^\rho asymptotically), covering most practical cases. To our knowledge, no method has been published with better than \Theta(n^2/s) FHE operations, suitable for any sparse matrix, and without privacy concerns.
Lodia utilizes a novel low-diagonal decomposition, which decomposes a sparse matrix into a series of special matrices named low-diagonal matrices. Based on a conventional method encoding the matrix in diagonal order, each low-diagonal matrix can be efficiently multiplied by a vector. This results in an efficient SpMV method suitable for any sparse matrix. Experiments show that Lodia practically achieves a speedup of up to 96\times compared to baselines that ignore matrix sparsity, and up to 3.6\times compared to implementations even with fewer security guarantees. This is the first SpMV solution on encrypted data that can process a substantial matrix with over 8 million rows/columns and 125 million non-zero elements.
ePrint: https://eprint.iacr.org/2025/1425
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .