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

Any Muanalifah, Sergei Sergeev

Research output: Contribution to journalArticlepeer-review

57 Downloads (Pure)

Abstract

Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain as a promising platform for 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 ⊗ F⊗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.
Original languageEnglish
Pages (from-to)861-879
Number of pages19
JournalCommunications in Algebra
Volume50
Issue number2
Early online date20 Sept 2021
DOIs
Publication statusPublished - 1 Feb 2022

Bibliographical note

Funding Information:
We would like to thank the anonymous referee of our paper for their careful reading, useful comments and appreciation of our work.

Publisher Copyright:
© 2021 Taylor & Francis Group, LLC.

Keywords

  • Cryptanalysis
  • matrix powers
  • semidirect product
  • tropical algebra

ASJC Scopus subject areas

  • Algebra and Number Theory

Fingerprint

Dive into the research topics of 'On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product'. Together they form a unique fingerprint.

Cite this