3

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

ccorn
  • 9,803
unterbrause
  • 111
  • Presumably we are to compute $R$, not $K$. Is $T$ public? If not, how do the users get it? – Ross Millikan Oct 31 '13 at 21:06
  • If the user knows $T$, why not compute $T^{-1}$ and then $U_1TT^{-1}TU_2$? – DKal Oct 31 '13 at 21:11
  • What is $T$? A (randomly chosen) shared secret between user1 and user2 or a public constant? – Magdiragdag Oct 31 '13 at 21:20
  • 1
    This reminds me of HDCP. Crosby at al. have done a cryptanalysis. – ccorn Oct 31 '13 at 21:25
  • @Ross: I have suggested edits to resolve the name collisions (in favor of $K$ for the key, renaming the field to $F$) – ccorn Oct 31 '13 at 21:55
  • HDCP uses only vectors per users. Thus, this resembles HDCP sessions with $n$ producers, $n$ consumers in all possible combinations, so $K$ is a matrix of the HDCP session keys for every transmitter-receiver combination, each key being a $56$-bit value. – ccorn Oct 31 '13 at 22:01
  • In HDCP, $F$ is finite (and it's actually just a ring, not a field). In such finite settings, it can well happen that the exchanged matrices do not have full rank. Thus $\operatorname{coker}(U_1\cdot T)\subseteq\operatorname{coker} K$ and $\ker(T\cdot U_2)\subseteq\ker K$. Thus, the protocol leaks information about $K$. In that sense, the protocol cannot be secure. But the question implicitly assumes invertability. Are rank deficiencies allowed or not? – ccorn Oct 31 '13 at 23:10
  • Well I also think that T is a public matrix that has been sent and could be catched up in advance? Could it be cracked if T was unknown? – unterbrause Nov 01 '13 at 20:51
  • 1
    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$. – ccorn Nov 02 '13 at 09:49
  • okay but how to compute it WITHOUT knowing T? – unterbrause Nov 02 '13 at 15:58

0 Answers0