2
$\begingroup$

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) ?

  • 0
    Crossposted to crypto.SE as http://crypto.stackexchange.com/questions/2023/security-analysis-of-a-matrix-multiplication-protocol2012-03-08

1 Answers 1

4

If A can be any matrix, then this protocol is not secure. In particular, if RA=0, then Bob can be reasonably confident that A=0 (or at least that A is sparse).

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]$.

  • 0
    @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)$.2012-07-03