Tropical cryptography

Tropical cryptography refers to the study of a class of cryptographic protocols built upon tropical algebras. In many cases, tropical cryptographic schemes have arisen from adapting "classical" schemes to instead rely on tropical algebras. The case for the use of tropical algebras in cryptography rests on at least two key features of "tropical" mathematics: in the "tropical" world, there is no classical multiplication (a computationally expensive operation), and the problem of solving systems of tropical polynomial equations has been shown to be NP-hard.

Basic Definitions

The key mathematical object at the heart of tropical cryptography is the tropical semiring $(\mathbb {R} \cup \{\infty \},\bigoplus ,\bigotimes )$ (also known as the min-plus algebra), or a generalization thereof. The operations are defined as follows for $x,y\in \mathbb {R} \cup \{\infty \}$:

$x\bigoplus y=min\{x,y\}$
$x\bigotimes y=x+y$

It is easily verified that with $\infty$ as the additive identity, these binary operations on $\mathbb {R} \cup \{\infty \}$ form a semiring.

References

Grigoriev, Dima; Shpilrain, Vladimir (2013). "Tropical Cryptography". arXiv:1301.1195 Freely accessible [math.AG].