9
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\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
    Commented Aug 25, 2023 at 13:43

3 Answers 3

11
$\begingroup$

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.
$\endgroup$
6
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

It is possible to estimate the cryptographic security of tropical cryptography without directly attacking it. To evaluate the security of tropical cryptography, we need to estimate whether tropical algebras contain the right kind of mathematical structure to be considered secure. I claim that tropical algebras do not have the right kind of mathematical structure for cryptographic security.

Define a operations $\oplus_\epsilon$ on $\mathbb{R}$ by setting $x\oplus_\epsilon y=\log_\epsilon(\epsilon^x+\epsilon^y)$. Then $x\oplus y=\lim_{\epsilon\rightarrow 0}x\oplus_\epsilon y$.

Therefore, the tropical semiring $(\mathbb{R},\oplus,\otimes)$ is a limit of the ring $(\mathbb{R},\oplus_\epsilon,\otimes)$ as $\epsilon\rightarrow 0$, but $(\mathbb{R},\oplus_\epsilon,\otimes)$ is isomorphic to $(\mathbb{R},+,\cdot)$. In general, the process of taking a limit decreases the cryptographic security of the underlying ring. The process of simplifying $(\mathbb{R},+,\cdot)$ to $(\mathbb{R},\oplus_\epsilon,\otimes)$ should be contrasted with the process of simplifying $\mathbb{Z}$ to the finite field $\mathbb{F}_p$ by taking a quotient modulo a maximal ideal. For cryptography, one should prefer algebraic structures that are finite and simple (by simple, I mean that the structure has no non-trivial quotient structures). If $X$ is a non-simple algebraic structure, then one may try to break a cryptosystem based on $X$ by first breaking $X$ in quotient structures $X/\simeq$ and then by using the information in $X/\simeq$ to break the cryptosystem in $X$. Therefore, the simplicity of $\mathbb{F}_q$ makes $\mathbb{F}_q$ a more secure platform than $\mathbb{Z}$.

One can show that the tropical semiring $(\mathbb{R},\oplus,\otimes)$ is simple by first showing that if $\simeq$ is a congruence on $(\mathbb{R},\oplus)$ and $x\leq y\leq z,x\simeq z$, then $x\simeq y$. While the tropical semiring $(\mathbb{R},\oplus,\otimes)$ is still simple, the tropical semiring $(\mathbb{R},\oplus,\otimes)$ is a degenerate form of $\mathbb{R}$.

On the other hand, the field of complex numbers is isomorphic to an ultraproduct $\prod_{p\in P}\overline{\mathbb{F}_p}$ where $P$ is the set of all primes and $\overline{K}$ denotes the algebraic closure of $K$. In other words, one can recover all the information from the field of complex numbers from the algebraic closures of finite fields, so finite fields are not that much simpler than the field of real or complex numbers. I would therefore prefer finite fields to tropical semirings since tropical semirings exhibit a level of degeneracy that we do not find in finite fields.

While tropical semirings exhibit some degeneracy, they can still be useful and they still exhibit complicated behavior. For example, neural networks with ReLU activation are essentially just $n$-th roots of rational functions over the tropical semiring $(\mathbb{R},\oplus,\otimes)$.

Observation 0: Tropical matrix exponentiation: If $(v_{i,j})_{i,j}$ is a square tropical matrix and is the adjacency matrix for a directed graph (where directed loops have possibly zero weight), then $(v_{i,j})_{i,j}^n=(u_{i,j})_{i,j}$ where $u_{i,j}$ is the weight of the shortest path from $i$ to $j$. Now if $v_{i,j}\geq 0$ and $v_{i,i}=0$ for all $i$, then the $(v_{i,j})_{i,j}^m=(v_{i,j})_{i,j}^n$ whenever $m,n$ are at least as large as the number of nodes in the graph. This means that matrix exponentiation is eventually constant in this case.

Observation 1: The operation $\oplus$ is commutative, associative, and idempotent. In other words, the $\oplus$ operation is the meet operation on a semilattice, and this semilattice is totally ordered. Lattice operations do not have the characteristics that we want for cryptography because they are too simple and lack the invertibility that algebraic structures like group have.

Observation 2: Every tropical polynomial function of several variables is concave (and much more). It is hard to get cryptographic security when one does not have access to non-concave functions.

Observation 3: Tropical matrix multiplication is non-avalanching. If $A_0,\dots,A_{2r},B_0,\dots,B_{2r}$ are tropical matrices, and $A_i=B_i$ for $i\neq r$, and $A_r,B_r$ differ by only a few entries, then $A_0\otimes\dots\otimes A_{2r},B_0\otimes\dots\otimes B_{2r}$ will closely resemble each other.

Tropical algebras do not bear much resemblance to the type of mathematical structure that is useful for cryptography. And some tropical cryptosystems have been broken in the past, so I would not bet too highly on the security of tropical cryptography. It is interesting to study tropical cryptography though since tropical cryptography can at least tell us what kinds of structures are good for cryptography and what kinds are not.

$\endgroup$

Your Answer

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

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