Tao R. Finite Automata and Application to Cryptography

Подождите немного. Документ загружается.

102 3. R

Transformation Method



−1



]

−→ G

is said to be linear over GF (q), if P



is a matrix over

GF (q) and for some r

k+1

 the k-height of G



, the ﬁrst r

k+1

rows of B



is linearly independent over GF (q)andB



has zeros in the last m − r

k+1

rows whenever r

k+1

<m,whereB



is the submatrix of the ﬁrst l columns

of G



. G

k+1

−1

k+1

]

−→ G



is said to be linear over GF (q), if the ﬁrst r

k+1

rows of B



is linearly independent over GF (q). An R

−1

transformation

sequence

k+1

−1

k+1

]

−→ G



−1



]

−→ G

,k= h,...,1, 0 (3.26)

is said to be linear over GF (q), if G

k+1

−1

k+1

]

−→ G



and G



−1



]

−→ G

are

linear over GF (q)fork = h,...,1, 0.

Lemma 3.3.3.

]

−→ G



k+1

]

−→ G

k+1

,k=0, 1,...,τ − 1

is a linear modiﬁed R

transformation sequence if and only if

k+1

−1

k+1

]

−→ G



−1

]

−→ G

,k= τ − 1,...,1, 0

is a linear R

−1

transformation sequence.

Proof. From Lemma 3.2.2,

]

−→ G



k+1

]

−→ G

k+1

,k=0, 1,...,τ − 1

is a modiﬁed R

transformation sequence if and only if

k+1

−1

k+1

]

−→ G



−1

]

−→ G

,k= τ − 1,...,1, 0

is an R

−1

transformation sequence. It is easy to see that G

]

−→ G



is linear if and only if G



−1

]

−→ G

is linear and that G



k+1

]

−→ G

k+1

linear if and only if G

k+1

−1

k+1

]

−→ G



is linear. From the deﬁnition of linear

transformation sequence, the lemma follows. 

Theorem 3.3.4. Let M be a ﬁnite automaton deﬁned by (3.12) and G

, ..., B

],τ r.

(a) M is a weak inverse ﬁnite automaton with delay τ if and only if there

exist an m × l(τ +1) (l, τ)-echelon matrix G

over GF (q) and a linear R

−1

transformation sequence

k+1

−1

k+1

]

−→ G



−1



]

−→ G

,k= τ − 1,...,1, 0 (3.27)

3.3 Invertibility of Quasi-Linear Finite Automata 103

such that the rank of the submatrix B

0τ

of the ﬁrst l columns of G

is m.

(b) M is weakly invertible ﬁnite automaton with delay τ if and only if

there exist an m × l(τ +1) (l, τ)-echelon matrix G

over GF(q) and a linear

−1

transformation sequence (3.27) such that the rank of the submatrix

0τ

of the ﬁrst l columns of G

is l.

Proof. (a) Suppose that M is a weak inverse with delay τ. Clearly, there

exists a linear modiﬁed R

transformation sequence

]

−→ G



k+1

]

−→ G

k+1

,k=0, 1,...,τ − 1.

From Theorem 3.3.3, the rank of B

0τ

is m,whereB

0τ

is the submatrix of

the ﬁrst l columns of G

. From Lemma 3.3.3, taking P



= P

−1

for k =

0, 1,...,τ − 1, (3.27) is a linear R

−1

transformation sequence.

Conversely, suppose that (3.27) is a linear R

−1

transformation se-

quence and the rank of B

0τ

is m.LetP

=(P



)

−1

, k =0, 1,...,τ − 1. From

Lemma 3.3.3,

]

−→ G



k+1

]

−→ G

k+1

,k=0, 1,...,τ − 1

is a linear modiﬁed R

transformation sequence. Using Theorem 3.3.3, M

is a weak inverse with delay τ .

(b) This part is similar to part (a). 

We use R

to denote an operator: shift the last c rows l columns to the

right entering zeros to the left.

Clearly, (3.27) is a linear R

−1

transformation sequence if and only if

the following conditions hold:



= R

m−r

k+1

= P



k = τ − 1,...,1, 0,



is an m × m invertible matrix over GF (q) in the form









is the k-height of G



, G

k+1

is an (l, k + 1)-echelon matrix over GF (q)with

(k +1)-heightr

k+1

 r

and the ﬁrst r

k+1

rows of the submatrix of the ﬁrst

l columns of G

k+1

