Paper 2024/1762

Homomorphic Matrix Operations under Bicyclic Encoding

Jingwei Chen, Chongqing Institute of Green and Intelligent Technology, CAS
Linhan Yang, Chongqing Jiaotong University
Wenyuan Wu, Chongqing Institute of Green and Intelligent Technology, CAS
Yang Liu, Chongqing Jiaotong University
Yong Feng, Chongqing Institute of Green and Intelligent Technology, CAS
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)
PDF
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
Creative Commons Attribution-NonCommercial
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.