# Security analysis of a matrix multiplication protocol

Suppose Alice would like to obtain the product of two $m\times m$ matrices i.e. $A$ and $B.$ Alice has $A,$ whereas Bob has $B.$

Since Alice does not want to reveal $A$ to Bob, she chooses a $m\times m$ random invertible matrix $R.$ She sends $RA$ to Bob over a secure channel.

Bob obtains $RA,$ and calculates $RAB,$ and sends it to Alice over a secure channel.

Alice obtains $AB$ by inverting $R$ i.e. $R^{-1}RAB$.

$R$ is only utilized once.

Any ideas on how to proceed with the security analysis of the above protocol?

Specifically is H(A|RA) = H(A) ?

-
oops sorry about that. – user996522 Mar 7 '12 at 13:04
Relevant: Check out this paper cs.bgu.ac.il/~kobbi/papers/oge_tcc_camera2.pdf and the forward/backward citations. There are existing works on secure multiparty computation, and secure function evaluations. – user2468 Mar 7 '12 at 13:31
What is this supposed to achieve compared to Bob simply sending $B$ to Alice over the secure channel? – Henning Makholm Mar 8 '12 at 0:13
Its a primitive that i need as i have an idea for securely solving a linear equation which depends on the security of this. – user996522 Mar 8 '12 at 0:26
Crossposted to crypto.SE as crypto.stackexchange.com/questions/2023/… – Ilmari Karonen Mar 8 '12 at 9:05

If A is invertible (over a fixed finite field), then this protocol is information-theoretically secure. To see this, first note that, for any $A$, the ciphertext $RA$ is uniformly distributed. Furthermore, the value of $RA$ is independent of $A$. Therefore, for any prior $P$ over messages, we have $\Pr[A|RA] = \Pr[A \wedge RA] / \Pr[RA] = \Pr[A]\Pr[RA] / \Pr[RA] = \Pr[A]$.
@user996522: The key is that R is chosen uniformly at random. By analogy, consider picking a point in $[0,1)$. Let A be an arbitrary point in the interval, and let let R by a uniform random value in $[0,1)$. Then $A+R$ is uniformly random over the interval $[A, A+1)$, and so the fractional part is uniform over $[0,1)$. – Jeremy Hurwitz Jul 3 '12 at 4:53