Cryptanalysis of matrix conjugation schemes

Alex D. Myasnikov, Alexander Ushakov

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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.

Original languageEnglish
Pages (from-to)95-114
Number of pages20
JournalJournal of Mathematical Cryptology
Volume8
Issue number2
DOIs
StatePublished - 1 Jun 2014

Keywords

  • Group-based cryptography
  • conjugacy search problem
  • matrix monoids
  • truncated polynomials

Fingerprint

Dive into the research topics of 'Cryptanalysis of matrix conjugation schemes'. Together they form a unique fingerprint.

Cite this