TY - JOUR
T1 - Cryptanalysis of matrix conjugation schemes
AU - Myasnikov, Alex D.
AU - Ushakov, Alexander
PY - 2014/6/1
Y1 - 2014/6/1
N2 - In this paper we cryptanalyze two protocols: the Grigoriev-Shpilrain authentication protocol and a public key cryptosystem due to Wang, Wang, Cao, Okamoto and Shao. Both of these protocols use the computational hardness of some variations of the conjugacy search problem in a class of noncommutative monoids. We devise a practical heuristic algorithm solving those problems. As a conclusion we claim that these protocols are insecure for the proposed parameter values.
AB - In this paper we cryptanalyze two protocols: the Grigoriev-Shpilrain authentication protocol and a public key cryptosystem due to Wang, Wang, Cao, Okamoto and Shao. Both of these protocols use the computational hardness of some variations of the conjugacy search problem in a class of noncommutative monoids. We devise a practical heuristic algorithm solving those problems. As a conclusion we claim that these protocols are insecure for the proposed parameter values.
KW - Group-based cryptography
KW - conjugacy search problem
KW - matrix monoids
KW - truncated polynomials
UR - https://www.scopus.com/pages/publications/84902313788
UR - https://www.scopus.com/pages/publications/84902313788#tab=citedBy
U2 - 10.1515/jmc-2012-0033
DO - 10.1515/jmc-2012-0033
M3 - Article
AN - SCOPUS:84902313788
SN - 1862-2976
VL - 8
SP - 95
EP - 114
JO - Journal of Mathematical Cryptology
JF - Journal of Mathematical Cryptology
IS - 2
ER -