are linear independent over GF (q), k = τ − 1,...,1, 0,

where E

is the r

× r

identity matrix. In computing elements of P



,we

deﬁne u · u = u +u = u, v · u = u · v = u,0· u = u · 0=0andw + u = u + w =

u,whereu stands for undeﬁned symbol, v(=0)andw are any elements in

GF (q). Notice that the k-height of G

isthesameasthek-height of G

and

the submatrices consisting of the ﬁrst l columnsandtheﬁrstr

rows of G

and G

are the same, for k<τ. From Theorem 3.3.4, we obtain the following.

104 3. R

Transformation Method

Theorem 3.3.5. Let M be a ﬁnite automaton deﬁned by (3.12).

(a) M is a weak inverse ﬁnite automaton with delay τ if and only if there

exist an m×l(τ +1) (l, τ)-echelon matrix G

and m×m nonsingular matrices









,k=0, 1,...,τ − 1

such that the rank of the submatrix B

0τ

of the ﬁrst l columns of G

is m,

and

,...,B

]=P



m−r



m−r

(...(P



τ−1

m−r

)) ...))

if τ>0 and [B

,...,B

]=G

otherwise, where E

is the r

× r

identity

matrix, and r

is the k-height of G

(b) M is a weakly invertible ﬁnite automaton with delay τ if and only if

there exist an m × l(τ +1) (l, τ)-echelon matrix G

and m × m nonsingular

matrices









,k=0, 1,...,τ − 1

such that the rank of the submatrix B

0τ

of the ﬁrst l columns of G

is l, the

ﬁrst r

rows of B

0τ

are linearly independent over GF (q), and

,...,B

]=P



m−r



m−r

(...(P



τ−1

m−r

)) ...))

if τ>0 and [B

,...,B

]=G

otherwise, where E

is the r

× r

identity

matrix, and r

is the k-height of G

Denote r

τ+1

= m.Leth =min k { r

= m, 1  k  τ +1}. Notice that

inthecaseofr

= m, R

m−r

is the identity operator and P



is the identity

matrix. In the case of h  τ,wehave



m−r



m−r

(...(P



τ−1

m−r

)) ...))

= P



m−r



m−r

(...(P



h−2

m−r

h−1



h−1

)) ...)).

Since P



h−1

is nonsingular, the rank of the submatrix of the ﬁrst l columns of



h−1

is the same as the rank of the submatrix of the ﬁrst l columns of G

Since h  τ,wehaver

= m. Therefore, the ﬁrst r

rows of the submatrix of

the ﬁrst l columns of P



h−1

are linearly independent over GF (q)ifandonly

if the ﬁrst r

rows of the submatrix of the ﬁrst l columns of G

are linearly

independent over GF (q). Clearly, P



h−1

is also an m×l(τ +1) (l, τ)-echelon

matrix over GF(q)ofwhichthei-height is the same as the i-height of G

for

any i,0 i  τ. From Theorem 3.3.5, taking G = P



h−1

,wethenhave

the following theorem.

3.3 Invertibility of Quasi-Linear Finite Automata 105

Theorem 3.3.6. Let M be a ﬁnite automaton deﬁned by (3.12).

(a) M is a weak inverse ﬁnite automaton with delay τ if and only if there

exist an m ×l(τ +1) (l, τ)-echelon matrix G and m × m nonsingular matrices









,k=0, 1,...,h− 2

such that the rank of the submatrix of the ﬁrst l columns of G is m, and

,...,B

]=P



m−r



m−r

(...(P



h−2

m−r

h−1

(G)) ...))

if h>1 and [B

,...,B

]=G otherwise, where E

is the r

× r

identity

matrix,r

is the k-height of G, and h =min k { r

= m, 1  k  τ +1}

τ+1

= m by convention).

(b) M is a weakly invertible ﬁnite automaton with delay τ if and only if

there exist an m × l(τ +1) (l, τ)-echelon matrix G and m × m nonsingular

matrices









,k=0, 1,...,h− 2

such that the rank of the submatrix G

of the ﬁrst l columns of G is l, the

ﬁrst r

rows of G

are linearly independent over GF (q), and

,...,B

]=P



m−r



m−r

(...(P



h−2

m−r

h−1

(G)) ...))

if h>1 and [B

,...,B

]=G otherwise, where E

is the r

× r

identity

matrix,r

is the k-height of G, and h =min k { r

= m, 1  k  τ +1}

τ+1

= m by convention).

