Cryptanalysis of matrix conjugation schemes

Alex D. Myasnikov; Alexander Ushakov

doi:10.1515/jmc-2012-0033

Cryptanalysis of matrix conjugation schemes

Alex D. Myasnikov
, Alexander Ushakov

Department of Mathematical Sciences

Stevens Institute of Technology

Research output: Contribution to journal › Article › peer-review

6 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 language	English
Pages (from-to)	95-114
Number of pages	20
Journal	Journal of Mathematical Cryptology
Volume	8
Issue number	2
DOIs	https://doi.org/10.1515/jmc-2012-0033
State	Published - 1 Jun 2014

Keywords

Group-based cryptography
conjugacy search problem
matrix monoids
truncated polynomials

Access to Document

10.1515/jmc-2012-0033

Cite this

@article{4abb0a2787cb4d0bb41c73e27b232966,

title = "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",

author = "Myasnikov, \{Alex D.\} and Alexander Ushakov",

year = "2014",

month = jun,

day = "1",

doi = "10.1515/jmc-2012-0033",

language = "English",

volume = "8",

pages = "95--114",

number = "2",

}

TY - JOUR

T1 - Cryptanalysis of matrix conjugation schemes

AU - Myasnikov, Alex D.

AU - Ushakov, Alexander

PY - 2014/6/1

Y1 - 2014/6/1

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

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

KW - Group-based cryptography

KW - conjugacy search problem

KW - matrix monoids

KW - truncated polynomials

UR - https://www.scopus.com/pages/publications/84902313788

UR - https://www.scopus.com/pages/publications/84902313788#tab=citedBy

U2 - 10.1515/jmc-2012-0033

DO - 10.1515/jmc-2012-0033

M3 - Article

AN - SCOPUS:84902313788

SN - 1862-2976

VL - 8

SP - 95

EP - 114

JO - Journal of Mathematical Cryptology

JF - Journal of Mathematical Cryptology

IS - 2

ER -

Cryptanalysis of matrix conjugation schemes

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this