The paper is dedicated to Multivariate Cryptography over general commutative ring K and protocols of symbolic computations for safe delivery of multivariate maps. We consider itera-tive algorithm of generation of multivariate maps of prescribed degree or density with the trapdoor accelerator, i.e. piece of information which allows to compute the reimage of the map in polynomial time. The concept of Jordan-Gauss temporal graphs is used for the obfus-cation of known graph based public keys ...

We propose a new key exchange protocol based on the Generalised Diffie-Hellman Key Exchange. In the latter, instead of using a group-action, we consider a semigroup action. In our proposal, the semigroup is the set of oriented knots in $\mathbb{S}^3$ with the operation of connected sum. As a semigroup action, we choose the action of the semigroup on itself through the connected sum. For the protocol to work, we need to use knot invariants, which allow us to create the shared secret key...

Cayley hash functions are based on a simple idea of using a pair of semigroup elements, $A$ and $B$, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the semigroup. The main advantage of Cayley hash functions compared to, say, hash functions in the SHA family is that when an already hashed document is amended, one does not have to hash the whole amended document all over again, but rather hash just...

Let n stands for the length of digital signatures with quadratic multivariate public rule in n variables. We construct postquantum secure procedure to sign O(n^t), t ≥1 digital documents with the signature of size n in time O(n^{3+t}). It allows to sign O(n^t), t <1 in time O(n^4). The procedure is defined in terms of Algebraic Cryptography. Its security rests on the semigroup based protocol of Noncommutative Cryptography referring to complexity of the decomposition of the collision...

The semidirect discrete logarithm problem (SDLP) is the following analogue of the standard discrete logarithm problem in the semidirect product semigroup $G\rtimes \mathrm{End}(G)$ for a finite semigroup $G$. Given $g\in G, \sigma\in \mathrm{End}(G)$, and $h=\prod_{i=0}^{t-1}\sigma^i(g)$ for some integer $t$, the SDLP$(G,\sigma)$, for $g$ and $h$, asks to determine $t$. As Shor's algorithm crucially depends on commutativity, it is believed not to be applicable to the SDLP. Previously, the...

Shor's algorithm efficiently solves the discrete logarithm problem (DLP) by taking advantage of the commutativity structure of the group underlying the problem. To counter Shor's algorithm, Horan et al. propose a DLP analogue in the semidirect product semigroup $G\rtimes \mathrm{End}(G)$, given a (semi)group $G$, to construct a quantum-resistant Diffie-Hellman key exchange based on it. For general (semi)groups, the semidirect discrete logarithm problem (SDLP) can be reduced to the hidden...

Algebraic Constructions of Extremal Graph Theory were efficiently used for the construction of Low Density Parity Check Codes for satellite communication, constructions of stream ciphers and Postquantum Protocols of Noncommutative cryptography and corresponding El Gamal type cryptosystems. We shortly observe some results in these applications and present idea of the usage of algebraic graphs for the development of Multivariate Public Keys (MPK). Some MPK schemes are presented at...

Studies of linear codes in terms of finite projective geometries form traditional direction in Coding Theory. Some applications of projective geometries are known. Noncommutative groups and semigroups defined in terms of projective geometries can serve as platforms of protocols of Post Quantum Cryptography. We introduce an idea of public keys of Multivariate Cryptography given by quadratic public rules generated via walks on incidence substructures of projective geometry with vertexes...

We consider actions of a group or a semigroup on a set, which generalize the setup of discrete logarithm based cryptosystems. Such cryptographic group actions have gained increasing attention recently in the context of isogeny-based cryptography. We introduce generic algorithms for the semigroup action problem and discuss lower and upper bounds. Also, we investigate Pohlig-Hellman type attacks in a general sense. In particular, we consider reductions provided by non-invertible elements in...

Multivariate rule x_i -> f_i, i = 1, 2, ..., n, f_i from K[x_1, x_2, ..., x_n] over commutative ring K defines endomorphism σ_n of K[x_1, x_2, ..., x_n] into itself given by its values on variables x_i. Degree of σ_n can be defined as maximum of degrees of polynomials f_i. We say that family σ_n, n = 2, 3, .... has trapdoor accelerator ^nT if the knowledge of the piece of information ^nT allows to compute reimage x of y = σ_n(x) in time O(n^2). We use extremal algebraic graphs for the...

Time dependent linguistic graphs over abelian group H are introduced. In the case $H=K*$ such bipartite graph with point set $P=H^n$ can be used for generation of Eulerian transformation of $(K*)^n$, i.e. the endomorphism of $K[x_1, x_2,… , x_n]$ sending each variable to a monomial term. Subsemigroups of such endomorphisms together with their special homomorphic images are used as platforms of cryptographic protocols of noncommutative cryptography. The security of these protocol is evaluated...

Some key agreement schemes, such as Diffie--Hellman key agreement, reduce to Rabi--Sherman key agreement, in which Alice sends $ab$ to Charlie, Charlie sends $bc$ to Alice, they agree on key $a(bc) = (ab)c$, where multiplicative notation here indicates some specialized associative binary operation. All non-interactive key agreement schemes, where each peer independently determines a single delivery to the other, reduce to this case, because the ability to agree implies the existence of an...

Large semigroups and groups of transformations of finite affine space of dimension n with the option of computability of the composition of n arbitrarily chosen elements in polynomial time are described in the paper. Constructions of such families are given together with effectively computed homomorphisms between members of the family. These algebraic platforms allow us to define protocols for several generators of subsemigroup of affine Cremona semigroups with several outputs. Security of...

