Studies of linear codes in terms of finite projective geometries form traditional direction in Coding Theory. Some applications of projective geometries are known. We introduce new 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 Proceedings ITTAP'2023: 3rd International Workshop on Information Technologies: Theoretical and Applied Problems, November 22-24, Proceedings
Multivariate
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). Nowadays finite geometries are 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. The tender of US National Institute of Standardisation 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]).
In July 2020 the Third Round of the competition started. In the category of Multivariate Cryptography (MC) remaining candidates are easy to observe. For the task (i) multivariate algorithm was not selected, single multivariate candidate is ''The Rainbow Like Unbalanced Oil and Vinegar'' (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 July 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 (
2020 Copyright for this paper by its authors. CEUR
ceur-ws.org outcomes motivate investigations of alternative options in Multivariate Cryptography oriented on encryption tools for (a) the work with the space of plaintexts (Fq)n 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 cn r , 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 vertexes 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 v G u 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 x I y 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=(Fq) n of nonzero dimension. This is the
incidence system with type function t(W)=dim(W), W ϵ n-1 PG(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 n-1PG(Fq) with the totality of linear codes in (Fq) n.The geometry n-1ℾ(q)= n-1PG(Fq)
is a partition of subsets n-1ℾ(q) i 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, x1, … , 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 n-1PG(Fq). They are known as large Schubert cells. Each of
orbits on the set ℾm(Fq) contains exactly one symplectic element spanned by elements ei(
Let K be a commutative ring. We consider group U=Un(K) of lower unitriangular n times n matrices with the 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-1. 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 a 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-1-dimensional projective geometry over F, i. e. totality of proper nonzero subspaces of the vector space F n(see [14]). The reader can find similar interpretations of Lie geometries and their Schubert cells, their generalisations via pairs of type (irreducible root system, commutative ring $K$) are presented in [5]. The concept of large and small Schubert cell in the classical case of field is presented in [15], [16].
We introduce ℾm(K), mLS(K) and graphs CS m,k n(K) 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-1 over commutative ring K. We refer to elements of this incidence system aslinear codes of Schubert type. We can define Schubert schemes over other DynkinCoxeter diagrams.
Let K be a commutative ring. We refer to an incidence structure with a point set P=Ps,m=Km+s and a line set L=Lr,m=Km+r as linguistic incidence structure I m(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) a2xs+2+b2yr+2=f2(x1, x2, ..., xs, xs+1, y1, y2, … , yr, 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 [5] and further references).
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 point (p) is line [l] are adjacent in the linguistic graph I if 1Jb(p)I 2Jc[l] for some colours b ϵKs and c ϵKr. Let ψ stands for the adjacency relation of the linguistic graph. 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.
Let us consider the sequence of colours c(
Let v0=(x) be a general point of the graph I then for the vertices v1=1Jc(
We consider the tuple of colours c(
We refer to the sequence of vertexes v1 =1J(v0), v2=Nc(
For each positive integer l we can consider graph Im(K) together with lIm= 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 walk on the adjacency graph ψ(K[y1, y2, …, yl]) of length 4t+1 with
starting point (y1, y2, …, ys, ys+1, ys+2, …, ym+s) and colours c(
Assume that c(t)=(h1(y1, y2,...,ys), h2(y1, y2,…, ys), …, hs(y1, y2,…, ys)).
Then v1=(h1, h2, …, hs, g1, g2,…, gm). Let us consider the polynomial map I(K),c Pass, cϵ K[x1,x2,…, xs] (2t+1)s+2rt of K s+m to itself which sends (y1, y2,…,ys, ys+1,…, ys+m) to vt, i. e. the map y1 → h1(y1, y2,...,ys), y2 → h2(y1, y2,...,ys),…, ys → hs(y1, y2,...,ys), ys+1 → g1(y1, y2,...,ys, ys+1, ys+2,...,ys+m), ys+2 → g2(y1, y2,...,ys, ys+1, ys+2,...,ys+m),…, ys+m → gm(y1, y2,...,ys, ys+1, ys+2,...,ys+m),
It is easy to see that this transformation is bijective if and only if the map y1 → h1(y1, y2,...,ys), y2 → h2(y1, y2,...,ys), …, ys → hs(y1, y2,...,ys), is bijective on Ks ([5] ). Defined above transformations form a semigroup I(K)SP of multivariate transformation. Some basic properties of this semigroup are discussed in [5].
Of course we can use lines instead of points and define another semigroup I(K)Sl formed by transformation of kind I(K),cPass, cϵ K[x1,x2,…, xs] (2t+1)r+2 ts acting on the variety Km+r.
We can treet the sequence c from K[x1,x2,…, xs] l as the tuple of its coordinates ci from K[x1,x2,…, xs] and define degree of c as of polynomials ci(x1, x2,…, xs). The following two statements are proven in [5]. Theorem 1.
Let K be a commutative ring. Cellular Schubert graph CSm,kn(K) is a linguistic graph of degree 2 of type (s, r, p) where s=|∆({n, n-1, n-2, …, n-m+1})- ∆({n, n-1, n-2, …, n-m+1}) ∩∆({n, n-1, n-2, …, n-k+1}) |, r=|∆({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 CSm,kn(K)be a Cellular Schubert as in the previous statement.Then transformations I(K),c Pass, cϵ K[x1,x2,…, xs] (2t+1)s+2rt, t ≥5 , cϵK[x1,x2,…, xs] (2t+1)s+2rt of the affine space Ks+p such that deg(c(i))+deg(c(i+1))≤2 for i=1 mod 2, i<t and deg(c(t))≤2, are elements of Cremona semigroup of degree ≤2. If the lefthand side of one of the written above inequalities is 2 then the degree of the transformation is 2.
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 and a and b are
selected constants. Alice takes finite field F=Fq, q=2d, d ≥32. Alice computes parameter s, r and p of the
linguistic graph CSm,kn(K). She selects the length of path j of kind j=4t+1.Alice will use vector space F s+p as
space of the plaintexts. Thus she selects parameters d1=deg c(
Alice forms maps c(i), i=1, 2, …. , j-1 of kind (f1(y1, y2,…, ys), f2(y1, y2,…, ys),…, fs(y1, y2,…, ys)) or (g1(y1, y2,…, ys), g2(y1, y2,…, ys),…, gr(y1, y2,…, ys)) of degree di. She can form these tuples of polynomials via selection of their coefficients as pseudorandom or genuinely random parameters.
Alice selects linear transformation (y1, y2,…, ys-1)→(y1, y2,…, ys-1)C=(l1(y1, y2,…, ys), l2(y1, y2,…, ys),…,
ls1(y1, y2,…, ys), ys→(ys) 2 ) where C is the matrix of the Singer cycle which is a linear transformation of order
qs-11, (see [17]) and forms c(j) as the tuple (l1(y1, y2,…, ys), l2(y1, y2,…, ys),…, ls-1(y1, y2,…, ys), (ys) 2 ). She
constructs the transformation I(K),c Pass=F of Theorem 2 with selected as above c=(c(
She presents multivariate rule G to public users.
Remark. The choice of cj insures that the inverse map of G has a polynomial degree ≥ 2d-1 (see [13]).
Noteworthy that the choice T2=(T1)-1 insures that cyclic group generated by G has order multiple to qs-1 -1.
Thus public user (Bob) works with the space of plaintexts (Fq) k, k=p+s. He is able to encrypt his plaintext in time O(k3).
Let us consider the private key procedure for the decryption. Assume that Alice gets the ciphertext z=(z1, z2, …, zs+p).
Step 1.
She treats it as column vector and computes (T2) -1(z)=(q1, q2, …, qs , qs+1,..., qs+2, ..., qs+p)=(p). Step 2.
Alice uses the matrix C of the Singer cycle to solve the following equations. l1(x1, x2, ..., xs)=q1, l2(x1, x2, … , xs)=q2,…, ls-1(x1, x2, … , xs)=qs-1, (xs) 2=qs Assume that xi=di, i=1, 2, …, s is the solution.
Step 3.
She computes numerical colours c(i)(d1, d2, …, ds)=(ia1, ia2, …, ias)=(ia) for i=1, 0 (mod 4), i≤j. c(i)(d1, d2, …, ds)=(ib1, ib2, …, ibr)=(ia) for i=2, 3 (mod 4), i<j.
Step 4.
Alice forms the point 1(p) of the graph CSm,kn(Fq). in the form 1Jc(j-1)(p)=(j-1a1, j-1a2, ..., j-1as, qs+1, qs+2, …., qs+p).
Step 5. She computes the path in this Schubert adjacency graph with the starting point 1(p) and other vertexes
Nc(j-2)(1(p))=2v, 2Jc(j-3)(2v)=3v, Nc(j-4)(3v)=4v,…, Nc(
Alice treats v as column vector and computes the plaintexts as (T1) -1(v)=(r1, r2, …, rs+p).
Let us assume the case of presented above public key in the case of finite field Fq of characteristic 2. So the space of plaintext will be a vector space (Fq) m where m=s+p= =O(n2), the colour spaces for points and lines will be the vector spaces (Fq)s and (Fq) r where r=O(n2) and s = O(n2). It will be convenient for us to use parameter n for the estimation of the complexity of decryption procedure for Alice The complexity of computation of the image of T1 I(K),c Pass T2 is determined by the time of computation of the path in the adjacence Schubert graph from the selected point from (Fq)m accordingly to the sequence of numerical colours i(a), i=1, 2,…,j obtained via the specialisation of the tuples c(j) of quadratic polynomials in s variables.
The key parameter for the computation of the complexity is j. The natural selection is j=O(n). Each i(a) can be computed O(n6). So the sequence of numerical colours of length j can be computed in time O(n7). Computation of the values of operators 1J and 2J takes O(n2) elementary operation. The computation of neighbour N(v) of v with colour c will take time O(n4).The repetition of this operation j times costs O(n5). Noteworthy that computation of affine transformation in O(n2) variables takes time O(n4). These arguments evaluate general complexity of the computation of the plaintexts as O(n7).
It means that the complexity of decryption is O(m3.5) where m is the dimension of the space of plaintexts
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 NP-hard 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 (see [20]).
Cryptographic primitives based on the hardness of decoding random linear codes are historically the first post-quantum 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, quasi-cyclic codes, and others). New approach promises to decrease the size of the public key.
Multivariate cryptography (see [18]).
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] or [19]). 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 these schemes have been submitted to the post-quantum 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, …, xn])) where PGn(Fq) is classical finite n-dimensional projective geometry and PGn(Fq[x1, x2, …, xn]) is its natural analogue defined over multivariate ring Fq[x1, x2, …, xn].
For the construction of public key a hidden problem to find a path between two vertexes of the adjacency Schubert graph of PGn(Fq[x1, x2, …, xn] ) 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 Fq, q=2d the multivariate rule is given by the system of quadratic equations. The choice of large d (like d=32, d=64) insures that the inverse map has a very large polynomial degree.
The new bijective public rule can be used as instrument of encryption as well as for making digital signatures. The suggested new public key algorithm is an obfuscation of the multivariate cryptosystem of [13].
This research is supported by the Fellowship of British Academy for RaR.
[13] V. Ustimenko, Linear codes of Schubert type and quadratic public keys of Multivariate
Cryptography, IACR e-print archive, 2023/175. [14] V. A. Ustimenko, On some properties of Chevalley groups and their generalisations, In: Investigations in Algebraic Theory of Combinatorial objects, Moskow, Institute of System Studies, 1985, in Investigations in Algebraic Theory of Combinatorial Objects, Kluwer, Dordrecht (1992) p. 112-119. [15] I. Gelfand, R. MacPherson, Geometry in Grassmanians and generalisationof the dilogarithm, Adv. in Math., 44 (1982), 279-312. [16] I. Gelfand, V. Serganova, Combinatorial geometries and torus strata on homogeneous compact manifolds, Soviet Math. Surv. 42 (1987), 133-168. [17] A. Cossidente, M. J. De Resmini, Remarks on Singer Cyclic Groups and Their
Normalizers, Designs, Codes and Cryptography, 32, 97–102, 2004. [18] J. Ding and A. Petzoldt, "Current State of Multivariate Cryptography," in IEEE
Security & Privacy, vol. 15, no. 4, pp. 28-36, 2017, doi: 10.1109/MSP.2017.3151328. [19] N. Koblitz, Algebraic aspects of cryptography, Springer (1998), 206 p. [20] N. Sendrier, "Code-Based Cryptography: State of the Art and Perspectives," in IEEE Security & Privacy, vol. 15, no. 4, pp. 44-50, 2017, doi: 10.1109/MSP.2017.3151345.