# Matrix key exchange

Given is a square matrix $M$ over a field $F$, we have a key exchange with the following conditions:

1. Person $X$ sends a message to Person $Y$: $C_{1}=AM$, where $A$ is a randomly chosen square matrix.
2. Person $Y$ sends a message to Person $X$: $C_{2}=MB$, where $B$ is a randomly chosen square matrix.
3. Both can compute the secret key $K=AMB$.

The question is how to find $K$ in polynomial time in the size of the matrix ring without knowing $M$, or alternatively to prove the security of the given protocol.

Can anybody help me with this problem? I am really stuck with it and don't see a way to solve it.

-
Is $M$ reused across multiple executions of the protocol? If yes, is the adversary assumed to know $K$ from previous iterations of the protocol? – fgrieu Nov 4 '13 at 11:22

One observation is that if we modify the problem so that $M, A, B$ are random invertible matrices, then it is easy to prove the security of the system. In fact, we can prove that the system is informationally secure; that is, for any observed $C_1, C_2$ pair, for any possible value of $K$, there is a unique set of values of $A, B, M$ that yield that $K$ (and hence the attacker gains no information from the $C_1, C_2$ pair about which values of $K$ are more likely). Of course, if that specific value of $M$ is reused in any other context, you lose this informational security.
Now, the original problem is about random matricies selected without regard to their invertibility. I'll leave this for you to solve: if $M, A$ or $B$ are noninvertable, to what extent can the attacker exploit that to recover $K$ (or, rather, limit the possible values that $K$ might be able to take on)?
@daniel: actually, the question asked if we can recover $K$, not $M$. In any case, it is possible (albeit unlikely) to recover $K$ just from $C_1, C_2$; consider the case that the random matrix $A$ just happened to be the all-zero matrix. – poncho Nov 4 '13 at 14:23