Multivariate cryptography studies applications of endomorphisms of K[x_1, x_2, …, x_n] where K is a finite commutative ring given in the standard form x_i &#8594;f_i(x_1, x_2,…, x_n), i=1, 2,…, n. The importance of this direction for the constructions of multivariate digital signatures systems is well known. Close attention of researchers directed towards studies of perspectives of quadratic rainbow oil and vinegar system and LUOV presented for NIST postquantum certification....

The intersection of Non-commutative and Multivariate cryptography contains studies of cryptographic applications of subsemigroups and subgroups of affine Cremona semigroups defined over finite commutative ring K with the unit. We consider special subsemigroups (platforms) in a semigroup of all endomorphisms of K[x_1, x_2, …, x_n]. Efficiently computed homomorphisms between such platforms can be used in Post Quantum key exchange protocols when correspondents elaborate common...

We suggest new applications of protocols of Non-commutative cryptography defined in terms of subsemigroups of Affine Cremona Semigroups over finite commutative rings and their homomorphic images to the constructions of possible instruments of Post Quantum Cryptography. This approach allows to define cryptosystems which are not public keys. When extended protocol is finished correspondents have the collision multivariate transformation on affine space K ^n or variety (K*)^n where K is a...

Non-commutative cryptography studies cryptographic primitives and systems which are based on algebraic structures like groups, semigroups and noncommutative rings. We con-tinue to investigate inverse protocols of Non-commutative cryptography defined in terms of subsemigroups of Affine Cremona Semigroups over finite fields or arithmetic rings $Z_m$ and homomorphic images of these semigroups as possible instruments of Post Quantum Cryptography. This approach allows to construct cryptosystems...

Noncommutative cryptography is based on applications of algebraic structures like noncommutative groups, semigroups and non-commutative rings. Its inter-section with Multivariate cryptography contains studies of cryptographic applications of subsemigroups and subgroups of affine Cremona semigroups defined overfinite commutative rings. Efficiently computed homomorphisms between stable subsemigroups of affine Cremona semigroups can be used in tame homomorphisms protocols schemes and...

Noncommutative cryptography is based on the applications of algebraic structures like noncommutative groups, semigroups and noncommutative rings. Its intersection with Multivariate cryptography contains studies of cryptographic applications of subsemigroups and subgroups of affine Cremona semigroups defined over finite commutative ring K. We consider special semigroups of transformations of the variety (K*)^n, K=F_q or K=Z_m defined via multiplications of variables. Efficiently...

Families of stable cyclic groups of nonlinear polynomial transformations of affine spaces $K^n$ over general commutative ring $K$ of increasing with $n$ order can be used in the key exchange protocols and related to them El Gamal multivariate cryptosystems. We suggest to use high degree of noncommutativity of affine Cremona group and modify multivariate El Gamal algorithm via the usage of conjugations for two polynomials of kind $g^k$ and $g^{-1}$ given by key holder (Alice) or giving...

In this survey, we describe a general key exchange protocol based on semidirect product of (semi)groups (more specifically, on extensions of (semi)groups by automorphisms), and then focus on practical instances of this general idea. This protocol can be based on any group or semigroup, in particular on any non-commutative group. One of its special cases is the standard Diffie-Hellman protocol, which is based on a cyclic group. However, when this protocol is used with a non-commutative...

In this paper we analyze the Kahrobaei-Lam-Shpilrain (KLS) key exchange protocols that use extensions by endomorpisms of matrices over a Galois field proposed in \cite{Kahrobaei-Lam-Shpilrain:2014}. We show that both protocols are vulnerable to a simple linear algebra attack.

We present a polynomial-time reduction of the discrete logarithm problem in any periodic (or torsion) semigroup (SGDLP) to the classic DLP in a _subgroup_ of the same semigroup. It follows that SGDLP can be solved in polynomial time by quantum computers, and that SGDLP has subexponential complexity whenever the classic DLP in the corresponding groups has subexponential complexity. We also consider several natural constructions of nonperiodic semigroups, and provide polynomial time solutions...

In this paper, we describe a brand new key exchange protocol based on a semidirect product of (semi)groups (more specifically, on extension of a (semi)group by automorphisms), and then focus on practical instances of this general idea. Our protocol can be based on any group, in particular on any non-commutative group. One of its special cases is the standard Diffie-Hellman protocol, which is based on a cyclic group. However, when our protocol is used with a non-commutative (semi)group, it...

We propose a couple of general ways of constructing authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several authentication schemes with long-term private keys where forgery (a.k.a. impersonation) is NP-hard. Computationally hard problems that can be employed in these realizations include Graph Colorability,...

After some excitement generated by recently suggested public key exchange protocols due to Anshel-Anshel-Goldfeld and Ko-Lee et al., it is a prevalent opinion now that the conjugacy search problem is unlikely to provide sufficient level of security if a braid group is used as the platform. In this paper we address the following questions: (1) whether choosing a different group, or a class of groups, can remedy the situation; (2) whether some other ``hard" problem from combinatorial group...

Stream ciphers are often used in applications where high speed and low delay are a requirement. The Solitaire stream cipher was developed by B. Schneier as a paper-and-pencil cipher. Solitaire gets its security from the inherent randomness in a shuffled deck of cards. In this paper we investigate semigroups and groups properties of the Solitaire stream cipher and its regular modifications.