Cryptanalysis of matrix conjugation schemes

Journal of mathematical cryptology

article

Alex D. Myasnikov¹  Alexander Ushakov¹ 

[1] Department of Mathematics, Stevens Institute of Technology

关键词: Group-based cryptography;    conjugacy search problem;    matrix monoids;    truncated polynomials;   

DOI  :  10.1515/jmc-2012-0033

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

Abstract. 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.

【 授权许可】

CC BY|CC BY-NC-ND