Geodesic
Cryptanalysis of Ushakov--Shpilrain's authentication protocol based on the twisted conjugacy problem
Prikladnaâ diskretnaâ matematika, no. 2 (2015), pp. 46-53

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: cryptography, authentication, twisted conjugacy, truncated polynomials.
Mots-clés : endomorphism 
@article{PDM_2015_2_a4,
     author = {M. N. Gornova and E. G. Kukina and V. A. Romankov},
     title = {Cryptanalysis of  {Ushakov--Shpilrain's} authentication protocol based on the twisted conjugacy problem},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {46--53},
     publisher = {mathdoc},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2015_2_a4/}
}
TY  - JOUR
AU  - M. N. Gornova
AU  - E. G. Kukina
AU  - V. A. Romankov
TI  - Cryptanalysis of  Ushakov--Shpilrain's authentication protocol based on the twisted conjugacy problem
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2015
SP  - 46
EP  - 53
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2015_2_a4/
LA  - ru
ID  - PDM_2015_2_a4
ER  - 
%0 Journal Article
%A M. N. Gornova
%A E. G. Kukina
%A V. A. Romankov
%T Cryptanalysis of  Ushakov--Shpilrain's authentication protocol based on the twisted conjugacy problem
%J Prikladnaâ diskretnaâ matematika
%D 2015
%P 46-53
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2015_2_a4/
%G ru
%F PDM_2015_2_a4
M. N. Gornova; E. G. Kukina; V. A. Romankov. Cryptanalysis of  Ushakov--Shpilrain's authentication protocol based on the twisted conjugacy problem. Prikladnaâ diskretnaâ matematika, no. 2 (2015), pp. 46-53. http://geodesic.mathdoc.fr/item/PDM_2015_2_a4/