Welcome to the resource topic for 2025/1367
Title:
Encrypted Matrix Multiplication Using 3-Dimensional Rotations
Authors: Hannah Mahon, Shane Kosieradzki
Abstract:Fully homomorphic encryption (FHE) enables computations over encrypted data without the need for decryption. Recently there has been an increased interest in developing FHE based algorithms to facilitate encrypted matrix multiplication (EMM) due to rising data security concerns surrounding cyber-physical systems, sensor processing, blockchain, and machine learning. Presently, FHE operations have a high computational overhead, resulting in an increased need for low operational complexity algorithms to compensate. We present a novel matrix encoding and EMM algorithm for power-of-2 cyclotomic based rings, utilizing three-dimensional rotations which offer improvements over the one-dimensional rotations used in previous work. We encode each d \times d matrix as a single, batch-encoded, ciphertext, with minimum ciphertext size d^3. The proposed algorithm improves the number of plaintext-ciphertext multiplications from O(d) to O(1) and the number of rotations from O(d) to O(\log_2{d}). In addition, our work supports rectangular matrix multiplication and matrix packing without incurring additional operations per execution. Benchmarks were obtained with a Microsoft SEAL implementation and compared against leading EMM algorithm, with our work performing 4 times faster for 16 \times 16 matrices on consumer hardware. Our algorithm is compatible with existing encrypted machine learning frameworks and can be a drop-in replacement for existing matrix multiplication algorithms for increased speed. The favorable time complexity is well suited for time sensitive encrypted algorithms such as computer vision, controls, and patient health monitoring.
ePrint: https://eprint.iacr.org/2025/1367
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 .