Let G be an m × l(τ + 1) incompletely speciﬁed matrix over GF (q). If

there are k

,...,k

such that 0  k

 ···  k

 τ, and for each j,

1  j  m,inrowj of G elements in the ﬁrst l(1 + k

) columns are deﬁned

andinthelastl(τ − k

) columns are undeﬁned, that is, G is in the form

⎡

⎢

⎣

... G

1,k

... G

1,k

... G

1,k

∗ ... ∗

... ... ... ... ... ... ... ... ... ...

... G

j,k

... G

j,k

∗ ... ∗∗... ∗

... ... ... ... ... ... ... ... ... ...

... G

m,k

∗ ... ∗∗ ... ∗∗... ∗

⎤

⎥

⎦

where ∗ stands for the 1 × l “undeﬁned matrix”, G

is a 1 × l completely

speciﬁed matrix, G is called an echelon matrix and k

is called the j-length of

G,forj =1,...,m.

Let G be an m × l(τ +1) (l, τ)-echelon matrix over GF (q)withi-height

, i =0, 1,...,τ.Let

106 3. R

Transformation Method

= τ − min i { 0  i  τ, r

<j r

i+1

},j=1,...,m, (3.28)

where r

τ+1

= m.ThenG is an echelon matrix with j-length k

, j =1,...,m.

In fact, for any j, 1  j  m,whenr

<j r

i+1

for some i, 0  i  τ ,

from the deﬁnition of i-height, we have that in row j of G elements in the

ﬁrst l(τ +1− i) columns are deﬁned and elements in the last li columns

are undeﬁned. From (3.28), k

= τ − i.Theninrowj of G elements in

the ﬁrst l(1 + k

) columns are deﬁned and elements in the last l(τ − k

)

columns are undeﬁned. Since r

 r

 ···  r

,itiseasytoverifythat

0  k

 ··· k

 τ.

Conversely, let G be an m × l(τ + 1) echelon matrix over GF (q)with

j-length k

, j =1,...,m.Let

=min c { 0  c  m, k

<τ+1− i if c<j m },i=1,...,τ.

Then G is an (l, τ)-echelon matrix with i-height r

, i =1,...,τ.

Since 0 = r

 r

 ··· r

 r

τ+1

= m,usingk

= τ − min i { 0 

i  τ, r

<m r

i+1

},wehavek

= τ − min i { 0  i  τ,m = r

i+1

}.It

follows immediately that

min k { 1  k  τ +1,m = r

}−1=min i { 0  i  τ,m = r

i+1

}

= τ − k

From the above discussion, Theorem 3.3.6 can be restated as follows.

Theorem 3.3.7. Let M be a ﬁnite automaton deﬁned by (3.12).

(a) M is a weak inverse ﬁnite automaton with delay τ if and only if there

exist an m × l(τ +1) echelon matrix G with j-length k

, j =1,...,m, and

m × m nonsingular matrices





k−1





,k=1, 2,...,τ − k

such that the rank of the submatrix of the ﬁrst l columns of G is m, and

,...,B

]=P



m−r



m−r

(...(P



τ−k

m−r

τ −k

(G)) ...))

if k

<τ and [B

,...,B

]=G otherwise, where E

k−1

is the r

k−1

× r

k−1

identity matrix,r

=0,

=min c { 0  c  m, k

<τ+1− i if c<j m },i=1,...,τ.

(b) M is a weakly invertible ﬁnite automaton with delay τ if and only if

there exist an m × l(τ +1) echelon matrix G with j-length k

,j =1,...,m,

and m × m nonsingular matrices

Historical Notes 107





k−1





,k=1, 2,...,τ − k

such that the rank of the submatrix G

of the ﬁrst l columns of G is l, the

ﬁrst r

rows of G

are linearly independent over GF (q), and

,...,B

]=P



m−r



m−r

(...(P



τ−k

m−r

τ −k

(G)) ...))

if k

<τ and [B

,...,B

]=G otherwise, where E

k−1

is the r

k−1

× r

k−1

identity matrix,r

=0,

=min c { 0  c  m, k

<τ+1− i if c<j m },i=1,...,τ.

Historical Notes

The R

transformation method is ﬁrst proposed in [96, 98] to deal with the

invertibility problem of linear ﬁnite automata over ﬁnite ﬁelds. The method is

then used to quasi-linear ﬁnite automata over ﬁnite ﬁelds in [21]. References

[135, 136] use the R

transformation method to ﬁnite automata over rings,

