New algorithms for fully homomorphic matrix addition and multiplication
Küçük Resim Yok
Tarih
2025
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Springer
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
New algorithms are introduced for embedding matrices with integer or fixed-point real number entries into plaintexts and for performing matrix addition and multiplication on encrypted matrices. The encryption algorithms used for this purpose are fully homomorphic, such as BGV, BFV, and CKKS. These algorithms have the property of performing SIMD style parallel operations on plaintext values encrypted into a single ciphertext vector by a technique called ciphertext packing using the Chinese Remainder Theorem. This concept was introduced by Halevi and Shoup, and algorithms for homomorphic matrix operations were further improved by Jiang et al. (JKLS). Our algorithms improve both Halevi and Shoup and JKLS algorithms in terms of arithmetic and data rotation complexity. The proposed algorithms are designed on top of the BFV fully homomorphic encryption scheme. We describe our algorithms in detail step by step in this article, providing numerical examples in Appendix A. Experimental results demonstrate that our matrix multiplication algorithm achieves superior efficiency in terms of running time compared to JKLS algorithm. Real-world applications of FHE-based matrix computations often require matrix dimensions in the hundreds of thousands. Given typical FHE parameter settings (polynomial degree N=213\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N = 2<^>{13}$$\end{document}, plaintext modulus t=65537\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t = 65537$$\end{document}), the total number of arithmetic and data-rotation operations can easily reach the order of 1012\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$10<^>{12}$$\end{document}. This scale necessitates state-of-the-art high-performance computing practices.
Açıklama
Anahtar Kelimeler
Matrix Addition And Multiplication, Homomorphic Encryption
Kaynak
Journal of Supercomputing
WoS Q Değeri
Q2
Scopus Q Değeri
Q1
Cilt
81
Sayı
16
