Cryptanalysis of matrix conjugation schemes
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2014-06-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2012-0033 |
| _version_ | 1798040034801090560 |
|---|---|
| author | Myasnikov Alex D. Ushakov Alexander |
| author_facet | Myasnikov Alex D. Ushakov Alexander |
| author_sort | Myasnikov Alex D. |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-11T22:01:56Z |
| format | Article |
| id | doaj.art-13c6d23ec4ea4d12bd6ca09e8f61a2ab |
| institution | Directory Open Access Journal |
| issn | 1862-2976 1862-2984 |
| language | English |
| last_indexed | 2024-04-11T22:01:56Z |
| publishDate | 2014-06-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-13c6d23ec4ea4d12bd6ca09e8f61a2ab2022-12-22T04:00:54ZengDe GruyterJournal of Mathematical Cryptology1862-29761862-29842014-06-01829511410.1515/jmc-2012-0033Cryptanalysis of matrix conjugation schemesMyasnikov Alex D.0Ushakov Alexander1Department of Mathematics, Stevens Institute of Technology, Hoboken, NJ 07030, USADepartment of Mathematics, Stevens Institute of Technology, Hoboken, NJ 07030, USAIn 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.https://doi.org/10.1515/jmc-2012-0033group-based cryptographyconjugacy search problemmatrix monoidstruncated polynomials94a6068w30 |
| spellingShingle | Myasnikov Alex D. Ushakov Alexander Cryptanalysis of matrix conjugation schemes Journal of Mathematical Cryptology group-based cryptography conjugacy search problem matrix monoids truncated polynomials 94a60 68w30 |
| title | Cryptanalysis of matrix conjugation schemes |
| title_full | Cryptanalysis of matrix conjugation schemes |
| title_fullStr | Cryptanalysis of matrix conjugation schemes |
| title_full_unstemmed | Cryptanalysis of matrix conjugation schemes |
| title_short | Cryptanalysis of matrix conjugation schemes |
| title_sort | cryptanalysis of matrix conjugation schemes |
| topic | group-based cryptography conjugacy search problem matrix monoids truncated polynomials 94a60 68w30 |
| url | https://doi.org/10.1515/jmc-2012-0033 |
| work_keys_str_mv | AT myasnikovalexd cryptanalysisofmatrixconjugationschemes AT ushakovalexander cryptanalysisofmatrixconjugationschemes |