Secure matrix multiplication support

[ameligrana]

Hi! Incredible library. I would like to ask if implementing secure matrix multiplication is on the schedule? I could also give it a stub if I don't have misconceptions. I think that it could be implemented by using the already implemented operators. But I'm not sure if a more performant and numerically stable version could be also made. I'm a beginner in HE so I could easily be very wrong :D

[sloede]

You are referring to linear algebra operations such as matrix-matrix and matrix-vector multiplication, do I understand you correctly? Because element-wise matrix multiplication and matrix-scalar multiplication are already supported in SecureArithmetic.jl.

At the moment we do not have any plans to add matrix-matrix or matrix-vector multiplication, but I know @ArseniyKholod had at least briefly looked at it in the past. Also know that there are some linear algebra operations supported by OpenFHE, e.g., inner product of two vectors. Thus it would probably make sense to first check if OpenFHE has native support for some of the operations (or at least their building blocks) you'd like to implement, and then add them to OpenFHE.jl first.

Having said all that, we'd be happy to see some external contributions. We're also happy to guide you through the process of supporting more of OpenFHE's functionality in OpenFHE.jl and subsequently in SecureArithmetic.jl 😊

[ArseniyKholod]

Following the link below, you can find a comment of one of the OpenFHE developers, that OpenFHE has in plans to release matrix arithmetic, including for example matrix vector multiplication. You can also find there some links to paper, describing the corresponding algorithms.

I am not sure, that the naive approach of for example matrix vector multiplication, that can be implemented with already supproted operations will be efficient enough, but I would be happy to see some implementational ideas!😄.

From OpenFHE discourse:
https://openfhe.discourse.group/t/is-there-a-built-in-method-to-perform-vector-matrix-multiplication/358/2?u=arseniy

[Tom-Finke]

The mentioned matrix arithmetic has since been released in the form of the openfhe-numpy
python library.
The exposed matrix operations include Matrix-Vector Multiplication and Square Matrix Multiplication.
Documented here and implemented here and here.

The implementation is based on https://eprint.iacr.org/2018/1041 and has complexity $O(d)$ with 1 cyphertext-cyphertext Multiplication and 2 scalar-cyphertext multiplications.

Since they implemented this in C++ in openfhe-numpy and not in openfhe-development directly, I suppose this is not coming to OpenFHE natively.