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)

  • 2
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Mar 7 '12 at 12:58
  • 1
    $\begingroup$ 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$? $\endgroup$ Mar 7 '12 at 14:11
  • $\begingroup$ Should B also be kept secret from anyone? Alice? Eve? $\endgroup$ Mar 7 '12 at 15:24
  • $\begingroup$ @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. $\endgroup$ Mar 7 '12 at 15:45
  • 1
    $\begingroup$ 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$. $\endgroup$ Mar 8 '12 at 3:36

Why over a secure channel? Wouldn't this work pretty well if you take A and B not invertible also in the presence of an eavesdropper? Then Bob could use a similar trick to get AB by sending BS to Alice (where S is invertible) and then recover AB from ABS that Alice sends back. This seems extremely inefficient though.

In any case, Bob knows quite a lot about A. Row-reducing RA should give the same reduced row-echelon form as A has. The rank of RA is the same as the rank of A and so on.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.