Maximality of affine group, and hidden graph cryptosystems
We describe a new algebraic-combinatorial method of public key encryption with a certain similarity to the well known Imai-Matsumoto. We use the general idea to treat vertices of a linguistic graph (see [21] and further references) as messages and use the iterative process to walk on such graph a...
Gespeichert in:
| Datum: | 2005 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2005
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/156606 |
| 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: | Maximality of affine group, and hidden graph cryptosystems / A.A. Ustimenko // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 1. — С. 133–150. — Бібліогр.: 25 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-156606 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1566062019-06-19T01:28:24Z Maximality of affine group, and hidden graph cryptosystems Ustimenko, A.A. We describe a new algebraic-combinatorial method of public key encryption with a certain similarity to the well known Imai-Matsumoto. We use the general idea to treat vertices of a linguistic graph (see [21] and further references) as messages and use the iterative process to walk on such graph as encryption process. To hide such encryption (graph and walk on it) we will use two affine transformation. Like in Imai - Matsumoto encryption the public rule is just a direct polynomial map from the plaintext to the ciphertext. The knowledge about graph and chosen walk on them (the key) allow to decrypt a ciphertext fast. We hope that the system is secure even in the case when the graph is Public but the walk is hidden. In case of "public" graph we can use same encryption as private key algorithm with the resistance to attacks when adversary knows several pairs:(plaintext, ciphertext). We shall discuss the general idea of combining affine transformations and chosen polynomial map of deg ≥ 2 in case of prime field Fp. As it follows from the maximality of affine group each bijection on Fp n can be obtained by such combining. 2005 Article Maximality of affine group, and hidden graph cryptosystems / A.A. Ustimenko // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 1. — С. 133–150. — Бібліогр.: 25 назв. — англ. 1726-3255 http://dspace.nbuv.gov.ua/handle/123456789/156606 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We describe a new algebraic-combinatorial method
of public key encryption with a certain similarity to the well known
Imai-Matsumoto. We use the general idea to treat vertices of a linguistic graph (see [21] and further references) as messages and use
the iterative process to walk on such graph as encryption process.
To hide such encryption (graph and walk on it) we will use two
affine transformation. Like in Imai - Matsumoto encryption the
public rule is just a direct polynomial map from the plaintext to
the ciphertext.
The knowledge about graph and chosen walk on them (the key)
allow to decrypt a ciphertext fast. We hope that the system is
secure even in the case when the graph is Public but the walk is
hidden. In case of "public" graph we can use same encryption as
private key algorithm with the resistance to attacks when adversary
knows several pairs:(plaintext, ciphertext).
We shall discuss the general idea of combining affine transformations and chosen polynomial map of deg ≥ 2 in case of prime
field Fp. As it follows from the maximality of affine group each
bijection on Fp
n
can be obtained by such combining. |
| format |
Article |
| author |
Ustimenko, A.A. |
| spellingShingle |
Ustimenko, A.A. Maximality of affine group, and hidden graph cryptosystems Algebra and Discrete Mathematics |
| author_facet |
Ustimenko, A.A. |
| author_sort |
Ustimenko, A.A. |
| title |
Maximality of affine group, and hidden graph cryptosystems |
| title_short |
Maximality of affine group, and hidden graph cryptosystems |
| title_full |
Maximality of affine group, and hidden graph cryptosystems |
| title_fullStr |
Maximality of affine group, and hidden graph cryptosystems |
| title_full_unstemmed |
Maximality of affine group, and hidden graph cryptosystems |
| title_sort |
maximality of affine group, and hidden graph cryptosystems |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2005 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/156606 |
| citation_txt |
Maximality of affine group, and hidden graph cryptosystems / A.A. Ustimenko // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 1. — С. 133–150. — Бібліогр.: 25 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT ustimenkoaa maximalityofaffinegroupandhiddengraphcryptosystems |
| first_indexed |
2025-07-14T09:00:00Z |
| last_indexed |
2025-07-14T09:00:00Z |
| _version_ |
1837612243877888000 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 1. (2005). pp. 133 – 150
c© Journal “Algebra and Discrete Mathematics”
Maximality of affine group, and hidden graph
cryptosystems
Vasiliy A. Ustimenko
Communicated by V. I. Sushchansky
Dedicated to Yu.A. Drozd on the occasion of his 60th birthday
Abstract. We describe a new algebraic-combinatorial method
of public key encryption with a certain similarity to the well known
Imai-Matsumoto. We use the general idea to treat vertices of a lin-
guistic graph (see [21] and further references) as messages and use
the iterative process to walk on such graph as encryption process.
To hide such encryption (graph and walk on it) we will use two
affine transformation. Like in Imai - Matsumoto encryption the
public rule is just a direct polynomial map from the plaintext to
the ciphertext.
The knowledge about graph and chosen walk on them (the key)
allow to decrypt a ciphertext fast. We hope that the system is
secure even in the case when the graph is Public but the walk is
hidden. In case of "public" graph we can use same encryption as
private key algorithm with the resistance to attacks when adversary
knows several pairs:(plaintext, ciphertext).
We shall discuss the general idea of combining affine transfor-
mations and chosen polynomial map of deg ≥ 2 in case of prime
field Fp. As it follows from the maximality of affine group each
bijection on Fp
n can be obtained by such combining.
1. Introduction
We are getting lots of information through e-mail, e-commerce (busi-
ness conducted over the Internet), cellular phones, or satellite and cable
Key words and phrases: Data and communication security, e-commerce, Public
Key Cryptography, Private Key Encryption.
134 Maximality of affine group, and hidden graph...
TV. The need for secure communications is more profound than ever, for
instance, the emergence of virtual organisations such as e-learning and
e-business in general shall rely on a secure way for online transactions.
In order for a data to be secured for storage or transmission, it must be
transformed in such a manner that it would be difficult for an unautho-
rised person to be able to discover its true meaning. This is the purpose of
cryptographic techniques. Development of new theoretical tools for data
protection and computational testing of their software implementations
is active area of research.
The idea to use arcs on graphs for encryption (section 3) has been
considered in [16],[17]. In this paper we shall combine "graphical en-
cryption" with two affine transformation (section 5) to get a public and
private key algorithms.
First (section 2), we discuss general idea of combining of different
affine transformations with the chosen polynomial map. In section 4 we
describe Imai-Matsumoto scheme following to [4], so the reader can com-
pare it with the graphical public key algorithm in section 5. To describe
public key algorithms we shall use traditional for the Cryptography char-
acters: Alice (the holder of the key), Bob (the public user) and Catherine
(the cryptoanalyst). In section 6 we consider some heuristic arguments
on the complexity of algorithms in case of linguistic graphs of high girth,
infinite family of such graphs. The toy example of proposed public key
encryption based the reader can find at the end of the article.
Papers [18]-[20], [23], [24] devoted to the implementations of the al-
gorithm using walks on graphs.
2. Maximality of affine group and Cryptography
Let (Fq)
n be a vector space over the finite field Fq, where q is the prime
power.
As it is usual in cryptography, we can apply a term plaintext to a string
of characters x = (x1, x2, . . . , xn) over the alphabet Fq. When working
with matrices, we shall consider vectors to be column vectors (although
in the text we shall continue use them as rows). We can consider x as a
message containing a certain information. If π is some bijective transfor-
mation of (Fq)
n, then π(x) is an encrypted message or a ciphertext.
The natural choice for π is a combination of some affine transfor-
mations ai = Aix + bi, i = 1, . . . , k, where Ai is a square matrix and
bi ∈ (Fq)
n, with some nonlinear transformation T of the vector space
(Fq)
n.
Let us consider the case of Fp, where p is a prime number. Affine
transformations x → Ax + b, where A be an invertible matrix and b ∈
V. A. Ustimenko 135
(Fq)
n form an affine group AGLn(Fp) of order pn(pn−1)(pn−p) . . . (pn−
pn−1. This is a subgroup of the symmetric group Spn of order (pn)!.
The following fact had been proven in [14].
Theorem 2.1. Let G a proper subgroup of Spn containing AGLn(Fp).
Then G coincides with AGLn(p) or Spn .
Let us choose the nonlinear transformation T . The following state-
ment follows directly from the theorem
Corollary 2.2. Let T be a chosen nonaffine transformation of the vec-
tor space V = Fp
n. Then each bijective transformation T of the vector
space V = (Fp)
n can be presented as a product of ”quantum” transfor-
mations Q(α1, α2) = alpha1Tα2 where α1 and α2 are appropriate affine
transformations of V .
We recall the following well-known algebraic fact:
Theorem 2.3. Each transformation T of the vector space V = (Fp)
n
can be treated as a polynomial map P : x → y, where x = (x1, . . . , xn),
y = (y1, . . . , yn), yi = Pi(x1, . . . , xn), i = 1, . . . , n for some polynomial
expressions Pi in variables xi over the finite field Fp.
The following ”public key” strategy can be derived naturally from the
statements above:
(A) Choose polynomial transformation P , which you can invert fast
(for polynomial number of steps f(n)), where degf(n) is ”small”)
(B) select the family Ω of affine transformations αi, i = 1, . . . , m and
quantum maps Qj = βjPγj , j = 1, . . . , l, where βj , γj ∈ Ω
(C) compute the polynomial map Q = Q1Q2 . . . Ql (composition of
Qi),i. e get the formula y = Q(x) = (P1(x1, . . . xn), . . . , Pn(x1, . . . , xn)),
where polynomials Pi written in canonical form.
(D) keep transformations Qi, αj and the decomposition of Q into
quantum maps Qi secret and give the list L of public equations Pi to you
correspondent B.
Now, you correspondent can encrypt his/her messages to you by ap-
plying Q to the plaintext, but the problem of decryption , i.e. compu-
tation of inverse map Q−1 can reach any level of complexity: you may
obtain any permutation from the symmetric group of Spn as your expres-
sion Q.
For you, the problem, of decryption can be feasible if length l is
”reasonably moderate”. You can invert each Qi and apply them to the
ciphertext in the reverse order with respect to the known decomposition
of Q in Qi.
136 Maximality of affine group, and hidden graph...
Of course, we have no illusion to solve mathematically the great prob-
lem of cryptography on the existence of asymmetric function: corollary
from the theorem 1 does not contain any restrictions on the number l of
quantum transformations.
But, it is reasonable to assume that even in case of polynomial length
l we are able to produce practically secure public keys. In fact, well
known Imai-Matsumoto encryption scheme and its modifications by J.
Patarin are realisation of A-D in case l = 1. They are "quantum trans-
formations". Double round of these algorithms corresponds to the case
of l = 2. Of course, for any encryption (RSA, in particular) exists a pre-
sentation in the form A-D, but we have just theorem of existence without
effective algorithms to construct a decomposition of given permutation
into composition of quantum transformations.
Remark 1. Substitution the field GF (q), where q = pj , p is a prime
number, instead of Fp in the scheme (A)-(D) does not led to more gen-
eral scheme, because of vector space (Fq)
d over the ground field Fq, is
a vector space of dimension jd over Fp, but such a substitution can be
useful in practical applications. We can consider also a Kj , where K is
a commutative field, instead of vector space Fp
j .
Remark 2. Size of the family Ω of step B can be bounded by poly-
nomial expression in variable n, we may think that Ω consist of some
elementary transvections ti,j(1), i 6= j and diagonal matrices for which
exactly one entry equals to fixed generator of of multiplicative group of
Fp and other entries equal 1, regular translations x → x + ei, where ei is
addition of 1 to xi. One can consider even smaller set of generators of
Affine group.
To compare public polynomial maps of kind P = (P1, . . . , Pn) ’in
glance" one may look on the degrees of polynomials Pi(x1, x2, xn), or
Grobner basis of the ideal generated by Pi. Like in case of RSA, heuristic
arguments are useful to convince public that problem of inverting P is
hard.
3. Parallelotopic and Linguistic graphs as tools for the
encryption
In this subsection we will consider the parallelotopic graphs for which
arcs can be identified naturally and effectively with words in a certain
alphabet M without marking of edges. We can just paint the vertices of
our graph for this purpose.
We say [17], [21] that Γ = (Γ, M, π) is a parallelotopic graph over a
finite set M if we have a surjective function π : V (Γ) → M such that for
V. A. Ustimenko 137
every pair (v, m), v ∈ V (Γ), m ∈ M , there is a unique neighbour u of v
satisfying π(u) = m.
given vertex v, and any colour m, there exists exactly one neighbour
u of v of colour m.
Let Γ be a parallelotopic graph. We shall treat its vertices as plain-
texts. So the set of vertices V (Γ) is the plainspace and cipherspace. Let
N(t, v) be the operator taking the neighbour u with colour t of a vertex v
of a parallelotopic graph Γ. If (t1, t2, · · · , tn), ti ∈ M is a tuple such that
ti 6= ti+2, then (v, v1 = N(t1, v), v2 = N(t2, v1), · · · , vn = N(tn, vn−1)) is
the arc of the graph Γ which we can consider as an encoding arc for any
chosen vertex v.
Let us refer to this tuple ρ = (t1, · · · , tn) over M as an encoding tuple.
It is clear that ρ−1 = (tn−1, · · · , t1, c(v)) is the ”decoding tuple”, because
it corresponds to the decoding arc.
We can modify this definition in case of bipartite graphs.
Let Γ be a bipartite graph with partition sets Pi, i = 1, 2. Let M be
a disjoint union of finite sets M1 and M2. We say that Γ is a bipartite
parallelotopic graph over (M1, M2) if there exists a function π : V (Γ) →
M such that if p ∈ Pi, then π(p) ∈ Mi and for every pair (p, j), p ∈ Pi,
j ∈ Mi, there is a unique neighbour u with given π(u) = j.
It is clear that the bipartite parallelotopic graph Γ is a (|M1|, |M2|) -
biregular graph.
We refer also to the function π in the definition of bipartite parallelo-
topic graph also as a labelling. We will often omit the term ”bipartite ”,
because all our graphs are bipartite.
Let M t be the Cartesian product of t copies of the set M .
We say that the graph Γ is a linguistic graph over the set M with
parameters m, k, r, s if
Γ is a bipartite parallelotopic graph over (V1, V2), M1 = M r, M2 =
M s with the set of points I = Mm (inputs) and set of lines O = Mk
(outputs). (i.e. Mm and Mk are the partition sets of Γ). It is clear that
m + r = k + s.
We use the term linguistic coding scheme for a pair (Γ, n), where Γ
is linguistic graph and n < g is the length of encoding sequences.
We choose a bipartite graph in the definition above because regular
trees are infinite bipartite graphs and many biregular finite graphs of high
girth can be obtained as their quotients (homomorphic images).
For linguistic graphs our messages and coding tools are words over the
alphabet M and we can use the usual matching between real information
and vertices of our graph.
138 Maximality of affine group, and hidden graph...
We use the term linguistic graph over GF (q) when we have a linguistic
graph with alphabet M = GF (q) and the set of neighbours of any vertex
v is an algebraic manifold over GF (q), i.e. is the totality of solutions of
a certain system of polynomial equations. Here,
our messages (plaintexts or ciphertexts) and enryption tools (pass-
words) are tuples over GF (q).
The following construction proves the existence of linguistic graphs,
shows that there are "many" of them on 2qn vertices, where q is arbitrary
prime power and n is arbitrary positive integer.
Let P and L be two n-dimensional vector spaces over GF (q). Ele-
ments of P will be called points and those of L lines. To distinguish points
from lines we use parentheses and brackets: If x ∈ V , then (x) ∈ P and
[x] ∈ L. It will also be advantageous to chose two fixed bases and write:
(p) = (p1, . . . , pn)
[l] = [l1, . . . , ln]
We now define an incidence structure (P, L, I) as follows. We say the
point (p) is incident with the line [l], and we write (p)I[l], if the following
relations between their coordinates hold:
a2l2 − b2p2 = P2(l1, p1)
. . .
aili − bipi = Pi(l1, . . . , li−1, p1, . . . , li−1) (1)
. . .
anln − bnpn = Pn(l1, . . . ln−1, p1, . . . , pn−1)
where Pi, i = 2, . . . , n can be any polynomial expressions in variables
l1, . . . , li−1, p1, . . . , pi−1 over Fq, ai, bi can be any nonzero elements from
Fq.
It is easy to see that the above graph is a linguistic graph such that
p1 and l1 are the "colours" of (p) and [l], respectively, and r = s = 1.
If q = 2, then the bipartite graph defined by equations (1) are disjoint
union of cycles.
Let us call the graphs defined by equations of kind (1) linguistic graphs
of triangular type over Fq.
V. A. Ustimenko 139
4. The Imai - Matsumoto scheme
Let K be an extension of degree n of the finite field Fq, where q is a power
of 2, and let β1, β2, . . . , βn be a basis of K as an Fq-vector space.
Alice will be using the Imai- Matsymoto system in K. She regards
each element of K as an n-tuple over q.
Alice may choose to keep her basis secret in which case we can not
assume that a cryptoanalyst (whom we shall name "Catherine") knows
what basis she is using.
Both plaintext message units and ciphertext message units will be n-
tples over Fq. We will use the vector notation x = (x1, x2, . . . , xn) ∈ Fq
n
for plaintext and y = (y1, y2, . . . , yn) ∈ Fq
n for ciphertext. When working
with matrices, we shall consider vectors to be column vectors (although
in the text we shall continue writing them as rows).
In transforming paintext into ciphertext, Alice will work two inter-
midiate vectors, denoted u = (u1, . . . , un) ∈ Fq
n and v = (v1, . . . , vn) ∈
Fq
n. Given a vector in Fq
n, we shall use boldface to denote the corre-
sponding element of K with respect to the basis βj .
Next, Alice chooses an exponent h, 0 < h < qn, that is of the form
h = qα + 1
and satisfies the condition g.c.d.(h, qn − 1) = 1. (Recall that q was
choosen to be a power of 2, if q were odd, then g.c.d.(h, qn −1) is at least
2.)
The condition g.c.d.(h, qn − 1) = 1 is equivalent to requiring that the
map u → uh on K is one to one, its inverse is the map u → uh′
, where h′
is the multiplicative inverse of h modulo qn − 1.
Alice may choose o keep h secret. However, since there are relatively
few possible values for h, she must asume that Catherine will be prepared
to run through all possibilities for h. That is, even if she keeps h secret,
the security of her system must be elsewhere.
In addition, Alice chooses two secret affine transformations, i. e.,
two invertible n × n matrices A = (aij), 1 ≤ i, j ≤ n and B = (bij),
1 ≤ i, j ≤ n with entries in Fq, and two constant vectors c = (c1, . . . , cn)
and d = (d1, . . . , dn).
The purpose of the two transformations is to "hide the monomial
map" u → uh - hence the name "hidden monomial cryptosystem".
We now describe how Alice gets her public rule for going from plain-
text x ∈ Fq
n to ciphertext y ∈ Fq
n.
First, she sets
u = Ax + c.
Next, she would like to have v ∈ K simply equal to the h-th power of
u ∈ K and then set
140 Maximality of affine group, and hidden graph...
y = B−1(v − d)
that is v = By + d.
However, her public encryption rule will go right from x to y, and will
not directly involve exponentiation at all.
In order to get formulas going from x directly to y Alice notices that
since v = uh and h = qθ + 1, she has
v = uqθ
u.
Recall that for any k = 1, 2, ..., n the operation of raising to the qk-th
power in K is an Fq-linear transformation. Using linear algebra, she can
get n-equations that express each y as a polynomial of total degree 2 in
the x1, . . . , xn.
Alice makes these n equations public. If Bob wants to send her a
plaintext message x, he substitutes the xi in these equations and finds yi.
On the other hand, Catherine, who knows only the ciphertext (and the
public key), must solve a nonlinear system for the unknowns xi.
When Alice receives the iphertext y, she uses her knoledge of A, B,
c and d and h to recover x, without having to solve the publicly known
equations for the xi. Namely, let h′ be the multiplicative inverse of h
modulo qn − 1, so that the map u = vh′
inverts the map v = uh on K.
Alice first computes v = By + d, then raises v=
∑
viβi ∈ K to the h′-th
power (i.e., sets u = vh′
, and finaly compute x = A−1(u − c.
The following summarises Alice’s decryption:
(y1, . . . , yn) → y = By + d → u = vh′
→ x = A−1(u − c)
Remark. The cryptosystem described above is a simplified version of
the one proposed in the original paper [6]. For details about breaking the
original Imai-Matsumoto system see [15].
5. Hidden linguistic graphs system, hidden walks systems
Let Fq, q > 2 be the finite field, where q is a prime power.
Alice shall be using the hidden graph scheme basd on the family of
linguistic graphs Ln(q) with the operators Nc(v) to take the neighbour u
of vertex v such that c is the colour of u.
Let I1(x1, . . . , xn), . . . , Ik(x1, . . . , xn) are some invariants of graph
Ln(q). It means that vertices v and u are within same connected com-
ponent of Is(v) = Is(u) for all possible values of s. We shall assume that
Is, s = 1, 2, . . . , n are polynomial expressions in n variables over the field
Fq.
Remark. The number of chosen invarians can be zero, like in case of
connected graph.
We shall consider the case of a bipartite graphs Ln(q), but one can
modify easily the procedure below on the case of general linguistic graphs.
V. A. Ustimenko 141
As in previous section the plaintext and the ciphertext are n-tuples
over Fq, q > 2 and we identify them with points (or lines) of the graph
Ln(q). Alice shall choose to keep her graph secret. We may assume that
the number of nonisomorphic bipartite linguistic graphs on qn points and
qn lines is growing with n. Thus the cryptoanalist (Catherina) does not
know the operator Nc(v).
In transforming plaintext into ciphertext Alice shall work with two in-
termediate vectors denoted u = (u1, . . . , un) ∈ Fq
n and v = (v1, . . . , vn) ∈
Fq
n.
First, Alice choose the symbolic key k = (P1, . . . , Pt), where Pi =
Pi(x1, . . . xk) are polynomials from Fq[x1, . . . , xk] of degree ≥ 0 such that
Pi 6= Pi+2, i = 0, . . . , t − 2.
REMARK: If we are working without graph invariants I1, . . . , Ik, then
P1, . . . , Pt are constants from Fq. We shall use term constant password in
this case.
In addition, Alice chooses two secret affine transformations, i.e. two
invertible matrices A = (aij), 1 ≤ i, j ≤ n and B = (bi,j), 1 ≤ i, j ≤ n
with entries in Fq and the constant vectors c = (c1, . . . , cn) and d =
(d1, . . . , dn).
The purpose of the two affine transformations is "to hide the graph
and to hide the walk on the hidden graph". First, she sets u = A× x + c
Second, Alice takes the plaintext (x1, . . . , xn) and computes the nu-
merical password K = (K1, . . . , Kt), where
Ks = Ps(I1(u1, . . . un), . . . , Ik(u1, . . . , un).
Next, she would like to have v ∈ Fq
n simply equal to the
v = N(u), where N(u) = NKt+c(u)(NKt−1
(. . . NK2
(NK1
(u))) . . . ).
Finally, Alice sets y = B−1(v − d) (that is v = By + d).
However, her public encryption rule will go right from x to y and
shall not include the transformations NKi
at all. The main part of com-
putation of public rule is computation of the polynomial map T : u → v
can be done with "Maple", "Matematica" or other software package for
symbolic computations. After, Alice will combine T with two affine trans-
formations and get a formula
y = (F1(x1, . . . , xn), . . . , Fn(x1, . . . , xn),
where Fi(x1, . . . , xn) are polynomials in n variables written in ex-
panded form, i.e. as the sums of monomials of kind x1
i1 . . . xn
in with the
coeficients from Fq. Alice makes polynomial equations yi = Fi(x1, . . . , xn)
public.
Again, like in Imai-Matsumoto scheme, if Bob wants to send her a
plaintext message x, he just substitutes xi in the public equations and
142 Maximality of affine group, and hidden graph...
finds yi. On the other hand Catherine, who knows only the ciphertext
and the public key must solve a nonlinear system for the unknowns xi.
When Alice receives the ciphertext y, she uses her knowledge of
A, B, c, d, graph Ln(q) and the prepassword.
Namely, she shall compute v = By+d. Next, Alice shall compute the
components of numerical password: Ki = Pi(v1, . . . , vn) because u and v
are in the same component of the graph.
The inverse to the map N : u → v is
N−1(v) = Nc(v)−Kt
(NK1
(NK2
(. . . (Nt−1(U) . . . )
because of Kt + c(u) = c(v). Thus Alice shall use iterative process to
compute u = N−1(v).
Finally, she computes the plaintext x = A−1 × (u − c).
GENERALIZATION. Let Fq be an extension of Fq′ . Then Fq be a
vector space over Fq′ . We shall choose a basis of this vector space and
consider each vertex of the linguistic graph as a tuple over Fq′ . So points
(lines) form the n×m -dimensional vector space V , where m = |F ′
q : Fq| is
the number of basic elements. It is allow us to take affine transformations
Ax+c and Bx+d of V , where entries of matrices and vectors are elements
in Fq′ instead of those with entries in Fq. The most important case is
q′ = p, q = pn, p is prime like in Irai-Matsumoto scheme.
PRIVATE KEY ALGORITHMS.
In case of sparse linguistic graphs, i. e. graphs such that polynomials
determine formula for the neighbour of given vertex, graphs invariant,
symbolic key contains "small" number of monomials, and matrices A
and B are sparse (small number of entries 6= 0) we can use the encryption
above as a private key algorithm. In that case Alice and Bob both have
the information about graph, chosen graph invariants, symbolic key and
two affine transformation. In the best case of sparse graph encryption
(and decryption) can be done for the lO(n) time, where l is the length of
the symbolic key and n is the length of the ciphertext.
The advantage of such method comparing with linear encryption or
some other private key algorithms is that such encryption can be resis-
tant to attacks when adversary (Catherine) has several pairs (plaintext,
ciphertext) and trying to get the key. We shall assume that matrices
A and B together with sparse vectors c and d and symbolic key form
the password. Catherine knows the graph, chosen graph invariants, the
general scheme of encrypion. So she is trying to restore the symbolic key
and control the communication between Alice and Bob.
Practically, private key algorithms serves for the encryption of suffi-
ciently large texts. Thus we have to use rather small passwords. -We
V. A. Ustimenko 143
may assume that the size of password, i. e. number of monomials in
symbolic key together with the number of nonzero entries in A, B, c and
d is constant or linear function an + b where a << 1.
We can say that the task of Catherine in such situation is harder than
in the situation of public key encryption with the same algorithm for Al-
ice, because in "public case" Catherine can create any pair (plaintext,
ciphertext). Catherine can study the graph properties and get descrip-
tion of connected components, list of all graph invariants, but without
knowledge about the symbolic key even reduction the problem to public
key case is hard.
6. Linguistic graphs of triangular type over Fq of high
girth
We consider some heuristic arguments on the complexity of constant
encryption scheme from previous section in case the linguistic graph is
public, its girth is "high" and chosen affine transformation are mutually
inverting. If we "hide" the graph, then decryption shall be essentially
harder.
The constructions of families of graphs of high girth are connected
with studies of some well-known problems in Extremal Graph Theory
(see [2]). Let ex(v, n) be, as usual, the greatest number of edges (size) in
a graph on v vertices, which contains no cycles C3, C4, . . ., Cn.
From Erdös’ Even Cycle Theorem and its modifications [2] it follows
that
ex(v, 2k) ≤ Cv1+1/k (2)
where C is a positive constant.
This bound is known to be sharp precisely when k = 2, 3, and 5.
Similar upper bound for the class of biregular bipartite graphs, which
includes linguistic graphs, the reader can find in [22].
If for graphs Gi, i = 1,∞ of degree li and girth gi we have
gi ≥ γ logli−1(vi) (3)
then they form an infinite family of graphs of large girth in the sense
of N. Biggs [1] (see, also [5],[7],[8],[9],[11],[12],[13] for examples of such
families).
We have γ ≤ 2, because of (2), but no family has been found for
which γ = 2. A. Lubotzky conjectured that γ ≤ 4/3.
In case of encryption algorithms for the linguistic graphs of girth k
with the password of length l, l ≤ k/2 there is not more than one pass
144 Maximality of affine group, and hidden graph...
between two vertices at a distance l and we have the following property
of encryption:
(P1) two different passwords of length l produce different ciphertexts
Let G be a linguistic graph over the extension Fq of the finite field
Fq′ and we are combining the "graphical" encryption procedure with two
affine transformations over Fq′ (see, the end of previous section). Then
the property (P1) is still in place, because our affine transformations are
bijections.
Let us consider the case when chosen affine transformations are mu-
tually invert each other. Then we have the following nice property
(P2) the plaintext and ciphertext are always different.
Proof. In case of just graphical encryption π this property holds because
of absence cycles of the length 2l, i. e. permutation π does not have
invariant points. The same property is valid for transformations which
are conjugate with π.
Remark Let L be the bipartite linguistic graph of high girth and π be
a graphical encryption corresponding to the pass of the odd length. Then
property P2 is immaterial because points and lines are formally different
vectors but as tuples over Fq they may coinside. Anyway there are ex-
amples of such encryption scheme with the property (P2), in particular,
graphs D(k, q), k is odd, below.
Let us bound the complexity of the decryption in case when our graph
Ln(q) is public and the length of the password is l:
(i) the plaintext x and the ciphertext y are at the distance l,
(ii) we can identify the totality of all vertices at a distance l ≤ k/2
with the subgraph in q-regular tree,
(iii) the decryption is equivalent to finding the pass between y and x,
two vertices of q-regular tree at the distance l can be estimated by
q(q − 1)l−1CN(n)(1) (4)
, where CN(n) is the complexity of the operation of taking neighbour
in the graph Ln(q).
For the encryption of "potentially infinite plaintext" we shall use an
infinite family of graphs F = {Lni
(q)}, i = 1, . . . ,∞ of increasing girth,
order and CN(ni) is a complexity of taking neighbour for Lni
. Let us
make simple suggestion that CN(ni) < CN(ni+1).
Then the complexity of decryption is increasing with increasing of the
length of password or increasing of the size of the plaintext. If we choose
l as a linear function l = an + b, from the length of the plaintext n then
our bound above getting exponential. Such a choice of l is possible if
V. A. Ustimenko 145
there is a linear from n lower bound for the girth of graphs from F , i. e.
F is a family of graphs of large girth
Let us suppose now that the graph is unknown and somebody trying
to decrypt text by solving public equations yi = P (x1, . . . , xn) for xi.
This task is a classical hard problem of algebra. The system above can
be investigated for dO(n2) steps, where d = d(l) is the maximal degree
of polynomials. We can do better (d(l)Cn) if we know that the system
is consistent. If l is a depending from n then this bound is much worse
that(4).
If you have a family of polynomial linguistic graph of bounded degree,
you may choose the dimension n such that your correspondent could en-
crypt but could not decrypt and use graph encryption in ”public key
fashion", because we should use the gap between computations of poly-
nomial in given point and investigation of given system of equations.
If we shall conjugate "Lni
"- encryption by hidden affine transforma-
tion T then complexity of decryption is not decreasing, the problem is
getting harder.
Let us assume that F is a family of triangular graphs over Fq, such
that Lni+1
is defined by just adding last ni+1 −ni equations to the equa-
tions for Lni
. If girth of graphs from F is unbounded, then natural
projective limit of graphs from F is the q-regular tree. In that class of
graphs we can find an infinite families of graphs of large girth.
Explicit example here is the family of graphs D(k, q) [7], [8], [9].
Let q be a prime power, and let P and L be two countable infinite
dimensional vector spaces over GF (q). Elements of P will be called points
and those of L lines. To distinguish points from lines we use parentheses
and brackets: If x ∈ V , then (x) ∈ P and [x] ∈ L. It will also be
advantageous to adopt the notation for co-ordinates of points and lines
introduced in [7]:
(p) = (p1, p11, p12, p21, p22, p
′
22, p23, . . . , pii, p
′
ii, pi,i+1, pi+1,i, . . .),
[l] = [l1, l11, l12, l21, l22, l
′
22, l23, . . . , lii, l
′
ii, li,i+1, li+1,i, . . .).
We now define an incidence structure (P, L, I) as follows. We say the
point (p) is incident with the line [l], and we write (p)I[l], if the following
relations between their co-ordinates hold:
l11 − p11 = l1p1
l12 − p12 = l11p1
l21 − p21 = l1p11 ((5))
146 Maximality of affine group, and hidden graph...
lii − pii = l1pi−1,i
l′ii − p′ii = li,i−1p1
li,i+1 − pi,i+1 = liip1
li+1,i − pi+1,i = l1p
′
ii
(The last four relations are defined for i ≥ 2.) This incidence structure
(P, L, I) we denote as D(q). We speak now of the incidence graph of
(P, L, I), which has the vertex set P ∪ L and edge set consisting of all
pairs {(p), [l]} for which (p)I[l].
For each positive integer k ≥ 2 we obtain an incidence structure
(Pk, Lk, Ik) as follows. First, Pk and Lk are obtained from P and L, re-
spectively, by simply projecting each vector onto its k initial coordinates.
The incidence Ik is then defined by imposing the first k−1 incidence
relations and ignoring all others. For fixed q, the incidence graph corre-
sponding to the structure (Pk, Lk, Ik) is denoted by D(k, q).
Looking at equations 7.1 we can see that D(k, q) are linguistic graphs
of triangular type over Fq.
Proposition 6.1. [8] Let q be a prime power, and k ≥ 2. Then for odd
k, g(D(k, q)) ≥ k + 5
Graphs D(k, q), k ≥ 2 form first infinite family of linguistic graphs of
unbounded girth.
Let us consider graph invariants for D(k, q).
To facilitate notation in future results, it will be convenient 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,
p0,1 = p2, l1,0 = l1, l′1,1 = l1,1, p′1,1 = p1,1, and to rewrite (5) in the form :
lii − pii = l1pi−1,i
l′ii − p′ii = li,i−1p1
li,i+1 − pi,i+1 = liip1
li+1,i − pi+1,i = l1p
′
ii
for i = 0, 1, 2, . . .
Notice that for i = 0, the four conditions (5) are satisfied by every
point and line, and, for i = 1, the first two equations coincide and give
l1,1 − p1,1 = l1p1.
Let k ≥ 6, t = [(k + 2)/4], and let
u = (ui, u11, · · · , utt, u
′
tt, ut,t+1, ut+1,t, · · · )
V. A. Ustimenko 147
be a vertex of D(k, q). (It does not matter whether u is a point or a line).
For every r, 2 ≤ r ≤ t, let
ar = ar(u) =
∑
i=0,m
(uiiu
′
r−i,r−i − ui,i+1ur−i,r−i−1),
and a = a(u) = (a2, a3, · · · , at). (Here we define
p0,−1 = l0,−1 = p1,0 = l0,1 = 0, p00 = l00 = −1, p0,1 = p1, l1,0 = l1,
l′11 = l11, p′1,1 = p1,1).
In [9], [10], the following statement was proved.
Proposition 6.2. . Let u and v be vertices from the same component
of D(k, q). Then a(u) = a(v). Moreover, for any t − 1 field elements
xi ∈ GF (q), 2 ≤ t ≥ [(k + 2)/4], there exists a vertex v of D(k, q) for
which
a(v) = (x2, . . . , xt) = (x).
So, Alice may choose symbolic password formed by polynomials
Pi(z1, . . . , zt−1), i = 1, . . . , l and work with the numerical password formed
by
Pi(a2(x1, . . . , xk), . . . , at(x1, . . . , xk)),
where (x1, . . . , xk) is the plaintext, which is the point (line) of D(k, q).
Choice of the type of plaintext (point or line), leeds to different encryption
procedures.
Looking at the equations of D(k, q) we can see that the complexity
of operation to take the neighbour of chosen colour is O(n). Thus the
complexity of operation to encrypt (or decrypt) for Alice shall be O(nl).
We realise such encryption by computer program written in Java, the
following table demonstrates its speed as function in variables l and n.
Other option is to work with the connected component of D(k, q) and
use constant password.
If you have a family of polynomial linguistic graph of bounded degree,
you may choose the dimension n such that your correspondent could
encrypt but could not decrypt and use graph encryption in ”public key
fashion", because we should use the gap between computations of poly-
nomial in given point and investigation of given system of equations.
6.1. "Toy example"-exercise
The purpose of this example is to demonstrate the encryption scheme of
section 3 involving graphs D(k, q). We illustrate the mechanical opera-
tions of cryptosystem, but its parameters are too small to give a serious
security.
1)The linguistic graph D(14, 127)
148 Maximality of affine group, and hidden graph...
It is convenient to write points (p) and lines [l] in the following form
(p) = (p1, p11, p12, p21, p22, p
′
22, p23, p32, p33, p
′
33, p34, p43, p44, p
′
44)
[l] = [l1, l11, l12, l21, l22, l
′
22, l23, l32, l33, l
′
33, l34, l43, l44, l
′
44]
The co-ordinates p1 and l1 are colours of point (p) and line [l], respec-
tively.
The girth of the graph D(14, 127) is 19. Thus we have advantages of
graphs of high girth if the length of the password is ≤ 9.
The graph D(k, q) is defined by the first 14 equations of (5). Thus the
operators to take neighbour of point (p) of the colour l1 and neighbour
of line [l] of the colour p1 can be written in the form
Nl1((p)) = [l] = [l1, p1 + l1p1, p12 + p1l11, p21 + l1p11, p22 + l1p12, p
′
22 +
p1l21, p23 + p1l22, p32 + l1p
′
22, p33 + l1p23, p
′
33 + p1l32, p34 + p1l33, p43 +
l1p
′
33, p44 + L1p34, p
′
44 + p1l43]
Np1
([l]) = (p) = (p1, p11−l1p1, p12−l1p11, p21−l1p11, p22−l1p12, p
′
22−
l21p1, p23−p1l22, p32−l1p
′
22, p33−l1p23, p
′
33−p1l32, p34−p1l22p43−l1p
′
33, p44−
l1p34, p
′
44 − p1l43)
We have to compute co-ordinates of the (p) and [l] in natural order
by iterative process.
The following graph invariants a2(u), a3(u), a4(u), where tuple u =<
u1, u11, . . . u
′
44 > can be point ot line, determine the connected compo-
nents of D(k, q).
a2(u) = ((u′
22 − u21u01) + (u11u
′
11 − u12u10) − u22
a3(u) = ((u′
33−u01u32)+(u11u
′
22−u12u21)+(u22−u′
11−u23u10)−u33),
a4(u) = (u′
44 − u01u43) + (u11u
′
33 − u12u32) + (u22u
′
22 − u23u21) +
(u33u
′
11 − u34u10) − u44)
2) The symbolic key
Let us take the following symbolic key with linear components (z1 +
z2 + z3 + 1, z1 + z2 + 2, z1 + z3 + 3, z2 + z3 + 4, z1 + 5, z2 + 6, z3 + 7, z1 −
z2 − z3 + 8, z2 − z1 − z3 + 9)
3) The affine transformations
Let us choose A = (aij), where aij = 1 is a nonzero entry iff i− j ≤ 4,
B = A−1, c = (1, 2, 1, 0, . . . , 0), d = −Bc.
4) Choice of type
Let us assume that the plaintext (x) is the point.
The information 1)- 4) allow us to determine public key encryption
scheme.
< 1 > you compute x′ = Ax + c, where x = (x1, . . . , x
′
44) is the
"symbolic" plaintext
< 2 > you can compute the numerical password np(u) for the sym-
bolic plaintext u with the "Maple" or "Matematica" by the substitution,
ai(u) instead of zi into the formula for the symbolic key.
V. A. Ustimenko 149
< 3 > you have to make a substitution of x’ instead of u and get
np = np(x′).
< 4 > consecutive application of operators Nl1(p) and Np1
(l) allow
you to compute v = x′np(x′).
< 5 > you are computing the expression
Bv + d = P(x) = (P1(x), . . . , P ′
44(x)).
< 6 > finally you can get your public expression P127(x) by taking
all integer coefficients mod127
Try to invert the public polynomial map directly by the symbolic
program in "Maple" or "Matematica".
You may repeat the exercise above with the constant password
(1, 2, 3, 4, 5, 6, 7, 8, 9).
References
[1] N.L. Biggs, Graphs with large girth, Ars Combinatoria, 25C (1988), 73–80.
[2] B. Bollobás, Extremal Graph Theory, Academic Press,
[3] Neal Coblitz, A Course in Number Theory and Cryptography, Second Edition,
Springer, 1994, 237 p.
[4] Neal Coblitz, Algebraic Aspects of Cryptography, Springer, 1998, 198 p.
[5] W. Imrich, Explicit construction of graphs without small cycles, Combinatorica 2
(1984) 53–59.
[6] Imai, Matsumoto,Public quadratic polynomial tuples for efficient signature verifi-
cation and message encryption, Advances in Cryptology, Eurocrypt ’88, Springer
Verlag, 419-453.
[7] F. Lazebnik and V. Ustimenko, Some Algebraic Constructions of Dense Graphs
of Large Girth and of Large Size, DIMACS series in Discrete Mathematics and
Theoretical Computer Science, V. 10 (1993), 75-93.
[8] F. Lazebnik F. and V. Ustimenko, Explicit construction of graphs with an arbi-
trary large girth and of large size, Discrete Appl. Math. , 60, (1995), 275 - 284.
[9] F. Lazebnik, V. A. Ustimenko and A. J. Woldar, A New Series of Dense Graphs
of High Girth, Bull (New Series) of AMS, v.32, N1, (1995), 73-79.
[10] F. Lazebnik, V. A. Ustimenko and A. J. Woldar, A characterization of the com-
ponents of the graphs D(k, q), Discrete Mathematics, 157 (1996), 271-283.
[11] A. Lubotsky, R. Philips, P. Sarnak, Ramanujan graphs, J. Comb. Theory., 115,
N 2., (1989), 62-89.
[12] G. A. Margulis, Explicit construction of graphs without short cycles and low den-
sity codes, Combinatorica, 2, (1982), 71-78.
[13] G. Margulis, Explicit constructions of concentrators, Probl. of Inform. Transm.,
10, (1975), 325-332.
[14] B. Mortimer, Permutation groups containing affine of the same degree, J. London
Math. Soc., 15, N3, 445-455.
150 Maximality of affine group, and hidden graph...
[15] J. Patarin, Cryptoanalysis of the Matsumoto and Imai public key scheme of the
Eurocrypt ’88, Advances in Cryptology, Eurocrypt ’96, Springer Verlag, 43-56.
[16] V. A. Ustimenko, Random walks on special graphs and Cryptography, Amer. Math.
Soc. Meeting, Loisville, March, 1988.
[17] V. A. Ustimenko, Coordinatization of regular tree and its quotients, In the vol-
ume "Voronoi’s Impact in Modern Science": ( Proceedings of Memorial Voronoi
Conference, Kiev, 1998), Kiev, IM AN Ukraine, July, 1998, pp. 125 - 152.
[18] V. Ustimenko, D. Sharma, Special Graphs in Cryptography in Proceedings of 2000
International Workshop on Practice and Theory in Public Key Cryptography
(PKC 2000), Melbourne, December 1.
[19] V. Ustimenko and D. Sharma, CRYPTIM: The system to encrypt text and image
data, in Proceedings of International ICSC congress on Intelligent Systems and
Applications, December 2000, University of Wollongong, 14 pp.
[20] V. Ustimenko, CRYPTIM: Graphs as Tools for Symmetric Encryption, in Lecture
Notes in Computer Science, Springer, v. 2227, 278-287.
[21] V. Ustimenko, Graphs with Special Arcs and Cryptography, Acta Applicandae
Mathematicae, 2002, vol. 74, N2, 117-153.
[22] V. Ustimenko, A. Woldar, Extremal properties of regular and affine generalised
polygons of tactical configurations, 2003, European Journal of Combinatorics,
2003, v. 24 , 99-111.
[23] V. Ustimenko, Yu. Khmelevsky, Walks on graphs as symmetric and assymetric
tools for encryption, South Pacific Journal of Natural Studies, 2002, vol. 20, 23-41.
[24] V. Ustimenko, A. Tousene, CRYPTALL-the system encrypt all type of data (to
appear)
[25] A. L. Weiss, Girth of bipartite sextet graphs, Combinatorika 4 (2-3) 1984, 241-245.
Contact information
V. A. Ustimenko Kiev Mohyla Academy (Ukraine)
E-Mail: vau@ukma.kiev.ua
Received by the editors: 22.02.2004
and in final form 21.03.2005.
|