0
$\begingroup$

In Cryptanalysing variants of_Stickel's key agreement_scheme original attack against Stikel's key agreement and of some variants are presented.

The method is to find matrices $X$,$Y$ such that $XA=AX$, $YB=BY$ and $U=XWY$ and perform algebraic manipulations to get a system of linear equations that allows to recover the shared secret.

The original Stikel's key exchange is similar in concept to the ordinary Diffie-Hellman key agreement, in particular the operation to get the intermediate value of Alice or Bob the following expressions are used:

$A,B,W\in GL(n,q)$

$AB\neq BA$

$U=A^lWB^m$

From these done both by Alice and Bob a common secret can be agreed, $l,m\in\mathbb{N}$ are the private key of Alice, similarly for Bob.

The method to break this scheme is to find matrices $X$,$Y$ such that $XA=AX$, $YB=BY$ and $U=XWY$ and perform algebraic manipulations to get a system of linear equations that allows to recover the shared secret.

In particular $X^{-1}$ is used to get rid of the multivariate equations in $U=XWY$, not solvable by Gaussian elimination, so $U=XWY$ is transformed into $X^{-1}U=WY$, which is now solvable by Gaussian elimination as there's no product of matrices as unknowns.

The proposed variant is similar but changing the intermediate value, $U$ or $V$:

$A,B,W\in GL(n,q)$

$AB\neq BA$

$U=A^lWB^m+A^pWB^q$

From this equations a key agreement is done almost the same way, $l,m,p,q\in \mathbb{N}$ are the private key of Alice, similarly for Bob.

The question is there's no necessarily a $U=XWY$ for this construction. We can try to find $U=X_1WY_1+X_2WY_2$, but not as a system of linear equations as the inverse of $X_1$ trick does not work since the second term of the addition remains a product of two unknown matrices, so not solvable as a linear system.

So the question is if being $U=A_1WB_1+A_2WB_2$, how many, if any, solutions in the form $U=XWY$ there are and if any if it's cryptographycaly relevant or a side case which can be considered irrelevant. $X$, $A_1$ and $A_2$ commute pairwise the same as $Y$, $B_1$ and $B_2$.

$\endgroup$

1 Answer 1

0
$\begingroup$

First we must ensure $U$ is in $GL(p,q)$. Then just try to solve the overdetermined system of equations $X_1A=AX_1$, $YB=BY$ and $X_1U=WY$. If the system of equations is inconsistent there's no solution of the form $U=XWY$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.