On new key exchange multivariate protocols based on pseudorandom walks on incidence structures
A new key exchange protocol formulated in terms of multivariate cryptography and based on the elaboration of a common walk in the linguistic graph by correspondents is proposed. This algorithm is described in details in the case of a known family of graphs of large girth given by nonlinear equati...
Збережено в:
| Опубліковано в: : | Доповіді НАН України |
|---|---|
| Дата: | 2015 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2015
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/95704 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | On new key exchange multivariate protocols based on pseudorandom walks on incidence structures / U. Romańczuk-Polubiec, V.A. Ustimenko // Доповiдi Нацiональної академiї наук України. — 2015. — № 1. — С. 41-49. — Бібліогр.: 15 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859727955466387456 |
|---|---|
| author | Romańczuk-Polubiec, U. Ustimenko, V.A. |
| author_facet | Romańczuk-Polubiec, U. Ustimenko, V.A. |
| citation_txt | On new key exchange multivariate protocols based on pseudorandom walks on incidence structures / U. Romańczuk-Polubiec, V.A. Ustimenko // Доповiдi Нацiональної академiї наук України. — 2015. — № 1. — С. 41-49. — Бібліогр.: 15 назв. — англ. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | A new key exchange protocol formulated in terms of multivariate cryptography and based on
the elaboration of a common walk in the linguistic graph by correspondents is proposed. This
algorithm is described in details in the case of a known family of graphs of large girth given by
nonlinear equations over a finite field.
Запропоновано новi протоколи обмiну ключами, що формулюються в термiнах алгебраїчної
криптографiї вiд багатьох змiнних та базуються на створеннi кореспондентами спiльного
блукання в лiнгвiстичному графi. Алгоритм детально описано у випадку вiдомої родини
графiв великого обгорту, що задається нелiнiйними рiвняннями над скiнченним полем.
Предложены новые протоколы обмена ключами, сформулированные в терминах алгебраической криптографии от многих переменных и основанные на создании корреспондентами
общего блуждания в лингвистическом графе. Алгоритм детально описан в случае известной
семьи графов большого захвата, заданной нелинейными уравнениями над конечным полем.
|
| first_indexed | 2025-12-01T11:53:18Z |
| format | Article |
| fulltext |
UDC 519.1,514.128
U. Romańczuk-Polubiec, V.A. Ustimenko
On new key exchange multivariate protocols based
on pseudorandom walks on incidence structures
(Presented by Correspondent Member of the NAS of Ukraine O.M. Trofimchuk)
A new key exchange protocol formulated in terms of multivariate cryptography and based on
the elaboration of a common walk in the linguistic graph by correspondents is proposed. This
algorithm is described in details in the case of a known family of graphs of large girth given by
nonlinear equations over a finite field.
Linguistic graphs and their properties. The missing definitions of graph-theoretical con-
cepts, which appear in this paper can be found in [1]. A tactical configuration introduced by
E.H. Moore [2] is a rank two incidence structure I consisting of vp points from the set P and vl
lines from the set L, where each point is incident to s lines, and each line is incident to r points.
We denote the incidence graph of the incidence structure I by Γ = Γ(P,L, I) and call Γ a
tc-graphs, though we shall identify I with the simple graph Γ of this incidence relation, if no
confusion can arise. We define the biregular and bipartite graphs as tc-graphs with bidegrees r, s.
Clearly, the graph Γ has order v = vl + vp (number of vertices) and size e = rvl = svp (number
of edges). We also mean, as usual, that the girth g(Γ) of the graph Γ is the length of the minimal
cycle in the graph, and the diameter of the graph is the maximal distance between two vertices u
and v in the graph, denoted by diam(Γ). The pair {x, y}, x ∈ P , y ∈ L such that xIy is called
a flag of the incidence structure I.
Let K be a finite commutative ring. We refer to an incidence structure I with a point set
Pr = KN and a line set Ls = KN as infinite linguistic tc-graphs LΓ(r, s,K), if the point (x) =
= (x1, x2, . . . , xr, xr+1, xr+2, . . .) ∈ Pr is incident to the line [y] = [y1, y2, . . . , ys, ys+1, ys+2 . . .] ∈
∈ Ls if and only if the following relations hold:
ξ1xr+1 + ζ1ys+1 = f1(x1, x2, . . . , xr, y1, y2, . . . , ys)
ξ2xr+2 + ζ2ys+2 = f2(x1, x2, . . . , xr, xr+1, y1, y2, . . . , ys, ys+1)
. . .
ξixr+i + ζiys+i = fi(x1, x2, . . . , xr+i−1, y1, y2, . . . , ys+i−1)
. . .
Here, ξj and ζj, j = 1, 2, . . . are nonzero divisors, and fj, j = 1, 2, . . . are multivariate polynomials
with coefficients from K. Brackets and parentheses allow us to distinguish points from lines
(see [3, 4]).
For each positive integer m > 2, we obtain an incidence structure Im with a point set
Pr,m = Kr+m and a line set Ls,m = Ks+m as follows: Pr,m and Ls,m are obtained from Pr
and Ls, respectively, by simply projecting each vector into its r+m and s+m initial coordinates
with respect to the above order, respectively. The incidence Im is then defined by imposing
© U. Romańczuk-Polubiec, V.A. Ustimenko, 2015
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2015, №1 41
the first m incidence equations and ignoring all others. The incidence graph corresponding to
the structure Im is denoted by LΓ(r, s,m,K), and we call it the linguistic incidence structure
or linguistic graph. Of course, LΓ(r, s,m,K) is a (|K|r, |K|s)-biregular bipartite graph of order
2|K|r+s+m.
For each positive integer m > n > 1, we consider the standard graph homomorphism φmn of
LΓ(r, s,m,K) onto LΓ(r, s, n,K) defined as a simple projection of each vector from Pr,m and Ls,m
onto its r+n and s+n initial coordinates with respect to the above-mentioned order, respectively.
Let v ∈ LΓ(r, s,m,K) and v′ ∈ LΓ(r, s, n,K) be the vertices of the same type point or line. We
refer the vertex v as a lift of v′, when v′ = φmn (v).
Recall that, for simple graphs Γ1 and Γ2, a graph homomorphism φ of Γ1 to Γ2 is a mapping
between these two graphs that respect their structure. More specifically, φ maps the adjacent
vertices of Γ1 to the adjacent vertices of Γ2.
Proposition 1. Let m > n > 1. The map φmn is a |K|m−n-to-1 surjective graph homomor-
phism from a graph LΓ(r, s,m,K) to a graph LΓ(r, s, n,K).
From the fact that φmn is a graph homomorphism, one can deduce that, for a fixed ring K,
the diameter and the girth of LΓ(r, s, n,K) are nondecreasing functions of n.
Proposition 2. Let m > n > 1, and let K be any commutative ring. Then
diam(LΓ(r, s,m,K)) > diam(LΓ(r, s, n,K), and girth(LΓ(r, s,m,K)) > girth(LΓ(r, s, n,K)).
LetM = {m1,m2, . . . ,md} be a subset of {1, 2, . . . m} (set of indices for the equations), d 6 m
with the standard order. Assume that the equations indexed by elements from M of the kind
ξm1xm1 + ζm1ym1 = fm1(x1, x2, . . . , xr, y1, y2, . . . , ys)
ξm2xm2 + ζm2ym2 = fm2(x1, x2, . . . , xr, xm1y1, y2, . . . , ys, ym1)
. . .
ξmdxmd + ζmdymd = fmd(x1, . . . , xr, xm1 , . . . , xmd−1
, y1, . . . , ys, ym1 , . . . , ymd−1
)
define another linguistic incidence structure IM . Then the natural projections
φmM : (x) → (x1, x2, . . . , xr, xm1 , xm2 , . . . , xmd),
φmM : [y] → [y1, y2, . . . , ys, ym1 , ym2 , . . . , ymd ]
of free modules define the natural homomorphism φ = φmM of the incidence structure Im onto IM .
We refer to ρ = phim∅ as a coloring homomorphism of LΓ(r, s, n,K) onto the complete bipartite
graph Ka,b, a = |Kr|, b = |Ks|. For each line [l] and colour t = [t1, t2, . . . , tr], there is a unique
neighbor (x) ∈ P of the line with the given color ρ(x) = t. Similarly, (p)] and color d =
= [d1, d2, . . . , ds], there is a unique neighbor [y] ∈ L of the point with the color ρ([x]) = d. We
will use the same symbol ρ for the coloring of the linguistic graph IM .
It is clear that, forφ = φmM , the relations ρ(x) = ρ(φ(x)) and ρ(y) = ρ(φ(y)) hold. This
means that φmM is a color-preserving homomorphism of the incidence structure (bipartite graph)
onto another one. We refer to φmM as a symplectic homomorphism and graph LΓ(r, s,M,K) =
= φmM (LΓ(r, s,m,K)) as a symplectic quotient of the linguistic incidence structure Im. In the
case of linguistic graphs defined by the infinite number of equations, we may consider the cases
of symplectic quotients defined by the infinite subset M .
Proposition 3. Let m > d > 1, and let M = {m1,m2, . . . ,md} be a subset of {1, 2, . . . ,m}.
The map φmM is a |K|m−d-to-1 surjective graph homomorphism from a graph LΓ(r, s,m,K) to
a graph LΓ(r, s,M,K).
42 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2015, №1
The color ρ(x) = ρ((x)) (ρ(y) = ρ([y])) of the point (x) (line [y]) is defined as the projection
of an element (x) ([y]) from a free module on its initial r (relatively s) coordinates. We note that
there exists the unique neighbor of a chosen color in a linguistic incidence structure (finite or
infinite) for each vertex of the incidence graph. We can generalize this fact as follows:
Proposition 4. Let v be a vertex in LΓ(r, s,m,K), let u be a vertex in LΓ(r, s, n,K)
(LΓ(r, s,M,K)), and let {φmn (v), u′} be a flag of the incidence structure In (IM , respectively).
Then there exists the unique vertex u ∈ LΓ(r, s,m,K) such that φmn (u) = u′ and {u, v} is a flag
of the incidence structure Im.
For a subgraph H of LΓ(r, s,m,K), we define φmn (H) and φmM (H) to be subgraphs of
LΓ(r, s, n,K) and LΓ(r, s,M,K), respectively. The following proposition allows us to extend
the notation of the graph lift to a tree.
Proposition 5. Let T ′ be a tree in LΓ(r, s, n,K) (LΓ(r, s,M,K)), and let v′ be the a fixed
vertex in T ′. Then, for each lift v of v′ from LΓ(r, s,m,K), there exists the unique tree T in
LΓ(r, s,m,K) such that the vertex v ∈ T and φmn (T ) = T ′ (φmn (T ) = T ′, respectively). Moreover,
the |K|m−n (|K|m−d) trees in LΓ(r, s,m,K), which are preimages of T ′, are pairwise disjoint
vertices.
We note that the set of lifts of T ′ does not depend on the chosen vertex v ∈ T ′, so the above
proposition could be stated as ”Each tree in LΓ(r, s, n,K) and LΓ(r, s,M,K) lifts to |K|m−n
and |K|m−d trees in LΓ(r, s,m,K) and LΓ(r, s,M,K), respectively, which are pairwise disjoint
vertices”. Note also that, in particular, it is true for paths lift to paths for these graphs.
Proposition 6. Let C be a component of LΓ(r, s,m,K), m > n > 1, and let LΓ(r, s,M,K)
be a symplectic quotient. Then φmn (C) and φmM (C) are components of LΓ(r, s,m,K) and
LΓ(r, s,M,K), respectively.
We introduce adjacency relation FIm on the set of flags F(Vm) of the incidence structure Im
with a vertex set Vm = Pr,m∪Ls,m over a commutative ring K as a flag relation (or flag linguistic
graph): the intersection of two distinct flags is a nonempty set (singleton). All vertices forming two
flags F1 = {(x1), [y1]} and F2 = {(x2), [y2]} could be located at the same connected component
of Im, or all of them are from distinct connected components of Im. Assume that the system of
equations G1(x) = g1, G2(x) = g2, . . ., Gt(x) = gt, where gi ∈ K are some constants, defines the
connectivity invariants specified for points (x) ∈ P in the linguistic incidence structure I. For
elements (x1), (x2) ∈ P from the same connectivity component in the graph Im, the following
relations hold: Gi(x1) = Gi(x2), i = 1, 2, . . . , t. The existence of i such that Gi(x1) 6= Gi(x2)
implies that (x1) and (x2) are points from different connected components of the graph Im.
As a consequence of Proposition 1, φmn induce a map on flags of the incidence structure Im,
φ̃mn : FIm → FIn defined by φ̃mn : {u, v} 7→ {φmn (u), φmn (v)}. Similarity, as a consequence of
Proposition 3, φmM induce a map on flags of the incidence structure Im, φ̃mM : FIm → FIM defined
by φ̃mM : {u, v} 7→ {φmM (u), φmM (v)}. It is clear that an edge of LΓ(r, s,m,K) corresponds to some
flag in FIm. So, we have the following proposition that can be stated as edges lift to edges.
Proposition 7. The maps φ̃mn and φ̃mM are |K|m−n-to-1 and |K|m−d-to-1 surjections, respecti-
vely. Moreover, qm−n and qm−d of LΓ(r, s,m,K), which are preimages of a fixed edge of
LΓ(r, s, n,K) and LΓ(r, s,M,K), are pairwise disjoint vertices, respectively.
Family of linguistic graphs D(k,K) We consider the family of graphs D(k,K), where
k > 2 is a positive integer, and K is a commutative ring. Such graphs have been considered in [5]
in the case K = Fq (see [6] for the description of connected components). Let PD and LD be
two copies of Cartesian power KN, where K is the commutative ring, and N is the set of positive
integers. Elements of PD will be called points, and those of LD lines.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2015, №1 43
To distinguish points from lines, we use parentheses and brackets. If x ∈ KN, then (x) ∈ PD
and [x] ∈ LD. It will be also advantageous to adopt the notation for the coordinates of points
and lines introduced in [13] in the case of a general commutative ring K:
(p) = (p0,1, p1,1, p1,2, p2,1, p2,2, p
′
2,2, p2,3, . . . , pi,i, p
′
i,i, pi,i+1, pi+1,i, . . .),
[l] = [l1,0, l1,1, l1,2, l2,1, l2,2, l
′
2,2, l2,3, . . . , li,i, l
′
i,i, li,i+1, li+1,i, . . .].
The elements of P and L can be thought as infinite ordered tuples of elements from K such
that only a finite number of components is different from zero.
We now define a linguistic incidence structure (PD, LD, ID) defined by an infinite system of
equations as follows. We say that the point (p) is incident with the line [l], and we write (p)I[l],
if the following relations between their coordinates hold:
li,i − pi,i = l1,0pi−1,i,
l′i,i − p′i,i = li,i−1p0,1,
li,i+1 − pi,i+1 = li,ip0,1,
li+1,i − pi+1,i = l1,0p
′
i,i
(these four relations are defined for i > 1, p′1,1 = p1,1, l
′
1,1 = l1,1). The incidence structure
(PD, LD, ID) is denoted by D(K). Now, we will say about the incidence graph of (PD, LD, ID),
which has the vertex set PD
⋃
LD and the edge set consisting of all pairs {(p), [l]}, for which
(p)I[l].
For each positive integer k > 2, we obtain a quotient (PD,k, LD,k, ID,k) as follows. First, PD,k
and LD,k are obtained from PD and LD, respectively, by simply projecting each vector into its k
initial coordinates. The incidence ID,k is then defined by imposing k− 1 first incidence relations
and ignoring all others. The incidence graph corresponding to the structure (PD,k, LD,k, ID,k)
is denoted by D(k,K).
To facilitate the notation in the future results on “connectivity invariants”, it will be conveni-
ent for us to define p−1,0 = l0,−1 = p1,0 = l0,1 = 0, p0,0 = l0,0 = −1, p′0,0 = l′0,0 = −1, p′1,1 = p1,1,
l′1,1 = l1,1) and to assume that our equations are defined for i > 0. Note that, for i = 0, four
above-written conditions are satisfied by every point and line. Moreover, for i = 1, the first two
equations coincide and give l1,1 − p1,1 = l1,0p0,1.
Let k > 6, t = [(k + 2)/4], and let u = (uα, u11, . . . , utt, u
′
tt, ut,t+1, ut+1,t, . . .) be a vertex
of D(k,K) (α ∈ {(1, 0), (0, 1)}, it does not matter whether u is a point or line). For every r,
2 6 r 6 t, let
Gr(u) = ar(u) =
∑
i=0,r
(uiiu
′
r−i,r−i − ui,i+1ur−i,r−i−1),
and a(u) = (a2, a3, . . . , at). Similarly, we assume that a(u) = (a2, a3, . . . , at, . . .) for the vertex u
of the infinite graph D(K).
Proposition 8. Let u and v be vertices from the same component of D(k,K). Then a(u) =
= a(v). Moreover, for any t−1 field elements xi ∈ Fq, 2 6 t 6 [(k+2)/4], there exists a vertex v
of D(k,K), for which a(v) = (x2, . . . , xt) = (x).
We refer to the first coordinate x1,0 = ρ(x) of a point x and the first coordinate y1,0 = ρ(y)
of a line y as the color of the vertex (point or line). The following property holds for the graph:
there exists the unique neighbor Nt(v) of a given vertex v of a given color t ∈ K.
44 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2015, №1
A flag of the incidence system D(n,K) (or D(K)) is an unordered pair {(x), [y]} such that
(x)I[y]. Obviously, the totality of flags FD(n,K) (FD(K)) of the bipartite flag D(n,K) (D(K),
respectively) is isomorphic to the variety Kn+1. So, the flag {(x), [y]} is defined by the tuple
(x10, x11, . . . , y01). Note that Ny1({x}) = [y].
We consider an operator NP,α({(x), [y]}), α ∈ K mapping a flag {(x), [y]} of the incidence
structure D(n,K) (or D(K)) into its image {(x′), [y]}, where (x′) = Nρ(y)+α([y]). Similarly, an
operator NL,α({(x), [y]}) maps {(x), [y]} into {(x), Nρ(x)+α(x)}).
Let α1, α2, . . . , αk and β1, β2, . . . , βk be chosen to be the random sequences of elements from
the commutative ring K. The composition E = NP,α1NL,β1NP,α2NL,β2 . . . NP,αkNL,βk transforms
flag {(x), [y]} into a new flag {(x′), [y′]}. The process of computation of E({(x), [y]} = {(x′), [y′]}
corresponds to a random walk in the expander graph D(n,K) with the original vertex (x) and
the final point (x′).
Symbolic keys and pseudorandom walks on flag space. Let Vs,r,m = Ps,m ∪ Lr,m,
Im = Im(K), m = 2, 3, . . . be a family of linguistic incidence structures with the point set
Ps,m = Ks+m and the line set Ls,m = Kr+m, where the parameters s and r are constants, and K
is a fixed commutative ring. The sets of colors for points and lines areKs andKr, respectively. We
assume that the subset M = {i1, i2, . . . , id}, d = d(m) 6 m defines the symplectic quotient IM
for each linguistic structure Im = Im(K). Let G1, G2, . . . , Gt be the connectivity invariants of
the incidence structures Im.
Let FIm be the flag relation, and let F(Vs,r,m) = F(Vm(K)) be a variety of flags for the
incidence structure Im. The information on the flag {(x), [y]} can be given by the pair (x) ∈
∈ Ks+m, ρ(y) ∈ Kr or, alternatively, by the pair [y] ∈ Kr+m and ρ(x) ∈ Ks. So, F(Vs,r,m) is
isomorphic to Km+r+s.
Let NP,a, a ∈ Ks be the operator of change of the point of a flag F = {(x), [y]} defined
by the rule NP,a({(x), [y]}) = {(x′), [y]}, where (x′)Im[y] and ρ(x′) = a. Similarly, let NL,a,
a ∈ Ks be the operator of change of the line of a flag F = {(x), [y]} specified by the rule
NL,b({(x), [y]}) = {(x), [y′]}, where [y′]Im(x) and ρ(y′) = b. It is clear that the application of
a composition of NP,a1 , NL,b1 , NP,a2 , NL,b2 , . . . , NP,ak , NL,bk to the flag F corresponds to a
walk in our linguistic graph with the starting point (p) or a walk in the graph FIm with the
starting vertex {(x), [y]}.
Let F = {(x), [y]} be a general flag of our linguistic structure Im, i. e., (x) = (x1, x2, . . . , xr,
xr+1, xr+2, . . . , xr+m), [y] = [y1, y2, . . . , ys, ys+1, ys+2 . . . , ys+m] are incident. We assume that x1,
x2, . . . , xr, y1, y2, . . . , ys, xs+1, xs+2, . . . , xs+m are the list of independent variables, which
give us the entire information on a flag F of the incidence structure Im. We assume that the
connectivity invariants G1, G2, . . . , Gt are written in terms of the coordinates of the point (x).
We refer to a tuple Tr(F ) = 〈x1, x2, . . . , xr, y1, y2, . . . , ys, G1(x), G2(x), . . . , Gt(x)〉 as the trace of
a flag F = {(x), [y]}, i. e., Tr(F ) = 〈ρ(x), ρ(y), G1(x), G2(x), . . . , Gt(x)〉.
We introduce a parameter n by the equality n = (r + s+ t). Let D1, D2, . . . ,Dh, Dh+1 and
E1, E2, . . . , Eh be two lists of elements, where Di, Ej ∈ K[z1, z2, . . . , zn], i = 1, 2, . . . , h + 1,
j = 1, 2, . . . , h. We refer to concatenation of both lists (writing the second list after the first
one) as a symbolic key.
We take the flag F = {(x), [y]} specified by parameters of the kind x1, x2, . . . , xr, y1, y2, . . . ,
ys, xr+1, . . . , xr+m with trace Tr(F ) = 〈x1, x2, . . . , xr, y1, y2, . . . , yr, G1(x), G2(x), . . . , Gt(x)〉.
We concatenate all these tuples with preservation of the order and form a string of parameters
β1, β2, . . . , βn from Q. After that, we compute specializations of the coordinates di = Di(Tr(F )),
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2015, №1 45
where i = 1, 2, . . . , h, h+1 and ej = Ej(Tr(F )), where j = 1, 2, . . . , h of our symbolic key. For the
chosen ring K, this allows us to treat coordinates of the string d1, d2, . . . , dh, dh+1 as elements
of Kr and coordinates of e1, e2, . . . , eh as a string from Ks. The string (d1, d2, . . . , dh, dh+1, e1,
e2, . . . , eh) is our numerical key.
Finally, we compute the decomposition N of operators NP,d1 , FL,e1 , NP,d2 , NL,e2 , . . . , NP,dh ,
NL,eh, NP,ed+1
. The application of N to the flag F corresponds to a walk in the graph FIm with
the starting point F and the final point N(F ).
Note that the colors of the point and the line forming F̌ = N(F ) = {(x̌), [y̌]} are dh+1 ∈ Ks
and eh ∈ Kr, respectively. Under certain conditions, we may restore the trace of a flag F from the
given F ′. We have Gi(x) = Gi(x̌), because both flags are from the same connected component.
Additionally,
(x̌1, x̌2, . . . , x̌r) = Dh+1(x1, . . . , xr, y1, . . . , ys, G1(x̌), . . . , Gt(x̌)),
(y̌1, y̌2, . . . , y̌r) = Eh(x1, . . . , xs, y1, . . . , ys, G1(x̌), . . . , Gt(x̌)).
(1)
We may choose functions Dh+1 and Eh such that the above-written system of equations has
the unique solution independently of the values of Gi(x′), i = 1, 2, . . . , t. Obviously, the first
choice is a system of equations linear in the variables x1, x2, . . . , xr, y1, y2, . . . , ys. Then we can
reconstruct our walk in the reverse order corresponding to the composition of NP,eh−1
, NL,dh−1
,
NP,eh−2
, . . . , NL,e1 , NP,d1 .
Multivariate transformations based on symbolic keys. The above-mentioned map
defined by a symbolic key has multivariate nature. The plainspace is the totality of
tuples (x1, x2, . . . , xs, y1, y2, . . . , yr, xs+r+1, xs+r+2, . . . , xs+r+m). For each function Di(z1, z2, . . .,
zs+r+t), we consider a specialization of the variables z1 = x1, z2 = x2, . . . , zs = xs, zs+1 = y1,
zs+2 = y2, . . . , zs+r = yr, zs+r+1 = G1(x), zs+r+2 = G2(x), . . . , zs+r+t = Gt(x). In such a way, we
construct the function D′
i depending on the general tuple (x1, . . . , xs, y1, . . . , yr, xr+1, . . . , xr+m)
of the plainspace. Similarly, we apply the same specialization to each Ei and get the transformati-
on E′
i. The transformations NP,D′
i
and NL,E′
j
are multivariate bijections on Kr+s+m. The formal
composition of NP,D′
1
, NL,E′
1
, NP,D′
2
, NL,E′
2
, . . . , NP,D′
h
, NL,E′
h
, and NP,D′
h+1
is a symbolic
presentation of the map N .
Algoritm 1. The algorithm of generation of an irreversible multivariate transformation with
the side door to the secret numeric key.
1. Choose the most preferable singular linear transformation T1 : W →W such that T1|W1 is
invertible and T1|W2 is not invertible, where W1 = Kr+d and W2 = Km−d.
2. Take the tuple z = (z1, z2, . . . , zk) ∈ W and compute w = T1(z).
3. Choose the flag symplectic quotient FIM of a flag linguistic graph FIm corresponding to
M = {m1,m2, . . . ,md} with natural order of elements and the incidence structure IM with a
point set Pr,M = KN and a line set Ls,M = KN, where a point (x) and a line [y] are of the kinds
(x) = (x1, x2, . . . , xr, xm1 , xm2 , . . . ,md) and [y] = [y1, y2, . . . , ys, ym1 , ym2 , . . . ,md], respectively.
4. Treat the tuple w ∈ W as a flag F1 in the linguistic graph FIm of the kind
F1 = (x1, . . . , xs, y1, . . . , yr, xr+1, xr+2, . . . , xm1 , xm1+1, . . . , xm2 , . . . , xmd , xr+m).
5. Generate the symbolic key corresponding to the symbolic way in the flag linguistic graph
FIπm, i. e., a list of polynomial functions Di(v1, v2, . . . , vr+s+t), i = 1, 2, . . . , h+ 1, Ej(v1, v2, . . .,
vr+s+t), j = 1, 2, . . . , h, and compute its specializations D′
i(F2)i = 1, 2, . . . , h + 1, E′
j(F2)j =
= 1, 2, . . . , h corresponding to the substitution vi = xi, i = 1, 2, . . . , r, vr+j = yj , j = 1, 2, . . . , s,
vr+s+e = Gi(F2), e = 1, 2, . . . , t.
46 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2015, №1
6. Determine the multivariate transformation N corresponding to the chosen symbolic key,
i. e.,
N = NP,D′
1
NL,E′
1
· · ·NP,D′
h
NL,EhNP,D′
h+1
.
7. Compute the flag F2 = N(F1) of the graph FIπm and treat it as a tuple u ∈ W .
8. Choose an invertible affine transformation T2 : W → W and compute c = T2(u).
9. Using the symbolic computation, determine a multivariate transformation H : W →W as
a composition of T1, N , and T2. It is clear that the transformation H : W → W is polynomial
over K of the kind
z1 → h1(z1, z2, . . . , zk),
z2 → h2(z1, z2, . . . , zk),
. . . ,
zk → hk(z1, z2, . . . , zk),
where
hi ∈ K[z1, z2, . . . , zk].
The general algorithms of the key exchange multivariate protocol based on pseu-
dorandom walks on incidence structures. Key exchange algorithms are used to exchange
cryptographic keys between two communicating users (in our case, Alice and Bob). The most
popular key exchange protocol was proposed in [7]. A key exchange algorithm enables the
communicating users, who do not know each other, to share a secret key over an unsecured
communication channel. This secret numerical key can then be used to encrypt any subsequent
communication between the two users, by using the encryption and decryption maps defined via
a path in the graph. In this new algorithm, the secret key is a pseudorandom walk determined
by a list of pseudorandom elements from the commutative ring.
Algoritm 2. The proposed key exchange between two users consists of the following steps:
I. Alice and Bob will determine together
I.1. The free module W = Kk over a commutative ring K, where k = r + s +m.
I.2. A linguistic graph LΓ(r, s,m,K) corresponding to the incidence structure Im.
I.3. The length of a pseudorandom path in the graph Im of the kind 2h + 1.
II. Alice should do the following steps:
II.1. Generate a multivariate transformation H : W → W using Algorithm
II.2. Use the symbolic computation and determine a deformed symbolic key D̃i, Ẽj ∈
∈ K[z1, z2, . . . , zn]
l, i = 1, 2, . . . , h + 1, j = 1, 2, . . . , h as a composition of the selected transfor-
mation T1 with the chosen symbolic key D̃i, i = 1, 2, . . . , h + 1, Ẽj , j = 1, 2, . . . , h used in
Algorithm 1.
II.3. Send the determined transformation H and the deformed symbolic key D̃i, i = 1, 2, . . .,
h + 1, Ẽj , j = 1, 2, . . . , h to Bob.
III. Next, Bob should do the following steps:
III.1. Choose a random tuple v = (v1, v2, . . . , vk), where vi ∈ K, i = 1, 2, . . . , k, compute
w = H(v) and send w to Alice.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2015, №1 47
III.2. Determine the secret numerical key d1, d2, . . . , dh+1, e1, e2, . . . , eh in the standard way,
by using the deformed symbolic key, i. e., d1 = D̃1(v), . . ., h+ 1 = D̃h+1, e1 = Ẽ1,(v), . . . ,
yr = vr, eh = Ẽh,(v).
IV. Finally, in order to restore the elements of the secret numerical key d1, d2, . . . ,
dh+1, e1, e2, . . . , eh from the element w ∈ W , Alice should do the following steps:
IV.1. Use the invertible affine transformation T2 to compute T−1
2 (w) = v′ and write it as a
flag F2 = {x̌, y̌} from the graph FIπm.
IV.2. Compute G1(x̌), G2(x̌), . . ., Gt(x̌) determined by equations (1) for the elements x1,
x2, . . . , xr, y1, y2, . . . , ys forming a flag F1 = {x, y}.
IV.3. Use the symbolic key and these calculations to determine a secret numerical key as a
list of pseudorandom elements d1, d2, . . . , dh, dh+1, e1, e2, . . . , eh from K.
Conclusion. We can use our algorithm in the case of linguistic structures D(m,K). The
previous section gives the full description of data, which we need for the implementation of our
key exchange protocol. The graphs D(m,K) have been used for the construction of a stream
cipher (see [9, 10, 11] and references therein). In this case, both algorithms (symmetric one
and key exchange protocol) can be used together. It is known that the graphs D(m,K) are
good expanders (see [12, 13]). This means that the behavior of pseudorandom walks generated
for their use in these algorithms is similar to the behavior of random walks on random graphs
(see [8, 14, 15]).
1. Biggs N. L. Algebraic graph theory. – Cambridge: Cambridge Univ. Press, 1993. – 324 p.
2. Moore E.H. Tactical memoranda // Amer. J. Math. – 1886. – 18. – P. 264–303.
3. Ustimenko V. Maximality of affine groups and hidden graph cryptosystems // J. Alg. Discr. Math. – 2005. –
No 1. – P. 133–150.
4. Ustimenko V. On walks of variable length in Schubert incidence systems and multivariate flow systems //
Dop. NAN Ukrainy. – 2014. – No 3. – P. 55–150.
5. Lazebnik F., Ustimenko V.A., Woldar A. J. A new series of dense graphs of high girth // Bull. Amer.
Math. Soc. (New Series). – 1995. – 32, No 1. – P. 73–79.
6. Lazebnik F., Ustimenko V.A., Woldar A. J. A characterization of the components of the graphs D(k, q) //
Discr. Math. – 1996. – 157. – P. 271–283.
7. Diffie M., Hellman M.E. New directions in cryptography // IEEE Trans. Inform. Theory. – 1976. – IT –
22. – P. 644–654.
8. Hoory S., Linial N., Wigderson A. Expander graphs and their applications // Bull. Amer. Math. Soc.
(New Series). – 2006. – 43, No 4. – P. 439–561.
9. Ustimenko V. Coordinatisation of trees and their quotients // Voronoj’s Impact on Modern Science. –
Kiev: Institute of Mathematics, 1998. – Vol. 2. – P. 125–152.
10. Ustimenko V. CRYPTI: Graphs as tools for symmetric encryption // Lecture Notes in Computer Science,
Proceedings of AAECC-14 Symposium on Applied Algebra, Algebraic Algorithms and Error Correction
Codes. – Berlin: Springer, 2001. – P. 278–286.
11. Kotorowicz J., Ustimenko V. On the implementation of cryptoalgorithms based on algebraic graphs over
some commutative rings // Condens. Matt. Phys. – 2008. – 11, No 2. – P. 347–360.
12. Ustimenko V. Graphs with special arcs and cryptography // Acta Appl. Math. – 2002. – 74. – P. 117–153.
13. Ustimenko V. On a group theoretical constructions of expanding graphs // J. Alg. Discr. Math. – 2003. –
No 3. – P. 102–109.
14. Lovász L. Random walks on graphs: A survey // Bolyai Soc. Math. Studies. – 1993. – 2. – P. 1–46.
15. Romańczuk U., Ustimenko V. On extremal graph theory. Explicit algebraic constructions of extremal
graphs and corresponding Turing encryption machines // Artificial Intelligence, Evolutionary Computing
and Metaheuristics. – Berlin: Springer, 2013. – P. 257–285.
Received 16.07.2014Institute of Telecommunications and Global
Information Space of the NAS of Ukraine, Kiev
Maria Curie-Sklodowska University, Lublin, Poland
48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2015, №1
У. Романчик-Полубець, В.О. Устименко
Про новi протоколи обмiну ключами, що базуються
на псевдовипадкових блуканнях в структурi iнциденцiї
Запропоновано новi протоколи обмiну ключами, що формулюються в термiнах алгебраїчної
криптографiї вiд багатьох змiнних та базуються на створеннi кореспондентами спiльного
блукання в лiнгвiстичному графi. Алгоритм детально описано у випадку вiдомої родини
графiв великого обгорту, що задається нелiнiйними рiвняннями над скiнченним полем.
У. Романчик-Полубец, В.А. Устименко
О новых протоколах обмена ключами, основанных
на псевдослучайных блужданиях в инцидентностной структуре
Предложены новые протоколы обмена ключами, сформулированные в терминах алгебраи-
ческой криптографии от многих переменных и основанные на создании корреспондентами
общего блуждания в лингвистическом графе. Алгоритм детально описан в случае известной
семьи графов большого захвата, заданной нелинейными уравнениями над конечным полем.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2015, №1 49
|
| id | nasplib_isofts_kiev_ua-123456789-95704 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | English |
| last_indexed | 2025-12-01T11:53:18Z |
| publishDate | 2015 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Romańczuk-Polubiec, U. Ustimenko, V.A. 2016-03-02T14:23:35Z 2016-03-02T14:23:35Z 2015 On new key exchange multivariate protocols based on pseudorandom walks on incidence structures / U. Romańczuk-Polubiec, V.A. Ustimenko // Доповiдi Нацiональної академiї наук України. — 2015. — № 1. — С. 41-49. — Бібліогр.: 15 назв. — англ. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/95704 519.1,514.128 A new key exchange protocol formulated in terms of multivariate cryptography and based on the elaboration of a common walk in the linguistic graph by correspondents is proposed. This algorithm is described in details in the case of a known family of graphs of large girth given by nonlinear equations over a finite field. Запропоновано новi протоколи обмiну ключами, що формулюються в термiнах алгебраїчної криптографiї вiд багатьох змiнних та базуються на створеннi кореспондентами спiльного блукання в лiнгвiстичному графi. Алгоритм детально описано у випадку вiдомої родини графiв великого обгорту, що задається нелiнiйними рiвняннями над скiнченним полем. Предложены новые протоколы обмена ключами, сформулированные в терминах алгебраической криптографии от многих переменных и основанные на создании корреспондентами общего блуждания в лингвистическом графе. Алгоритм детально описан в случае известной семьи графов большого захвата, заданной нелинейными уравнениями над конечным полем. en Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика On new key exchange multivariate protocols based on pseudorandom walks on incidence structures Про новi протоколи обмiну ключами, що базуються на псевдовипадкових блуканнях в структурi iнциденцiї О новых протоколах обмена ключами, основанных на псевдослучайных блужданиях в инцидентностной структуре Article published earlier |
| spellingShingle | On new key exchange multivariate protocols based on pseudorandom walks on incidence structures Romańczuk-Polubiec, U. Ustimenko, V.A. Інформатика та кібернетика |
| title | On new key exchange multivariate protocols based on pseudorandom walks on incidence structures |
| title_alt | Про новi протоколи обмiну ключами, що базуються на псевдовипадкових блуканнях в структурi iнциденцiї О новых протоколах обмена ключами, основанных на псевдослучайных блужданиях в инцидентностной структуре |
| title_full | On new key exchange multivariate protocols based on pseudorandom walks on incidence structures |
| title_fullStr | On new key exchange multivariate protocols based on pseudorandom walks on incidence structures |
| title_full_unstemmed | On new key exchange multivariate protocols based on pseudorandom walks on incidence structures |
| title_short | On new key exchange multivariate protocols based on pseudorandom walks on incidence structures |
| title_sort | on new key exchange multivariate protocols based on pseudorandom walks on incidence structures |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/95704 |
| work_keys_str_mv | AT romanczukpolubiecu onnewkeyexchangemultivariateprotocolsbasedonpseudorandomwalksonincidencestructures AT ustimenkova onnewkeyexchangemultivariateprotocolsbasedonpseudorandomwalksonincidencestructures AT romanczukpolubiecu pronoviprotokoliobminuklûčamiŝobazuûtʹsânapsevdovipadkovihblukannâhvstrukturiincidencií AT ustimenkova pronoviprotokoliobminuklûčamiŝobazuûtʹsânapsevdovipadkovihblukannâhvstrukturiincidencií AT romanczukpolubiecu onovyhprotokolahobmenaklûčamiosnovannyhnapsevdoslučainyhbluždaniâhvincidentnostnoistrukture AT ustimenkova onovyhprotokolahobmenaklûčamiosnovannyhnapsevdoslučainyhbluždaniâhvincidentnostnoistrukture |