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