Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
8.3 Linearly Independent Latin Arrays 335
Lemma 8.3.5. Assume that two 2
r
× r matrices V and V
are equivalent.
(a) Columns of V
−
are linearly independent if and only if columns of V
−
are linearly independent.
(b) Rows of P
−1
V are distinct if and only if rows of P
−1
V
are distinct.
Proof. (a) Since V and V
are equivalent, there exists D
Q
,δ,C in G
r
such that V
= V
D
Q
,δ,C
.Thus
V
−
=
⎡
⎢
⎣
P
2Q
.
.
.
P
rQ
⎤
⎥
⎦
V
−
C.
Therefore, columns of V
−
are linearly independent if and only if columns of
V
−
are linearly independent.
(b) Since D
Q
is a permutation matrix, rows of P
−1
V are distinct if
andonlyifrowsofD
Q
(P
−1
V ) are distinct. Since C is nonsingular, rows
of D
Q
(P
−1
V ) are distinct if and only if rows of D
Q
(P
−1
V )C are distinct.
From Lemma 8.3.4, P
−1
V are distinct if and only if rows of P
−1
V
are dis-
tinct.
Theorem 8.3.3. Let ϕ and ϕ
be two transformations on R
r
2
,andV
ϕ
and
V
ϕ
be submatrices of the last r columns of PΦ and PΦ
, respectively, where Φ
and Φ
are truth tables of ϕ and ϕ
, respectively. If V
ϕ
and V
ϕ
are equivalent,
then the condition that c
ϕ
> 1 and ϕ is invertible holds if and only if the
condition that c
ϕ
> 1 and ϕ
is invertible holds.
Proof. From Lemma 8.3.5, Proposition 8.3.4(b) and Proposition 8.3.5.
On S(V
0
,V
1
)
For any row vector V
0
of dimension r over GF (2) and any r × r matrix V
1
over GF (2), we use S(V
0
,V
1
) to denote a set of 2
r
× r matrices over GF (2)
such that V ∈ S(V
0
,V
1
) if and only if the following conditions hold: the first
row of V is V
0
, the submatrix of rows 2 to 1 + r of V is V
1
, columns of V
−
are linearly independent, and rows of P
−1
V are distinct.
For any transformation ϕ on R
r
2
,letV
ϕ
be the last r columns of PΦ,
where Φ is the truth table of ϕ. Denote the first row of V
ϕ
by V
ϕ0
,andthe
submatrix consisting of rows 2 to r +1 of V
ϕ
by V
ϕ1
. From Propositions
8.3.4 (b) and 8.3.5, if c
ϕ
> 1andϕ is invertible, then V
ϕ
∈ S(V
ϕ0
,V
ϕ1
).
Conversely, from Propositions 8.3.4 (b) and 8.3.5, for any V ∈ S(V
0
,V
1
), if
ϕ is the transformation on R
r
2
with V
ϕ
= V ,thenc
ϕ
> 1andϕ is invertible.
336 8. One Key Cryptosystems and Latin Arrays
Theorem 8.3.4. Let δ be a row vector of dimension r over GF (2), Q an
r × r permutation matrix over GF (2),andC an r × r nonsingular matrix
over GF (2). Then we have
S((V
0
⊕ δ)C, QV
1
C)={V
D
Q
,δ,C
| V ∈ S(V
0
,V
1
)},
and |S((V
0
⊕ δ)C, QV
1
C)| = |S(V
0
,V
1
)|.
Proof. For any V ∈ S(V
0
,V
1
), from the definitions, using Lemma 8.3.5,
we have V
D
Q
,δ,C
∈ S((V
0
⊕ δ)C, QV
1
C). Thus S((V
0
⊕ δ)C, QV
1
C) ⊇
{V
D
Q
,δ,C
| V ∈ S(V
0
,V
1
)}. Clearly, for any V,
¯
V ∈ S(V
0
,V
1
), if V =
¯
V ,thenV
D
Q
,δ,C
=
¯
V
D
Q
,δ,C
. It follows that |S((V
0
⊕ δ)C, QV
1
C)|
|S(V
0
,V
1
)|. On the other hand, we have S(V
0
,V
1
) ⊇{V
D
Q
−1
,δC,C
−1
| V ∈
S((V
0
⊕ δ)C, QV
1
C)} and |S((V
0
⊕ δ)C, QV
1
C)| |S(V
0
,V
1
)|.Thuswehave
|S((V
0
⊕ δ)C, QV
1
C)| = |S(V
0
,V
1
)|. It follows that S((V
0
⊕ δ)C, QV
1
C)=
{V
D
Q
,δ,C
| V ∈ S(V
0
,V
1
)}.
For any positive integer r, denote G
r
= {Q, C|Q is an r×r permutation
matrix over GF (2), C is an r ×r nonsingular matrix over GF (2 }.Let· be an
operation on G
r
defined by Q, C·Q
,C
= QQ
,C
C.Itiseasytoverify
that G
r
, · is a group. For any r × r matrix V
1
over GF (2) and any Q, C in
G
r
, denote V
Q,C
1
= QV
1
C. V
1
and V
Q,C
1
are said to be equivalent under
G
r
. It is easy to verify that the equivalence relation is reflexive, symmetric
and transitive. Any equivalence class of the equivalence relation under G
r
includes r × r matrices in the form
E 0
B 0
,whereE is the identity matrix,
columns of B are in decreasing order in some ordering. The minimum one in
the ordering is called the canonical form of the equivalence class under G
r
.
Notice that the property that rows of V
1
are nonzero and the distinct
keeps unchanged under equivalence. Clearly, S(0,V
1
) = ∅ implies that rows
of V
1
are nonzero and distinct. From Theorem 8.3.4, generation of linear inde-
pendent permutations can be reduced to generating S(0,V
1
), where V
1
ranges
over canonical forms under G
r
,androwsofV
1
are nonzero and distinct. For
example, in the case of r =4,V
1
has only three alternatives (see [38] for more
details):
⎡
⎢
⎢
⎣
1000
0100
0010
0001
⎤
⎥
⎥
⎦
,
⎡
⎢
⎢
⎣
1000
0100
0010
1100
⎤
⎥
⎥
⎦
,
⎡
⎢
⎢
⎣
1000
0100
0010
1110
⎤
⎥
⎥
⎦
.
Lemma 8.3.6. Let
R =
⎡
⎣
I
0
00
0 E
1
0
0 W
∗
P
R
⎤
⎦
,P
R
=
⎡
⎣
I
0
E
1
P
R
⎤
⎦
,
8.3 Linearly Independent Latin Arrays 337
where P
R
is a (2
r
− 1 − r) × (2
r
− 1 − r) permutation matrix over GF(2),and
W
∗
= W ⊕ P
R
W, W =
⎡
⎢
⎣
W
2
.
.
.
W
r
⎤
⎥
⎦
.
Then we have P
R
P
−1
= P
−1
R,andR satisfying this equation is uniquely
determined by P
R
.
Proof. Partition P
−1
into blocks with 1, r,2
r
− 1 − r rows and columns
in turn
P
−1
=
⎡
⎣
I
0
00
I
1
E
1
0
I
WE
⎤
⎦
,
where I
is the column vector of dimension 2
r
−1−r of which each component
is 1, and E
is the (2
r
− 1 − r) × (2
r
− 1 − r) identity matrix. It is easy to
verify that both P
R
P
−1
and P
−1
R are equal to
⎡
⎣
I
0
00
I
1
E
1
0
I
P
R
WP
R
⎤
⎦
.
Therefore, P
R
P
−1
= P
−1
R.WeprovethatifP
R
P
−1
= P
−1
R
then R = R
.
Partition R
into blocks with 1, r,2
r
− 1 − r rows and columns in turn
R
=
⎡
⎣
R
11
R
12
R
13
R
21
R
22
R
23
R
31
R
32
R
33
⎤
⎦
.
Since P
−1
R
= P
R
P
−1
,wehaveR
11
= I
0
, R
12
=0,R
13
= 0. It follows that
R
21
=0,R
22
= E
1
, R
23
=0.Furthermore,wehaveI
⊕ R
31
= I
, W ⊕
R
32
= P
R
W , R
33
= P
R
. It follows that R
31
=0,R
32
= W ⊕ P
R
W = W
∗
.
Therefore, R
= R.
Lemma 8.3.7. For any 2
r
×r matrices V and V
over GF (2), the following
two conditions are equivalent: (a) the first r +1 rows of P
−1
V and of P
−1
V
are the same, and rows of P
−1
V
are a permutation of rows of P
−1
V ; (b) the
first r +1 rows of V and of V
are the same, and there exists a (2
r
− 1 − r) ×
(2
r
− 1 − r) permutation matrix P
R
such that V
−
=(E
⊕ P
R
)WV
1
⊕ P
R
V
−
,
where V
−
and V
−
are the submatrices consisting of the last 2
r
− 1 − r rows
of V and V
, respectively, V
1
is the submatrix consisting of rows 2 to r +1 of
V , E
is the (2
r
− 1 − r) × (2
r
− 1 − r) identity matrix, and W =
W
2
.
.
.
W
r
.
338 8. One Key Cryptosystems and Latin Arrays
Proof. From the form of P
−1
, it is easy to verify that the first r +1 rows
of P
−1
V and P
−1
V
are the same if and only if the first r +1 rows of V and
of V
are the same.
Suppose that the first r +1 rows of V and of V
are the same and that
V
−
=(E
⊕ P
R
)WV
1
⊕ P
R
V
−
.Let
R =
⎡
⎢
⎣
I
0
00
0 E
1
0
0(E
⊕ P
R
)WP
R
⎤
⎥
⎦
.
Then we have V
= RV . Therefore, P
−1
V
= P
−1
RV .Let
P
R
=
⎡
⎣
I
0
E
1
P
R
⎤
⎦
.
From Lemma 8.3.6, we obtain P
−1
V
= P
−1
RV = P
R
P
−1
V .Thatis,rows
of P
−1
V
are a permutation of rows of P
−1
V .
Conversely, suppose that rows of P
−1
V
are a permutation of rows of
P
−1
V and the first r + 1 rows of them are the same. Then there exists a
permutation matrix P
R
=
I
0
E
1
P
R
such that P
−1
V
= P
R
P
−1
V .From
Lemma 8.3.6, we obtain P
−1
V
= P
−1
RV . It follows that V
= RV .There-
fore, V
−
=(E
⊕ P
R
)WV
1
⊕ P
R
V
−
.
Theorem 8.3.5. Let V
0
and V
1
be 1 × r and r × r matrices over GF (2),
respectively. Assume that rows of V
1
are distinct and nonzero. Let U
−
be a
(2
r
− 1 − r) × r matrix over GF (2) of which rows consist of all different row
vectors of dimension r except V
0
and rows of I
1
V
0
⊕ V
1
.ThenS(V
0
,V
1
) is
the set of all
⎡
⎢
⎣
V
0
V
1
WV
1
⊕ P
R
(I
V
0
⊕ U
−
)
⎤
⎥
⎦
,
P
R
ranging over (2
r
− 1 − r) × (2
r
− 1 − r) permutation matrices such that
columns of WV
1
⊕ P
R
(I
V
0
⊕ U
−
) are linearly independent, where I
1
and I
are column vectors of dimensions r and 2
r
− 1 − r of which each component
is 1, respectively.
Proof.Let
V = P
⎡
⎢
⎣
V
0
I
1
V
0
⊕ V
1
U
−
⎤
⎥
⎦
.
8.3 Linearly Independent Latin Arrays 339
Clearly, the first row of V is V
0
, the submatrix consisting of rows 2 to r +1
of V is V
1
,androwsofP
−1
V are distinct. Since U
−
= I
V
0
⊕ WV
1
⊕ V
−
,we
have WV
1
⊕ V
−
= I
V
0
⊕ U
−
.
Suppose that V
∈ S(V
0
,V
1
). Then the first row of V
is V
0
, the submatrix
consisting of rows 2 to r+1 of V
is V
1
, columns of V
−
are linearly independent,
and rows of P
−1
V
are distinct. Thus V and V
satisfy the condition (a)
in Lemma 8.3.7. From Lemma 8.3.7, there exists a permutation matrix P
R
such that V
−
=(E
⊕ P
R
) WV
1
⊕ P
R
V
−
= WV
1
⊕ P
R
(WV
1
⊕ V
−
). Since
WV
1
⊕ V
−
= I
V
0
⊕ U
−
,wehaveV
−
= WV
1
⊕ P
R
(I
V
0
⊕ U
−
). Therefore,
columns of WV
1
⊕ P
R
(I
V
0
⊕ U
−
) are linearly independent.
Conversely, suppose that P
R
is a permutation matrix and that columns
of WV
1
⊕ P
R
(I
V
0
⊕ U
−
) are linearly independent. Let
V
=
⎡
⎢
⎣
V
0
V
1
WV
1
⊕ P
R
(I
V
0
⊕ U
−
)
⎤
⎥
⎦
.
Then columns of V
−
are linearly independent. Since WV
1
⊕ V
−
= I
V
0
⊕ U
−
,
we have V
−
= WV
1
⊕ P
R
(WV
1
⊕ V
−
). Thus V and V
satisfy the condi-
tion (b) in Lemma 8.3.7; therefore, the condition (a) in Lemma 8.3.7 holds.
Since rows of P
−1
V are distinct, rows of P
−1
V
are distinct. Therefore, V
∈
S(V
0
,V
1
).
Problem P (a
1
,...,a
k
,b
1
,...,b
k
)
Given a row vector V
0
of dimension r over GF (2) and an r × r matrix V
1
over GF (2) with distinct and nonzero rows, we fix a (2
r
− 1 − r) × r matrix
U
−
over GF (2) such that rows of V
0
, I
1
V
0
⊕ V
1
and U
−
are all different
row vectors of dimension r.DenotingA = WV
1
and B = I
V
0
⊕ U
−
,from
Theorem 8.3.5, the problem on generation of S(V
0
,V
1
) is reduced to choosing
(2
r
− 1 − r) × (2
r
− 1 − r) permutation matrices P
R
’s such that columns
of A ⊕ P
R
B are linearly independent. The latter can be generalized to the
following problem.
Problem P (a
1
,...,a
k
,b
1
,...,b
k
): given row vectors a
1
,...,a
k
,b
1
,...,b
k
of dimension r over GF (2), find all permutations, say π,on{1, 2,...,k} such
that columns of V
π
are linearly independent, where
V
π
=
⎡
⎢
⎢
⎢
⎢
⎣
a
1
⊕ b
π(1)
a
2
⊕ b
π(2)
.
.
.
a
k
⊕ b
π(k)
⎤
⎥
⎥
⎥
⎥
⎦
.
340 8. One Key Cryptosystems and Latin Arrays
Clearly, if k<r, then Problem P (a
1
,...,a
k
,b
1
,...,b
k
) has no solution.
Below we assume k r.
For any sequences (c
1
,...,c
r
)and(d
1
,...,d
r
), if there exists i,1 i r,
such that c
1
= d
1
, ..., c
i−1
= d
i−1
and c
i
<d
i
,(c
1
,...,c
r
)issaidtobe
less than (d
1
,...,d
r
). For any solution π of Problem P (a
1
,...,a
k
,b
1
,...,b
k
),
consider the set of all sequences (c
1
,...,c
r
) such that 1 c
1
<c
2
<...<
c
r
k,rowsc
1
,...,c
r
of V
π
are linearly independent. The minimum sequence
in the set is called the rank-spectrum of π. Since columns of V
π
are linearly
independent, the rank-spectrum of π is defined.
Denote the set of all solutions of Problem P (a
1
,...,a
k
,b
1
,...,b
k
)with
rank-spectrum (c
1
,...,c
r
)byV (c
1
,...,c
r
). Let
V (c
1
,...,c
r
; d
1
,...,d
r
)={π | π ∈ V (c
1
,...,c
r
),π(c
1
)=d
1
,...,π(c
r
)=d
r
}.
Let π ∈ V (c
1
,...,c
r
; d
1
,...,d
r
). Then a
1
⊕ b
π(1)
= ... = a
c
1
−1
⊕
b
π(c
1
−1)
=0anda
c
1
⊕ b
d
1
= 0. Therefore, if for some i<c
1
, a
i
is differ-
ent from each b
j
, j =1,...,k,thenV (c
1
,...,c
r
)=∅.
We use R(c
1
,...,c
i
,d
1
,...,d
i
) to denote the vector space generated by
a
c
1
⊕ b
d
1
, ..., a
c
i
⊕ b
d
i
, which is the 0-dimensional space {0} inthecaseof
i = 0. For any I ⊆{1, ..., k},let
Π(I,h,c
1
,...,c
i
,d
1
,...,d
i
)
= {j | j ∈{1,...,k}\I, b
j
∈ a
h
⊕ R(c
1
,...,c
i
,d
1
,...,d
i
)}.
Given c
1
,...,c
r
and d
1
,...,d
r
such that 1 c
1
<c
2
< ···<c
r
k and
that d
1
,...,d
r
are distinct elements in {1, ..., k}, denote c
0
=0,c
r+1
= k+1.
Let
H
i
= {h | c
i
<h<c
i+1
},i=0, 1,...,r.
Define a relation ∼
i
on H
i
h ∼
i
h
⇔ a
h
⊕ a
h
∈ R(c
1
,...,c
i
,d
1
,...,d
i
),
0 i r. Clearly, ∼
i
is reflexive, symmetric and transitive. We use H
i1
,
H
i2
,..., H
it
i
to denote all equivalence classes of ∼
i
on H
i
.
Lemma 8.3.8. Assume that 1 c
1
<c
2
< ··· <c
r
k and that
d
1
,...,d
r
are distinct elements in {1, ..., k}.LetI ⊆{1, ..., k}.Then
for any i, 0 i r,andanyh, h
∈ H
i
we have (a) if h ∼
i
h
holds,
then Π(I,h,c
1
,...,c
i
,d
1
,...,d
i
)=Π(I,h
,c
1
,...,c
i
,d
1
,...,d
i
),and(b) if
h ∼
i
h
does not hold, then Π (I, h, c
1
,..., c
i
, d
1
, ..., d
i
) and Π (I, h
,
c
1
,..., c
i
, d
1
, ..., d
i
) are disjoint.
8.3 Linearly Independent Latin Arrays 341
Proof. (a) Since h ∼
i
h
holds, we have a
h
⊕ a
h
∈ R(c
1
,...,c
i
,d
1
,...,d
i
).
Therefore, a
h
⊕ R(c
1
,...,c
i
,d
1
,...,d
i
)=a
h
⊕ R(c
1
,...,c
i
,d
1
,...,d
i
). It
follows that Π(I, h, c
1
, ..., c
i
, d
1
, ..., d
i
)=Π(I, h
, c
1
, ..., c
i
, d
1
, ..., d
i
).
(b) Since h ∼
i
h
does not hold, a
h
⊕ a
h
is not in R(c
1
,...,c
i
,d
1
,...,d
i
).
It follows that the coset a
h
⊕ R(c
1
,...,c
i
,d
1
,...,d
i
)andthecoseta
h
⊕
R(c
1
,..., c
i
, d
1
, ..., d
i
) are disjoint. Therefore, Π (I, h, c
1
, ..., c
i
, d
1
, ...,
d
i
)andΠ (I, h
, c
1
,..., c
i
, d
1
, ..., d
i
)aredisjoint.
Lemma 8.3.9. Assume that 1 c
1
<c
2
< ··· <c
r
k and that d
1
,...,d
r
are distinct elements in {1, ..., k}.LetI ⊆{1, ..., k}. Then for any i and i
,
0 i
<i r,anyh ∈ H
i
and any h
∈ H
i
, Π(I,h
,c
1
,...,c
i
,d
1
,...,d
i
)
is a subset of Π(I,h,c
1
,...,c
i
,d
1
,...,d
i
) or they are disjoint.
Proof. Suppose that the intersection set of Π(I,h
,c
1
,...,c
i
,d
1
,...,d
i
)
and Π(I,h,c
1
,...,c
i
,d
1
,...,d
i
) is nonempty. Then the intersection set of
a
h
⊕ R(c
1
,...,c
i
,d
1
,...,d
i
)anda
h
⊕ R(c
1
,...,c
i
,d
1
,...,d
i
)isnonempty.
This yields h ∼
i
h
,sinceR(c
1
, ..., c
i
, d
1
, ..., d
i
) is a subspace of
R(c
1
,...,c
i
,d
1
,...,d
i
). Thus a
h
⊕ R(c
1
, ..., c
i
, d
1
, ..., d
i
) ⊆ a
h
⊕
R(c
1
, ..., c
i
, d
1
, ..., d
i
)=a
h
⊕ R(c
1
,...,c
i
,d
1
,...,d
i
). It follows that
Π(I,h
,c
1
,...,c
i
,d
1
,...,d
i
) ⊆ Π(I,h, c
1
, ..., c
i
, d
1
, ..., d
i
).
Let N
0j
= ∅ for any j. For any i, j,1 i r,1 j t
i
,let
N
ij
= { (i
,j
) | 0 i
<i, 1 j
t
i
,
(∃h)
H
ij
(∃h
)
H
i
j
[Π(I,h
,c
1
,...,c
i
,d
1
,...,d
i
)
⊆ Π(I,h,c
1
,...,c
i
,d
1
,...,d
i
)] }.
Theorem 8.3.6. Assume that 1 c
1
<c
2
< ··· <c
r
k and that
d
1
,...,d
r
∈{1,...,k} are distinct. Let I = {d
1
, ..., d
r
}. Then for any
transformation π on {1, ..., k}, π is in V (c
1
,...,c
r
; d
1
,...,d
r
) if and only
if the following conditions hold:
(a) π(c
j
)=d
j
, j =1,...,r;
(b) a
c
1
⊕ b
d
1
, ..., a
c
r
⊕ b
d
r
are linearly independent;
(c) any i, j, 0 i r, 1 j t
i
, |π(H
ij
)| = |H
ij
| and
π(H
ij
) ⊆ Π(I,h
ij
,c
1
,...,c
i
,d
1
,...,d
i
) \
(i
,j
)∈N
ij
π(H
i
,j
),
where h
ij
is an arbitrary element in H
ij
.
Proof. only if : Suppose that π ∈ V (c
1
,...,c
r
; d
1
,...,d
r
). From the de-
finition of V (c
1
,...,c
r
; d
1
,...,d
r
), (a) and (b) are obvious. Since π is a
permutation, numbers of elements of H
ij
and π(H
ij
)arethesame.For
any i, i
,0 i
<i r,sinceH
i
and H
i
are disjoint, π(H
i
)and
342 8. One Key Cryptosystems and Latin Arrays
π(H
i
) are disjoint. It follows that π(H
ij
)and
(i
,j
)∈N
ij
π(H
i
,j
)aredis-
joint. On the other hand, for any h in H
ij
,since(c
1
,...,c
r
) is the rank-
spectrum of π, a
h
⊕ b
π(h)
is in R(c
1
,...,c
i
,d
1
,...,d
i
). Since π is a permuta-
tion, π(h)isnotinI. Therefore, π(h) ∈ Π(I,h,c
1
,...,c
i
,d
1
,...,d
i
). Since
h ∼
i
h
ij
, from Lemma 8.3.8, we obtain Π(I, h, c
1
, ..., c
i
, d
1
, ..., d
i
)=
Π(I,h
ij
,c
1
,...,c
i
,d
1
,...,d
i
). Thus π(h) ∈ Π(I,h
ij
,c
1
,...,c
i
,d
1
,...,d
i
). It
follows that π(H
ij
) ⊆ Π(I,h
ij
,c
1
,...,c
i
,d
1
,...,d
i
). Therefore, (c) holds.
if : Suppose that the transformation π satisfies conditions (a), (b) and
(c). First of all, we prove a proposition by reduction to absurdity: for any
i, i
,0 i
<i r, π(H
i
)andπ(H
i
) are disjoint. Suppose to the con-
trary that there exist i and i
,0 i
<i r, such that π(H
i
)andπ(H
i
)
intersect. Then there exist j and j
,1 j t
i
,1 j
t
i
, such that
π(H
ij
)andπ(H
i
j
) intersect. Since (c)holds,Π(I,h,c
1
,...,c
i
,d
1
,...,d
i
)
and Π(I,h
,c
1
,...,c
i
,d
1
,...,d
i
) intersect, for any h ∈ H
ij
, h
∈ H
i
j
.Using
Lemma 8.3.9, Π(I,h
,c
1
,...,c
i
,d
1
,...,d
i
) is a subset of Π(I,h,c
1
,...,c
i
,
d
1
,...,d
i
). Therefore, (i
,j
) ∈ N
ij
.Sinceπ(H
ij
)andπ(H
i
j
) intersect,
π(H
ij
)and
(s,t)∈N
ij
π(H
st
) intersect. This contradicts the condition (c).
Thus the proposition holds. From (a), (c) and the proposition, it is easy to
show that π is a permutation if and only if for any i,0 i r,anyj and
j
,1 j
<j t
i
, π(H
ij
)andπ(H
ij
) are disjoint. Using Lemma 8.3.8,
whenever h ∼
i
h
does not hold, Π (I, h, c
1
, ..., c
i
, d
1
, ..., d
i
)andΠ (I,
h
, c
1
, ..., c
i
, d
1
, ..., d
i
) are disjoint. From (c), it is easy to see that for
any i,0 i r,anyj and j
,1 j
<j t
i
, π(H
ij
)andπ(H
ij
)are
disjoint. Thus π is a permutation. From (b) and (c), it is easy to prove that
(c
1
,...,c
r
)istherank-spectrumofπ.Itimmediatelyfollows,using(a),that
π ∈ V (c
1
,...,c
r
,d
1
,...,d
r
).
Solutions π and π
of Problem P (a
1
,...,a
k
,b
1
,...,b
k
)aresaidtobe
equivalent, if rank-spectra of π and π
are the same, say (c
1
,...,c
r
), and
π(c
i
)=π
(c
i
)fori =1,..., r, π(H
ij
)=π
(H
ij
)fori =0,1,..., r and
j =1,..., t
i
. (In the definition of H
ij
,thevalueofd
i
is taken as π(c
i
),
i =1,..., r.) It is easy to verify that the equivalent relation is reflexive,
symmetric and transitive.
Corollary 8.3.2. If V (c
1
,...,c
r
; d
1
,...,d
r
) = ∅, then the number of so-
lutions in each equivalence class is
0ir,1jt
i
|H
ij
|!, and the equivalence
class containing π can be obtained by changing the restriction of π on H
ij
to
bijections from H
ij
to π(H
ij
) for i =0, 1, ..., r and j =1, ..., t
i
.
Corollary 8.3.3. Assume that 1 c
1
<c
2
< ··· <c
r
k and that
d
1
,...,d
r
∈{1,...,k} are distinct. Let I = {d
1
,...,d
r
}.Ifthereexist
i, j, 0 i<r, 1 j t
i
, such that |H
ij
| +
(i
,j
)∈N
ij
|H
i
j
| >
8.3 Linearly Independent Latin Arrays 343
|Π(I,h
ij
,c
1
,...,c
i
,d
1
,...,d
i
)|,whereh
ij
∈ H
ij
,thenV (c
1
,...,c
r
; d
1
,...,d
r
)
= ∅.
Noticing that H
ij
and Π(I,h
ij
,c
1
,...,c
i
,d
1
,...,d
i
) do not depend on
parameters c
i+2
,...,c
r
,d
i+1
,...,d
r
, Corollary 8.3.3 can be generalized to
the following.
Corollary 8.3.4. Let 0 i<r. Assume that 1 c
1
<c
2
< ···<c
i+1
k − r + i +1 and that d
1
,...,d
i
∈{1,...,k} are distinct. Let I = {d
1
, ...,
d
i
}.Ifthereexistsj, 1 j t
i
such that |H
ij
| +
(i
,j
)∈N
ij
|H
i
j
| >
|Π(I,h
ij
,c
1
,...,c
i
,d
1
,...,d
i
)|,whereh
ij
∈ H
ij
, then for any c
i+2
, ..., c
r
,
d
i+1
,..., d
r
, we have V (c
1
, ..., c
r
; d
1
,..., d
r
)=∅.
Theorem 8.3.6 and Corollaries 8.3.3 and 8.3.4 give criteria to decide
whether V (c
1
, ..., c
r
; d
1
, ..., d
r
) is empty and a method of enumerat-
ing its elements in nonempty case. The first step is computing a
c
j
⊕ b
d
j
,
j =1,..., r and deciding whether they are linear independent; in the case of
V (c
1
,...,c
r
; d
1
,...,d
r
) = ∅, they must be linearly independent. The second
step is, for each i from 1 to r in turn, choosing π(H
ij
), 1 j t
i
, so that the
condition (c) in Theorem 8.3.6 holds. In the case of V (c
1
,...,c
r
; d
1
,...,d
r
) =
∅, this process can go on, that is, the circumstances without enough elements
for choosing mentioned in Corollaries 8.3.3 and 8.3.4 can not happen. Point
out that t
r
=1andΠ(I, h, c
1
, ..., c
r
, d
1
, ..., d
r
)={1, ..., k}−I,so
π(H
r1
) is unique, i.e., π(H
r1
)={1, ..., k}−{π(i), i =1,..., c
r
}.Thethird
step is choosing π so that π(c
i
)=d
i
for i =1,..., r and that the restriction
of π on H
ij
is a surjection from H
ij
to π(H
ij
) (in fact, a bijection because of
|H
ij
| = |π(H
ij
)|)fori =0,1,..., r and j =1,..., t
i
.
Notice that in the sense of equivalence π is determined by π(H
ij
), i =0,1,
..., r, j =1,..., t
i
. From the method mentioned above we have the following.
Corollary 8.3.5. Assume that 0 c
1
<c
2
< ··· <c
r
k and that
d
1
,...,d
r
∈{1,...,k} are distinct. Let I = {d
1
, ..., d
r
}. For any i, j,
1 i r, 1 j t
i
,letq
ij
= |H
ij
| and
s
ij
= |Π(I,h,c
1
,...,c
i
,d
1
,...,d
i
)|−
(i
,j
)∈N
ij
q
i
j
,
where h is an arbitrary element in H
ij
.
(a) V (c
1
,...,c
r
; d
1
,...,d
r
) = ∅ if and only if a
c
1
⊕ b
d
1
, ..., a
c
r
⊕ b
d
r
are
linearly independent and (∀i)(∀j)[0 i r &1 j t
i
→ q
ij
s
ij
].
(b) For nonempty V (c
1
,...,c
r
; d
1
,...,d
r
), the number of its equivalence
classes is
0i<r,1jt
i
s
ij
q
ij
344 8. One Key Cryptosystems and Latin Arrays
and the number of its elements is
0i<r,1jt
i
s
ij
q
ij
· q
ij
!
· (k − c
r
)!.
Example 8.3.1. Let a
i
and b
i
be the i-th row of A and B, respectively, where
A =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1110
1000
0110
0100
1010
1100
1010
0110
0000
1110
0010
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,B=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0001
0011
0101
0110
1001
1010
0111
1011
1101
1110
1111
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
Find V (2, 6, 8, 9; 5, 11, 1, 9).
We first compute
C =
⎡
⎢
⎢
⎣
a
2
⊕ b
5
a
6
⊕ b
11
a
8
⊕ b
1
a
9
⊕ b
9
⎤
⎥
⎥
⎦
=
⎡
⎢
⎢
⎣
0001
0011
0111
1101
⎤
⎥
⎥
⎦
.
Let R
j
be the vector space spanned by the first j rows of C, j =1, 2, 3.
Let R
0
= {0} be the vector space of dimension 0. We use Π
ij
to denote the
set of all h ∈ I
such that a
k
⊕ b
h
∈ R
i
,whereI
= {1,...,11}\{5, 11, 1, 9},
k is an arbitrarily given element in H
ij
. We compute H
ij
and Π
ij
.
H
0
= H
01
= {1}, Π
01
= {10}.
H
1
= {3, 4, 5}, H
11
= {3}, H
12
= {4}, H
13
= {5}, Π
11
= {4, 7}, Π
12
=
{3}, Π
13
= {6, 8}.
H
2
= H
21
= {7}, Π
21
= {6, 8}.
H
3
= ∅.
H
4
= H
41
= {10, 11}, Π
01
= I
.
We define the permutation π on {1,...,11}.
First define π(2) = 5, π(6) = 11, π(8) = 1, π(9) = 9.
Then for points with |H
ij
| = |Π
ij
|, define π(1) = 10, π(4) = 3. Similarly,
define π({5, 7})={6, 8}.
Now define π(3) ∈{4, 7}. In the case where π(3) = 4, define π({10, 11})=
{2, 7}. In the case where π(3) = 7, define π({10, 11})={2, 4}.
To sum up, the solutions of π(1),...,π(11) are: