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

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