Paper 2024/010

On the tropical two-sided discrete logarithm and a key exchange protocol based on the tropical algebra of pairs

Sulaiman Alhussaini, University of Birmingham
Craig Collett, University of Birmingham
Serge˘ı Sergeev, University of Birmingham
Abstract

Since the existing tropical cryptographic protocols are either susceptible to the Kotov-Ushakov attack and its generalization, or to attacks based on tropical matrix periodicity and predictive behaviour, several attempts have been made to propose protocols that resist such attacks. Despite these attempts, many of the proposed protocols remain vulnerable to attacks targeting the underlying hidden problems, one of which we call the tropical two-sided discrete logarithm with shift. An illustrative case is the tropical Stickel protocol, which, when formulated with a single monomial instead of a polynomial, becomes susceptible to attacks based on solutions of the above mentioned tropical version of discrete logarithm. In this paper we will formally introduce the tropical two-sided discrete logarithm with shift, discuss how it is solved, and subsequently demonstrate an attack on a key exchange protocol based on the tropical semiring of pairs. This particular protocol is compromised due to the existence of efficient (albeit heuristic) solution of the tropical two-sided logarithm problem, and this highlights the ongoing challenges in search of a "good" key exchange protocol in tropical cryptography.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
public key cryptographykey exchange protocolcryptographic attacktropical cryptography
Contact author(s)
s alhussaini @ bham ac uk
CRC957 @ student bham ac uk
s sergeev @ bham ac uk
History
2024-01-05: approved
2024-01-03: received
See all versions
Short URL
https://ia.cr/2024/010
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/010,
      author = {Sulaiman Alhussaini and Craig Collett and Serge˘ı Sergeev},
      title = {On the tropical two-sided discrete logarithm and a key exchange protocol based on the tropical algebra of pairs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/010},
      year = {2024},
      url = {https://eprint.iacr.org/2024/010}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.