Could tropical cryptography become another candidate for post-quantum cryptography?

Question

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?

Answer 1

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.

Answer 2

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.