Let $T \in F^{n \times n}$ , $F$ be a field

Let $U_1, U_2 \in F^{n \times n}$ be randomly chosen by user 1 resp. user 2.

user1 sends $U_1\cdot T$ to user2 , user2 sends $T\cdot U_2$ to user1 .

Both are now able to compute the secret key $K=U_1\cdot T\cdot U_2$ .

Exercise: Compute $K$ in polynomial time (in the size of the matrix ring) or prove that the protocol is secure!

My tries:

Computing the inverse is a polynomial thing, at least in $n$. Gauss elimination does it in $O(n^3)$ But what's the difference to polynomial time "in size of the matrix ring" ?

Well I can not compute $K$ by inverting $U_1\cdot T$ which has $T^{-1}\cdot U_1^{-1}$ as inverse. Then if I combine this one with any $T\cdot U_2$ or $U_2^{-1}\cdot T^{-1}$ I do not get a reasonable result. Well okay I can get

$U_2^{-1}\cdot T^{-1}\cdot U_1\cdot T$ but what does it help?

Does anyone of you see an ansatz? Would you prove the communication here to be secure and how would one do that?


  • $\begingroup$ Presumably we are to compute $R$, not $K$. Is $T$ public? If not, how do the users get it? $\endgroup$ – Ross Millikan Oct 31 '13 at 21:06
  • $\begingroup$ If the user knows $T$, why not compute $T^{-1}$ and then $U_1*T*T^{-1}*T*U_2$? $\endgroup$ – DKal Oct 31 '13 at 21:11
  • $\begingroup$ What is $T$? A (randomly chosen) shared secret between user1 and user2 or a public constant? $\endgroup$ – Magdiragdag Oct 31 '13 at 21:20
  • 1
    $\begingroup$ This reminds me of HDCP. Crosby at al. have done a cryptanalysis. $\endgroup$ – ccorn Oct 31 '13 at 21:25
  • 1
    $\begingroup$ If $T$ were public, $K$ could be computed as noted in @DKal's comment. Therefore I suppose that $T$ is not known to the eavesdropper. In the context of this question however $T$ is a secret shared between user$_1$ and user$_2$. $\endgroup$ – ccorn Nov 2 '13 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.