Cryptanalysis of matrix conjugation schemes

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.

Keywords

• group-based cryptography
• conjugacy search problem
• matrix monoids
• truncated polynomials
• 94a60
• 68w30