Matrix computation

Hello, I was able to implement matrix multiplication and make it work, but now I want to grab elements from that matrix to make a new matrix. Is this possible? for example if I could just grab every other element and make a matrix now n/2 x n/2? or take the first element of other matrices and make a matrix out of them? Is this something that has been done? can someone point me in the right direction. I am just unsure how to grab elements in this manner. Thanks.

I think the most straightforward way to achieve what you want is by using masking. You multiply (point-wise multiplication) your input matrix by a selector mask matrix that includes ones at the specific positions (indices) in your input matrix that you want to retain, and zeros elsewhere. The resultant matrix will contain the coefficients you are interested in.

You might need to do some rotations to remove the bubbles created due to masking.

this new matrix would still be the same size as the original correct? This sounds like what I did. I used a mask that multiplies all the nonimportant elements by zero so only the ones I need are left. I could do this but i have a 64x64 matrix where I just want to reduce it to a 8x8 or even 4x4 to improve the performance on. If I misunderstood what you suggest then im sorry.

Please describe how you pack the elements in the matrix inside the ciphertext and what method you use for matrix multiplication. If you pack the rows/columns/diagonals/whole matrix in a ciphertext, then regardless of whether the matrix is 64x64 or 8x8, the ciphertext will still pack N slots, where N is the ring dimension.

I assume that when you say you want to improve the performance, this is related to the number of operations you need to perform for the matrix multiplication, i.e., to be dependent on n/2 instead of n? Depending on the matrix multiplication method you are using, you just need to ensure that the elements of an n/2 x n/2 matrix are packed in the right way in order to use a matrix multiplication procedure for size n/2 instead of n. This might mean not only multiplicative masking, but also rotations to achieve repetitions.

Thank you. I followed https://eprint.iacr.org/2018/1041.pdf for matrix multiplication. And I wasnt considering this (my mistake) but I think you are right on the packing. It will be N slots regardless. I just notice larger matrices such as 64x64 take longer to multiply than say a 4x4 but this is most likely due to the number of rotations? I would like a little explanation here to make sure I am on the right track. But for now I could use masking to get rid of the elements I dont want and then I could move the remaining elements together (i.e. the first n/2 x n/2 elements and the rest zero) but I would have to be careful how I multiply to reduce the costs?

For a matrix n x n, you will do O(n) homomorphic multiplications, additions and rotations (or O(sqrt{n} rotations if optimized). So for a n/2 x n/2, the complexity should be O(n/2). But if you zero out the elements to get a matrix that is n/2 x n/2 but use the multiplication algorithm for size n, then the complexity will be the same as for the n x n matrix. You should use masking (and potential rotations) to obtain the appropriate encoding for your n/2 x n/2 extracted matrix so that you can use the matrix multiplication algorithm for size n/2.

I am trying this and it seems to be working. I will have to better see how to make the masking work. A related question: I am having difficulty scaling up to matrix sizes 16x16 and bigger (want to try a 32x32) but getting a killed error. I know there is scaleModSize, firstModSize, depth, etc which I am tweaking to try to make work but not able to. Is there other things to try? I know there are many more things to try.

I cannot say for sure, but if you just get a “killed” message, you might be running out of memory. Make sure you do not generate more rotation keys and ciphertexts than necessary, and try to first run it using a small (insecure) ring dimension to test the functionality.