Paper 2024/010 Original: eprint.iacr.org/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.