Tropical cryptography

Last updated

In tropical analysis, tropical cryptography refers to the study of a class of cryptographic protocols built upon tropical algebras. [1] 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 (also known as the min-plus algebra), or a generalization thereof. The operations are defined as follows for :


It is easily verified that with as the additive identity, these binary operations on form a semiring.

Related Research Articles

In mathematics, rings are algebraic structures that generalize fields: multiplication need not be commutative and multiplicative inverses need not exist. Informally, a ring is a set equipped with two binary operations satisfying properties analogous to those of addition and multiplication of integers. Ring elements may be numbers such as integers or complex numbers, but they may also be non-numerical objects such as polynomials, square matrices, functions, and power series.

In mathematics, in particular abstract algebra, a graded ring is a ring such that the underlying additive group is a direct sum of abelian groups such that . The index set is usually the set of nonnegative integers or the set of integers, but can be any monoid. The direct sum decomposition is usually referred to as gradation or grading.

In mathematics, K-theory is, roughly speaking, the study of a ring generated by vector bundles over a topological space or scheme. In algebraic topology, it is a cohomology theory known as topological K-theory. In algebra and algebraic geometry, it is referred to as algebraic K-theory. It is also a fundamental tool in the field of operator algebras. It can be seen as the study of certain kinds of invariants of large matrices.

In algebra, a valuation is a function on a field that provides a measure of the size or multiplicity of elements of the field. It generalizes to commutative algebra the notion of size inherent in consideration of the degree of a pole or multiplicity of a zero in complex analysis, the degree of divisibility of a number by a prime number in number theory, and the geometrical concept of contact between two algebraic or analytic varieties in algebraic geometry. A field with a valuation on it is called a valued field.

In abstract algebra, a semiring is an algebraic structure. It is a generalization of a ring, dropping the requirement that each element must have an additive inverse. At the same time, it is a generalization of bounded distributive lattices.

In mathematics, the tensor product of two fields is their tensor product as algebras over a common subfield. If no subfield is explicitly specified, the two fields must have the same characteristic and the common subfield is their prime subfield.

In mathematics, Kähler differentials provide an adaptation of differential forms to arbitrary commutative rings or schemes. The notion was introduced by Erich Kähler in the 1930s. It was adopted as standard in commutative algebra and algebraic geometry somewhat later, once the need was felt to adapt methods from calculus and geometry over the complex numbers to contexts where such methods are not available.

<span class="mw-page-title-main">Tropical geometry</span> Skeletonized version of algebraic geometry

In mathematics, tropical geometry is the study of polynomials and their geometric properties when addition is replaced with minimization and multiplication is replaced with ordinary addition:

In mathematics, especially in homological algebra and algebraic topology, a Künneth theorem, also called a Künneth formula, is a statement relating the homology of two objects to the homology of their product. The classical statement of the Künneth theorem relates the singular homology of two topological spaces X and Y and their product space . In the simplest possible case the relationship is that of a tensor product, but for applications it is very often necessary to apply certain tools of homological algebra to express the answer.

In mathematics, loop algebras are certain types of Lie algebras, of particular interest in theoretical physics.

In mathematics, coherent duality is any of a number of generalisations of Serre duality, applying to coherent sheaves, in algebraic geometry and complex manifold theory, as well as some aspects of commutative algebra that are part of the 'local' theory.

In algebraic topology, a Steenrod algebra was defined by Henri Cartan to be the algebra of stable cohomology operations for mod cohomology.

In mathematics, there are usually many different ways to construct a topological tensor product of two topological vector spaces. For Hilbert spaces or nuclear spaces there is a simple well-behaved theory of tensor products, but for general Banach spaces or locally convex topological vector spaces the theory is notoriously subtle.

In mathematics, a super vector space is a -graded vector space, that is, a vector space over a field with a given decomposition of subspaces of grade and grade . The study of super vector spaces and their generalizations is sometimes called super linear algebra. These objects find their principal application in theoretical physics where they are used to describe the various algebraic aspects of supersymmetry.

In idempotent analysis, the tropical semiring is a semiring of extended real numbers with the operations of minimum and addition replacing the usual ("classical") operations of addition and multiplication, respectively.

In mathematics, an algebraic structure consisting of a non-empty set and a ternary mapping may be called a ternary system. A planar ternary ring (PTR) or ternary field is special type of ternary system used by Marshall Hall to construct projective planes by means of coordinates. A planar ternary ring is not a ring in the traditional sense, but any field gives a planar ternary ring where the operation is defined by . Thus, we can think of a planar ternary ring as a generalization of a field where the ternary operation takes the place of both addition and multiplication.

In mathematics, a graded Lie algebra is a Lie algebra endowed with a gradation which is compatible with the Lie bracket. In other words, a graded Lie algebra is a Lie algebra which is also a nonassociative graded algebra under the bracket operation. A choice of Cartan decomposition endows any semisimple Lie algebra with the structure of a graded Lie algebra. Any parabolic Lie algebra is also a graded Lie algebra.

In mathematics, in the field of tropical analysis, the log semiring is the semiring structure on the logarithmic scale, obtained by considering the extended real numbers as logarithms. That is, the operations of addition and multiplication are defined by conjugation: exponentiate the real numbers, obtaining a positive number, add or multiply these numbers with the ordinary algebraic operations on real numbers, and then take the logarithm to reverse the initial exponentiation. Such operations are also known as, e.g., logarithmic addition, etc. As usual in tropical analysis, the operations are denoted by ⊕ and ⊗ to distinguish them from the usual addition + and multiplication ×. These operations depend on the choice of base b for the exponent and logarithm, which corresponds to a scale factor, and are well-defined for any positive base other than 1; using a base b < 1 is equivalent to using a negative sign and using the inverse 1/b > 1. If not qualified, the base is conventionally taken to be e or 1/e, which corresponds to e with a negative.

In algebraic geometry, a derived scheme is a homotopy-theoretic generalization of a scheme in which classical commutative rings are replaced with derived versions such as cdgas, commutative simplicial rings, or commutative ring spectra.

In mathematics, the set of positive real numbers, is the subset of those real numbers that are greater than zero. The non-negative real numbers, also include zero. Although the symbols and are ambiguously used for either of these, the notation or for and or for has also been widely employed, is aligned with the practice in algebra of denoting the exclusion of the zero element with a star, and should be understandable to most practicing mathematicians.

References

  1. Grigoriev, Dima; Shpilrain, Vladimir (2014). "Tropical Cryptography". Communications in Algebra. 42 (6): 2624–2632. arXiv: 1301.1195 . doi:10.1080/00927872.2013.766827. ISSN   0092-7872. S2CID   6744219.