Paper 2024/1762
Homomorphic Matrix Operations under Bicyclic Encoding
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.
Metadata
- Available format(s)
- Category
- Applications
- Publication info
- Published elsewhere. Minor revision. IEEE Transactions on Information Forensics and Security
- Keywords
- Secure matrix multiplicationfully homomorphic encryptionSIMDbicyclic encoding
- Contact author(s)
-
chenjingwei @ cigit ac cn
linhanyang @ mails cqjtu edu cn
wuwenyuan @ cigit ac cn
liuyang13 @ cqjtu edu cn
yongfeng @ cigit ac cn - History
- 2024-10-30: approved
- 2024-10-29: received
- See all versions
- Short URL
- https://ia.cr/2024/1762
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2024/1762, author = {Jingwei Chen and Linhan Yang and Wenyuan Wu and Yang Liu and Yong Feng}, title = {Homomorphic Matrix Operations under Bicyclic Encoding}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1762}, year = {2024}, url = {https://eprint.iacr.org/2024/1762} }