A LINEAR ATTACK ON A KEY EXCHANGE PROTOCOL USING EXTENSIONS OF MATRIX SEMIGROUPS

JINTAI DING; ALEXEI MIASNIKOV; ALEXANDER USHAKOV

Paper 2015/018

A LINEAR ATTACK ON A KEY EXCHANGE PROTOCOL USING EXTENSIONS OF MATRIX SEMIGROUPS

JINTAI DING, ALEXEI MIASNIKOV, and ALEXANDER USHAKOV

Abstract

In this paper we analyze the Kahrobaei-Lam-Shpilrain (KLS) key exchange protocols that use extensions by endomorpisms of matrices over a Galois field proposed in \cite{Kahrobaei-Lam-Shpilrain:2014}. We show that both protocols are vulnerable to a simple linear algebra attack.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: Group-based cryptography semidirect product Galois field Key Exchange
Contact author(s): jintai ding @ gmail com
History: 2015-01-14: revised; 2015-01-12: received; See all versions
Short URL: https://ia.cr/2015/018
License: CC BY

BibTeX

@misc{cryptoeprint:2015/018,
      author = {JINTAI DING and ALEXEI MIASNIKOV and ALEXANDER USHAKOV},
      title = {A {LINEAR} {ATTACK} {ON} A {KEY} {EXCHANGE} {PROTOCOL} {USING} {EXTENSIONS} {OF} {MATRIX} {SEMIGROUPS}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/018},
      year = {2015},
      url = {https://eprint.iacr.org/2015/018}
}