On walks of variable length in the Schubert incidence systems and multivariate flow ciphers
The flow cipher algorithm based on walks at the flag variety of a Schubert system over the finite commutative ring is proposed. The restriction of the incidence relation of the geometry of a finite simple Lie group of the normal type on the union of large Schubert cells of the maximal dimension i...
Збережено в:
| Опубліковано в: : | Доповіді НАН України |
|---|---|
| Дата: | 2014 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/87142 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | On walks of variable length in the Schubert incidence systems and multivariate flow ciphers / V.A. Ustimenko // Доповiдi Нацiональної академiї наук України. — 2014. — № 3. — С. 55-63. — Бібліогр.: 15 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859651257365430272 |
|---|---|
| author | Ustimenko, V.A. |
| author_facet | Ustimenko, V.A. |
| citation_txt | On walks of variable length in the Schubert incidence systems and multivariate flow ciphers / V.A. Ustimenko // Доповiдi Нацiональної академiї наук України. — 2014. — № 3. — С. 55-63. — Бібліогр.: 15 назв. — англ. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | The flow cipher algorithm based on walks at the flag variety of a Schubert system over the finite
commutative ring is proposed. The restriction of the incidence relation of the geometry of a
finite simple Lie group of the normal type on the union of large Schubert cells of the maximal
dimension is an example of the Schubert system. More general examples are connected with
Kac–Moody groups. We introduce some applications of such ciphers based on periodic walks for
the construction of multivariate private keys, security of which is connected with the discrete
logarithm problem for cyclic subgroups of polynomial transformations of increasing order.
Запропоновано алгоритм струменевого кодування, що грунтується на блуканнях на многовидах прапорiв системи Шуберта, визначеної над комутативним кiльцем. Прикладом системиШуберта є обмеження вiдношень iнцидентностi геометрiї простої групи Лi нормального типу на об’єднання великих клiтин максимального вимiру. Бiльш загальнi приклади
пов’язанi з групами Каца–Мудi. Наводено приклад використання таких струменевих алгоритмiв, визначених на перiодичних блуканнях, для створення вiдкритого полiномiального ключа, безпека якого пов’язана з проблемою дискретного логарифма для циклiчних пiдгруп
полiномiальних перетворень зростаючого порядку.
Предложен алгоритм потокового шифрования, основанный на блужданиях на многообразиях флагов системы Шуберта, определенной над коммутативным кольцом. Примером
системы Шуберта является ограничение отношений инцидентности геометрии простой
группы Ли нормального типа на объединение больших клеток максимальной размерности.
Более общиe примеры соответствуют группам Каца–Муди. Приведен пример использования таких симметричних алгоритмов, определенных на периодических блужданиях, для
создания публичного ключа, безопасность которого связана с проблемой дискретного логарифма для циклических подгрупп полиномиальных преобразований возрастающего порядка.
|
| first_indexed | 2025-12-07T13:33:55Z |
| format | Article |
| fulltext |
UDC 519.1,514.128
V.A. Ustimenko
On walks of variable length in the Schubert incidence
systems and multivariate flow ciphers
(Presented by Corresponding Member of the NAS of Ukraine O. M. Trofimchuk)
The flow cipher algorithm based on walks at the flag variety of a Schubert system over the finite
commutative ring is proposed. The restriction of the incidence relation of the geometry of a
finite simple Lie group of the normal type on the union of large Schubert cells of the maximal
dimension is an example of the Schubert system. More general examples are connected with
Kac–Moody groups. We introduce some applications of such ciphers based on periodic walks for
the construction of multivariate private keys, security of which is connected with the discrete
logarithm problem for cyclic subgroups of polynomial transformations of increasing order.
Schubert systems, definitions, and examples. All graphs we consider are simple, i. e. undi-
rected without loops and multiple edges. Let V (G) and E(G) denote the set of vertices and the
set of edges of G, respectively. Then |V (G)| is called the order of G, and |E(G)| is called the size
of G. A path in G is called simple if all its vertices are distinct. When it is convenient, we shall
identify G with the corresponding antireflexive 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 vertices u and v (or neighbors).
The girth of a graph G, denoted by g = g(G), is the length of the shortest cycle in G.
We use a term incidence structure for a triple consisting of the set Γ, its partition Γ =
= Γ1
⋃
Γ2
⋃
· · ·
⋃
Γn, and a symmetric antireflexive binary relation I (incidence) on the set Γ
such that xIy implies ∈ Γi, y ∈ Γj, and i 6= j.
We refer to the number n as the rank of an incidence structure. In the case n = 2, the triple
is called an incidence structure, and P = Γ1 and L = Γ2 are called the set of points and the
set of lines, respectively.
Let K be a finite commutative ring. Linguistic is called the incidence structure with the point
set Γ1 = Ks+m and the line set Γ2 = Kr+m such that point (x) = (x1, x2, . . . , xs, xs+1, . . . , xs+m)
is incident to the line [y] = [y1, y2, . . . , yr, yr+1, yr+2, . . . , ym+r] if and only if the relations
a1xs+1 + b1yr+1 = f1(x1, x2, . . . , xs, y1, y2, . . . , yr),
a2xs+2 + b2yr+2 = f2(x1, x2, . . . , xs+1, y1, y2, . . . , yr+1),
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
amxs+m + bmyr+m = f1(x1, x2, . . . , xs+m−1, y1, y2, . . . , yr+m−1)
hold, where aj and bj, j = 1, 2, . . . ,m, are not zero divisors, and fj are multivariate polynomials
with coefficients from K. Brackets and parentheses allow us to distinguish point from line (see [2]).
The color r(p) (r([l])) of point (p) (line [l]) is defined as the projection of an element p from the
free module on its initial s (respectively, r) coordinates. As follows from the definition of linguistic
incidence structure, there exists the unique neighbor with a chosen color for each vertex of the
incidence graph.
© V.A. Ustimenko, 2014
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2014, №3 55
Recall that a flag F of the incidence system Γ = Γ1
⋃
Γ2
⋃
· · ·
⋃
Γm is the clique of a simple
graph I. This means that x, y ∈ F implies xIy.
Let Ω = {1, 2, . . . , t} be a finite set. For each subset M in Ω and each commutative ring K,
we consider the totality KM = {f : M → K} of partial functions from Ω into K with support
supp(f) = M . It is convenient for us to write element f ∈ KM as a pair (M,f). Let M1 and M2
be nonempty sets of Ω. We denote, by L(M1,M2,K), the linguistic graph with a point set KM1
and a line set KM2 such that the incidence of the point (M1, f1) and the line (M2, f2) will be
given by the following conditions:
mif1(si) + lif2(si)) = Fi(f1(r1), f1(r2), . . . , f1(rd1), f2(p1), f2(p2), . . . , f2(pd2), f1(s1),
f1(s2), . . . , f1(si−1), f2(s1), f2(s2), . . . , f2(si−1)), i = 1, 2, . . . , t.
Here, elements of M1 − M1
⋂
M2 and M2 − M1
⋂
M2 are defined by lists {r1, r2, . . . , rd1}
and {p1, p2, . . . , pd2}, and elements of M1
⋂
M2 are listed as s1, s2, . . . , st. The color r(v) of the
vertex v = (Mi, fi), i = 1, 2, in the graph L(M1,M2,K) is defined as the restriction of fi onto
Mi − M1
⋂
M2. A linguistic incidence system L(Mt,Ω,K), t ∈ J , is defined for the family of
subsets Mt, t ∈ Ω, of Ω and the commutative ring K as a disjoint union of KMt, t ∈ J , together
with the incidence relation I such that its restriction Iij on KMi
⋃
KMj , where i, j ∈ J are
defined by a linguistic graph L(M1,M2,K). We call the Schubert system a linguistic incidence
structure L(Mt,Ω,K), t ∈ J , with a nonempty set of maximal flags of rank |J | such that, for each
order i1, i2, . . . , is on J , each maximal flag is uniquely defined by its representative of KMi1 , its
neighbor of kind (Mi2 , fi2) is uniquely defined by fi2 |Mi2−Mi1 , a flag element of kind (Mi3 , fi3) is
uniquely defined by the projection fi3 |Mi3−Mi1
⋂
Mi2 , and a representative of KMis is uniquely
defined by the projection of fis onto Kis − Mi1
⋂
Mi2
⋂
· · ·
⋂
Mis−1
.
As follows from the definition of Schubert systems, the sets Di = Mi −M1
⋂
M2 · · ·Mi−1
⋂
⋂
Mi+1
⋂
Mi+2 · · ·Ms are nonempty. For each flag of kind (M1, f1), (M2, f2), . . . , (Mi−1, fi−1),
(Mi+1, fi+1), (Mi+2, fi+2) . . . , (Ms, fs), its completion to the maximal flag by adding (Mi, fi) is
uniquely defined by the projection of fi onto Di. A natural example of the Schubert system can be
obtained via the restriction of the incidence relation of the geometry Γ(G) = Γ1
⋃
Γ2
⋃
· · ·
⋃
Γn
of a simple Lie group G of the normal type onto a disjoint union of large Schubert cells of
maximal degree in each Γi, i = 1, 2, . . . , n.
More general examples correspond to Kac–Moody groups. Let L be a Kac–Moody algebra
defined by the Cartan matrix A over the field of complex numbers C. The algebra L can be
written in the form L− + L0 + L+, where L0 is a Cartan subalgebra, and L+ is a direct sum
of root subspaces corresponding to positive real and imaginary roots r in the chosen Chevalley
basis. Let a1, a2, . . . , an be the list of fundamental roots, then dual elements a∗1, a
∗
2, . . . , a
∗
n form
a basis in L0. Let us denote, by LZ , a Lie groupoid of all vectors in L with integer coordinates
in the chosen basis. Let K be a commutative ring. Then the tensor product of LZ and K is a
Lie groupoid LK over K. Let Γi be the totality of elements in K of kind ai
∗ + x, where x is
an element of the direct sum Si of root subspaces Lr, where r is a positive root, and a∗i (r) is
different from zero. We define an incidence system SΓ(A,K), which is a disjoint union of Γi such
that x from Γi and y from Γj are incident if and only if [x, y] = 0. As was shown in [3] (see
also [4]) in the case of a finite-dimensional algebra L over the field K of characteristic zero (or
“sufficiently large” characteristic), the incidence system SΓ(A,K) is isomorphic to the Schubert
system of the geometry of a simple group G, which is an adjoint group for the Lie algebra L. If
det(A) = 0, then the incidence system SΓ(A,K) is a variety of infinite dimension (see [4]). In
56 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2014, №3
the case of K = Fq, SΓ(A,K) can be approximated by a finite Schubert system obtained by the
change of the space L by a direct sum of root spaces Lr, where the positive root r satisfies the
condition r < r0 for certain r0 and the chosen lexicographical order on roots (see [4, 5]). In a
similar way, the Schubert system of the geometry of a simple Lie group of the twisted type can
be embedded into the corresponding Lie algebra [6].
Let Γ, I be an incidence graph in the Schubert incidence system over a commutative ri-
ng K. Geometry elements forming two flags F1 = {(M1, f1), (M2, f2), . . . , (Ms, fs)} and F2 =
= {(M+
1 , f+
1 ), (M+
2 , f+
2 , . . . , (M+
s , f+
s )} may be located at the same connected component of I,
or the representatives of F1 and F2 are from distinct connected components. Assume that the
system of equations G1(x) = a1, G2(x) = a2, . . . , Gk(x) = ak, where ai ∈ K are some constants,
defines the connectivity invariants. For elements x, y ∈ Γ1 from the same connectivity component,
the relation Gi(x) = Gi(y), i = 1, 2, . . . , k, holds.
The existence of i such that Gi(x) = Gi(y) implies that x and y are vertices from different
connected components of graph I.
On the flag varieties and walks on them. Finite geometries and the metric spaces
connected with them are traditionally used in coding theory. Some cryptographical applications
of finite geometries were proposed in [7]. The idea to use walks in a Schubert system for the
generation of nonlinear bijective maps of vector spaces was proposed in [8]. The present arti-
cle is devoted to generalizations of cryptographical algorithms based on a Schubert automaton
proposed in [9].
Let us consider the set ΓF of maximal flags of a Schubert system. We define the spectrum
spec(F ) of a flag F = {(M1, f1), (M2, f2), . . . , (Ms, fs)} as a sequence of colors ti = fi|Mi −
−(M1
⋃
M2
⋃
· · ·
⋃
Mi−1
⋃
Mi+1
⋃
· · ·
⋃
Ms) of its elements (Mi, fi). We introduce the adjacency
relation R on the set ΓF as the following relation (or graph): the intersection of two flags is a
flag of rank s − 1. We refer to maximal flags satisfying relation R as adjacency flags.
If F1RF2 for flags F1 = {(M1, f1), (M2, f2), . . . , (Ms, fs)} and F2 = {(M+
1 , f+
1 ), (M+
2 , f+
2 ),
. . . , (M+
s , f+
s )}, then there exists the index i such that colors ti and t+i are distinct, and the
functions fi and f+
i differ by their values on Mi −M1
⋃
M2
⋃
· · ·
⋃
Mi−1
⋃
Mi+1
⋃
· · ·
⋃
Ms. As
follows from the definition of Schubert systems, the operator N i
t+(F ), which maps a flag F with
spectrum (t1, t2, . . . , ti−1, ti, ti+1, . . . , ts) into the adjacent flag F+ of color (t1, t2, . . . , ti−1, t
+
i ,
ti+1, . . . , ts), is well defined. Obviously, the equality ti = t+i implies that N i
t (F ) = F . We define
the color of the edge of graph R between vertices F and F+ as number i. The composition
N i1
t1
N i2
t2
· · ·N ik
tk
for different colors {i1, i2, . . . , ik} computed for flag F corresponds to walk F ,
F1 = N i1
t1
(F ), F2 = N i2
t2
(F1), . . . , Fk = N ik
tk
(Fk−1) in graph R. Note that edges FRF1, F1RF2, . . .,
Fk−1RFk are colored in distinct colors. As follows from the definition of a Schubert system, the
varieties of maximal flags ΓF and the color spaces Si = KMi−M1∪M2∪···∪Mi−1∪Mi+1∪···∪Ms are
free modules over the commutative ring K.
Let Q be a subring K such that K is a free module over Q of dimension d. Then ΓF and Si
are affine spaces over Q of dimensions v and vi, respectively. It is clear that d is a divisor of
these integers. Polynomial functions Gi : Q
v → Qd map the affine variety of flags ΓF (Q) over the
commutative ring Q into spaces Ai of dimension d. We refer to the direct sum S(A) of spaces
Si(Ai) as the spectral space (space of invariants) of the variety ΓF (Q). With the maximal flag F ,
we associate its trace sp(F ) = (t1, t2, . . . , ts, G1(F ), G2(F ), . . . , Gt(F )), where (t1, t2, . . . , ts) is
the spectrum corresponding to the vector х(F ) = (x1, x2, . . . , xl), l = v1 + v2 + · · · + vs from S
and (G1(F ), G2(F ), . . . , Gt(F )) is an element from the space of invariants, which could be given
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2014, №3 57
also by the vector y(F ) = (y1, y2, . . . , ym), m = td. Let fi = f(x1, x2, . . . , xl, y1, y2, . . . , ym) be
a polynomial (or birational) map from S + A into Si defined over the commutative ring, Q.
Let Z be an abstract flag from the totality ГF (Q) with the spectrum z1, z2, . . . , zl and invariants
G1(Z), G2(Z), . . . , Gm(Z). A specialization fi(Z) = fi(Z1, Z2, . . . , Zl, G1(Z), G2(Z), . . . , Gm(Z))
associates the tuple fi(Z) from Si with given Z. We define the symbolic code of a walk as
the string fi1 , fi2 , . . . , fit of such maps, where the sequence i1, i2, . . . , it is such that is differs
from is+1 for each s, and t is determined by a certain function t = T (x1, x2, . . . , xl, y1, y2, . . . , ym),
which maps S + A into the set Z+ of positive integers. Let F be a flag from ΓF (Q). First,
we compute its spectrum and the set of invariants G1(F ), G2(F ), . . . , Gt(F ) and get the tuple
(x1, x2, . . . , xl, y1, y2, . . . , ym) (extended spectrum of the flag) from the module S + A. Then
we compute t = t(F ) and fi1(F ), fi2(F ), . . . , fit(F ) for our flag F . It allows us to compute
N = N i1
t1
N i2
t2
· · ·N im
tt
(F ), where tis = fis(F ). So we get the element F+ = N(F ), which is the
last vertex of the computed walk in graph R. This means that the symbolic code fi1 , fi2 , . . . , fit of
length t = T (x1, x2, . . . , xl, y1, y2, . . . , ym) determines the map N = N(fi1 , fi2 , . . . , fit) of ΓF (Q)
into itself. Under certain conditions, the reimage of flag F+ under the above-described map can
be computed. Obviously, the flags F+ and F are from the same connected component of graph R.
So, for the extended spectra (x+1 , x
+
2 , . . . , x
+
l , y
+
1 , y
+
2 , . . . , y
+
m) and (x1, x2, . . . , xl, y1, y2, . . . , ym),
the following equalities hold: y+1 = y1, y
+
2 = y2, . . . , y
+
m = ym. The tuple (x+1 , x
+
2 , . . . , x
′+
l ) is
uniquely determined by the symbolic code and the spectrum of flag F . For each i, we consider
the function of kind fir , ir = i, which appears in the symbolic code on the last position. If
such a function really exists, we denote it by f∗
i ; if not, we assume f∗
i = xi. We refer to the
set f∗
1 , f
∗
2 , . . . , f
∗
l as the boundary of a symbolic code. For each function fik of the symbolic
code, we denote the previous function with the index ik by f+
ik
, if such a function exists. If not,
we assume that f+
ik
= xik . It is clear that x+i = f∗
i(x1, x2, . . . , xl) for each i. Let us assume
now that the map g from S into itself shifting xi into x+i is a bijection. Then flag F+ can
be used for the computation of the spectrum g−1(x1, x2, . . . , xl) and the set of invariants yj
of F . We can compute the length t = T (x1, x2, . . . , xl, y1, y2, . . . , ym) and the reverse walk F+,
Fit = N it
f+
it
(F+), Fit−1
= N it−1
f+
it−1
(Fit−1), . . . , F = N i1
f+
1
(F1). Note that sp(F ′+) = (x+1 , x
+
2 , . . . , x
+
s ),
where the coordinate x+i equals xi plus the sum of all fj for j equal to i. The simplest example
of invertible functions can be obtained in the case where all functions f∗
i are linear functionals
of the kind x1H
i1(F ) + x2H
i2(F ) + · · ·+ xlH
il(F ) +H0, where H0 and H is depend only on y1,
y2, . . . , ym, and the matrix H ij(F ), j ∈ {i1, i2, . . . , il}, i = 1, 2, . . . , l, is invertible.
General algorithm of encryption. Let us consider the following private key encryption
algorithm. Let ΓFn(K) be a sequence of varieties of maximal flags of Schubert systems Γn(K)
of rank n over finite commutative rings K of increasing order. The parameter d = d(n) will
stand for the dimension of the variety of maximal flags in ΓFn(K). Let us assume that Q is
a subring of K such that a commutative ring K is isomorphic to a free module Qm over Q.
Let ΓFn(Q) be a set of maximal flags as a variety of dimension dm over Q. Correspondents
Alice and Bob consider the variety ΓFn(K) as a plainspace ΓFn(K). A subring Q will be
treated as a part of the common key. Similarly to the case of the Imai–Matsumoto multivariate
cryptosystem, the key contains two bijective affine transformations L1 and L2 of the variety
ΓF dm(Q). So, the plaintext can be identified with the string x = (p1, p2, . . . , pdm) written as
a row vector in the alphabet Q. The transformation Li : x → xAi + bi, i = 1, 2, is given by
the matrix Ai of size dm and the vector bi. We assume that the orders of transformations Ti,
i = 1, 2, increase with the parameter n. The “nonlinear part” of the key (symbolic code) is
58 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2014, №3
a “potentially infinite” sequence of pairs (is, fis), where fis = f(x1, x2, . . . , xl, y1, y2, . . . , ym),
s = 1, 2, . . . , N , is a polynomial (or birational) map from S + A into Si defined as above. We
assume that the boundary of the symbolic key {f∗
1 , f
∗
2 , . . . , f
∗
l } is fixed, and the expansion of
this key can be achieved by writing, from the left, a new set of initial elements. Additional
requirements are inequalities is 6= is+1, which hold for each s. The key contains also three time
functions hi = ti(x1, x2, . . . , xl, y1, y2, . . . , ym), i = 0, 1, 2, which are certain maps from S + A
into the set of positive integers Z+. At the beginning, Alice applies the affine transformation L1
to the plaintext x and gets the flag F = L1(x) written as a string over the alphabet K. Then she
computes the length h = h0(F ) of the nonlinear part of the symbolic key, as well as the values
fi1(F ), fi2(F ), . . . , fih(F ) of functions from the symbolic key for the obtained flag F . The next
step for Alice is the computation of N = N i1
t1
N i2
t2
· · ·N ih
th
(F ), where tis = fis(F ), and she gets
the last flag of computed walks F+ = N(F ). The flag L2(F
+) = Y is sent to Bob via an open
channel. We shall assume that the input and output data for our encryption algorithm are given
in the form of tuples over the commutative ring K. The length of the sequence (is, fis) is chosen
in a special way, so the reimage of flag F+ for the map N is always computable (or computable
in the case of “almost all” flags). Bob gets Y and computes flag L2
−1(Y ) = F+, which belongs
to the connected component of graph R containing F . He computes numerically the invariants
G1(F
+), G2(F
+), . . . , Gt(F
+) and uses the boundary {f∗
1 , f
∗
2 , . . . , f
∗
l } for the computation of
the spectrum of F . He computes the reverse walk in the graph R for finding its initial vertex F .
Finally, Bob computes L1
−1(F ) and writes this tuple in the form of a string over the alphabet K.
At the end of the communication session, the correspondents may change affine maps L1 and L2
for their powers Li
Ti , i = 1, 2.
An example of effectively computable enciphering map. Obviously, an arbitrary li-
nguistic graph is a Schubert structure. Let K be a finite commutative ring. Let us consider
the infinite bipartite graph D(K) with the point set Γ1 = P consisting of elements x =
= (x1, x2, x3, x
−
3 , . . . , xn, x
−
n , . . .) and the line set Γ2 = L consisting of lines y = [y1, y2, y3, y
−
3 , . . .,
yn, y
−
n , . . .] with the incidence relation I : xIy, x ∈ P , and y ∈ L if and only if the following
two sets of relations hold:
(1) x2 − y2 = y1x1, x3 − y3 = x1y2, x4 − y4 = y1x3, x5 − y5 = x1y4, . . . , xn − yn = x1yn−1
for odd n and xn − yn = y1xn−1 for even n.
(2) x−3 − y−3 = y1x2, x
−
4 − y−4 = x1y
−
3 , x−5 − y−5 = y1x
−
4 , . . . , x−n − y−n = y1x
−
n−1 for odd n
and x−n − y−n = x1y
−
n−1 for even values of parameter n. Let us consider also the bipartite graph
D(n,K) defined on the set of points Pn = Kn and lines Ln = Kn in the following way: vectors
xn and yn from Pn and Ln, are identified with the projections of the infinite tuples x ∈ P and
y ∈ L into their n initial coordinates, xn and yn are connected by an edge if and only if the first
n−1 relations from the definition of incidence of x and y hold. In the case K = Fq, the family of
graphs D(n,K) = D(n, q) together with special induced subgraphs was defined in [10]. In that
paper, some extremal properties of these graphs were investigated. For the general commutative
rings, the simplest properties of D(n,K) and CD(n,K) were considered in [11].
The most general connectivity properties of graphs CD(n,K) were obtained in [12]. The
discrete dynamical systems corresponding to these families of graphs were studied in [13]. If the
characteristic of a commutative ring K equals 2, then the graph CD(n,K) simply coincides
with the connected component of D(n,K). Note that all connected components of D(n,K) are
isomorphic. The partition sets Pn and Ln of the graph CD(n, q) can be identified with Kt, where
t = [3/4n] + 1 for n = 0, 2, 3 (mod 4) and t = [3/4n] + 2 for n = 1 (mod 4).
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2014, №3 59
It is known that there exist m quadratic invariants a1, a2, . . . , am where m = [1/4n]− e with
e = −1 for n = 0, 2, 3 (mod4) and e = 0 in the remaining case such that, for two points (or lines)
x and y of the graph D(n, q) from the same connected component, the equalities a1(x) = a1(y)
and a2(x) = a2(y), . . . , am(x) = am(y) hold. The inequality ai(x) 6= ai(y) for some i implies that
x and y are vertices from distinct connected components.
In the case of characteristic 2, the above-written conditions uniquely define the partition into
connected components. Colors of point (x) = (x1, x2, . . . , xn) and line [y] = [y1, y2, . . . , yn] are
just the first coordinates x1 and y1 of these tuples. The flag (x), [y], (x)I[y] of this linguistic
graph is uniquely determined by coordinates of point (x1, x2, . . . , xn) and color y1 of line [y].
Let us assume that the commutative ring K is a free module Qr over another ring Q, and
the multiplication of K is a quadratic map of K × K into K over Q. The natural example
is the Kronecker extension of the ring Q, i. e. K = Q[x]/g(x), where g(x) ∈ Q[x] is some
polynomial.
Let us consider the above-described algorithm in the case of a symbolic key x1 + d1, y1 +
+d+1 , . . . , xl+dl, y1+d′+l of even variative length 2l, l = T (x, y1) (in the case of odd length 2l+1,
one can use the symbolic key (x1+d1, y1+d+1 , . . . , xl+dl, y1+d+l , xl+dl+1)), where the function T
is obtained from the map f(z1, z2, . . . , zr, zr+1, zr+2, . . . , z2r, z2r+1, z2r+2, . . . , zr(m+2)) from the
set Qr(m+2) into Z+ by the specialization (z1, z2, . . . , zr(m+2)) = (x+1 , x
+
2 , . . . , x
+
r , y
+
1 , y
+
2 , . . . , y
′+
r ,
a11, a12, . . . , a1r, a21, a22, . . . , a2r, . . . , am1, am2, . . . , amr), where (x+1 , x
+
2 , . . . , x
+
r ) and (y+1 , y
+
2 ,
. . . , y+r ) are coordinates of the flag xIy written in the chosen base of K = Qr,
and (ai1, ai2, . . . , air), i = 1, 2, . . . ,m, are the coordinates of the invariant values
a1(x), a2(x), . . . , am(x) of the point x from the flag. Let the flag from Kn+1 be defined by the
vector v of the free module Qr(n+1). Let L1 and L2 be two invertible affine transformations of
the plainspace Qr(n+1). We assume that they are a part of the key of our symmetric algorithm.
For simplification, we assume that the length of a symbolic key is an odd number.
Let us denote, by N , the composition of maps Nx1+d1 , Ny1+d+
1
, Nx2+d2 , Ny2+d+
2
, . . . , Nxl+dl ,
Ny1+d+
l
. The encryption consists of the following steps:
(a) application of the affine map L1 to the plainspace v, the resulting vector L1(v) from
Qr(n+1) have to be written as a vector u from the free module over the extension K of Q.
(b) the computation of the vector w = N(u) and its presentation by the vector w+ in the
chosen base of Qr(n+1).
(c) computation of the vector z = L2(w
+). The deciphering is the reverse process. The
correspondent (Bob) receives the ciphertext z in the form of a vector from Qr(n+1). He computes
L2
−1 and writes this vector as a element w from Kn+1. Then Bob defines u = N−1(w) and
writes the result in the form of a vector u+ with coordinates from Q. For the determination of
the plainspace v, he writes L−1
1 (u+) in the form of an element from Kn+1.
On the properties of an encryption map It turns out that, independently of the choice
of sequences d1, d2, . . . , dl and d+1 , d+2 , . . . , d
+
l , the transformation N is a polynomial map of ki-
nd (x1, x2, . . . , xn) → (f1(x1, x2, . . . , xn+1), f2(x1, x2, . . . , xn+1), . . . , fn(x1, x2, . . . , xn+1)), where
all polynomials fi(x1, x2, . . . , xn+1), i = 1, 2, . . . , n, n + 1, are cubic (see [15] and references
therein). This means that both the encryption map E = L1NL2 and the inverse map E−1 =
= L−1
1 N−1L−1
2 , together with the inverse map E′ = L′
2N
′L′
1 are cubic transformations. Recall
that E−1 corresponds to d1, d2, . . . , dl and d′1, d
′
2, . . . , d
′
l written in the inverse order.
Let us assume that a fixed key is in multiple use, and the adversary has an access to some
plaintext and can obtain a rather large set of pairs of the plaintext-ciphertext kind. In this case,
60 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2014, №3
the fact that the degree of the polynomial inverse map is bounded by 3 makes the linearization
attacks feasible. In fact, the key can be computed in a polynomial time. The above-written
condition is not a realistic one. So, the cubic encryption map was used for the protection of real
communication networks for various rings.
First, the algorithms were used in the case of prime finite fields (e. g., Z127). Then the ari-
thmetical rings Z2n , n = 7, 8, 16, 32, and the Galois fields F2n for n = 7, 8, 16, 32, were used. The
attractive side of the encryption algorithm is its speed (complexity O(nl)), resistance against
attacks without access to plaintexts. In the case of l 6 [n/2] + 2 and K = Fq, the different
sequences di (di 6= di+1), d
+
i , (d+i 6= d+i+1, i = 1, 2, . . . , l) give different ciphertexts. The generali-
zations of this fact to the case of arbitrary commutative rings are given in [13]. Computer
simulations (see surveys [14], [15] and references therein) in the case of a special choice of affi-
ne transformations demonstrate that the encryption function has strong mixing properties. It
satisfies the well-known Madryga’s requirements: change of one character in the plaintext or in
the key leads to a change of the vast majority characters of the ciphertext if the alphabet K
is used.
The enciphering algorithm with the key of variative length described in the example gi-
ven above allows one to increase the level of resistance of an encryption against attacks with
an access to some plaintexts without essential change of the robustness and the mixing qua-
lity.
The dependence of the length function l on a plainspace makes classical linearization attacks
impossible.
Let us show that the complexity of the known difficult discrete logarithm problem can serve
as a security argument for the algorithm. Assume that the sequences di and d+i , i = 1, 2, . . . , l,
are periodic. This means that there exists r such that l = rj, d
+
i+r = d+i , di+r = di. Additionally,
we assume that L1 = L2−1
and the parameter r is constant. Let G = L1N
+L2, where the
map N+ = Nx1+d1Ny1+d+
1
Nx2+d2Ny2+d+
2
· · ·Nxr + dl, Nyr + d+r L2 is computed with the use of
some computer algebra program. The resulting polynomial transformation G will be written
as (x1, x2, . . . , xn) → (g1(x1, x2, . . . , xn+1), g2(x1, x2, . . . , xn+1), . . . , gn(x1, x2, . . . , xn+1)), where
each polynomial gi(x1, x2, . . . , xn+1), i = 1, 2, . . . , n + 1, is a cubic expression given by a list of
monomials in lexicographical order. So, the value of G at the given point will be computed in
the time bounded by O(n4). Note that the order of a map G coincides with the order of N+.
As follows from the above-written facts, each power of the map G in the symmetric group
S(Kn) is a cubic map or the identity. Let M be a multiplicative subset of the commutative
ring K. This means that M is closed under multiplication and does not contain zero. If all
di + di+1, d
+
i + d+i+1, i = 1, 2, . . . , l, and d1 + dl, d
+
1 + d+l are elements of M , then the order
of the transformation G tends to infinity with the growth of the parameter n. The increase of
the map order is going on with the increase of the characteristic of the ground ring (see [13]
and references therein).
Recall that, in our case, the correspondents use the periodic map G = Gr, and the length
function l is a function of the plainspace, which can generally has any value. We assume that
the adversary can get many pairs (p, c), where p is a plaintext, and c is a corresponding ci-
phertext.
Additionally, we assume that the basic polynomial G is known to the adversary. The natural
attack on the key can be conducted via the investigation of the equation Gz(p) = c with the known
tuples p and c and the unknown positive integer z. So, we get the discrete logarithm problem
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2014, №3 61
for the cyclic subgroup generated by G. We have to solve the equation Gz = H, where H is
some function transforming p into c. The opponent could not solve this problem in the case of a
sufficiently large number of variables, because the order of G is increasing, but the degree of the
right-hand side is still cubic. The investigation of iterations of G brings no additional data for the
investigation of the discrete logarithm problem. The adversary can determine G−1 by computing
many pairs of kind (v,G(v)) and by conducting a linearization attack. The computation of the
unknown functions l = l(x), j(x) = l(x)/r, and G−j(x) is related to the above-mentioned discrete
logarithm problem with the base G. Note that the function j(x) can be very sophisticated, for
instant, defined as a specialization of the known Matijasevich polynomial.
The author expresses his sincere gratitude to Professor Richard Weiss (Boston) for his constant
support of the idea to use geometries over diagrams for the problems of informational defence and a
stimulating lecture course at the University of Maria Curie Sklodowska in Lublin.
1. Buekenhout F. Handbook of incidence geometry. – Amsterdam: North-Holland, 1995. – 1399 p.
2. Ustimenko V. Maximality of affine group and hidden graph cryptosystems // J. Alg. Discr. Math. – 2005. –
No 1. – P. 133–150.
3. Ustimenko V. Linear interpretations for flag geometries of Chevalley groups // Ukr. Mat. Zh. – 1990. –
42, No 3. – P. 383–387.
4. Ustimenko V. On the varieties of parabolic subgroups, their generalisations and combinatorial applica-
tions // Acta Appl. Math. – 1998. – 52. – P. 223–238.
5. Ustimenko V. Small Schubert cells as subsets in Lie algebras // Funct. Analysis and Appl. – 1991. – 25,
No 4. – P. 81–83.
6. Ustimenko V. Geometries of twisted groups of Lie type as objects of linear algebra // Questions of Group
Theory and Homological Algebra. – Yaroslavl: Yaroslavl State Univ., 1990. – P. 33–56 (in Russian).
7. Beutelspachera A. Enciphered geometry. Some applications of geometry to cryptography // Ann. of Discr.
Math. – 1988. – 37. – P. 59–68.
8. Ustimenko V. Graphs with special arcs and cryptography // Acta Appl. Math. – 2002. – 74, No 2. –
P. 117–153.
9. Ustimenko V. Schubert cells in Lie geometries and key exchange via symbolic computations // Albanian
J. of Math. – 2010. – 4, No 4. – P. 135–145.
10. Lazebnik F., Ustimenko V.A., Woldar A. J. New series of dense graphs of high girth // Bull. (New Series)
of AMS. – 1995. – 32, No 1. – P. 73–79.
11. Ustimenko V. Coordinatisation of trees and their quotients // Voronoj’s Impact on Modern Science. –
Kiev: Institute of Mathematics of the NASU, 1998. – 2. – P. 125–152.
12. Ustimenko V. Algebraic groups and small world graphs of high girth // Albanian J. of Math. – 2009. – 3,
No 1. – P. 25–33.
13. Ustimenko V., Romanczuk U. On dynamical systems of large girth or cycle indicator and their applications
to multivariate cryptography // Artificial Intelligence, Evolutionary Computing and Metaheuristics. –
Berlin: Springer, 2013. – P. 257–285.
14. Ustimenko V. On the cryptographical properties of extreme algebraic graphs // Algebraic Aspects of Digital
Communications, edited by T. Shaska, E. Hasimaj. – Amsterdam: IOS Press, 2009. – P. 256–281.
15. Ustimenko V. On the extremal graph theory for directed graphs and its cryptographical applications //
Advances in Coding Theory and Cryptography, edited by T. Shaska, W.C. Huffman, D. Joyner, V. Usti-
menko. – Singapore: World Scientific, 2007. – 3. – P. 181–200.
Received 02.09.2013Institute of Telecommunications
and Global Information Space, the NAS of Ukraine, Kiev
University of Maria Curie Sklodowska, Poland
62 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2014, №3
В.А. Устименко
O блужданиях переменной длины в системах инцидентности
Шуберта и полиномиальном потоковом шифровании
Предложен алгоритм потокового шифрования, основанный на блужданиях на многообра-
зиях флагов системы Шуберта, определенной над коммутативным кольцом. Примером
системы Шуберта является ограничение отношений инцидентности геометрии простой
группы Ли нормального типа на объединение больших клеток максимальной размерности.
Более общиe примеры соответствуют группам Каца–Муди. Приведен пример использова-
ния таких симметричних алгоритмов, определенных на периодических блужданиях, для
создания публичного ключа, безопасность которого связана с проблемой дискретного лога-
рифма для циклических подгрупп полиномиальных преобразований возрастающего порядка.
В.О. Устименко
Про блукання змiнної довжини в системах iнцидентностi Шуберта
та полiномiальному струменевому кодуваннi
Запропоновано алгоритм струменевого кодування, що грунтується на блуканнях на много-
видах прапор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ї наук України, 2014, №3 63
|
| id | nasplib_isofts_kiev_ua-123456789-87142 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | English |
| last_indexed | 2025-12-07T13:33:55Z |
| publishDate | 2014 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Ustimenko, V.A. 2015-10-11T16:29:34Z 2015-10-11T16:29:34Z 2014 On walks of variable length in the Schubert incidence systems and multivariate flow ciphers / V.A. Ustimenko // Доповiдi Нацiональної академiї наук України. — 2014. — № 3. — С. 55-63. — Бібліогр.: 15 назв. — англ. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/87142 519.1,514.128 The flow cipher algorithm based on walks at the flag variety of a Schubert system over the finite commutative ring is proposed. The restriction of the incidence relation of the geometry of a finite simple Lie group of the normal type on the union of large Schubert cells of the maximal dimension is an example of the Schubert system. More general examples are connected with Kac–Moody groups. We introduce some applications of such ciphers based on periodic walks for the construction of multivariate private keys, security of which is connected with the discrete logarithm problem for cyclic subgroups of polynomial transformations of increasing order. Запропоновано алгоритм струменевого кодування, що грунтується на блуканнях на многовидах прапорiв системи Шуберта, визначеної над комутативним кiльцем. Прикладом системиШуберта є обмеження вiдношень iнцидентностi геометрiї простої групи Лi нормального типу на об’єднання великих клiтин максимального вимiру. Бiльш загальнi приклади пов’язанi з групами Каца–Мудi. Наводено приклад використання таких струменевих алгоритмiв, визначених на перiодичних блуканнях, для створення вiдкритого полiномiального ключа, безпека якого пов’язана з проблемою дискретного логарифма для циклiчних пiдгруп полiномiальних перетворень зростаючого порядку. Предложен алгоритм потокового шифрования, основанный на блужданиях на многообразиях флагов системы Шуберта, определенной над коммутативным кольцом. Примером системы Шуберта является ограничение отношений инцидентности геометрии простой группы Ли нормального типа на объединение больших клеток максимальной размерности. Более общиe примеры соответствуют группам Каца–Муди. Приведен пример использования таких симметричних алгоритмов, определенных на периодических блужданиях, для создания публичного ключа, безопасность которого связана с проблемой дискретного логарифма для циклических подгрупп полиномиальных преобразований возрастающего порядка. The author expresses his sincere gratitude to Professor Richard Weiss (Boston) for his constant support of the idea to use geometries over diagrams for the problems of informational defence and a stimulating lecture course at the University of Maria Curie Sklodowska in Lublin. en Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика On walks of variable length in the Schubert incidence systems and multivariate flow ciphers Про блукання змiнної довжини в системах iнцидентностi Шуберта та полiномiальному струменевому кодуваннi O блужданиях переменной длины в системах инцидентности Шуберта и полиномиальном потоковом шифровании Article published earlier |
| spellingShingle | On walks of variable length in the Schubert incidence systems and multivariate flow ciphers Ustimenko, V.A. Інформатика та кібернетика |
| title | On walks of variable length in the Schubert incidence systems and multivariate flow ciphers |
| title_alt | Про блукання змiнної довжини в системах iнцидентностi Шуберта та полiномiальному струменевому кодуваннi O блужданиях переменной длины в системах инцидентности Шуберта и полиномиальном потоковом шифровании |
| title_full | On walks of variable length in the Schubert incidence systems and multivariate flow ciphers |
| title_fullStr | On walks of variable length in the Schubert incidence systems and multivariate flow ciphers |
| title_full_unstemmed | On walks of variable length in the Schubert incidence systems and multivariate flow ciphers |
| title_short | On walks of variable length in the Schubert incidence systems and multivariate flow ciphers |
| title_sort | on walks of variable length in the schubert incidence systems and multivariate flow ciphers |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/87142 |
| work_keys_str_mv | AT ustimenkova onwalksofvariablelengthintheschubertincidencesystemsandmultivariateflowciphers AT ustimenkova problukannâzminnoídovžinivsistemahincidentnostišubertatapolinomialʹnomustrumenevomukoduvanni AT ustimenkova obluždaniâhperemennoidlinyvsistemahincidentnostišubertaipolinomialʹnompotokovomšifrovanii |