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

JINTAI DING; ALEXEI MIASNIKOV; ALEXANDER USHAKOV

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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},
      note = {\url{https://eprint.iacr.org/2015/018}},
      url = {https://eprint.iacr.org/2015/018}
}