- Source: Tropical cryptography
In tropical analysis, 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 (non-tropical) 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
(
R
∪
{
∞
}
,
⊕
,
⊗
)
{\displaystyle (\mathbb {R} \cup \{\infty \},\oplus ,\otimes )}
(also known as the min-plus algebra), or a generalization thereof. The operations are defined as follows for
x
,
y
∈
R
∪
{
∞
}
{\displaystyle x,y\in \mathbb {R} \cup \{\infty \}}
:
x
⊕
y
=
min
{
x
,
y
}
{\displaystyle x\oplus y=\min\{x,y\}}
x
⊗
y
=
x
+
y
{\displaystyle x\otimes y=x+y}
It is easily verified that with
∞
{\displaystyle \infty }
as the additive identity, these binary operations on
R
∪
{
∞
}
{\displaystyle \mathbb {R} \cup \{\infty \}}
form a semiring.