Paper 2021/040

On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product

Any Muanalifah and Serge˘ı Sergeev

Abstract

Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain ~\cite{grigoriev2014tropical,grigoriev2018tropical} as a promising platform for the implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: ``Given that $A=V\otimes F^{\otimes t}$ for a unique $t$ and matrices $A$, $V$, $F$ of appropriate dimensions, find this $t$.'' We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Tropical algebrasemidirect productmatrix powerscryptanalysis
Contact author(s)
any math13 @ gmail com
s sergeev @ bham ac uk
History
2021-01-12: received
Short URL
https://ia.cr/2021/040
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/040,
      author = {Any Muanalifah and Serge˘ı Sergeev},
      title = {On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product},
      howpublished = {Cryptology ePrint Archive, Paper 2021/040},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/040}},
      url = {https://eprint.iacr.org/2021/040}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.