Cryptology ePrint Archive: Report 2012/694

Cryptanalysis of matrix conjugation schemes

A. D. Myasnikov and A. Ushakov

Abstract: In this paper we 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 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.

Category / Keywords: public-key cryptography / Group-based cryptography, conjugacy search problem, matrix monoids, truncated polynomials

Publication Info: Not published

Date: received 10 Dec 2012

Contact author: amyasnik at stevens edu

Available format(s): PDF | BibTeX Citation

Version: 20121214:185113 (All versions of this report)

Short URL: ia.cr/2012/694

Discussion forum: Show discussion | Start new discussion