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 - http://www.scopus.com/inward/record.url?scp=84902313788&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84902313788&partnerID=8YFLogxK
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 -