Given two players $P_1 , P_2$ . In our setting $P_1$ poses two encrypted matrices $M_{1_{k \times k}},M_{2_{k \times k}}$ over field $F$, and the encryption has additive homomorphic property, over public-key scheme. Where $P_2$ posses the private key to that encryption.
We can compute the matrix multiplication via a basic naive approach, as follow:
for each cell of the desire matrix , we compute a multiplication of row vector from $M_a$ and a column vector from $M_b$.
To compute that vector multiplication The players can do the following 2-step protocol :
First, Given $Enc(a_{1i})$ , $Enc(b_{i1})$, player 1 can obtain : $Enc(a_{1i} \cdot b_{i1})$ via a folklore protocol [1]
Next, to compute the addition of the k-parts of that vector using homomorphic properties as follow:
$Enc(\sum_{k}^{i=1} a_{1i}b_{i1}) = \prod Enc(a_{1i}b_{i1})$
That solution give us a complexity of $O(k^3)$ and communication cost of $O(k^2)$, while matrix multiplication (in the plain text version) can be reduce down to ~$O(k^{2.38})$.
My question: Can we also do it better(in term of computation complexity) over the encrypted version of that problem?
[1] folklore protocol for scalar multiplication
(i) $P_1$ chooses a random vectors $r_a , r_b \in_{R} \mathbb{F}$ and compute $Enc(r_b) , Enc(r_b)$, then continue to compute and send the values: $Enc(a) \cdot Enc(r_a) =Enc(a+r_a)$ and $Enc(b) \cdot Enc(r_b) =Enc(b+r_b)$. (ii) $P_2$ decipher the values $a+r_a$ and $b+r_b$ and compute $Enc((a+r_a)(b+r_b))$ then sent it to $P_1$. (iii) $P_1$ receive the above value, and can compute $Enc((a+r_a)(b+r_b) - a\cdot r_b - b\cdot r_a - r_a \cdot r_b)= Enc(ab)$ by using the homomorphic properties of that public encryption scheme.
