Тропическая криптография

В тропическом анализе тропическая криптография относится к изучению класса криптографических протоколов, построенных на тропических алгебрах . Во многих случаях тропические криптографические схемы возникли в результате адаптации классических (нетропических) схем к использованию тропических алгебр. Аргументы в пользу использования тропических алгебр в криптографии основаны как минимум на двух ключевых особенностях тропической математики: в тропическом мире нет классического умножения (вычислительно затратная операция), а проблема решения систем тропических полиномиальных уравнений была решена. показано, что это NP-трудно .

Основные определения

Ключевым математическим объектом, лежащим в основе тропической криптографии, является тропическое полукольцо. $(\mathbb {R} \cup \{\infty \},\oplus ,\otimes )$ (также известная как мин-плюс-алгебра ) или ее обобщение. Операции определяются следующим образом для $x,y\in \mathbb {R} \cup \{\infty \}$:

$x\oplus y=\min\{x,y\}$
$x\otimes y=x+y$

Легко проверить, что при $\infty$ как аддитивная идентичность , эти бинарные операции над $\mathbb {R} \cup \{\infty \}$ образовать полукольцо .