Cryptanalysis of Ushakov–Shpilrain's authentication protocol based on the twisted conjugacy problem

We give a cryptanalysis of Ushakov–Shpilrain's authentication protocol based on the twisted conjugacy problem for a pair of endomorphisms on the semigroup of all $2\times2$ matrices over the ring of truncated one-variable polynomials over the field $\mathbb F_2$. It is shown that the private key of the protocol can be computed by solving the system of linear equations over $\mathbb F_2$. We present a theoretical estimation for the complexity of this cryptanalysis and describe practical results obtained in a computer experiment. It is shown that the protocol is theoretically and practically vulnerable.