# 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 

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?

 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.

• 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. – Cryptonaut Mar 19 '19 at 4:20