According to Wikipedia, tropical cryptographic protocols are built upon tropical algebras, i.e., a semiring $(\mathbb{R} \cup \{\infty\}, \oplus, \otimes)$ where $x \oplus y = \min \{x,y\}$ and $x \otimes y = x+y$. Recently, several tropical algebra-based cryptographic protocols have been proposed, and they rely on some tropical algebraic-based problems that are claimed NP-hard (such as the multiple exponentiation problem of matrices and the two-side tropical circular matrix problem).

I am aware that some post-quantum cryptographic protocol candidates correlate to linear algebraic problems (as in code-based cryptography and lattice-based cryptography). Hence, my question is, could tropical cryptography become another candidate for post-quantum cryptography (as claimed by some of its proponents)? If so, what makes research in tropical cryptography still relatively limited?

  • 1
    $\begingroup$ "They rely on some tropical algebraic-based problems that are claimed NP-hard"; solving a large set of simultaneous tropical equations is NP-hard (one way to show this is a reduction from 3SAT). However, the 'two-side tropical circular matrix problem' paper essentially shows that if you can solve that NP-hard problem, you can solve their problem - that isn't very interesting (that gives an upper bound, not a lower bound, on the hardness of their problem). What would be very interesting if they showed the reduction went the other way; they do not claim that (and that looks unlikely to be true) $\endgroup$
    – poncho
    Aug 25 at 13:43

2 Answers 2


I can think of the following reasons, and maybe further research into these systems can change this situation:

  • When there is a proposed cryptosystem based on a different algebraic system, it is up to the proposers to demonstrate the advantage over the existing systems. Even in usual applied fields, let alone cryptography where by nature everyone is a bit conservative in terms of changing to new relatively untested techniques. Then there is the timeline of active research and cryptanalysis and slowly leading to specification of protocols and standardization. Just think back to when code based and lattice based cryptography was first proposed, many decades ago.
  • The claimed, or even proved NP-hard problems do not necessarily result in strong cryptosystems. The classical case is the knapsack proposed by Merkle-Hellman. This is because (handwaving somewhat) the average case difficulty is important not worst case difficulty.
  • In algebraic coding theory, which is a related area, there is lots of research that is interesting/beautiful for its own sake, and a lot of these codes never make it to implementation or use--their decoding may be too complex, for example. Cryptography is different in that the goal is applied, to design and implement a strong cryptosystem.

Anything can become a candidate for post-quantum cryptography if there has been sufficient cryptanalytic interest in it for long enough that practitioners believe it is plausibly hard to break for both pre-and-post quantum computers.

What "sufficient interest" for "long enough" is very nebulous though. If you follow discussions on the PQC forum, some well-known cryptanalysts will get quite annoyed that lattices

  1. were of niche research interest for perhaps 10 years [say 95-2007]
  2. specialized interest for 10 [say 2007-2015]
  3. generalized interest for 8 years [say 2015-2023]

before being chosen for standardized. This timeline is sometimes seen as being too aggressive.

For a faster timeline, you could think of Isogeny-based crypto (though I am not qualified to break it down in the above way). By whatever measure, it was a more niche research area than lattices, and ended up suffering a devestating attack some (almost) 2 decades after first being proposed. The key technical result of this attack (Kani's theorem) was even published before the first isogeny-based cryptosystem was developed, yet it still took those ~20 years for a real cryptanalytic test to occur.

Perhaps with enough research interest tropical cryptography may have merits. But it is much too early to say anything, given that an average practicing cryptographer has a decent chance of never having heard of it before (such as myself), so it perhaps has not been sufficiently exposed to cryptanalysis.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.