On the flag geometry of simple group of Lie type and multivariate cryptography
We propose some multivariate cryptosystems based on finite BN-pair G defined over the fields Fq. We convert the adjacency graph for maximal flags of the geometry of group G into a finite Tits automaton by special colouring of arrows and treat the largest Schubert cell Sch isomorphic to vector space...
Gespeichert in:
| Veröffentlicht in: | Algebra and Discrete Mathematics |
|---|---|
| Datum: | 2015 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2015
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/152794 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | On the flag geometry of simple group of Lie type and multivariate cryptography / V. Ustimenko // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 130-144. — Бібліогр.: 18 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-152794 |
|---|---|
| record_format |
dspace |
| spelling |
Ustimenko, V. 2019-06-12T21:06:52Z 2019-06-12T21:06:52Z 2015 On the flag geometry of simple group of Lie type and multivariate cryptography / V. Ustimenko // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 130-144. — Бібліогр.: 18 назв. — англ. 1726-3255 https://nasplib.isofts.kiev.ua/handle/123456789/152794 We propose some multivariate cryptosystems based on finite BN-pair G defined over the fields Fq. We convert the adjacency graph for maximal flags of the geometry of group G into a finite Tits automaton by special colouring of arrows and treat the largest Schubert cell Sch isomorphic to vector space over Fq on this variety as a totality of possible initial states and a totality of accepting states at a time. The computation (encryption map) corresponds to some walk in the graph with the starting and ending points in Sch. To make algorithms fast we will use the embedding of geometry for G into Borel subalgebra of corresponding Lie algebra. We also consider the notion of symbolic Tits automata. The symbolic initial state is a string of variables tα∈Fq, where roots α are listed according Bruhat's order, choice of label will be governed by special multivariate expressions in variables tα, where α is a simple root. Deformations of such nonlinear map by two special elements of affine group acting on the plainspace can produce a computable in polynomial time nonlinear transformation. The information on adjacency graph, list of multivariate governing functions will define invertible decomposition of encryption multivariate function. It forms a private key which allows the owner of a public key to decrypt a ciphertext formed by a public user. We also estimate a polynomial time needed for the generation of a public rule. The paper is dedicated to the memory of my teacher Lev Kaluzhnin.His wide mathematical vision brought us, participants of his Seminar, thelight of Modern Algebra. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics On the flag geometry of simple group of Lie type and multivariate cryptography Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
On the flag geometry of simple group of Lie type and multivariate cryptography |
| spellingShingle |
On the flag geometry of simple group of Lie type and multivariate cryptography Ustimenko, V. |
| title_short |
On the flag geometry of simple group of Lie type and multivariate cryptography |
| title_full |
On the flag geometry of simple group of Lie type and multivariate cryptography |
| title_fullStr |
On the flag geometry of simple group of Lie type and multivariate cryptography |
| title_full_unstemmed |
On the flag geometry of simple group of Lie type and multivariate cryptography |
| title_sort |
on the flag geometry of simple group of lie type and multivariate cryptography |
| author |
Ustimenko, V. |
| author_facet |
Ustimenko, V. |
| publishDate |
2015 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| description |
We propose some multivariate cryptosystems based on finite BN-pair G defined over the fields Fq. We convert the adjacency graph for maximal flags of the geometry of group G into a finite Tits automaton by special colouring of arrows and treat the largest Schubert cell Sch isomorphic to vector space over Fq on this variety as a totality of possible initial states and a totality of accepting states at a time. The computation (encryption map) corresponds to some walk in the graph with the starting and ending points in Sch. To make algorithms fast we will use the embedding of geometry for G into Borel subalgebra of corresponding Lie algebra.
We also consider the notion of symbolic Tits automata. The symbolic initial state is a string of variables tα∈Fq, where roots α are listed according Bruhat's order, choice of label will be governed by special multivariate expressions in variables tα, where α is a simple root.
Deformations of such nonlinear map by two special elements of affine group acting on the plainspace can produce a computable in polynomial time nonlinear transformation. The information on adjacency graph, list of multivariate governing functions will define invertible decomposition of encryption multivariate function. It forms a private key which allows the owner of a public key to decrypt a ciphertext formed by a public user. We also estimate a polynomial time needed for the generation of a public rule.
|
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/152794 |
| citation_txt |
On the flag geometry of simple group of Lie type and multivariate cryptography / V. Ustimenko // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 130-144. — Бібліогр.: 18 назв. — англ. |
| work_keys_str_mv |
AT ustimenkov ontheflaggeometryofsimplegroupoflietypeandmultivariatecryptography |
| first_indexed |
2025-11-24T21:46:39Z |
| last_indexed |
2025-11-24T21:46:39Z |
| _version_ |
1850498513455022080 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 19 (2015). Number 1, pp. 130–144
© Journal “Algebra and Discrete Mathematics”
On the flag geometry of simple group of Lie
type and multivariate cryptography
Vasyl Ustimenko
Communicated by V. I. Sushchansky
Abstract. We propose some multivariate cryptosystems
based on finite BN -pair G defined over the fields Fq. We convert
the adjacency graph for maximal flags of the geometry of group G
into a finite Tits automaton by special colouring of arrows and treat
the largest Schubert cell Sch isomorphic to vector space over Fq
on this variety as a totality of possible initial states and a totality
of accepting states at a time. The computation (encryption map)
corresponds to some walk in the graph with the starting and ending
points in Sch. To make algorithms fast we will use the embedding of
geometry for G into Borel subalgebra of corresponding Lie algebra.
We also consider the notion of symbolic Tits automata. The
symbolic initial state is a string of variables tα ∈ Fq, where roots α
are listed according Bruhat’s order, choice of label will be governed
by special multivariate expressions in variables tα, where α is a
simple root.
Deformations of such nonlinear map by two special elements of
affine group acting on the plainspace can produce a computable
in polynomial time nonlinear transformation. The information on
adjacency graph, list of multivariate governing functions will define
invertible decomposition of encryption multivariate function. It
forms a private key which allows the owner of a public key to
decrypt a ciphertext formed by a public user. We also estimate a
polynomial time needed for the generation of a public rule.
Key words and phrases: Multivariate Cryptography, flag variety, Geometry of
Simple Group of Lie type, Schubert cell, symbolic walks.
V. Ustimenko 131
1. Introduction
Linear codes over finite field Fq are subspaces of Fq
n. The subspaces
form a finite projective geometry of dimension n−1, which is a very impor-
tant object of Pure Mathematics and Classical Coding Theory. Since late
80th some other applications of Finite Projective Geometry to Information
Security have appeared (see [3], [4], devoted to Network Coding). In par-
ticular, it was used in Cryptography ( see [5], where projective geometry
were used for audentification protocols, or [6], [7], where it was used for the
symmetric encryption and key exchange protocols respectively). Finite
geometries now are widely used as tools for secret sharing. In current
article we will introduce a new public key algorithms based on finite Lie
geometries of normal and twisted type over the Coxeter Dynkin diagrams
An, Bn, Cn and Dn. Public key algorithm of Multivariate Cryptography
[1] based on finite projective geometry already was introduced recently at
the conference Algebraic Combinatoric and Applications 2015 (ALCOMA
2015, Kloster Banz, Germany , see the program and book of abstracts on
its web). In this paper we are going to present more general cryptosystem
corresponding to the geometry of a finite simple group of rank n > 2.
In section 2 we present the concepts of a family of multivariate maps
with polynomially invertible decomposition and its applications to cryp-
tography.
In section 3 symbolic Tits automaton for the case of variety of maximal
flags of the geometry of finite simple group will be defined. Its computa-
tions are polynomial maps of the vector space Fq
N , where N is a number
of positive roots in corresponding root system. In fact, some special Tits
automata over various diagrams have been used for the construction of
key exchange protocols [7].
In section 3 we also consider the invertibility conditions for the map
produced by Tits automaton.
We show that the polynomial map produced by Tits automaton can
be treated as the polynomial map with invertible decomposition.
In section 4 we consider an interpretation of the geometry of simple
Lie group of normal type and its flag system in terms of linear algebra.
We will use the approach suggested in [9], [10], [11] for the description
of the geometry of Shevalley group and the work of corresponding Tits
automaton.
Conclusions are in section 5. The complexity estimates for the public
key algorithm based on flag variety of geometry of Simple Group of Lie
type are presented there.
132 On the flag geometry of simple group of Lie type
2. On the general scheme for a cryptosystem
based on a family of multivariate maps
with an invertible decomposition
Multivariate cryptography (see [1]) is one of the directions of Postquan-
tum Cryptography, which concerns with algorithms resistant to hypothetic
attacks conducted by Quantum Computer. The encryption tools of Multi-
variate Cryptography are nonlinear multivariate transformations of affine
space Kn, where K is a finite commutative ring.
Recall that affine Cremona group C(Kn) is a totality of invertible
maps f of affine space Kn over a Commutative ring K into itself, such
that the inverse map f−1 is also a polynomial one.
Let us refer to the sequence of maps f(n) from C(Kn), n = 1, 2, . . .
as a family of polynomial degree if the degree of each transformation is a
parameter s of the size O(nt).
We say that a family f(n) ∈ C(Kn) has a polynomially invert-
ible decomposition if f(n) can be written as a composition of elements
f1(n), f2(n), . . . , fk(n)(n) and the knowledge on this decomposition will
allow us to compute the value of y = f(x) and the re-image of given y in
polynomial time k(n)O(nd) (see [2]).
We can create a new encryption map h(n) as a deformation τLf(n)τR
of f(n) with special invertible affine transformations τL and τR of Kn.
If the family h(n) on a symbolic level is presentable in a computable
form and the value of h(n) in given point of affine space is computable in
polynomial time, then h(n) is also a map with polynomially invertible
decomposition.
Let f(n) ∈ C(Kn)) be a family of transformations with polynomially
invertible decomposition. Then the following public key can be imple-
mented.
Alice chooses parameter n. She knows the decomposition f(n) =
f(n, 1) f(n, 2) . . . f(n, k(n)). Notice that some transformations f(n, i)
can be not a bijective. Additionally she chooses an invertible monomial
linear transformations τL of kind xi → λixπ(i), where π is a permutation
on the set {1, 2, . . . , n}. Alice also takes a bijective affine transformation
τR of kind x → xA + b, where A is a non-singular matrix.
She computes the transformation G = τLf(n)τR in affine Cremona
group and writes it in the standard form xi → gi(x1, x2, . . . , xn), i =
1, 2, . . . , n.
Assume that public rules gi are governed by the lists of monomial
terms, written in some chosen order.
V. Ustimenko 133
Notice, that the left application of τL does not change the number of
monomial terms. The right application of τR can increase the number of
monomial terms in n times. So the density den(τLf(n)τR) is O(nd+1).
A public user (Bob) gets symbolic transformation G = G(n) in the
form of public rule xi → gi(x1, x2, . . . , xn). He can encrypt by computation
of the value of G on his plaintext (x1, x2, . . . , xn) in O(ns+d+1).
Alice keeps the decomposition f(n) = f(n, 1)f(n, 2) . . . f(n, k(n)) as
a deep secret. It allows her to decrypt Bob’s ciphertext for k(n)O(nt+3)
elementary steps, because applications of known τL
−1 and τR
−1 cost O(n)
and O(n2), respectively. If Bob does not have an additional information
on the transformation G then he has a difficult task of computation G−1.
3. Symbolic Tits automata and bijective multivariate maps
Below we consider an abstract scheme for cryptosystem for special
class of geometrical maps corresponding to the geometry of finite simple
group G = Xn(q) of rank n > 2. In this article we assume that Xn(q) is
a Shevalley group (in other terminology a simple group of normal type).
This group corresponds to Coxeter-Dynkin diagram Xn which also
defines Weyl group W corresponding to root system Ω. Let α1, α2, . . . , αn
be the list of simple roots, Ω+ and Ω− correspond to the list of sets of
positive and negative roots. We assume that |Ω+| = |Ω−| = N . For each
β ∈ Ω subgroup Uβ =< xβ(t)|t ∈ Fq > is isomorphic to additive group
Fq (see [12]). Group G is generated by Uβ , β ∈ Ω, its unipotent subgroup
U =< Uβ|β ∈ Ω+ > is a Sylow p subgroup of Xn(q), q = pm for prime
integer p. In fact, |U | = qN .
Let P1, P2, . . . , Pn be the list of maximal parabolic subgroups of G
corresponding to nodes of diagram Xn, then the Borel subgroup P1 ∩ P2 ∩
. . . Pn coincides with the normaliser NG(U) of the unipotent subgroup U .
The geometry of G is a totality Γ(G) of all left cosets gPi, where
g ∈ G, 1 6 i 6 n with the type function t, such that t(gPi) = i), and
symmetric and irreflexive incidence relation I, such that a, b ∈ Γ(G) if
and only if t(a) 6= t(b) and the intersection of left cosets is nonempty. Let
Γi(G) = {a ∈ Γ(G)|t(a) = i}. We refer to a subset F of Γ(G) as a flag of
the geometry if each pair of elements from F is incident. We assume that
t(F ) = {t(a)|a ∈ F}. In case of maximal flag t(F ) = {1, 2, . . . , n} = M .
Let GF (G) be the totality of maximal flags of Γ(G) with the partition
onto large Schubert cells, i. e. orbits of unipotent subgroup U on this set.
In fact there is the unique largest Schubert cell of size qN on which the
unipotant group acts regularly.
134 On the flag geometry of simple group of Lie type
Assume that for a flag F its type is t(F ) = M − {i}. The residue
Res(F ) = {x ∈ Γi|xIa, a ∈ F}. We assume that Ext(F ) is the totality of
all flags of kind F ∪ {x}, x ∈ ResF . In fact |Ext(F )| = |Res(F )| = q + 1.
The elements of Ext(F ) are from two different Schubert cells S0 and
S1 such that Ext(F ) ∩ S0 and Ext(F ) ∩ S1 have cardinalities 1 and q.
If F ∪ {y}, where y ∈ Res(F ) is located in Schubert cell S0 then we
join F and maximal flag F ∪ {y} by a directed arrow labeled by pair
(i, ∞), where ∞ is a formal symbol. If y ∈ S1, then there is a unique
root subgroup Uβ = {xβ(t)|t ∈ Fq} which acts regularly on Ext(F ) ∩ S1.
Element z = F ∪{y} from S1 can be identified with corresponding element
xr(t) ∈ U and with parameter µ(z) = t ∈ Fq. We join F and z by an
arrow with the label (i, µ(z)) in that case.
Let F be a maximal flag. For each i ∈ {1, 2, . . . , n} we consider a
subflag F i of type M − {i} and join F and representative y from Ext(F i)
by an arrow with the label (i, µ(y)), where µ(y) ∈ {∞} ∪ Fq. So we
constructed a labeled directed graph T (G) on the set of maximal flags
with n(q + 1) output arrows for each vertex, n of them are loops.
We convert T (G) to Tits automaton by an announcement that the
initial and accepting states of this automaton have to be elements of the
largest Schubert cells.
If we ignore labels and loops of T (G), this graph can be identified
with the directed graph of adjacency relation : two flags are adjacent if
their intersection has cardinality n − 1. The action of unipotant subgroup
U defines the partition on the large Schubert cells and labeling of T (G).
Let F, F ′ be flags joined by an arrow of T (G) labeled by (i, a), i ∈ M
,a ∈ ∞ ∪ Fq. The transition function T i
a sends F to F ′ for each pair
of flags joined by arrow with the label (i, a). The regular computation
of Tits automaton is the composition E of T i1
a1
, T i2
a2
, . . . , T ir
ar , where
il 6= il+1, l = 1, 2, . . . , r − 1 which sends flag from the largest Schubert cell
to another element of this cell. As it follows from the definition of Tits
automaton its computation is not a bijective linear map on the vector
space of the largest Schubert cell. The existence of the reverse directed
walk from the image to the initial state insures that the initial state is
uniquely defined by its projection on tangent space and the computation.
We also define a Schubert automaton Sch(G) as one obtained from
Tits automaton for T (G) by deleting all flags located outside of the largest
Schubert cell together with input and output arrows and their labels.
The regular action of unipotent subgroup U on the largest Schubert
cell Sch(G) allows us to identify Sch(G) with Fq
N .
V. Ustimenko 135
Finally we define symbolic Tits automaton with the symbolic initial
state (t1, t2, . . . , tN ), where ti are variables corresponding to roots from
Ω+ and parameters aj 6= ∞ are polynomials in N variables ti1
, ti2
, . . . , tin
related to simple roots. The computation of a symbolic Tits automaton in-
duces polynomial transformation En of Fq
N . The map En corresponds to a
”symbolic walk” Sn,m of length m in An(q). The map En appears together
with their decomposition on “symbolic transition functions”. The infinite
families of highly nonlinear bijective computable transformations En with
polynomially invertible decompositions have been introduced. So the
described above (section 1) scheme can be implemented to create a cryp-
tosystem in the case of groups of normal type An(q), Bn(q), Cn(q), Dn(q)
and twisted groups 2An(q).
Symbolic Tits automata of groups of restricted rank E6(q), E7(q),
E8(q), F4(q), G2(q), 2E6(q), 2F4(q), q = 22l+1, 2D4(q), 3D4(q) (see [12])
can be used for the construction of S-boxes and hash functions.
Special Tits automata can be a base for stream ciphers (see [8]).
Let us consider a regular computation of symbolic Tits automaton with
the symbolic initial state (t1, t2, . . . , tN ), where ti, i = 1, 2, . . . , N are vari-
ables, defined by putting labels from Fq[ti1
, ti2
, . . . , tin ]∪{∞}. The special-
ization of symbolic initial state t1 = a1, t2 = a2, . . . , tN = aN produces the
computation of Tits automaton with initial state (a1, a2, . . . , aN ) ∈ Fq
N .
Let e1, e2, . . . , eN be the fixed basis which we use for writing elements of
Fq
N as tuples.
We refer to the symplectic subspace S of all tuples of kind ei1
,ei2
,. . . ,ein
as a tangent subspace of the largest Schubert cell. The computation in a
symbolic Tits automaton sends a symbolic initial state t = (t1, t2, . . . , tN )
into E(t) , where E is a polynomial multivariate map of Fq
N into it-
self. Tangent subspace is invariant subspace for a transformation E.
Let (j1, f1), (j2, f2), . . . , (jk, fk) be the sequence of the labels such that
fi ∈ Fq[ti1
, ti2
, . . . , tin ] ∪ ∞ for the computation of a symbolic Tits au-
tomaton.
We assume that js 6= is+1, s = 1, 2, . . . , k − 1. The computation E is
the composition of symbolic transition functions Gi1
fi1 , Gi2
fi2 , . . . , Gim
fim .
Recall, that the resulting state of our computation is the flag of the largest
Schubert cell.
Let E′ be the restriction of E on S.
Proposition 3.1. The map E is a bijection if and only if its restriction
E′ on the tangent space is one to one correspondence.
136 On the flag geometry of simple group of Lie type
Proof. Let us assume that bβ, β ∈ Ω+ are coordinates of the image
of the vector t. The bijective map E′ can be written in the form
hi(tα1
, tα2
, . . . tαn) = bi, i = 1, 2, . . . , n.
Theoretically we can solve this system and find tα1
= a1, tα2
= a2,
. . . , tαn = an. After that we can compute cj = fj(a1, a2, . . . , an) for
j = 1, 2, . . . , m. The map E acts outside of tangent space as tβ →
Gi1
c1Gi2
c2 . . . Gim
cm(t) for nonsimple root β. It is a linear map depending
on N −n variable. Notice that alternatively we can consider the specialisa-
tion tα1
= a1, tα2
= a2, . . . , tαn = an of standard presentation of E which
exists and write linear equations. We can take a unique solution of system
Gi1
c1Gi2
c2 . . . Gim
cm(t) = bβ for variables tβ, β ∈ Ω+ − {α1, α2, . . . , αn}.
So we get the well defined unique re-image t.
The map E corresponds to a symbolic walk of a length k in a symbolic
Tits automaton.
Proposition 3.2. Let map E be a bijection defined by Tits automaton
and it is computable in a given vector from Fq
N in a polynomial time.
Assume that a tangent space is known and the reimage of E′ in a given
point is also computable in a polynomial time. Then the reimage of E in
a given point is computable in a polynomial time.
Proof. The restriction of map E on symplectic subspace S is the map
tαr → ajr [tα1
, tα2
, . . . , tαn ] = t′
αr , r = 1, 2, . . . , n, where jr is the last
appearance of r as a first coordinate of label (r, al), al ∈ F [tα1
, tα2
, . . . , tαn ]
if such appearance exists. In the opposite case we have simply tαr → tαr .
We refer to expressions ajr [tα1
, tα2
, . . . , tαn ] as tangent coordinates of
the walk (or computation).
The computation of the inverse for E|S in polynomial time will allow
us to solve the system of equations ajr [tα1
, tα2
, . . . , tαn ] = t′
αr
for tαi
=
t∗
i, i = 1, 2, . . . , n. It gives us an opportunity to compute parameters
as = fis(t∗
1, t∗
2, . . . t∗
n−1), s = 1, 2, . . . , m.
After that we can consider the computation of Tits automaton
Gi1
a1Gi2
a2 . . . Gim
am sending vector with coordinates tβ onto the known
image of E. Recall that tαi
coincides with t∗
i, i = 1, 2, . . . , n. So, we have
system of N − n linear equations in N − n variables, which has a unique
solution. It is clear that we can solve this system for polynomial time
O(N3) and get the re-image of the map E. Notice, that we can get
system of linear equations with N − n variable via specialisation tαi
= t∗
i,
i = 1, 2, . . . , n of polynomial map E.
V. Ustimenko 137
Corollary 3.3. Under the conditions of previous statement the
map E is a map with the polynomially invertible decomposition
E = Gi1
fi1 Gi2
fi2 . . . Gim
fim .
We say that the computation of Tits automaton is a tame one if it
corresponds to symbolic walk given by (j1, f1), (j2, f2), . . . , (jk, fk), fi ∈
Fq[xi1
, xi2
, . . . , xim ] ∪ ∞, for i = 1, 2, . . . , k, js 6= js+1, s = 1, 2, . . . , k − 1,
each r ∈ M appears in the list j1, j2, . . . , jk not more than O(1) times
and degree of each fi is bounded by O(n) and density O(1).
In the last section of the paper we show that the following statement
holds.
Lemma 3.4. Let En be the map corresponding to tame computation
of Tits automaton. Then it has a polynomial density and a polynomial
degree bounded by O(n3) and O(n2) respectively.
Example. Polynomially invertible En corresponding to the tame com-
putation of Tits automaton can be constructed by the following method.
We choose the length of the walk m as a linear expressions from n. We
assume additionally that the restriction E′ of E onto S is the bijective
map tis → bistµ(is)
kis + dis , s ∈ {1, 2, . . . , n}, where µ is a permutation
on {i1, i2, . . . , in}, and bis , dis are constants from Fq and kis are constant
integers such that the equation of kind zkis = b have unique solution. We
assume that the field Fq is fixed. It means that the re-image for E′ in
given vector can be computed for O(n) elementary steps.
Notice that functions fjs which are not a tangent coordinates can be
arbitrary polynomials of degree O(n) and density O(1).
We refer to such invertible map E′ as invertible tame map. We can use
more general maps of kind E′ = τ1Hτ2 where τi(x) = xAi + ci, i = 1, 2
where rows and columns of invertible n×n matrices Ai have finite number
of nonzero entries and H is an invertible tame map. Natural example of
tame computation is the following.
Let E : Fq
N → Fq
N be the polynomial map induced by a regular
tame computation of symbolic Tits automaton, such that different from
∞ labels are “shifted” monomial terms of kind at
s1(n)
i1
t
s2(n)
i2
, . . . , t
sn(n)
in
+ b,
where a and b are constants, parameters si(n), i = 1, 2, . . . , n are linear
expressions in n, such that s1(n) + s2(n) + · · · + sn−1(n) is also a linear
expression. We choose the length of the walk k as a linear expressions
from n.
138 On the flag geometry of simple group of Lie type
Remark. Let us consider the deformation Ẽn = τ1Enτ2 of ∆, where τ1 is
invertible monomial transformation ti → λitπ(i), λi ∈ F ∗
q , i = 1, 2, . . . , N ,
π is a permutation on {1, 2, . . . , N}, τ2 is a general bijective affine map
of Fq
N into itself.
For the deformation Ẽ of E the equality deg(Ẽ) = deg(E) holds.
Transformations E and τ1E have the same densities. Density of Eτ2 is at
most n2 times larger than the density of E.
Let us evaluate the complexity of the multivariate cryptosystem based
on tame computation of the Tits automaton.
Notice that evaluations of degree and density shows that Bob can
compute the value of Ẽ in a given point for O(n7) = O(N3+1/2) elementary
steps.
We can use invertible tame computations defined in the Example
above. The time of its generation and the time of the computation of its
inverse will be evaluated in the last section.
4. On the interpretation of Lie geometry and Tits automa-
ton in terms of linear algebra
4.1. Graphs and incidence system
The missing definitions of graph-theoretical concepts which appear in
this paper can be found in [13], [14] or [16]. Simple graphs are undirected
graphs 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. When it
is convenient, we shall identify G with the corresponding anti-reflexive
binary relation on V (G), i.e. E(G) is a subset of V (G) × V (G) and write
vGu for the adjacent vertices u and v (or neighbours). The sequence of
distinct vertices v0, v1, . . . , vt, such that viGvi+1 for i = 1, . . . , t − 1 is the
pass in the graph. The length of a pass is a number of its edges. The
distance dist(u, v) between two vertices is the length of the shortest pass
between them. The degree of vertex v is the number of its neighbours.
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
(bipartite graph). If number of neighbours of each element is finite and
depends only on its type (point or line), then the incidence structure is a
tactical configuration in the sense of Moore (see [15]).
V. Ustimenko 139
The graph is k-regular if each of its vertices has degree k, where k is
a constant.
The incidence system is the triple (Γ, I, t) where I is a symmetric
antireflexive relation (simple graph) on the vertex set Γ, t : Γ → ∆ is
a type function onto the set of types ∆ such that αIβ and t(α) = t(β)
implies α = β.
The flag F is a nonempty subset in Γ such that α, β ∈ F implies αIβ.
We assume that t(F ) = {t(x)|x ∈ F}
4.2. Groups, Coxeter systems and BN -pairs
An important example of the incidence system as above is the so-called
group incidence system Γ(G, Gs)s∈S . Here G is the abstract group and
Gss∈S is the family of distinct subgroups of G. The objects of Γ(G, Gs)s∈S
are the left cosets of Gs in G for all possible s ∈ S Cosets α and β are
incident precisely when α ∩ β 6= ∅. The type function is defined by
t(α) = s where α = gGs for some s ∈ S.
Let (W, S) be a Coxeter system, i.e. W is a group with a set of
distinguished generators given by S = {s1, s2, . . . , sl} ana generic relation
(si × sj)
mi,j = e. Here M = (mi,j) is a symmetrical l × l matrix with
mi,i = 1 and off-diagonal entries satisfying mi,j > 2 (allowing mi,j = ∞
as a possibility, in which case the relation (si × sj)
mi,j = e is omitted).
Letting Wi =< S − {si} >, 1 6 i 6 l we obtain a group incidence system
ΓW = Γ(W, Wi)16i6l is called the Coxeter geometry of W . The Wi are
referred to as the maximal standard subgroups of W (see [17]).
Let G be a group, B and N subgroups of G, and S a collection of
cosets of B ∩ N in N . We call (G, B, N, S) Tits system ( or we say that
G has a BN -pair) if
(i) G =< B, N > and B ∩ N is normal in N ,
(ii) S is a set of involutions which generate W = N/(B ∩ N),
(iii) sBw is a subset in BuB ∪ BswB for any s ∈ S and w ∈ W ,
(iv) sBs 6= B for all s ∈ S.
Properties (i)–(iv) imply that (W, S) is a Coxeter system (see [17]
or [12]). Whenever (G, B, N, S) is Tits system, we call the group W
Weyl group of the system, or more usually the Weyl group of G. The
subgroups Pi of G defined by BWiB are called the standard maximal
parabolic subgroups of G. The group incidence system ΓG = Γ(G, Pi)16i6l
is commonly referred to as Lie geometry of G (see [16]). Note that Lie
140 On the flag geometry of simple group of Lie type
geometry of G and Coxeter geometry of the corresponding Weyl group
have the same rank. In fact there is a type preserving morphism from ΓG
onto ΓW given by gPi → wWi, where w is determined from the equality
BgPi = BwPi. This morphism Ret is called a retraction (see [18]).
Throughout this section (G, B, N, S) is Tits system which arises in
connection with Chevalley group G, although we point that the results of
this section remain valid in a far more general setting (see [18],[12], [17]).
We write G = Xl(K) to signify that G is Chevalley group over the field
K, with associated Dynkin diagram Xl. We are most interested in the
case when K is finite, and we shall write Xl(q) instead of Xl(Fq) in that
case.
So, fix Chevalley group G = Xl(K) with corresponding Weyl group W .
As in the previous section ΓW and ΓG are associated Coxeter and Lie
geometries.
4.3. On the embeddings of geometries into Lie algebra
Below we turn our attention to a method of embedding ΓW to a
lattice. Let A = (ai,j) be Cartan matrix corresponding to the root system
Ω of W . We consider the lattice R which is generated by simple roots
α1, α2, . . . , αl and the reflection r1, r2, . . . rl of R defined by the equality
(αi)
rj = αi − ai,jαj .
Let S = {r1, r2, . . . , rl} be the set of Coxeter generators of Weyl group
W . Let α1
∗, α2
∗, . . . , αl
∗ be a dual basis of α1, α2, . . . , αl, i.e. αi
∗ is the
linear functional on R which satisfies αi
∗(αj) = δi,j . We define the action
of W on the dual lattice R∗ by l(x)s = l(xs), where l(x) ∈ R∗ and s ∈ S.
Consider the orbit Hi = {αi
∗w|w ∈ W} of permutation group (W, R∗),
which contains α1
∗. Let H be the disjoint union of Hi. We give the set H
the structure of an incidence system as follows. Linear functionals l1(x)
and l2(x) are incident if and only if products l1(α)l2(α) > 0 for all α ∈ Ω.
The type function t is defined by t(l(x)) = i where l(x) ∈ Hi. It can
be shown that (H, I, t) is isomorphic to Coxeter geometry ΓW . In fact
there is a unique isomorphism of ΓW with (H, I, t) which sends Wi to αi,
1 6 i 6 l.) This gives the desired embedding since H is a subset in R∗.
We now consider an analogous embedding of Lie geometry ΓG into
Borel subalgebra U = L0 + L+ of L. Let d = α1
∗ + α2
∗ + . . . αl
∗. Then
we can take Ω+ = {α ∈ Ω|d(α) > 0} to be our set of positive roots in Ω.
For any l(x) ∈ R∗ define η(L) = {α ∈ Ω+|l(α) < 0}.
Let Lα be the root space corresponding to positive root α. For each
h ∈ H we define the subalgebra Lh as the sum of Lα, α ∈ η−(h). Let
V. Ustimenko 141
Ui = {h + v|h ∈ Hi, v ∈ Lh} and U be a disjoint union of Ui. We give
U the structure of an incident system as follows. Elements h1 + v1 and
h2 + v2 are incident if and only if each of the following holds:
(i) h1(α)h2(α) > 0 for all α ∈ Ω, i.e. h1 and h2 are incident in (H, I, t).
(ii) [h1 + v1, h2 + v2] = 0.
Element h + v has type i if h + v ∈ Ui. In [10] (see [11]) it is shown
that this newly defined incident system is isomorphic to Lie geometry ΓG,
provided that the characteristic of K is zero or sufficiently large one to
ensure the isomorphism at the level of the subgeometries (H, I, t) and
ΓW . Then analogous to Weyl case there exists a unique isomorphism Retr
of Γ(G) into (U, I, t) which sends Pi to αi, 1 6 i 6 l.
Proposition 4.1. Let Γ = Γ(G) be the geometry of group G = Xn(q).
The above interpretation of Γ(G) allows
(i) generate Γ in O(|Γ|) elementary steps and check whether or not two
elements of Γ are incident for time O(N2), where N is the number
of positive roots.
(ii) evaluate the degree and density of a deformation of tame com-
putation of Tits automaton as values of size O(n2) and O(n3)
respectively.
(iii) generate a tame computation of Tits automaton consisting of k
elementary steps for time O(n5).
Proof. The part (i) is straightforward. Let us discuss point (ii). Let us
consider the tame computation corresponding to the password p = (j1, f1),
(j2, f2), . . . , (jk, fs), where fi ∈ Fq[ti1
, ti2
, . . . tin ] ∪ ∞.
The maximal flag F of the Γ(G) can be treated as sequence (h1, v1),
(h2, v2), . . . (hn, vn) of elements of geometry of type 1, 2, . . . , n such
{h1, h2, . . . hn} is a flag in Weyl geometry and [hi + vi, hj + vj ] = 0,
i, j ∈ M . We refer to such a sequence as expanded data of the flag.
Let us denote η(hi) as Di and treat vectors from Lhi
as functions
from Di to Fq.
It is easy to see that the flag is uniquely defined by the flag h1,h2,. . . ,hn
of Weyl geometry, vector v1, v2|D2 − D1, v3|(D3 − (D1 ∪ D2)), . . . ,
vn|(Dn − (D1 ∪ D2 · · · ∪ Dn−1)). We refer to such a data of the flag
as compressed data of the flag. We assume that the projection of vector
on empty set is the formal symbol ∞.
142 On the flag geometry of simple group of Lie type
We have the following interpretation of Tits automaton.
Assume that a flag F ′ of type M − {i} is a subset of F of type
M as above. The residue Res(F ′) = {x ∈ Γi|xIa, a ∈ F}. There are
two elements h, h′ of type i such that sets S1 = {h + x|x ∈ Lh} and
S0 = {h′ + x′|x′ ∈ Lh′ have nonempty intersections with Res(F ′) of type
i of cardinality q and 1.
Then we join flags F and F̃ of kind (h1 + v1), (h2 + v2), . . . ,
(hi−1 + vi−1), (h + x), (hi+1 + vi+1), . . . , (hn + vn), h + x ∈ Res(F ) by
(i, ai), ai = x|η(h) − ((D1 ∪ D2 · · · ∪ Dn) − Di). Additionally we join F
and F ′ ∪ S0 ∩ Res(F ′) by symbol (i, ∞). We have to do such labeling for
each subset of F ′ of cardinality n − 1. Repetition of this procedure for
each maximal flag bring us Tits automaton for which elements from the
largest Schubert cells are accepting states. An initial state also has to be
chosen as element of the largest Schubert cell.
Let us consider the tame computation corresponding to the password
p = (j1, f1), (j2, f2), . . . , (jk, fs), where fi ∈ Fq[x1, x2, . . . , xn] ∪ ∞.
We define a type Sig(p) o as sequence (σ1, σ2, . . . , σk), where σi = 1
if ai 6= ∞ and σi = ∞ in remaining cases.
Let F be an initial state. Notice that for symbolic transition functions
produces the chain F = F0, F1 = Gj1
f1(F ), F2 = Gj2
f2(F1), . . . Fk =
Gjk
fik (Fk−1).
The sequence Ri = Res(Fi), i = 0, 1, 2, . . . , k does not depend on the
choice of different from ∞ functions f1, f2, . . . , fk or their specialisations.
It depends only on sequences (j1, j2, . . . , jk) and (σ1, σ2, . . . , σk). Conse-
qutive elements Ri and Ri+1, i = 0, 1, . . . , k − 1 are adjacent elements of
Γ(W ) or Ri = Ri+1. Recall that R0 = Rk, corresponds to element of group
W with the maximal length of irreducible representation in generators
from S (Coxeter element).
So the map E is a composition of multivariate maps Gj1
f1 : LR0
→
LR1
, Gj2
f2 : LR1
→ LR2
, . . . , Gjk
fk : LRk−1
→ LRk
.
The best way to compute is a consequtive computation of F1, F2,. . . ,Fk.
We assume that F0 is given in its compressed form. For O(n3) operations
we can convert compressed data into the expanded form. Further, we make
all steps of Tits computation and present the final data in compressed
form. Each step gives us addition of O(n2) new monomial terms, number
of steps is O(n).
It means that we can evaluate the density as O(n3). During the com-
putation a monomial terms of degree O(n2) will appear. So we justify (ii).
The computation of each monomial term costs O(n2). The product of
two monomial terms can be done in time O(n2). Each step of compu-
V. Ustimenko 143
tation costs O(n2) operations and the number of terms is n. It means
that the generation of the map in the standard form costs O(n5) and we
prove (iii).
5. Conclusion and complexity estimates
Let us consider the deformation Ẽn = τ1Enτ2 of ∆, where τ1 is
invertible monomial transformation ti → λitπ(i), λi ∈ F ∗
q , i = 1, 2, . . . , N ,
π is a permutation on {1, 2, . . . , N}, τ2 is a general bijective affine map
of Fp
N into itself.
Recall that for the deformation Ẽ of E the equality deg(Ẽ) = deg(E)
holds. Transformations E and τ1E have the same densities. Density of
Eτ2 is at most n2 times larger than the density of E.
Let us evaluate the complexity of the multivariate cryptosystem based
on tame computation of Tits automaton.
Notice that evaluations of degree and density shows that Bob can
compute the value of Ẽ in a given point for O(n7) elementary steps.
Alice can use described above method of proposition 4.1 as algorithm
for the decryption of ciphertext c given by Bob. The application of τ−1
2
to c costs O(N2) = O(n4). The solution of the nonlinear equations and
the computation of E′ costs O(n). The solution of linear system costs
O(N3) = O(n6). So re-image of E can be computed for O(n7). The
application of known τ1
−1 costs O(N). It means that for O(n13) Alice
can decrypt.
Generation of E costs O(n5), its deformation by τ1 and τ2 need O(n2)
and O(n4) operations, respectively. So generation of Ẽ costs O(n11).
As usually, we have to evaluate complexity as function from the
dimension N of plainspace. So Bob applies public rule for O(N3+1/2).
Alice can decrypt in time 0(N6+1/2). The generation of public key costs
O(N5+1/2).
The paper is dedicated to the memory of my teacher Lev Kaluzhnin.
His wide mathematical vision brought us, participants of his Seminar, the
light of Modern Algebra.
References
[1] Ding J., Gower J. E., Schmidt D. S., Multivariate Public Key Cryptosystems, 260.
Springer, Advances in Information Security, v. 25, (2006).
[2] V. Ustimenko, On Multivariate Cryptosystems Based on Computable Maps with
Invertible Decompositions, Annales of UMCS, Informatica, volume 14 (2014) ,
Special issue ”Proceedings of International Conference Cryptography and Security
Systems”, pp. 7-18.
144 On the flag geometry of simple group of Lie type
[3] Anton Betten, Mihael Braun, Adalbert Kerber, Axel Kohnert, Alfred Wasserman
Error Correcting Linear Codes Isometry and Applications, Springer, 2006.
[4] Andreas Stephan Essenhans, Axel Kohnert, Alfed Wassermann, Constructions of
codes for Network Coding, arXiv:1005, 2839[cs].
[5] A. Beultespacher, Enciphered Geometry, Some Applications of Geometry to Cryp-
tography, Annals of Discrete Mathematics, v. 37, 1988, 59-68.
[6] V. A. Ustimenko, Graphs with Special Arcs and Cryptography, Acta Applicandae
Mathematicae, vol. 71, N2, November 2002, 117-153.
[7] V. Ustimenko, Schubert cells in Lie geometries and key exchange via symbolic com-
putations, Proceedings of the International Conference ”Applications of Computer
Algebra, ACA 2010”, Vlora, Albanian Math. J., 2010, Vol 4, n. 4, 135-145.
[8] V. Ustimenko, On walks of variable length in Schubert incidence systems and
multivariate flow ciphers, Dopovidi of Nathional Acad. Sci. of Ukraine, 2014, No
3, P. 55 - 150.
[9] 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, 134 - 138 (in Russian), Engl.trans.: Kluwer, Dordrecht,
1992, pp. 112-119
[10] V. A. Ustimenko, Linear interpretation of Chevalley group flag geometries, Ukraine
Math. J. 43, Nos. 7,8 (1991), pp. 1055–1060 (in Russian).
[11] V. A. Ustimenko, On the Varieties of Parabolic Subgroups, their Generalizations
and Combinatorial Applications, Acta Applicandae Mathematicae 52 (1998): pp.
223–238.
[12] R. W. Carter, Simple Groups of Lie Type, Wiley, New York (1972).
[13] F. Harary, Graph Theory, Addison-Wesley Publishing Co, Reading, MA (1966).
[14] R. Wilson, Introduction to Graph Theory, Oliver & Boyd, Edinburg, (1972).
[15] E. Moore, Tactical Memoranda 1-3, Amer. J. of Math., vol. 18, n3 (1896), 264-29o.
[16] A. Brower, A. Cohen, A. Nuemaier, Distance regular graphs, Springer, Berlin, 1989
[17] N. Bourbaki, Lie Groups and Lie Algebras, Chapters 1 - 9, Springer, 1998-2008.
[18] F. Buekenhout (Editor), Handbook on Incidence Geometry, North Holland, Ams-
terdam, 1995.
Contact information
Vasyl Ustimenko University of Maria Curie Skłodowska, Pl. Maria
Curie Skłodowska 1, pok. 323, 20-931, Lublin,
Poland
E-Mail(s): vasyl@hektor.umcs.lublin.pl
Received by the editors: 23.01.2015
and in final form 21.02.2015.
|