and [22] to quadratic ﬁnite automata. The R

transformation method is

also generalized to generate a kind of weakly invertible ﬁnite automata and

their weak inverses in [118, 127]. Sections 3.1 and 3.2 are based on [127] and

Sect. 3.3 is based on [21].

4. Relations Between Transformations

Renji Tao

Institute of Software, Chinese Academy of Sciences

Beijing 100080, China trj@ios.ac.cn

Summary.

In application to public key cryptosystems, for ﬁnite automata in public

keys no feasible inversion algorithm had been found. In Sect. 3.1 of the

preceding chapter, an inversion method by R

transformation was given

implicitly. In this chapter, a relation between two R

transformation

sequences beginning at the same equation is derived. It means that in

the inversion process it is enough to choose any one of the linear R

transformation sequences. Then, by exploring properties of “composition”

of two R

transformation sequences, it is shown that the inversion

method by R

transformation works for some special compound ﬁnite

automata.

Other two inversion methods are by reduced echelon matrices, and by

canonical diagonal matrix polynomials. Results in the last two sections

show that the two inversion methods are “equivalent” to the inversion

method by R

transformation.

This chapter provides a foundation for assertions on the weak key of

the public key cryptosystem based on ﬁnite automata in Sect. 9.4.

Key words: R

transformation, reduced echelon matrix, canonical di-

agonal matrix polynomial

In application to public key cryptosystems, for ﬁnite automata in public keys

no feasible inversion algorithm had been found. In Sect. 3.1 of the preceding

chapter, an inversion method by R

transformation was given implicitly.

That is, from a given ﬁnite automaton M make an equation eq

(i), choose

an R

transformation sequence of length 2τ beginning at eq

(i), check

whether the variable x

in the equation eq

(i) has at most one solution (re-

spectively a solution), if so, then an weak inverse (respectively original weak

inverse) ﬁnite automaton with delay τ of M can be feasibly constructed from

110 4. Relations Between Transformations

(i). In the ﬁrst section of this chapter, a relation between two R

trans-

formation sequences beginning at the same equation is derived. It means that

in the inversion process it is enough to choose any one of the linear R

transformation sequences.

By exploring properties of “composition” of two R

transformation

sequences, it is shown that the inversion method by R

transformation

works for some special compound ﬁnite automata, for example, one com-

ponent belongs to quasi-linear ﬁnite automata, and another component is a

weakly invertible or weak inverse ﬁnite automaton generated by linear R

transformation or with delay 0.

Another inversion method is to solve equations corresponding to an output

sequence of length τ + 1 by means of ﬁnding the reduced echelon matrix of

the coeﬃcient matrix of the equations. Section 4.3 proves that for a weakly

invertible ﬁnite automaton with delay τ, its weak inverse can be found by

the reduced echelon matrix method if and only if it can be found by the R

transformation method.

Using a “time shift” operator z, coeﬃcient matrices of pseudo-memory

ﬁnite automata may be expressed by matrix polynomials of z.Bymeans

of reducing to canonical diagonal matrix polynomials, an inversion method

was derived. In Sect. 4.4, relations between terminating and elementary R

transformation sequences and canonical diagonal matrix polynomials and

the existence of such R

transformation sequence are investigated. From

presented results, it is easy to see that the inversion method by canonical

diagonal matrix polynomial works if and only if the inversion method by R

transformation works.

This chapter provides a foundation for assertions on the weak key of the

public key cryptosystem based on ﬁnite automata in Sect. 9.4.

4.1 Relations Between R

Transformations

Throughout this chapter, for any integer i, any nonnegative integer k and any

symbol string z,weusez(i, k) to denote the symbol string z

i−1

,...,z

i−k+1

Let X and U be two ﬁnite nonempty sets. Let Y be a column vector space

of dimension m over a ﬁnite commutative ring R with identity, where m is

a positive integer. In this section, for any integer i,weusex

, u

and y

denote elements in X, U and Y , respectively.

Let ψ

μν

be a column vector of dimension l of which each component is

a single-valued mapping from U

μ+1

× X

ν+1

to Y for some integers μ  −1,

ν  0andl  1. For any integers h  0andi,let

4.1 Relations Between R

Transformations 111

μν

(u, x, i)=

⎡

⎢

⎣

μν

(u(i, μ +1),x(i, ν +1))

μν

(u(i − h, μ +1),x(i − h, ν +1))

⎤

⎥

⎦

