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

Iqazra

8/23/24, 11:20 AM

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?

2626

2 + 1

post-quantum-cryptography

poncho

8/25/24, 1:43 PM

"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)

Score:11

Crypto

kodlu

8/23/24, 2:19 PM

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.

+ 0

Score:6

Crypto

Mark

8/23/24, 9:27 PM

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

were of niche research interest for perhaps 10 years [say 95-2007]
specialized interest for 10 [say 2007-2015]
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.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.