Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 3 down vote favorite

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)

share|improve this question
2  
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
1  
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$? – Dilip Sarwate Mar 7 '12 at 14:11
Should B also be kept secret from anyone? Alice? Eve? – Henrick Hellström 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. – Dilip Sarwate Mar 7 '12 at 15:45
1  
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$. – Dilip Sarwate Mar 8 '12 at 3:36
show 2 more comments

1 Answer

up vote 1 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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