Paper 2024/010
On the tropical two-sided discrete logarithm and a key exchange protocol based on the tropical algebra of pairs
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)
- 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
-
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} }