Paper 2023/1649

A New Framework for Fast Homomorphic Matrix Multiplication

Xiaopeng Zheng, School of Mathematical Sciences, University of Chinese Academy of Sciences, KLMM, Academy of Mathematics and Systems Science, Chinese Academy of Sciences
Hongbo Li, School of Mathematical Sciences, University of Chinese Academy of Sciences, KLMM, Academy of Mathematics and Systems Science, Chinese Academy of Sciences
Dingkang Wang, School of Mathematical Sciences, University of Chinese Academy of Sciences, KLMM, Academy of Mathematics and Systems Science, Chinese Academy of Sciences
Abstract

Homomorphic Encryption (HE) is one of the mainstream cryptographic tools used to enable secure outsourced computation. A typical task is secure matrix computation. Popular HE schemes are all based on the problem of Ring Learning with Errors (RLWE), where the messages are encrypted in a ring. In general, the ring dimension should be large to ensure security, which is often larger than the matrix size. Hence, exploiting the ring structure to make fast homomorphic matrix computation has been an important topic in HE. In this paper, we present a new framework for encoding a matrix and performing multiplication on encrypted matrices. The new framework requires fewer basic homomorphic operations for matrix multiplication. Suppose that the ring dimension is $n$ and the matrix size is $d\times d$ with $d= n^{\rho}$. (1) In the compact case where $\rho \leq \frac{1}{3}$, the multiplication of two encrypted matrices requires $\tilde{O}(1)$ basic homomorphic operations, which include plaintext-ciphertext multiplications, ciphertext-ciphertext multiplications, and homomorphic Galois automorphisms. (2) In the large sized case where $\rho> \frac{1}{3}$, our new method requires $O\big(d^{(1 - \frac{1}{3\rho})\cdot \log_2 7 }\big)$ basic homomorphic operations, which is better than all existing methods. In addition, the new framework reduces the communication cost, since it requires fewer key-switching keys. The number of key-switching keys is reduced from $O(d)$ to $O(\log d)$.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint.
Keywords
Homomorphic EncryptionSecure Outsourced Matrix MultiplicationTensor RingLattice Basis and Dual Basis
Contact author(s)
zhengxiaopeng @ amss ac cn
hli @ mmrc iss ac cn
dwang @ mmrc iss ac cn
History
2023-10-26: approved
2023-10-25: received
See all versions
Short URL
https://ia.cr/2023/1649
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1649,
      author = {Xiaopeng Zheng and Hongbo Li and Dingkang Wang},
      title = {A New Framework for Fast Homomorphic Matrix Multiplication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1649},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1649}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.