Cryptanalysis of a key exchange protocol based on a digital semiring
A. Ponmaheshkumar, M. Kotov, R. Srinivasa Perumal · Communications in Algebra · 2025
This paper is devoted to tropical cryptography, a branch of non-commutative cryptography that uses tropical structures as platforms for cryptographic protocols. In this paper, we focus on the key exchange scheme based on a digital semiring proposed by Huang et al. [Citation16]. Analyzing the protocol, we study systems of equations of degree two of a special form and suggest an algorithm to solve them based on the branch-and-bound approach. We show how this method can be used to attack this scheme. Additionally, we show that the 3-SAT can be reduced in polynomial time to the problem of solving systems of quadratic polynomial equations of a special form over this semiring.