In the case of μ = −1, ψ

μν

(u, x)andψ

μν

(u, x, i) are abbreviated to ψ

(x)

and ψ

(x, i), respectively.

In this section, for any nonnegative integer c,leteq

(i) be an equation

(y(i + c, c + t +1))+[B

,...,B

]ψ

μν

(u, x, i)=0,

and let eq



(i) be an equation



(y(i + c, c + t +1))+[B



,...,B



]ψ

μν

(u, x, i)=0,

where ϕ

and ϕ



are two single-valued mappings from Y

c+t+1

to Y , B

and



are m × l matrices over R, j =0, 1,...,h. Similarly, for any nonnegative

integer c,let ¯eq

(i) be an equation

¯ϕ

(y(i + c, c + t +1))+[

,...,

]ψ

μν

(u, x, i)=0,

and let ¯eq



(i) be an equation

¯ϕ



(y(i + c, c + t +1))+[



,...,



]ψ

μν

(u, x, i)=0,

where ¯ϕ

and ¯ϕ



are two single-valued mappings from Y

c+t+1

to Y ,

and



are m × l matrices over R, j =0, 1,...,h.

For such expressions, eq

(i)

]

−→ eq



(i)issaidtobelinear over R,ifP

is a matrix over R, and for some r

c+1

 0 the ﬁrst r

c+1

rows of B



is linearly

independent over R and B



has zeros in the last m − r

c+1

rows whenever

c+1

<m. eq



(i)

c+1

]

−→ eq

c+1

(i)issaidtobelinear over R, if the ﬁrst

c+1

rows of B



is linearly independent over R.AnR

transformation

sequence

(i)

]

−→ eq



(i),eq



(i)

c+1

]

−→ eq

c+1

(i),c=0, 1,...,n (4.1)

is said to be linear over R,ifeq

(i)

]

−→ eq



(i)andeq



(i)

c+1

]

−→ eq

c+1

(i)

are linear over R for c =0, 1,...,n.TheR

transformation sequence (4.1)

is said to be elementary over R, if (4.1) is linear over R and P

is in the form





c =0, 1,...,n,whereE

stands for the r × r identity matrix for any r,and

=0.

112 4. Relations Between Transformations

For any integers n and r with 0  r  n,weuseE

n,r

to denote the n × n

matrix



n−r



,andE

n,−r

to denote E

n,n−r

.Denotethen × r zero matrix

by 0

n,r

.AlsoweuseDIA

P,n

to denote the quasi-diagonal matrix





with n occurrences of P .

Below the ring R is restricted to a ﬁnite ﬁeld GF (q), and the R

trans-

formation means multiplying two sides of an equation on the left by a matrix

over GF (q).

Lemma 4.1.1. Let c>0,andlet

c−1

(i)

c−1

]

−→ eq



c−1

(i),eq



c−1

(i)

]

−→ eq

(i) (4.2)

be linear over GF (q) and

¯eq

c−1

(i)

[

c−1

]

−→ ¯eq



c−1

(i), ¯eq



c−1

(i)

[¯r

]

−→ ¯eq

(i). (4.3)



j=0

j,c−1



c−1



j=0

j,c−1





j=0

j,c−1



(4.4)

for some m × m matrices Q

j,c−1

over GF (q), j =0, 1,...,c− 1,thenthere

exist m × m matrices Q

over GF (q), j =0, 1, ..., c such that



j=0





j=0





j=0



. (4.5)

Moreover, if Q

0,c−1

is nonsingular and (4.3) is linear over GF (q),thenQ

is nonsingular and ¯r

= r

Proof.LetR

= E

m,¯r

, R

=[0

m,¯r

m,m−¯r

], R

= DIA

c−1



0,c−1

1,c−1

... Q

c−1,c−1

0 Q

0,c−1

... Q

c−2,c−1

c−1,c−1



= DIA

−1

c−1

,c+2

, R

= E

m(c+2),r

, R

= DIA

m,−r

,c+2

.Thenwehave

−1

= DIA

c−1

,c+2

, R

−1

= E

m(c+2),−r

, R

−1

= DIA

m,r

,c+2

Let Q = R

. Partition Q =[Q

, ..., Q

c+1,c

], where Q

has m columns, j =0, 1,...,c +1. We prove that Q

c+1,c

is 0. For any j,

0  j  c − 1, let Q



j,c−1

c−1

j,c−1

−1

c−1

and Q



j,c−1



j,c−1

