Date Added: Dec 2012
The conjugacy search problem plays a special role in group-based cryptography. Most of the cryptosystems based on groups use one or another variation of that problem. For instance: employs conjugacy search problem in braid groups, employ simultaneous conjugacy search problem in braid groups, employs twisted conjugacy problem, employ decomposition problem in different (semi-)groups, employs conjugation and exponentiation in matrix groups. In this paper, the authors cryptanalyze two protocols: Grigoriev-Shpilrain authentication protocol and Wang et al. public key encryption protocols that use computational hardness of some variations of the conjugacy search problem in non-commutative monoids. They devise a practical heuristic algorithm solving those problems. As a conclusion they claim that, these protocols are insecure for the proposed parameter values.