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

<span class="mw-page-title-main">Ring (mathematics)</span> Algebraic structure with addition and multiplication

In mathematics, rings are algebraic structures that generalize fields: multiplication need not be commutative and multiplicative inverses need not exist. In other words, 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, 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.

<span class="mw-page-title-main">Semiring</span> Algebraic ring that need not have additive negative elements

In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse.

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 (1955) 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 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 effect, in computer architecture, this ternary operation is known, e.g., as the multiply–accumulate operation (MAC).

In mathematics, a split-biquaternion is a hypercomplex number of the form

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 the field of mathematics known as differential geometry, a generalized complex structure is a property of a differential manifold that includes as special cases a complex structure and a symplectic structure. Generalized complex structures were introduced by Nigel Hitchin in 2002 and further developed by his students Marco Gualtieri and Gil Cavalcanti.

The term external is useful for describing certain algebraic structures. The term comes from the concept of an external binary operation which is a binary operation that draws from some external set. To be more specific, a left external binary operation on S over R is a function and a right external binary operation on S over R is a function where S is the set the operation is defined on, and R is the external set.

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 pair consisting of a topological space X and a sheaf either of simplicial commutative rings or of commutative ring spectra on X such that (1) the pair is a scheme and (2) is a quasi-coherent -module. The notion gives a homotopy-theoretic generalization of a scheme.

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.