The intersection of 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 two special families of subsemigroups in a semigroup of all endomorphisms of K[x1, x2, …, xn]. They can be used in Post Quantum Cryptography for the development of key exchange protocols of Noncommutative Cryptography with output presented as multivariale map of high degree and density. The security of these schemes is based on a complexity of Conjugacy Power Problem. Suggested schemes can be converted in protocol based cryptosystems of El Gamal type and used for post quantum protection of Virtual Organisations in Global Information Space. Algorithms are implemented in the cases of finite fields of characteristic 2 and arithmetic rings Zm, m=2n, n=8,16,32.
NIST 2017 tender starts the standardisation
process of possible Post-Quantum Public keys
aimed for purposes to be:
Encryption tools.
Tools for digital signatures [
In July 2020 the Third round of the
competition was started. In the category of
Multivariate Cryptography (MC) remaining
candidates are easy to observe [
For the first task multivariate algorithm were
not selected, single multivariate candidate is
Rainbow Like Unbalanced Oil and Vinegar
(RUOV) In fact RUOV algorithm is investigated
as appropriate instrument for the second task
[
Noteworthy that all multivariate NIST candidates were presented by multivariate rule of degree bounded by constant (2 or 3) of kind x1→f1(x1, x2, …, xn), x2→f2(x1, x2, …, xn), …, xn→fn(x1, x2, …, xn).
In fact RUOV is given by quadratic system of
polynomial equations. During Third Round of
NIST project [
We think that these NIST outcomes motivate investigations of alternating options in Multivariate Cryptography oriented on encryption tools and conducting digital signatures.
(a) To work with plainspace Fqn and its transformation G of linear degree cn, c > 0 on the level of stream ciphers or public keys.
(b) To use protocols of Noncommutative Cryptography with platforms of multivariate transformations for the secure elaboration of multivariate map G from End(Fq[x1, x2, …, xn]) of linear or superlinear degree and density bounded below by function of kind cnr, where c>0 and r>1.
Recall that density is the number of all monomial term in standard form xi → gi(x1, x2, …, xn), i = 1,2,…,n of G, where polynomials g1 are given via the lists of monomial terms in the lexicographical order.
Solution of task (b) can be used for the control access to the portal B of virtual organisation (knowledge base, virtual decision making centre, etc.) via secure communications of portal administrator (Alice) and public user (Bob).
Assume that the information in B is presented in binary alphabet. So we can identify characters of this alphabet with elements of finite field Fq, q=256. Portal has a search engine. So, we can assume that the size of the information through the portal is practically unlimited.
Assume that some secure tools are used to protect the entrance of B. To enter the system user need a password which is a tuple E of length n written in alphabet Fq. It has to be changed regularly with the usage of certain period ∆.
We suggest the following access control scheme. Alice and Bob use several session of Postquantum Secure Protocols of Noncommutative Cryptography based on a subsemigroup S of End Fq [x1, x2, …, xn] to elaborate multivariate map G from S of kind xi→fi(x1, x2, …, xn), i = 1,2,…,n of degree bounded below by cn, c>0 and density bounded below by dnr where c, d are positive constants and r > 2.
The standard form of G can be unknown. This map could be non bijective one. It has to be given with a polynomial algorithm of computation the value of G in given tuple P = (p1, p2, …, pn).
Alice use some pseudorandom generator of tuples for the creation of P = (p1, p2, …, pn) and sends it to Bob via open channel. She enters password E = G(p1, p2, …, pn) to secure the portal.
Bob also computes the tuple E and enters the system. We can assume that data storage B contains a pseudorandom (or genuinely random, obtained via quantum computations) matrix of rows Mi = (mi,1, mi,2, …, mi,n), i ϵ J for some “potentially infinite” set J.
So, Alice and Bob can periodically compute G(Mi) and use this tuple as entrance password.
Additionally they can use G for symmetric communication via one time pad.
Alice writes her plaintext P=(p1, p2, …, pn) from Fqn. She computes P + G(Mi) and sends it to Bob. He knows Mi as well. So, Bob restores the plaintext.
Surely instead of one time pad correspondents can use other stream cipher with periodical change of password.
It is naturally to consider more general case of arbitrarily commutative ring K instead of finite field Fq. We will use Algebraic Graphs to generate highly nonlinear automorphisms of K[x1, x2, …, xn] over commutative ring.
For creation of Mi, i ϵ J ontological technologies can be used. We use files obtained by ontological instruments presenting for example key words of texts with the relations between them in the form of graph (trees or other diagrams). One can combine ontological extraction with hashing technologies to make digests of documents of appropriate size.
We hope that this new application of technologies for special ontological extractions will motivate further research in this important direction.
The task is new because of postquantum protocols with outputs in the form of highly nonlinear map of affine map of K n to itself appear very recently.
We present one of them below.
Regular algebraic graph A(n, q) =A(n, Fq) is an important object of Extremal Graph Theory. In fact we can consider more general graphs A(n, K) defined over arbitrary commutative ring K.
This graph is a bipartite graph with the point set P=Kn and line set L=Kn (two copies of a Cartesian power of K are used). It is convenient to use brackets and parenthesis to distinguish tuples from P and L.
So, (p) = (p1, p2, …, pn) ϵ Pn and [l] = [l1, l2, …, ln] ϵ Ln. The incidence relation I = A(n,K) (or corresponding bipartite graph I) can be given by condition p I l if and only if the equations of the following kind hold: p2 – l2 = l1p1 p3 – l3 = p1l2, p4 – l4 = l1p3, p5 – l5 = p1l4, … , pn – ln = p1ln-1 for odd n and pn – ln = l1pn–1 for even n.
They were intensively used for the constructions of LDPC codes for satellite communications and cryptographic algorithms.
In the case of K=Fq, q > 2 of odd characteristic graphs A(n, Fq), n > 1 form a family of small world graphs because their diameter is bounded by linear function in variable n. We can consider an infinite bipartite graph A(K) with points (p1, p2, …, pn, …) and lines [l1, l2, …,ln, …]. If K, |K| > 2 is an integrity then A(K) is a tree and A(n, K), n=2,3,… is its algebraic approximation of large girth.
We refer to the first coordinates p1=ῤ((p)) and l1=ῤ([l]) as colors of vertices of A(K) (or A(n, K)). It is easy to check that each vertex v of the graph has a unique neighbor Na(v) of selected colour a. So the walk of length 2k from vertex (0,0,…) will be given by the sequence w of colours of its elements b1, a1, b2, a2, …, bk, ak.
It will be the walk without repetition of edges if 0 ≠ a1, ai ≠ ai+1 and bi ≠ bi+1 for i=1, 2,…, k-1. So we can identify walks from 0 point of even length point with sequence of kind w. Let w’=(b’1, a’1, b’2, a’2, …, b’s, a’s).We define the composition u of w and w’ as the sequence u=(b1, a1, b2, a2, …,bk, ak, b’1 + ak, ak + a’1, b’2 + ak, …, b’s + ak, a’s + ak). If w and w’ are paths and b’1 + ak ≠ bk then u is also a path.
Let BP(K) be a semigroup of all walks with this operation. One can identify empty string with the unity of BP(K).We use term branching semigroup for BP(K). 3.1.
Let us take graph A(n, K) together with A(n, K[x1, x2, …, xn]). For each element w from BP(K) we consider a walk ∆(w) in A(n, K[x1, x2, …, xn]) with starting point (x1, x2, …, xn) where xi are generic elements of K[x1, x2, …, xn] and special colors of vertices x1 + b1, x1 + a1, …, x1 + bk, x1 + ak. Let p’=dest(∆(w)) be a destination, i. e. a final point of this walk. The destination has coordinates (x1 + ak, f1(x1, x2), f2(x1, x2, x3), …, fn1(x1, x2, …, xn) where f1 are elements of K[x1, x2, …, xn]. We consider the transformation nή(w) of P=K n defined bythe rule x1 → x1 + ak, x2→f1(x1, x2), x3 → f2(x1, x2, x3), …, xn→ fn-1(x1 x2, …, xn).This transformation is bijective map of Kn to itself. It is an element of affine Cremona group CG(Kn) of elements from Aut(K[x1, x2, …, xn]) acting naturally on Kn. The inverse for this map is nή(w)-1 which coincides with nή(w’) for w’ =Rev(w)=(-at ,b1-at, a2-at, b2-at, …, bt-at).We refer to Rev(w) as reverse string for w from BP(K).
Proposition 2.1.1 [
We refer to nή as compression map and denote nή(BP(K)) as GA(n, K). Degree of element g of Cremona group CG(Kn) of kind xi→gi(x1, x2, …, xn) is the maximal degree of polynomials gi.
Theorem 2.1.1 [
It means that subgroup G of kind TGA(n,K)T–1 where T is an element of AGLn(K) can be used efficiently as a platform for the implementation of protocols of Noncommutative Cryptography. 3.2.
Let K be a finite commutative ring with the unit such that multiplicative group K* of regular elements of the ring contains at least 2 elements. We take Cartesian power nE(K) = (K*)n and consider an Eulerian semigroup nES(K) of transformations of kind x1 → ϻ1x1 a(1,1)x2 a(1,2) … xm a(1,n), x2 → ϻ2x1a(2,1)x2 a(2,2) … xn a(2,n), (1) … xn → ϻnx1 a(n,1) x2 a(n,2) … xn a(n,n), where a(i,j) are elements of arithmetic ring Zd, d=|K*|, ϻiϵK*. 3.3.
Let nEG(K) stand for Eulerian group of invertible transformations from nES(K). It is easy to see that the group of monomial linear transformations Mn is a subgroup of nEG(K). So semigroup nES(K) is a highly noncommutative algebraic system. Each element from nES(K) can be considered as transformation of a free module Kn.
1. Twisted Diffie-Hellman protocol.
Let S be an abstract semigroup which has some invertible elements.
Alice and Bob share element g ϵ S and pair of invertible elements h, h–1 from this semigroup.
Alice takes positive integer t = kA and d = rA and forms h-dghd = gA. Bob takes s = kB and p = rB. and forms h-pgshp = gB. They exchange gA and gB and compute collision element X as Ag = h-dgBthd and Bg = h-pgAs hp respectively.
2. Inverse twisted Diffie-Hellman protocol. Let S be a group.
Correspondents follow the scheme 1 with the inverse element g ϵ nEG(K) and Alice sends h–dg–thd = gA to Bob and she gets h–pgshp = gB from him. They use the same formulae for Ag and Bg. But in the new version these elements are mutual inverses. Alice has X but Bob possesses X–1.
Both schemes can be implemented with the multivariate platforms S=TGA(n,K)T–1 and nES(K).
Algorithm 2.3.1. Correspondents executes pairs of directed twisted DH protocols with platforms P1 = nES(K) and P2 = TGA(n,K)T–1. Assume that they have outputs H and X.
Each of correspondents have HX of linear degree Θ(n) and density Θ(n4).
They can compute standard form of G=HX, or use two step procedure to compute G(p) as 1p = H(p) and 2p = X(1p).
Remark 2.3.1 The density of HX is the number of monomial terms of this map in its standard form. It is function of the length of reimage of X under the homomorphism ή’ sending u from BP(K) to Tnή(u)T–1. It depends on d(HX)=d(X)=l(ή’–1 (X)).
Parameter d(X) depends on kA, kB, rA, rB, ή’–
1(g), ή’-1(h) and linear transformation T of the
protocol with the platform TGA(n,k)T–1 [
Thus, adversary does not able to estimate d(HX).
Results of computer simulation demonstrate connection between d(HX) in the case of field Fq of characteristic 2.
Table 1 corresponds to the case of sparse matrix T eith 2n – 1 no zero entries. Table 2 reflects the case of the matrix with n2 nonzero entries.
Algorithm 2.3.2. Correspondents executes pairs of inverse twisted DH protocols with platforms P1 = nES(K) and P2 = TGA(n,K)T–1. Assume that Alice has outputs H and X, Bob has H–1 and X–1 from P1 and P2 respectively. Correspondents use space of plaintexts (K*)n and space of ciphertexts Kn.
Alice and Bob encrypt via HX and H–1X–1 and decrypt via XH and X–1 H–1.
Remark 2.3.2. In the case of inverse protocols. The access control does not use the extraction of information from knowledge base B. Alice enters the access password P and sends HX(P) it to Bob. He restores the P and enters B.
Alternatively Bob enters the access password P andsends H–1X–1(P) to Alice. She restores P and puts as entrance rule to the system.
Usage of transformations of kind HX as in
algorithm 2 in the form of public key was
considered in [
Multivariate Cryptography started from studies of bijective transformations G of a vector space (Fq)n. as possible encryption tools. One can increase number of variables n in the equation of kind G(x) = b and rewrite the condition of existence of solution for this equation in the form G’(y) = b’ where G’ is quadratic transformation of V = (Fq)m where m is essentially larger than n, y and b’ are vectors from V.
The complexity of initial and rewritten systems of equations are essentially differs. Anyway this possibility motivates studies of quadratic maps as tools for Public Key Cryptography.
All algorithms of Multivariate Cryptography under NIST investigation were based on quadratic equations and were not selected as finalists. The first four winners of the NIST competition are described in term of Lattice based Cryptography.
We have to mention that NIST project compares implementations of some public keys as products of Software Engineering. On the level of Theoretical Computer Science all 5 classic direction of Post Quantum Cryptography inclusive Multivariate Cryptography have future perspectives because they are based on known NP-hard problems. One of such problems is about finding solution of nonlinear system of m = m(n) equations in n variables.
We already mention that restriction on the case of quadratic equations is not well motivated. Outcomes of NIST project motivates for search of efficient and secure public keys based on multivariate transformation of unbounded degrees of affine space Kn defined over finite commutative ring K.
Noteworthy that some efficient public keys
over finite fields and arithmetical rings Zm are
suggested in [