Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
264 7. Linear Autonomous Finite Automata
Ψ
(1)
M
1
(s, z)=
∞
i=0
s
i
z
i
, β
τ
=0whenever τ l
0
,andψ is defined by (7.72)
and (7.73).
For a linear backward autonomous finite automaton M
= Y,S, δ
,λ
over GF (q) of which the state transition matrix A
is not in the form of (7.78),
we can transform it to the form of (7.78) by similarity transformation, that
is, we can find a nonsingular matrix P over GF (q) such that A = P
−1
A
P
can be expressed in the form of (7.78). Let M = Y, S, δ,λ,whereδ(s)=As,
λ(s)=λ
(Ps). Then M is a linear backward autonomous finite automaton
over GF (q). It is easy to verify that M and M
areisomorphicandthestate
s
of M
and the state P
−1
s
of M are equivalent.
Notice that if the (ε
1
,...,ε
r
)rootcoordinateofaperiodicΩ in Φ
M
is β,
then the linear complexity of Ω equals to
r
i=1
n
i
l
i1
,wherel
i1
=minh[h 0,
β
i1k
=0 if h<k l
i
], i =1,...,r, the linear complexity of Ω means the
minimal state space dimension of linear shift registers over GF (q)which
generate Ω.
We finish this section by the following theorem.
Theorem 7.4.4. For any autonomous finite automaton M = Y,S, δ,λ,if
Y is a column vector space over GF (q), then there exists a linear autonomous
finite automaton
¯
M = Y,
¯
S,
¯
δ,
¯
λ over GF (q) such that the dimension of
¯
S
|S| and M is isomorphic to a finite subautomaton of
¯
M.
Proof.LetS = {s
1
,...,s
n
} and
δ(s
i
)=s
j
i
,
λ(s
i
)=
⎡
⎢
⎣
y
1i
.
.
.
y
mi
⎤
⎥
⎦
, (7.86)
i =1,...,n,
where y
ji
∈ GF (q), i =1,...,n, j =1,...,m.Let
¯
S be the column vector
space over GF (q) of dimension n.Let¯γ
i
be the column vector of dimension
n of which the i-th component is 1 and 0 elsewhere, i =1,...,n. Define
¯
δ(¯s)=
¯
A¯s,
¯
λ(¯s)=
¯
C¯s, ¯s ∈
¯
S, (7.87)
where
¯
A =[¯γ
j
1
,...,¯γ
j
n
],
¯
C =
⎡
⎢
⎢
⎢
⎣
y
11
y
12
... y
1n
y
21
y
22
... y
2n
.
.
.
.
.
.
.
.
.
.
.
.
y
m1
y
m2
... y
mn
⎤
⎥
⎥
⎥
⎦
. (7.88)
7.5 Decimation 265
Take
˜
S = {¯γ
1
,...,¯γ
n
}.
From (7.87) and (7.88),
¯
δ(¯γ
i
)=¯γ
j
i
, i =1,...,n. Therefore,
˜
S is closed in
¯
M. It follows that
˜
M = Y,
˜
S,
˜
δ,
˜
λ is a finite subautomaton of
¯
M,where
˜
δ(¯s)=
¯
δ(¯s),
˜
λ(¯s)=
¯
λ(¯s), for ¯s ∈
˜
S.Let
ϕ(s
i
)=¯γ
i
,i=1,...,n.
Clearly, ϕ is a bijection from S to
˜
S.From
¯
δ(ϕ(s
i
)) =
¯
δ(¯γ
i
)=¯γ
j
i
= ϕ(s
j
i
)=
ϕ(δ(s
i
)), we have
¯
δ(ϕ(s)) = ϕ(δ(s)),s∈ S.
Since
¯
λ(ϕ(s
i
)) =
¯
λ(¯γ
i
)=[y
1i
,...,y
mi
]
T
= λ(s
i
), we have
¯
λ(ϕ(s)) = λ(s),s∈ S.
Thus ϕ is an isomorphism from M to
˜
M. We conclude that M and
˜
M are
isomorphic.
7.5 Decimation
For any sequence ω =[w
0
,w
1
,...,w
τ
,...] and any positive integer u,the
sequence [w
0
,w
u
,...,w
uτ
,...] is called the u-decimation of ω.
Let M be a linear shift register over GF (q) with structure parameters m,
n and structure matrices A, C.Letf (z) be the characteristic polynomial of
M.
Assume that GF (q
∗
) is a splitting field of f(z). Let M
∗
be the natural
extension of M over GF (q
∗
). Take an (ε
1
,...,ε
r
) root basis of Ψ
(1)
M
∗
(z), where
f(z)=z
l
0
r
i=1
n
i
j=1
(z − ε
q
j−1
i
)
l
i
.
Given a positive integer u,letR be a relation on {1,...,r},whereiRj
if and only if ε
u
i
and ε
u
j
are conjugate on GF (q), i.e., ε
u
i
=(ε
u
j
)
q
k
for some
nonnegative integer k . Clearly, the relation R is reflexive, symmetric and
transitive. Let
P
1
,P
2
,...,P
¯r
(7.89)
be the equivalence classes of R.Foreachh,1 h ¯r, fix an integer m
h
in
P
h
.Let
266 7. Linear Autonomous Finite Automata
¯ε
h
= ε
u
m
h
. (7.90)
From the definition of P
h
, for any i in P
h
, ε
u
i
and ε
u
m
h
are conjugate on
GF (q); therefore, there exists k 0 such that ε
u
i
= ε
uq
k
m
h
, i.e., ε
u
i
=¯ε
q
k
h
.Let
v
i
=mink(k 0&ε
u
i
=¯ε
q
k
h
), (7.91)
i ∈ P
h
,h=1,...,¯r.
We use ¯n
h
to denote the degree of the minimal polynomial over GF (q)of¯ε
h
.
Then ¯ε
q
¯n
h
h
=¯ε
h
.Thus
v
i
< ¯n
h
,i∈ P
h
,h=1,...,¯r. (7.92)
Let i ∈ P
h
. Then the minimal polynomials over GF (q)ofε
u
i
and ¯ε
h
are the
same. Thus ¯n
h
=mink(k>0&ε
uq
k
i
= ε
u
i
). Since ε
uq
n
i
i
=(ε
q
n
i
i
)
u
= ε
u
i
,we
have ¯n
h
|n
i
.Let
q
i
= n
i
/¯n
h
,i∈ P
h
,h=1,...,¯r. (7.93)
Then q
i
is a positive integer. Let u = p
w
u
,whereu
and p are coprime. Take
1
¯
l
0
=min k ( ku l
0
),
¯
l
h
=max k ( k − 1=(l
i
− 1)/p
w
,i∈ P
h
), (7.94)
h =1,...,¯r.
Let
¯
f(z)=z
¯
l
0
¯r
h=1
¯n
h
j=1
(z − ¯ε
q
j−1
h
)
¯
l
h
. (7.95)
It is easy to show that
¯
f(z) is a polynomial over GF (q) with leading coefficient
1. Let
¯
M be a linear autonomous shift register over GF (q) with characteristic
polynomial
¯
f(z). Let
¯
M
∗
be the natural extension of
¯
M over GF (q
∗
). Then
¯ε
1
,...,¯ε
¯r
determine an (¯ε
1
,...,¯ε
¯r)
root basis of Ψ
(1)
¯
M
∗
.
Assume that Ω =[s
0
,s
1
,...,s
τ
,...]isinΨ
(1)
M
and its (ε
1
,...,ε
r
)root
coordinate is β.Then
s
τ
= β
τ
+
r
i=1
n
i
j=1
l
i
k=1
β
ijk
τ+k−1
k−1
ε
τq
j−1
i
,
τ =0, 1,...,
1
x stands for the maximal integer x.
7.5 Decimation 267
where β
τ
= 0 whenever τ l
0
.Let
¯
Ω =[¯s
0
, ¯s
1
,...,¯s
τ
,...]betheu-
decimation of Ω.Then
¯s
τ
= s
uτ
= β
uτ
+
r
i=1
n
i
j=1
l
i
k=1
β
ijk
uτ+k−1
k−1
ε
uτq
j−1
i
= β
uτ
+
¯r
h=1
i∈P
h
n
i
j=1
l
i
k=1
β
ijk
uτ+k−1
k−1
¯ε
τq
v
i
+j−1
h
= β
uτ
+
¯r
h=1
i∈P
h
¯n
h
j=1
q
i
−1
c=0
l
i
k=1
β
i,c¯n
h
+j,k
uτ+k−1
k−1
¯ε
τq
v
i
+c¯n
h
+j−1
h
= β
uτ
+
¯r
h=1
i∈P
h
¯n
h
j=1
q
i
−1
c=0
l
i
k=1
β
i,c¯n
h
+j,k
uτ+k−1
k−1
¯ε
τq
v
i
+j−1
h
(7.96)
= β
uτ
+
¯r
h=1
i∈P
h
v
i
+¯n
h
j=v
i
+1
q
i
−1
c=0
l
i
k=1
β
i,c¯n
h
+j−v
i
,k
uτ+k−1
k−1
¯ε
τq
j−1
h
= β
uτ
+
¯r
h=1
i∈P
h
¯n
h
j=1
q
i
−1
c=0
l
i
k=1
β
i,c¯n
h
+(j−v
i
)( mod ¯n
h
),k
uτ+k−1
k−1
¯ε
τq
j−1
h
= β
τ
+
¯r
h=1
¯n
h
j=1
˜
l
h
k=1
β
hjk
uτ+k−1
k−1
¯ε
τq
j−1
h
,
τ =0, 1,...,
where a(mod ¯n
h
)=min b(b>0&a = b (mod ¯n
h
)),
˜
l
h
=max{l
i
,i ∈ P
h
},
h =1,...,¯r,
β
τ
=0, if τ
¯
l
0
,
β
τ
= β
uτ
,τ=0,...,
¯
l
0
− 1, (7.97)
β
hjk
=
i∈P
h
q
i
−1
c=0
β
i,c¯n
h
+(j−v
i
)( mod ¯n
h
),k
,
h =1,...,¯r, j =1,...,¯n
h
,k =1,...,
˜
l
h
,
and β
ijk
=0fori ∈ P
h
, h =1,...,¯r, j =1,...,n
i
, k = l
i
+1,...,
˜
l
h
.Weuse
θ(c) to denote c/p
w
. From Theorem 7.1.3, it is easy to show that
uτ+k−1
k−1
=
p
w
(u
τ+θ(k−1))+ν
p
w
θ(k−1)+ν
=
u
τ+θ(k−1)
θ(k−1)
ν
ν
(mod p)
=
u
τ+θ(k−1)
θ(k−1)
(mod p),
where 0 ν<p
w
and ν = k − 1(mod p
w
). From (7.11), for any k,wehave
268 7. Linear Autonomous Finite Automata
u
τ+k−1
k−1
=
k
a=1
c(u
,k− 1,a− 1)
τ+a−1
a−1
,
c(u
,k− 1,a− 1) =
a−1
i=1
(−1)
i
a−1
i
−u
(i+1)+k−1
k−1
,
a =1,...,k.
Thus
u
τ+θ(k−1)
θ(k−1)
=
θ(k−1)+1
a=1
c(u
,θ(k − 1),a− 1)
τ+a−1
a−1
.
It follows that
uτ+k−1
k−1
=
θ(k−1)+1
a=1
c(u
,θ(k − 1),a− 1)
τ+a−1
a−1
(mod p).
Replacing the leftside by the rightside of the above equation in (7.96), letting
c(u
,k
,a)=0fora>k
,wehave
¯s
τ
= β
τ
+
¯r
h=1
¯n
h
j=1
˜
l
h
k=1
β
hjk
θ(k−1)+1
a=1
c(u
,θ(k − 1),a− 1)
τ+a−1
a−1
¯ε
τq
j−1
h
= β
τ
+
¯r
h=1
¯n
h
j=1
˜
l
h
k=1
β
hjk
k
a=1
c(u
,θ(k − 1),a− 1)
τ+a−1
a−1
¯ε
τq
j−1
h
= β
τ
+
¯r
h=1
¯n
h
j=1
˜
l
h
a=1
˜
l
h
k=a
c(u
,θ(k − 1),a− 1)β
hjk
τ+a−1
a−1
¯ε
τq
j−1
h
(7.98)
= β
τ
+
¯r
h=1
¯n
h
j=1
θ(
˜
l
h
−1)+1
a=1
˜
l
h
k=a
c(u
,θ(k − 1),a− 1)β
hjk
τ+a−1
a−1
¯ε
τq
j−1
h
,
τ =0, 1,...
Since
˜
l
h
=max{l
i
,i ∈ P
h
}, from (7.94), we have
¯
l
h
= θ(
˜
l
h
− 1) + 1, h =
1,...,¯r.Let
¯
β
τ
= β
τ
,τ=0,...,
¯
l
0
− 1,
¯
β
hja
=
˜
l
h
k=a
c(u
,θ(k − 1),a− 1)β
hjk
, (7.99)
h =1,...,¯r, j =1,...,¯n
h
,a=1,...,
¯
l
h
.
Then (7.98) can be written as
7.5 Decimation 269
¯s
τ
=
¯
β
τ
+
¯r
h=1
¯n
h
j=1
¯
l
h
a=1
¯
β
hja
τ+a−1
a−1
¯ε
τq
j−1
h
,
τ =0, 1,...,
where
¯
β
τ
= 0 whenever τ
¯
l
0
. Therefore,
¯
Ω is a sequence in Ψ
(1)
¯
M
of which
the (¯ε
1
,...,¯ε
¯r
)rootcoordinateis
¯
β.
(7.97) and (7.99) can be written in matrix form. We use E
i
to denote the
i × i identity matrix, 0
ij
to denote the i × j zero matrix; and the leftmost
j columnsandtherightmosti − j columns of E
i
are denoted by E
i
(j)and
E
i
(−j), respectively. Let
I
0
(i)=[E
¯n
h
(−v
i
),E
¯n
h
,...,E
¯n
h
! "# $
n
i
/¯n
h
−1
,E
¯n
h
(v
i
)],i∈ P
h
,h=1,...,¯r,
I
0
=
⎡
⎢
⎢
⎢
⎣
I
0
(0)
DIA
I
0
(1),l
1
.
.
.
DIA
I
0
(r),l
r
⎤
⎥
⎥
⎥
⎦
,
I
hkic
=
E
¯n
h
, if i ∈ P
h
,k = c,
0
¯n
h
¯n
h
, if i ∈ P
h
,h= h
or k = c,
h =1,...,¯r, k =1,...,
˜
l
h
,i=1,...,r, c=1,...,l
i
, (7.100)
I
hk
=[I
hk11
... I
hk1l
1
... I
hkr1
... I
hkrl
r
],h=1,...,¯r, k =1,...,
˜
l
h
,
I
1
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
I
11
.
.
.
I
1
˜
l
1
.
.
.
I
¯r1
.
.
.
I
¯r
˜
l
¯r
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,I
1
=
E
¯
l
0
I
1
,
I
2
(h)=
⎡
⎢
⎢
⎢
⎣
c(0, 0) c(1, 0) ... c(
¯
l
h
− 1, 0) ... c(
˜
l
h
− 1, 0)
0 c(1, 1) ... c(
¯
l
h
− 1, 1) ... c(
˜
l
h
− 1, 1)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
00 ... c(
¯
l
h
− 1,
¯
l
h
− 1) ... c(
˜
l
h
− 1,
¯
l
h
− 1)
⎤
⎥
⎥
⎥
⎦
,
h =1,...,¯r,
270 7. Linear Autonomous Finite Automata
I
2
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
E
¯
l
0
I
2
(1)
I
2
(2)
.
.
.
I
2
(¯r)
⎤
⎥
⎥
⎥
⎥
⎥
⎦
,
where the definition of the symbol DIA is in Sect. 4.1 of Chap. 4, I
0
(0) is
an
¯
l
0
× l
0
matrix of which the element at row i and column u(i − 1) + 1 is
1 and 0 elsewhere, and c(i, j) stands for c(u
,θ(i),j)E
¯n
h
.Itiseasytoverify
that (7.97) can be written as β
= I
1
I
0
β and that (7.99) can be written as
¯
β = I
2
β
. Therefore,
¯
β = I
2
I
1
I
0
β. We complete the proof of the following
theorem.
Theorem 7.5.1. Let Ω be a sequence in Ψ
(1)
M
,andβ the (ε
1
,...,ε
r
) root
coordinate of Ω.If
¯
Ω is the u-decimation of Ω,then
¯
Ω is in Ψ
(1)
¯
M
and its
(¯ε
1
,...,¯ε
¯r
) root coordinate
¯
β is determined by
¯
β = I
2
I
1
I
0
β.
Corollary 7.5.1. Let
J = D(¯ε
1
,...,¯ε
¯r
,
¯
M)I
2
I
1
I
0
D(ε
1
,...,ε
r
,M)
−1
,
where D(·) is defined by (7.35).ThenΨ
(1)
¯
M
(¯s) is the u-decimation of Ψ
(1)
M
(s)
if and only if ¯s = Js;therefore,J is a matrix over GF (q).
By the way, if the characteristic polynomial f(z)ofM has no nonzero
repeated root, then
˜
l
h
=
¯
l
h
=1,h =1,...,¯r.ThusI
2
(h) in (7.100) equals
E
¯n
h
; therefore I
2
is the identity matrix.
Theorem 7.5.2. Each sequence in Ψ
(1)
¯
M
is u-decimations of q
n−¯n
sequences
in Ψ
(1)
M
,andu-decimations of Ψ
(1)
M
(s
1
) and Ψ
(1)
M
(s
2
) are the same if and only
if Js
1
= Js
2
,where¯n =
¯
l
0
+
¯r
h=1
¯n
h
¯
l
h
.
Proof. It is easy to see that the rank of I
0
is n
=
¯
l
0
+
¯r
h=1
i∈P
h
¯n
h
l
i
and the rank of I
1
is ˜n =
¯
l
0
+
¯r
h=1
¯n
h
˜
l
h
.Sinceu
and p are coprime, we have
c(u
,a,a)=(u
)
a
=0(modp). Using this fact, noticing c(u
,k
,a)=0for
k
<a, we can prove that the rank of I
2
(h)is¯n
h
¯
l
h
; therefore, the rank of I
2
is
¯n. Clearly, D(¯ε
1
,...,¯ε
¯r
,
¯
M)andD(ε
1
,...,ε
r
,M) are nonsingular matrices.
Using Sylvester inequality, that is, “the rank of G + the rank of H − the
number of rows of H the rank of GH the rank of G, the rank of H”, it is
easy to see that the rank of J is ¯n.Since¯n isthenumberofrowsofJ, for any
state ¯s of
¯
M, the equation ¯s = Js has q
n−¯n
solutions. From Corollary 7.5.1,
Ψ
(1)
¯
M
(¯s)isu-decimations of q
n−¯n
sequences in Ψ
(1)
M
, i.e., Ψ
(1)
M
(s), s ∈ S,¯s = Js.
From Corollary 7.5.1, u-decimations of Ψ
(1)
M
(s
1
)andΨ
(1)
M
(s
2
)arethesame
if and only if Js
1
= Js
2
.
Historical Notes 271
Corollary 7.5.2. If ¯n = n, then each sequence in Ψ
(1)
¯
M
is the u-decimation
of one sequence in Ψ
(1)
M
; therefore, the u-decimation of any nonzero sequence
in Ψ
(1)
¯
M
is nonzero.
It is easy to prove that in the case of u>1, ¯n = n holds if and only if the
following conditions hold: ε
u
1
,...,ε
u
r
are not conjugate on GF (q)witheach
other, degrees of minimal polynomials of ε
i
and ε
u
i
are the same, i =1,...,r,
0isnotarepeatedrootoff(z), f(z) has no nonzero repeated root or u and
p are coprime. In particular, whenever u>1andf(z) is irreducible other
than z,¯n = n holds if and only if degrees of minimal polynomials of ε
1
and
ε
u
1
are the same.
Historical Notes
Each component sequence of an output sequence of a linear autonomous
finite automaton over a finite field is equivalent to a linear shift register
sequence over a finite field. A great deal of work has been done on linear shift
register sequences (equivalently, linear autonomous finite automata with 1-
dimensional output), see [51] and its references for example. In particular, a
root representation for linear shift register sequences is found in [54], pp. 20–
22. References [97, 98] devote mainly to general (viz. the output dimension
1) linear autonomous finite automata over finite fields. The material of this
chapter is taken out from Appendix III and Chap. 3 of [98], but Theorem 7.3.2
is narrowed and its proof is slightly simplified.
8. One Key Cryptosystems and Latin Arrays
Renji Tao
Institute of Software, Chinese Academy of Sciences
Beijing 100080, China trj@ios.ac.cn
Summary.
In the first seven chapters, theory of finite automata is developed. From
now on, some applications to cryptography are presented. This chapter
proposes a canonical form for one key cryptosystems in the sense: for any
one key cryptosystem without data expansion and with bounded error
propagation implementable by a finite automaton, we always find a one
key cryptosystem in canonical form such that they are equivalent in be-
havior. This assertion is affirmative by results concerned on feedforward
invertibility in Sects. 1.5 and 5.2. Under the framework of the canonical
form, the next is to study its three components: an autonomous finite au-
tomaton, a family of permutations, and a nonlinear transformation. The-
ory of autonomous finite automata has been discussed in the preceding
chapter. As to permutational family, theory of Latin arrays, a topic on
combinatory theory, is presented in this chapter also.
Key words: one key cryptosystem, canonical form, Latin array
In the first seven chapters, theory of finite automata is developed. From now
on, some applications to cryptography are presented. This chapter proposes
a canonical form for one key cryptosystems in the sense: for any one key
cryptosystem without data expansion and with bounded error propagation
implementable by a finite automaton, we always find a one key cryptosystem
in canonical form such that they are equivalent in behavior. This assertion is
affirmative by results concerned on feedforward invertibility in Sects. 1.5 and
5.2. Under the framework of the canonical form, the next is to study its three
components: an autonomous finite automaton, a family of permutations, and
a nonlinear transformation. Theory of autonomous finite automata has been
discussed in the preceding chapter. As to permutational family, theory of
Latin arrays, a topic on combinatory theory, is presented in this chapter
also.
274 8. One Key Cryptosystems and Latin Arrays
8.1 Canonical Form for Finite Automaton One Key
Cryptosystems
From a mathematical viewpoint, a cryptographic system,orcryptosystem for
short, is a family of transformations {f
k
,k ∈ K} depended on a parameter k
called the key,whereK is called the key space, f
k
is called the cryptographic
transformation which is an injective mapping from a set P (the plaintext
space) to a set C (the ciphertext space). For sending a message α which is re-
ferred to as plaintext through an insecure channel, where it may be tapped by
an adversary, using this cryptosystem, the sender first encrypts α by applying
f
k
to it and then sends the result f
k
(α) which is referred to as ciphertext
over the channel. The receiver decrypts the ciphertext f
k
(α) by applying f
−1
k
to it and retrieves the plaintext α,wheref
−1
k
is an inverse transformation of
f
k
. The receiver and the sender share the key k; this cryptosystem is referred
to as a one key cryptosysyem.
An example of cryptosystems is the stream cipher of which the key string
is a pseudorandom sequence generated by a binary shift register of order n.
The key space is the vector space of dimension n over GF (2), the plaintext
space and the ciphertext space consist of all words over GF (2), and the cryp-
tographic transformation f
k
is defined by f
k
(x
0
x
1
...x
l−1
)=y
0
y
1
...y
l−1
,
where y
i
= s
i
⊕ x
i
, i =0, 1,...,l− 1, and the key string s
0
s
1
...s
l−1
is the
first l digits of the output of the shift register for the initial state k.Itis
well known that shift register sequences have received extensive attentions in
cryptology community since the 1950s. Although shift registers are impor-
tant sequence generators in stream ciphers, they are merely a special kind of
autonomous finite automata. Finite automata have been regarded as a nat-
ural mathematical model of cryptosystems from an implementing viewpoint,
where the plaintext space and the ciphertext space consist of all words over
some finite sets, and the cryptographic transformation f
k
(α)equalsλ(k, α),
λ being the output function of some weakly invertible finite automaton, and
the key space is a set of weakly invertible finite automata and their initial
states.
Assume that a finite automaton M = X, Y, S, δ,λ is chosen as an en-
coder to implement encryption. Then M must satisfy some conditions on
invertibility. In the case where M is invertible with delay τ,wemaychoose
its inverse finite automaton with delay τ,sayaτ-order input-memory finite
automaton M
= Y, X, S
,δ
,λ
, as the corresponding decoder to imple-
ment decryption. To encrypt a plaintext x
0
...x
l−1
in X
∗
,wefirstexpand
randomly τ letters x
l
,...,x
l+τ−1
in X to its end and choose randomly a state
s of M, then compute