Suppose Alice would like to obtain the product of two mXm matrices i.e. A and B.

Question

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)

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.