Analysis of a certain polycyclic-group-based cryptosystem

Matvei Kotov; Alexander Ushakov

doi:10.1515/jmc-2015-0013

Analysis of a certain polycyclic-group-based cryptosystem

Matvei Kotov
, Alexander Ushakov

Department of Mathematical Sciences

Stevens Institute of Technology

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

5 Scopus citations

Abstract

We investigate security properties of the Anshel-Anshel-Goldfeld commutator key-establishment protocol [Math. Res. Lett. 6 (1999), 287-291] used with certain polycyclic groups described by Eick and Kahrobaei [http://arxiv.org/abs/math.GR/0411077]. We show that despite low success of the length based attack shown by Garber, Kahrobaei and Lam [J. Math. Crypt. 9 (2015), 33-43] the protocol can be broken by a deterministic polynomial-time algorithm.

Original language	English
Pages (from-to)	161-167
Number of pages	7
Journal	Journal of Mathematical Cryptology
Volume	9
Issue number	3
DOIs	https://doi.org/10.1515/jmc-2015-0013
State	Published - 1 Oct 2015

Keywords

Cryptography
commutator-key establishment
conjugacy problem
metabelian groups
polycyclic groups

Access to Document

10.1515/jmc-2015-0013

Cite this

@article{dac51253db5e4cb2a88578268769f1e8,

title = "Analysis of a certain polycyclic-group-based cryptosystem",

abstract = "We investigate security properties of the Anshel-Anshel-Goldfeld commutator key-establishment protocol [Math. Res. Lett. 6 (1999), 287-291] used with certain polycyclic groups described by Eick and Kahrobaei [http://arxiv.org/abs/math.GR/0411077]. We show that despite low success of the length based attack shown by Garber, Kahrobaei and Lam [J. Math. Crypt. 9 (2015), 33-43] the protocol can be broken by a deterministic polynomial-time algorithm.",

keywords = "Cryptography, commutator-key establishment, conjugacy problem, metabelian groups, polycyclic groups",

author = "Matvei Kotov and Alexander Ushakov",

note = "Publisher Copyright: {\textcopyright} 2015 by De Gruyter.",

year = "2015",

month = oct,

day = "1",

doi = "10.1515/jmc-2015-0013",

language = "English",

volume = "9",

pages = "161--167",

number = "3",

}

TY - JOUR

T1 - Analysis of a certain polycyclic-group-based cryptosystem

AU - Kotov, Matvei

AU - Ushakov, Alexander

PY - 2015/10/1

Y1 - 2015/10/1

N2 - We investigate security properties of the Anshel-Anshel-Goldfeld commutator key-establishment protocol [Math. Res. Lett. 6 (1999), 287-291] used with certain polycyclic groups described by Eick and Kahrobaei [http://arxiv.org/abs/math.GR/0411077]. We show that despite low success of the length based attack shown by Garber, Kahrobaei and Lam [J. Math. Crypt. 9 (2015), 33-43] the protocol can be broken by a deterministic polynomial-time algorithm.

AB - We investigate security properties of the Anshel-Anshel-Goldfeld commutator key-establishment protocol [Math. Res. Lett. 6 (1999), 287-291] used with certain polycyclic groups described by Eick and Kahrobaei [http://arxiv.org/abs/math.GR/0411077]. We show that despite low success of the length based attack shown by Garber, Kahrobaei and Lam [J. Math. Crypt. 9 (2015), 33-43] the protocol can be broken by a deterministic polynomial-time algorithm.

KW - Cryptography

KW - commutator-key establishment

KW - conjugacy problem

KW - metabelian groups

KW - polycyclic groups

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

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

U2 - 10.1515/jmc-2015-0013

DO - 10.1515/jmc-2015-0013

M3 - Article

AN - SCOPUS:84943807619

SN - 1862-2976

VL - 9

SP - 161

EP - 167

JO - Journal of Mathematical Cryptology

JF - Journal of Mathematical Cryptology

IS - 3

ER -

Analysis of a certain polycyclic-group-based cryptosystem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this