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.

[Tom-Finke]

Key difference to (openfhe-)numpy: Julia arrays are column-major, thus the algorithm as proposed in https://eprint.iacr.org/2018/1041 cannot be directly applied to SecureMatrices. Transposition before and after applying the algorithm could solves this but introduces additional overhead.

[sloede]

thus the algorithm as proposed in https://eprint.iacr.org/2018/1041 cannot be directly applied to SecureMatrices.

Are you sure? Given that the underlying implementation relies on 1D vector-like data structures, I am surprised to hear that the algorithm needs changes.

[Tom-Finke]

• Key feature: Matrix x Vector --> We must support whichever algorithm is most efficient at supporting this operation
• We want to support both encrypted and plain matrix
• Custom Struct / Type for "encrypted matrix for multiplication", i.e. diagonal order. It does not have to support (efficient) rotations, but efficient multiplication
• Transformation between the encrypted types is not a priority, as its cost is probably prohibitive

[Tom-Finke]

thus the algorithm as proposed in https://eprint.iacr.org/2018/1041 cannot be directly applied to SecureMatrices.

Are you sure? Given that the underlying implementation relies on 1D vector-like data structures, I am surprised to hear that the algorithm needs changes.

If ct.A and ct.B encode matrices $A$ and $B$ in column order, then ct.A and ct.B also encode $A^T$ and $B^T$ in row order.
If ct.C encodes $(A \times B)^T$ in row order, then ct.C also encodes $ A \times B$ in column order.
Since $(A \times B)^T = B^T \times A^T$, we can simply swap the roles of $A$ and $B$ to use the algorithm on column-order matrices and get the correct result back, in column order.