Encrypted Matrix Multiplication Using 3-Dimensional Rotations w/ Shane Kosieradzki and Hannah Mahon
#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.
#About the Speaker
Shane Kosieradzki is a Cryptographic Engineer at Crypto Asset Technology Labs, specializing in the development of Fully Homomorphic Encryption technology. In his current role he is working to develop next generation crypto-currency tools to empower law enforcement and government agencies to tackle the rising threat posed by digital assets.
Hannah Mahon is a Research Scientist at the Georgia Tech Research Institute. Her research interests include algebraic geometry, fully homomorphic encryption, and formal verification of software and hardware.
#More Information
Want more information, recordings of the presentations, slides, and other resources from the meetup? Visit this meetup's resource page at https://fhe.org/meetups/079
#Never Miss an Update
The newsletter where we post community announcements: https://fheorg.substack.com/
The discord server where you can discuss FHE related topics with the community: https://discord.fhe.org
Make sure to join either (or both) of these to stay informed about future events!