Welcome to the resource topic for 2023/1649
Title:
A New Framework for Fast Homomorphic Matrix Multiplication
Authors: Xiaopeng Zheng, Hongbo Li, Dingkang Wang
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).
ePrint: https://eprint.iacr.org/2023/1649
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 .