Investigate paper "Encrypted Matrix Multiplication Using 3-Dimensional Rotations"

[asraa]

https://eprint.iacr.org/2025/1367.pdf

Authors: Hannah Mahon, Shane Kosieradzki

Abridged Abstract: 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 dxd 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 16x16 matrices on consumer hardware.

Some cool notes to investigate incorporating:

• The work explains the encoding ordering to allow for row, column, and row+column rotations with a single galois automorphism
• We get a ctxt-ctxt matrix multiplication kernel

[j2kun]

I just started reading the paper, so no notes yet, but I noticed they claim in 1.3 that the bicyclic encoding method doesn't support power-of-two cyclotomics, and I think that's not strictly true. All that is required is that the number of slots is sufficiently larger than the product of the matrix dims (I think 2x is enough? I forget exactly what)