# Complexity of computing homomorphic encrypted matrix multiplication

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 pubic encryption scheme.

• How does this give a communication of $O(k^2)$? To me it gives a communication of $O(k^3)$, as $P_1$ and $P_2$ will have to perform $k$ scalar multiplication protocols for each entry in $P_1$'s matrix. – Geoffroy Couteau Jan 4 '17 at 11:40
• We can reduce the cost by send all the $2 * K^2$ elements at once, and then use them at demand. -Another note about the rounds: I found that it's can be reduced to 2 rounds, later i will write down how. – user1387682 Jan 6 '17 at 16:19
• Right, and what do you want to optimize? Computation? Communication? – Geoffroy Couteau Jan 7 '17 at 13:17
• Computation complexity – user1387682 Jan 7 '17 at 15:54
• The folklore protocol (iacr.org/archive/tcc2007/43920291/43920291.pdf) that you describe can be used a little simpler. To multiply Enc(A) and Enc(B), P1 chooses $R_A$ and $R_B$ and sends Enc(A + $R_A$) and Enc(B + $R_B$) to P2. The rest of the protocol is as you described just with the vectors being replaced by matrices. – ZeroKnowledge Mar 19 at 4:20