# Security analysis of a matrix multiplication protocol

Suppose Alice would like to obtain the product of two mXm 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 mXm random invertable matrix R. She sends R*A to Bob over a secure channel.

Bob obtains R*A, and calculates R*A*B, and sends it to Alice over a secure channel.

Alice obtains A*B by inverting R i.e. (R^-1)*R*A*B.

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)

• You should define the set of elements of the matrix. If it is not finite, you should also define what "a random invertable matrix" is. Also the statement has issues with the size of the matrices when $m\ne n$; e.g $R\cdot A$ does not compute.
– fgrieu
Mar 7 '12 at 12:58
• Not only does $R\cdot A$ not compute, but what Alice desires, the product $A\cdot B$, does not compute either since $A$ and $B$ are $m\times n$ matrices, unless we assume $m=n$ to fix these niggling problems. Once they are fixed, Eve hears $R\cdot A = X$ and $R\cdot A\cdot B = X\cdot B$ going over the "secure" channels which gives her $n^2$ linear equations for the $n^2$ entries in $B$. Can these equations be solved for $B$? Mar 7 '12 at 14:11
• Should B also be kept secret from anyone? Alice? Eve? Mar 7 '12 at 15:24
• @HenrickHellström Good question. Once Alice recovers $A\cdot B$ from Bob's transmission, she too gets $n^2$ linear equations for the $n^2$ entries in $B$, and might be able to solve them for $B$. Poor Bob! His generosity in returning $R\cdot A\cdot B$ to Alice might reveal his $B$. He might as well just send $B$ directly to Alice (and to Eve) to do what they please with it. Mar 7 '12 at 15:45
• The revised protocol is asymetric in that there is a good chance that Alice will be able to determine $B$ from $A$ and $AB$ -- in fact, if $A$ is invertible, recovery of $B$ is guaranteed -- while Bob is considerably in the dark as far as knowledge of $A$ is concerned. If Bob is unconcerned about Alice knowing $B$, the entire protocol can be simplified to Bob simply sending $B$ to Alice over the secure channel, thus saving half the transmission cost as well as all his computational cost, and most of Alice's too since she does not need to invert $R$, and $R\cdot A$ is replaced by $A\cdot B$. Mar 8 '12 at 3:36