Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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
up vote 5 down vote accepted

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

share|improve this answer
The only way to get M is to break the underlying cipher to get K, and then proceed with 3 matrix equations on 3 unknowns. – daniel Nov 4 '13 at 14:05
@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

Your Answer


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.