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 from two largest Schubert cells. It differs from the known algorithms of Code Based Cryptography and can be considered as the first attempt to combine ideas of this area with the approach of Multivariate Multivariate cryptography, code base cryptography, projective geometry, largest
Schubert cell, symbolic computation.
Finite projective geometries were traditionally used for the construction of algorithms of Coding Theory [1]. Their applications to other areas of Information Security have been published (see [2], [3] devoted to Network Coding). In particular, it was used in Cryptography (see [4], where projective geometry were used for authentication protocols).
widely used as tools for secret sharing.
Additionally they can be used for the design of some stream ciphers of multivariate nature and protocols of Noncommutative Cryptography (see [5] and further references). We introduce the first graph based multivariate public keys with bijective encryption maps generated via special walks on incidence graph of projective geometry.
of Standartisation Technology (NIST, 2017) has started the standardisation process of possible Post-Quantum Public keys aimed for the purposes to be (i) encryption tools, (ii) tools for digital signatures (see [6], [7]).
competition
started. In the category of
For the task (i) multivariate algorithm was not selected, single multivariate candidate is ”The
(RUOV) digital signature method. As you see RUOV algorithm is investigated as appropriate instrument for the task (ii). During the Third Round some cryptanalytic instruments to deal with ROUV were found (see [8], [9]). That is why different algorithms were chosen at the final stage. In
2022 first four winners of
NIST
standardisation competition were chosen. They all
are lattice based algorithms. Noteworthy that all
multivariate NIST candidates were presented by
multivariate rules of degree bounded by constant
(
investigations of alternative options in
2023 Copyright for this paper by its authors. Multivariate Cryptography oriented on encryption tools for
(a) The work with the space of plaintexts Fqn and its transformation G of linear degree cn, c > 0 on the level of stream ciphers or public keys.
(b) The usage of 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.
Some ideas in directions of (a) and (b) are presented in [10].
Alternatively we hope that classical multivariate public key approach (see [11]), i. e. the usage of multivariate rules of degree 2 is still able to bring reliable encryption algorithms.
In this paper we suggest new quadratic multivariate public rules defined in terms of Projective Geometry. Recall that multivariate public rule G has to be given in its standard form xi → gi(x1, x2, …, xn), where polynomials gi are given via the lists of monomial terms in the lexicographical order.
The missing definitions of graph-theoretical concepts which appear in this paper can be found in [12]. All graphs we consider are simple graphs, i. e. undirected without loops and multiple edges. Let V(G) and E(G) denote the set of vertixes and the set of edges of G respectively. When it is convenient, we shall identify G with the corresponding anti-reflexive binary relation on V(G), i.e. E(G) is a subset of V(G) × V(G) and write vGu for the adjacent vertexes u and v (or neighbours). We refer to |{x ∈ V (G)|xGv}| as degree of the vertex v.
The incidence structure is the set V with partition sets P (points) and L (lines) and symmetric binary relation I such that the incidence of two elements implies that one of them is a point and another one is a line. We shall identify I with the simple graph of this incidence relation or bipartite graph. The pair x, y, x ∈ P, y ∈ L such that xIy is called a flag of incidence structure I.
Projective geometry n−1PG(Fq) of dimension n – 1 over the finite field Fq, where q is a prime power, is a totality of proper subspaces of the vector space V = Fqn of nonzero dimension. This is the incidence system with type function t(W) = dim(W), W ∈ n−1PG(Fq) and incidence relation I defined by the condition W1IW2 if and only if one of these subspaces is embedded in another one.
We can select standard base e1, e2, …, en of V and identify nPG(Fq) with the totality of linear codes in Fqn. The geometry nΓ(q) =n−1 PG(Fq) is a partition of subsets nΓi(q) consisting of elements of selected type i, i = 1, 2, …,n – 1.
We assume that each element of V is presented in the chosen base as column vector (x1, x2, …, xn). Let U stands for the unipotent subgroup of automorphism group PGLn(Fq) consisting of lower unitriangular matrices. Let us consider orbits of the natural action of U on the projective geometry nPG(Fq). They are known as large Schubert cells. Each of orbits on the set Γm(Fq) contains exactly one symplectic element spanned by elements ei1, ei2, …, eim. So the number of orbits of (U, Γm(Fq)) equals to binomial coefficient C(n, m). Noteworthy that the cardinality of nΓm(Fq) is expressed by Gaussian binomial coefficient. Unipotent subgroup U is generated by elementary transvections xi,j(t), i < j, t ∈ Fq. If we select i and j then elements of kind xi,j(t) form root subgroup Ui,j corresponding to the positive root ei − ej of root system An.
Let J be a proper subset of {1, 2, …, n} = N, JS be Schubert cell containing symplectic subspace WJ spanned by ej ∈ J, ∆(J) = {(i, j)|i ∈ J, j ∈ N − J, i < j}. Then a subgroup U(J) generated by root subgroups Ui,j, (i, j) ∈ ∆(J) of order qk, k = |∆(J)| acts regularly on JS. It means that we can identify JS and U(J). Noteworthy that each Γm(Fq) has a unique largest Schubert cell of size qm(n – m), it is JS for J = {n, n – 1, n – 2, …, n – m + 1}. We denote this cell as mLS(q).
We consider the bipartite graph m,kIn(Fq) of the restriction of I onto disjoint union mLS(Fq) and kLS(Fq). It is bipartite graph with bidegrees qr and qs where r = |∆({n, n – 1, n – 2, …, n – m + 1}) – ∆({n, n – 1, n – 2, …, n – m + 1}) ∆({n, n – 1, n – 2, …, n – k + 1})| and s = |∆({n, n – 1, n – 2, …, n – k + 1}) – ∆({n, n – 1, n – 2, …, n – m + 1}) ∆({n, n – 1, n – 2, …, n – k + 1})|.
We refer to m,kIn(q) as Cellular Schubert graph and denote it as CSnm,k(Fq) graph. In particular case n = 2m + 1, k = m these graphs are known as Double Schubert graphs [13].
Let K be a commutative ring. We consider group U = Un(K) of lower unitriangular n × n matrices with entries from K. Let ∆ be the totality of all entries of (i, j), 1 ≤ i < j ≤ n, i. e. totality of positive roots from An. We identify element M from Un(K) with the function f : ∆ → K such that f (i, j) = mi,j. The restriction M|D of M on subset D of ∆ is simply f|D.
For each proper nonempty subset J of {1, 2, …, n} we define U (J) as totality of matrices M = (mi,j) from U such that (i, j) ∈ ∆ – ∆(J) implies that mi,j = 0.
We define incidence system n−1PG(K) as totality of pairs (J, M), M ∈ U(J) with type function t(J, M) = |J and incidence relation given by conditions (1J,1M)I(2J,2M) if and only if one of subsets 1J and 2J is embedded in another one and (1M − 2M)|∆(1J)∩∆(2J) = 1M × 2M − 2M × 1M.
We refer to this incidence system as projective geometry scheme over commutative ring K. If K = F is the field then n−1PG(F) coincides with n – 1dimensional projective geometry over F, i. e. totality of proper nonzero subspaces of the vector space Fn (see [14]).
The reader can find similar interpretations of Lie geometries and their Schubert cells in [15], [16], their generalisations via pairs of type (irreducible root system, commutative ring K) are presented in [17] and [5]. The concept of large and small Schubert cell in the classical case of field is presented in [18], [19].
We introduce Γm(K), mLS(K) and graphs CSm,k(Fq) for m = 1, 2, …, n − 1 via simple substitution of K instead Fq. We refer to disjoint union of mLS(K), m = 1, 2, …, n − 1 with the restriction of incidence relation I and type function t on this set as Schubert geometry scheme of type An over commutative ring K. We refer to elements of this incidence system as linear codes of Schubert type. We can define Schubert schemes over other Dynkin-Coxeter diagrams.
Let K be a commutative ring. We refer to an incidence structure with a point set P = Ps,m = Ks+m and a line set L = Lr,m = Kr+m as linguistic incidence structure Im(K) of type (r, s, m) if point x = (x1, x2, …, xs, xs+1, xs+2, …, xs+m) is incident to line y = [y1, y2, …, yr, yr+1, yr+2, …, yr+m] if and only if the following relations hold a1xs+1 + b1yr+1 = f1(x1, x2, …, xs, y1, y2, …, yr) a1xs+2 + b2yr+2 = f2(x1, x2, …, xs, xs+1, y1, y2, …, yn, yr+1) … amxs+m+bmyr+m = fm(x1, x2, …, xs, xs+1, …, xs+m, y1, y2, …, yr, yr+1, …, yr+m) where aj and bj, j = 1, 2, …, m are not zero divisors, and fj are multivariate polynomials with coefficients from K. Brackets and parenthesis allow us to distinguish points from lines (see [20], [5]).
The colour ρ(x) = ρ((x)) (ρ(y) = ρ([y])) of point (x) (line [y]) is defined as projection of an element (x) (respectively [y]) from a free module on its initial s (relatively r) coordinates. As it follows from the definition of linguistic incidence structure for each vertex of incidence graph there exists the unique neighbour of a chosen colour.
We refer to ρ((x)) = (x1, x2, …, xs) for (x) = (x1, x2, …, xs+m) and ρ([y]) = (y1, y2, …, yr) for [y] = [y1, y2, …, yr+m] as the colour of the point and the colour of the line respectively.
For each b ∈ Kr and p = (p1, p2, …, ps+m) there is the unique neighbour of the point [l] = Nb(p) with the colour b. Similarly, for each c ∈ Ks and line l = [l1, l2, …, lr+m] there is the unique neighbour of the line (p) = Nc([l]) with the colour c. We refer to operator of taking the neighbour of vertex accordingly chosen colour as neighbourhood operator.
On the sets P and L of points and lines of linguistic graph we define jump operators 1J = 1Jb(p) = (b1, b2, …, bs, p1, p2, …, ps+m), where (b1, b2, …, bs) ∈ Ks and 2J = 2Jb([l]) = [b1, b2, …, br, l1, l2, …, lr+m], where (b1, b2, …, br) ∈ Kr. We refer to tuple (s, r, m) as type of the linguistic graph I.
We say that linguistic graph has degree d, d ≥ 2 if maximal degree of nonlinear multivariate polynomials fi, i = 1, 2, …, m is d. Noteworthy, that the path v0, v1, …, vk in the linguistic graph Im is determined by starting vertex v0 and colours of vertexes v1, v2, …, vk such that ρ(vi) /= ρ(vi+2) for i = 0, 1, …, k − 2. We can consider graph Im(K) together with I˜m = Im(K[y1, y2, …, yl]) defined by the same polynomials fi, i = 1, 2, …, m with coefficients from K.
Assume that l = m + s. We can consider the path of length 2k with starting point (y1, y2, …, ys, ys+1, ys+2, …, ym) and colours G1 = (1g1(y1, y2, …, ys), 1g2(y1, y2, …, ys), …, 1gr(y1, y2, …, ys)), H1= (1h1(y1, y2, …, ys), 1h2(y1, y2,..., ys), …, 1hs(y1, y2, …, ys)), G2 = (2g1(y1, y2, …, ys), 1g2(y1, y2, …, ys), …,
We define degree of tuple (g1, g2, …, gd) ∈ K[x1, x2, …, xl]d as maximal degree of polynomials gi, i = 1, 2, …, d. The following two statements are proven in [5].
Theorem 1. Let K be a commutative ring. Cellular Schubert graph CSnm,k(K) is a linguistic graph of degree 2 of type (r, s, p) where r = |∆({n, n − 1, n − 2, …, n − m + 1}) − ∆({n, n − 1, n − 2, …, n − m + 1}) ∩ ∆({n, n − 1, n − 2, …, n − k + 1})|, s = |∆({n, n − 1, n − 2, …, n − k + 1}) − ∆({n, n − 1, n − 2, …, n − m + 1}) ∩ ∆({n, n − 1, n − 2, …, n − k + 1})| and p = |∆({n, n − 1, n − 2, …, n − m + 1}) ∩ ∆({n, n − 1, n − 2, …, n − k + 1})|.
Theorem 2. Let CSnm,k(K) be a Cellular Schubert as in the previous statement. Then transformations Pas(G1, G2, …, Gj, H1.H2, …, Hj), j ≥ 1 of the affine space Ks+p such that deg(Hi) = 1, deg(Gi) = 1, i = 1, 2, …, j are quadratic multivariate maps of this space into itself. on
As usually we have to describe procedures for the owner of the key (Alice) and public user Bob. We start from the generating procedure for the multivariate map.
Alice selects parameter n, constants α and β
from open interval (
She sets parameters m = [αn + a] and k = [βn + b], where parenthesis denote the flow function. Alice takes finite field F = F2t, t ≥ 32.
Alice computes parameter s, r and p of the
linguistic graph CSnm,k(K). She selects the length
of path j. Alice will use vector space Fs+p as space
of plaintexts. Thus she selects square matrices A1,
A2, …, Aj of dimensions s × s and matrices B1, B2,
…, Bj of dimensions r × s. Alice takes rows of
Ai(y1, y2, …, ys)T as linear forms ihl(y1, y2, …, yn)
for i = 1, 2, …, j, l = 1, 2, …, s and Bi(y1, y2, …, ys)T
to get linear forms igl(y1, y2, …, ys), i = 1.2, …, j, l
= 1, 2, …, r. Thus she constructed Hi and Gi for
the computation of the path in the graph CSnm,k(F
[y1, y2, …, ys, ys+1, …, ys+p]) and transformation
Pas(G1, G2, …, Gj, H1, H2, …, Hj) of kind (
After creation of the point (p) = (jh1, jh2, …, jhs, fs+1, fs+2, …, fs+m) of the graph CSnm,k(F [y1, y2, …, ys, ys+1, …, ys+p]). Alice uses jump operator to get 1Jb(p) with b formed in the following way.
She divide variables into two groups y1, y2, …,
ys(
Alice takes map D of kind y1 → y12, y2 → y22,
…, ys(
ys(
ys → as,1y1 + as,2y2 + ··· + as,s(
Noteworthy that the restriction Q of E on
variables y1, y2, …, ys(
The order of cyclic group generated by E′
which is the restriction of E on variables y1, y2, …,
ys is multiple of m × 2s−s(
Alice selects two elements 1T and 2T of affine group AGLs+p(F ). and computes the superposition E˜ = 1TE2T in its standard form y1 → f˜1(y1, y2, …, ys+p), y2 → f˜1(y1, y2, …, ys+p), … ys+p → f˜1(y1, y2, …, ys+p).
She presents multivariate rule E˜ to public users.
The inverse of E˜ has polynomial degree ≥ 2m−1. Noteworthy that the choice 2T = 1T−1 insures that cyclic group generated by E˜ has order multiple to m × (2m − 1).
Thus public user (Bob) works with the space of plaintexts Fqd, d = p + s. He is able to encrypt his plaintext in time O(d3).
Let us consider the private key procedure for the decryption. Assume that Alice gets the ciphertext c = (c1, c2, …, cs+p).
Step 1. She treats it as column vector and computes T2−1(c) = (q1, q2, …, qs, qs+1, …, qs+p).
Step 2. Alice uses affine transformation T and matrix B to solve the following equations.
E′(z1, z2, …, zs) = c1, E′(z1, z2, …, zs) = c2, … E′(z1, z2, …, zs) = cs.
Assume that zi = di, i = 1, 2, …, s is the solution.
Step 3. She computes numerical colours Gt(d1, d2, …, ds) = (ta1, ta2, t ar) = ta and Ht(d1, d2, …, ds) = tb for t = 1, 2, …, j.
Step 4. Alice forms the point 1p of the graph CSnm,k(F) in the form (jb1, jb2, …, jbs, qs+1, qs+2, …, qs+p).
Step 5. She computed the path in this graph with the starting point 1p and consecutive colours ja, j−1b, j−1a, j−2b, j−2a, …, 1b, 1a, 0b = (d1, d2, …, ds). Let 2p be the final vertex of the computed path with the colour 0b.
Step 6. Alice treats 2p as column vector and computes the plaintexts as T1−1(2p).
We can define mentioned above Double Schubert Graph DS(k, K) over commutative ring K simply as incidence structure defined as disjoint union of partition sets PS = Kk(k+1) consisting of points which are tuples of kind x = (x1, x2, …, xk, x1,1, x1,2, …, xk,k) and LS = Kk(k+1) consisting of lines which are tuples of kind z = [z1, z2, …, zk, z11, z12, …, zk,k], where x is incident to z, if and only if xi,j − zi,j = xizj for i = 1, 2, …, k and j = 1, 2, …, k. It is convenient to assume that the indexes of kind i, j are placed for tuples of Kk(k+1) in the lexicographical order.
Remark. The term Double Schubert Graph is chosen, because points and lines of DS(k, Fq) can be treated as subspaces of Fq2k+1 of dimensions k + 1 and k, which form two largest Schubert cells. Recall that the largest Schubert cell is the largest orbit of group of unitriangular matrices acting on the variety of subsets of given dimension.
We define the colour of point x = (x1, x2, …, xk, x1,1, x1,2, …, xk,k) from PS as tuple (x1, x2, …, xk) and the colour of a line y = [z1, z2, …, zk, z1,1, z1,2, …, zk,k] as the tuple (z1, z2, …, zk). For each vertex v of DS(k, K), there is the unique neighbour y = Na(v) of a given colour a = (a1, a2, …, ak).
Let us consider the list of variables corresponding to coordinates of the point. So we get y1, y2, …, yk , y1,1, y1,2, …, yk,k. We will use the ring R = K[y1, y2, …, yk, y1,1, y1,2, …, yk,k].
Let D˜S(k, K) = DS(k, R). To define Pas = Pas(G1, G2, …, Gj, H1, H2, …, Hj) and construct the path with starting point (y1, y2, …, yk, y11, y12, …, yk,k) and the symbolic colours Gi(y1, y2, …, yk) = ib1y1 + ib2y2 + ··· + ibkyk, Hi(y1, y2, …, yk) = ia1y1 + ia2y2 + ··· + iakyk, ai ∈ K, bi ∈ K are used.
The complexity of computation of T1PasT2 is determined by the time of computation of the path u, 1u, 2u, …, 2ju in the graph DS(k, R) with the starting point u = (T1(y1), T1(y2), …, T1(yk), T1(y1,1), T1(y1,2), …, T1(yk,k)) and colours
G1(u1, u2, …, uk, u1,1, u1,2, …, uk,k), H1(u1, u2, …, uk, u1,1, u1,2, …, uk,k),
G2(u1, u2, …, uk, u1,1, u1,2, …, uk,k), H2(u1, u2, …, uk, u1,1, u1,2, …, uk,k), …,
Gj(u1, u2, …, uk, u1,1, u1,2, …, uk,k), Hj(u1, u2, …, uk, u1,1, u1,2, …, uk,k).
The key parameter here is j. Let us assume that j = O(k). The computation of selected coordinate of final point of the walk requires computation of GiHi depending k + k2 for each parameter i and adding obtained quadratic polynomials. Thus it takes 2k4j operations of addition and multiplication in K and the complexity is O(k5). We have to execute this procedure k2 + k times. So the complexity of public rule development is O(k7) or O(d3+1/2), where d = k2 + k is the dimension of the space of plaintexts.
Public user encrypts in time O(d3).
Let us estimate the complexity of private encryption procedure of Alice. She applies the inverse of T2 to the obtained ciphertext c and gets 1c = T2−1(c). It requires O(d2) elementary operations in the field K. Alice has to solve the system of k equations to find the reimage of 1c of the map E′ with the usage of known matrices T and B of size ≤ k × k. Getting the solution z = (d1, d2, …, dk) of the system of equations requires less than O(d2) operations. It allows her to compute colours gi = Gi(d1, d2, …, dk), hi = Hi(d1, d2, …, dk), i = 1, 2, …, j.
Alice changes the first coordinate of T2−1(c) for hj and gets the point 2ju. She computes the chain with the starting point 2ju and further consecutive members with colours gj, hj−1, gj−1, hj2 , …, g1, h1, z. Alice gets the final point u of the chain with the colur z in time less than O(d2). Finally she need O(d2) operation to compute the ciphertext as T1−1. So the complexity of entire private encryption procedure is O(d2).
As we mentioned above graph CS2k+1k,k (K) is isomorphic to Double Schubert graph DS(k, K). It is easy to check that theoretical complexity of described above public key algorithm based on graph CS2k+α+β+1k+α,k+β, where α and β are nonnegative constants, is the same with the case of the DS(k, K). The dimension of the space of plaintext is d = (k + α + β) × (α + 1). Cost of generation of public rule is O(d3+1/2), complexity of private key decryption is O(d2), public encryption costs O(d3).
We select this class of algorithms and K = F2³² for the implementation.
Modern public key cryptography is based on the complexity of hard unsolved problems. Especially important is the fundamental assumption of cryptography that there are no polynomial-time algorithms for solving any NPhard problem. A consequence of this assumption is that there are cryptographically interesting problems that are hard to solve in the quantum setting. Each of five core directions of Post Quantum Cryptography is based on the complexity of some NP-hard problem. The paper is connected with the following two directions.
Code-based cryptography: cryptographic primitives based on the hardness of decoding random linear codes are historically the first postquantum systems. Since the late 1970s schemes like McEliece encryption have withstood a long series of cryptanalytic attacks. In order to embed a trapdoor that enables decryption one converts a structured code with good decryption capabilities like a Goppa code by linear transformations into a “random-looking” code C. An attacker now faces the problem to either distinguish C from a purely random code using the properties of the underlying structured code or to directly decode C. The last approach leads to the best known generic attacks. Recent significant progress on decoding binary linear codes C of dimension n leads to a new trend in code-based cryptography based on the usage of linear codes that are different than Goppa code initially proposed by McEliece (MDPC codes, Rank codes, quasicyclic codes, and others). New approach promises to decrease the size of the public key.
Multivariate cryptography is usually defined as the set of cryptographic schemes using the computational hardness of the Polynomial System Solving problem over a finite field. Solving systems of multivariate polynomial equations is proven to be NP-hard or NP-complete. That is why these schemes are often considered to be good candidates for post-quantum cryptography. The first multivariate scheme based on multivariate equations was introduced by Matsumoto and Imai in 1988. Later J. Patarin found nice and efficient cryptanalytic solution to break this scheme (see [11]). Two following schemes suggest the most robust solutions. They are HFE (Hidden Field Equations) and UOV (Unbalanced Oil and Vinegar), both developed by J. Patarin in the late 1990s. Special variants of theses schemes have been submitted to the postquantum standardization process organized by NIST. During this process new cryptanalytic methods to break these cryptosystems were found (see [7]). It motivates development of new public keys of Multivariate Cryptography.
We suggest the usage of the bridge between Coding Theory and Multivariate Cryptography based on the pairs of kind (PGn(Fq), PGn(Fq[x1, x2, …, xm]) where PGn(Fq) is classical finite ndimensional projective geometry and PGn(Fq[x1, x2, …, xm]) is its natural analog defined over multivariate ring Fq[x1, x2, …, xm]. For the construction of public key a hidden problem to find a path between two vertexes of the incidence graph of PGn(Fq[x1, x2, …, xm]) is used. We take these vertexes in general position, i.e. they are of different type and belong to distinct largest Schubert cells. In the case of finite field F2t the multivariate rule is given by the system of quadratic equations. The choice of large t (like 32, 64) insures that the inverse map has a very large polynomial degree.
The bijective public rule can be used as instrument of encryption as well as for making digital signatures. In case of digital signatures the usage of nonbijective modifications of E˜ as above is also possible.
This research is supported by British Academy Fellowship for Researchers at Risk 2022.