Cryptanalysis of Semidirect Product Key Exchange Using Matrices Over Non-Commutative Rings

Christopher Battarbee; Delaram Kahrobaei; Siamak F. Shahandashti

Cryptanalysis of Semidirect Product Key Exchange Using Matrices Over Non-Commutative Rings

Christopher Battarbee, Delaram Kahrobaei, Siamak F. Shahandashti

Computer Science

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

Abstract

It was recently demonstrated that the Matrix Action Key Exchange (MAKE) algorithm, a new type of key exchange protocol using the semidirect product of matrix groups, is vulnerable to a linear algebraic attack if the matrices are over a commutative ring. In this note, we establish conditions under which protocols using matrices over a non-commutative ring are also vulnerable to this attack. We then demonstrate that group rings R[G] used in arXiv:1304.6572, where R is a commutative ring and G is a non-abelian group, are examples of non-commutative rings that satisfy these conditions.

Original language	English
Article number	130528
Pages (from-to)	2-9
Journal	Mathematical Cryptology
Volume	1
Issue number	2
Publication status	Published - 18 Mar 2022
Event	MathCrypt 2021 - Duration: 15 Aug 2021 → … https://crypto.iacr.org/2021/mathcrypt.php

Bibliographical note

Keywords

key exchange
cryptography
post-quantum cryptography
semidirect product
cryptanalysis
linear algebra

Access to Document

paper-103
(c) 2022 Christopher Battarbee, Delaram Kahrobaei, Siamak F. Shahandashti
Final published version, 266 KBLicence: CC BY-NC

https://journals.flvc.org/mathcryptology/article/view/130528/133265Licence: CC BY-NC

Cite this

@article{81f2b594a73d4d6195f1767ef236c1c6,

title = "Cryptanalysis of Semidirect Product Key Exchange Using Matrices Over Non-Commutative Rings",

abstract = " It was recently demonstrated that the Matrix Action Key Exchange (MAKE) algorithm, a new type of key exchange protocol using the semidirect product of matrix groups, is vulnerable to a linear algebraic attack if the matrices are over a commutative ring. In this note, we establish conditions under which protocols using matrices over a non-commutative ring are also vulnerable to this attack. We then demonstrate that group rings R[G] used in arXiv:1304.6572, where R is a commutative ring and G is a non-abelian group, are examples of non-commutative rings that satisfy these conditions. ",

keywords = "key exchange, cryptography, post-quantum cryptography, semidirect product, cryptanalysis, linear algebra",

author = "Christopher Battarbee and Delaram Kahrobaei and Shahandashti, {Siamak F.}",

year = "2022",

month = mar,

day = "18",

language = "English",

volume = "1",

pages = "2--9",

journal = "Mathematical Cryptology",

number = "2",

url = "https://crypto.iacr.org/2021/mathcrypt.php",

}

TY - JOUR

T1 - Cryptanalysis of Semidirect Product Key Exchange Using Matrices Over Non-Commutative Rings

AU - Battarbee, Christopher

AU - Kahrobaei, Delaram

AU - Shahandashti, Siamak F.

PY - 2022/3/18

Y1 - 2022/3/18

N2 - It was recently demonstrated that the Matrix Action Key Exchange (MAKE) algorithm, a new type of key exchange protocol using the semidirect product of matrix groups, is vulnerable to a linear algebraic attack if the matrices are over a commutative ring. In this note, we establish conditions under which protocols using matrices over a non-commutative ring are also vulnerable to this attack. We then demonstrate that group rings R[G] used in arXiv:1304.6572, where R is a commutative ring and G is a non-abelian group, are examples of non-commutative rings that satisfy these conditions.

AB - It was recently demonstrated that the Matrix Action Key Exchange (MAKE) algorithm, a new type of key exchange protocol using the semidirect product of matrix groups, is vulnerable to a linear algebraic attack if the matrices are over a commutative ring. In this note, we establish conditions under which protocols using matrices over a non-commutative ring are also vulnerable to this attack. We then demonstrate that group rings R[G] used in arXiv:1304.6572, where R is a commutative ring and G is a non-abelian group, are examples of non-commutative rings that satisfy these conditions.

KW - key exchange

KW - cryptography

KW - post-quantum cryptography

KW - semidirect product

KW - cryptanalysis

KW - linear algebra

M3 - Article

VL - 1

SP - 2

EP - 9

JO - Mathematical Cryptology

JF - Mathematical Cryptology

IS - 2

M1 - 130528

T2 - MathCrypt 2021

Y2 - 15 August 2021

ER -