Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
8.2 Latin Arrays 325
195 : 2
4
, 4, 6, 4; ((1), (12)(34), (1), (13)(24));
((234), (234), (34), (34)); ((4321), (4321)).
196 : 1, 8, 2, 4; ((1), (34), (1), (1423)); ((34), (1)); ((1423), (1)).
197 : 1, 4, 2, 2; ((1), (1234)); ((34), (1)); ((12), (12)(34)).
198 : 1, 2, 1
, 4; ((1), (13)(24)); e;((13)(24), (1), (14)(23), (12)(34)).
199 : 1, 2, 2, 4; ((1), (34)); ((24), (12)); ((4321), (1)).
200 : 1, 1, 2, 3; e;((34), (34)); ((431), (234)).
201 : 1, 4, 6, 4; ((1), (12)(34), (1), (14)(23));
((34), (23), (234), (234)
); ((4321), (12)).
Thus we have
n
1
=3
5
2
17
,n
89
=3
5
2
8
,n
2
=3
4
2
17
,n
3
= n
4
=3
4
2
12
,n
6
= n
7
=3
4
2
9
,
n
13
=3
4
2
8
,n
i
=3
4
2
7
,i=10, 16, 21, 40,n
46
=3
4
2
6
,n
52
=3
4
2
5
,
n
12
= n
33
=3
3
2
9
,n
22
= n
43
=3
3
2
6
,n
39
=3
3
2
5
,
n
5
=3
2
2
14
,n
37
=3
2
2
12
,n
8
=3
2
2
10
,n
14
= n
34
=3
2
2
9
,
n
55
= n
74
=3
2
2
8
,n
i
=3
2
2
7
,i=19, 20, 26, 90, 91,
n
i
=3
2
2
6
,i=17, 18, 23, 47, 49, 61,n
i
=3
2
2
5
,i=63, 124,
n
i
=3
2
2
4
,i=38, 60, 123, 139,n
181
=3
2
2
3
,
n
190
=3
1
2
13
,n
15
=3
1
2
12
,n
36
=3
1
2
10
,n
i
=3
1
2
9
,i=35, 87, 195,
n
27
=3
1
2
8
,n
i
=3
1
2
7
,i=28, 53, 165,
n
i
=3
1
2
6
,i=24, 44, 45, 54, 62, 65, 68, 70, 100, 111, 128,
n
i
=3
1
2
5
,i=25, 41, 42, 48, 50, 51, 66, 67, 82, 99, 110, 138, 186, 201,
n
i
=3
1
2
4
,i=57, 58, 64, 151, 179, 184, 192,
n
i
=3
1
2
3
,i=56, 59, 108, 109, 191,n
174
=3
1
2
2
,n
200
=3
1
2
1
,
n
9
=2
14
,n
11
= n
83
=2
12
,n
30
=2
11
,n
i
=2
9
,i=29, 96, 171,
n
i
=2
8
,i=32, 72, 73, 77, 88, 98, 106, 158, 160, 169, 182,
n
i
=2
7
,i=31, 75, 92, 93, 94, 95, 97, 101, 107, 134, 143, 149, 164, 167, 183,
n
i
=2
6
,i=69, 85, 103, 105, 121, 126, 140, 194, 196,
n
i
=2
5
,i=71, 76, 79, 80, 84, 86, 102, 104, 118, 119, 125, 127, 137, 144, 147,
150, 159, 162, 166, 168, 170, 172, 178,
n
i
=2
4
,i=78, 81, 112, 113, 115, 116, 117, 122, 131, 132, 133, 136, 141, 142,
145, 152, 154, 161, 163, 175, 188, 193, 197, 199,
n
i
=2
3
,i= 114, 120, 129, 130, 148, 153, 155, 156, 157, 176, 177, 185, 187, 198,
n
i
=2
2
,i= 135, 146, 180, 189,n
173
=2.
326 8. One Key Cryptosystems and Latin Arrays
Since the number of elements in the isotopy class containing Ai44 is 4!4!16!/n
i
,
noticing 4!4!16! = 3
2
2
6
16! = 3
8
2
18
7007000, we have
U(4, 4, 1) =
201
i=196
4!4!16!/n
i
= 16!3
2
2
6
(1/2
6
+1/2
4
+1/2
3
+1/2
4
+1/(3 · 2) + 1/(3 · 2
5
))
= 16!(3
2
+3
2
2
2
+3
2
2
3
+3
2
2
2
+3· 2
5
+3· 2)
= 16!255 = 5335311421440000,
U(4, 4) =
201
i=1
4!4!16!/n
i
= 11460887640 · 7007000 = 80306439693480000.
We point out that U (4, 4, 1) can also be obtained from Theorem 8.2.2 (b)
and Theorem 8.2.11, that is, U (4, 4, 1) = U (4, 2, 1)(4! − 4 · 2)!/(4 · 2)! =
10281600 · 16!/8! = 5335311421440000.
Enumerating high order Latin arrays is not easy. Among others, sev-
eral useful permutational families corresponding to (2
r
, 2
r
)-Latin arrays are
g
w
1
w
2
(x)=ϕ(w
1
−(w
2
⊕(w
1
−ϕ(x)))), g
w
1
w
2
(x)=ϕ(w
1
⊕(w
2
−(w
1
⊕ϕ(x)))),
g
w
1
w
2
(x)=w
1
⊕ ϕ(w
2
− ϕ(w
1
⊕ x)), g
w
1
w
2
(x)=w
1
− ϕ(w
2
⊕ ϕ(w
1
− x)),
where ϕ is a bijection. In the case where ϕ is an involution (i.e., ϕ
−1
= ϕ),
such g
w
’s are involutions.
We return to giving an application of (4, 4)-Latin array to cryptography.
It is known that the following binary steam cipher is insecure: a plaintext
x
0
...x
l−1
is encrypted into a ciphertext y
0
...y
l−1
by
y
i
= x
i
⊕ w
i
,i=0,...,l− 1,
where the key string w
0
...w
l−1
is generated by a binary linear shift register.
In fact, this cipher can not resist the plain-chosen attack. Assume that the
key string satisfies the equation
w
i
= a
1
w
i−1
⊕···⊕a
n
w
i−n
,i=0,...,l− 1. (8.1)
The key of the cipher is a
1
,...,a
n
,w
−n
,...,w
−1
.Ifonecanobtainasegment
of plaintext of length 2n,sayx
j
...x
j+2n−1
,thenw
j
...w
j+2n−1
may be
evaluated by
w
i
= x
i
⊕ y
i
,i= j,...,j+2n − 1;
therefore, by solving the equation
w
i
= a
1
w
i−1
⊕···⊕a
n
w
i−n
,i= j + n,...,j+2n − 1,
the coefficients a
1
,...,a
n
can be easily found. By (8.1), the key bits w
j+2n
,...,
w
l−1
can be easily computed from w
j+n
...w
j+2n−1
, and the key bits w
0
,...,
8.3 Linearly Independent Latin Arrays 327
w
j−1
can be easily computed from w
j
...w
j+n−1
. If we describe this cipher
in the form in Fig.8.1.2, then M
a
is a binary linear shift register and the
permutational family {g
w
,w =0, 1} is {w ⊕ x, w =0, 1} which corresponds
to a (2,2)-Latin array. The permutational family is too small! To improve this
situation, one may adopt a more complex shift register or a permutational
family corresponding to a higher order Latin array. For the latter, we give an
example using (4,4)-Latin array which can resist the plain-chosen attack.
Example 8.2.1. A maximal linear shift register sequence plus (4,4)-Latin ar-
ray cipher.
In Fig.8.1.2, let X and Y be GF (2
2
)={00, 01, 10, 11}.LetM
a
be an
n-order maximal linear shift register sequence generator (i.e., a linear shift
register over GF(2) with characteristic polynomial period 2
n
− 1) with 4 bits
output. And the permutation g
w
on GF (2
2
) corresponds to a (4,4)-Latin
array A in such a way: for any w = w
3
w
2
w
1
w
0
∈ GF (2
4
), if the element
of A at column (w
3
2
3
+ w
2
2
2
+ w
1
2+w
0
)+1 and row (x
1
2+x
0
)+1 is
(y
1
2+y
0
)+1, then g
w
(x
1
x
0
)=y
1
y
0
. The key consists of g
w
, M
a
and its
initial state; the amount of keys is the product of the number of (4,4)-Latin
arrays, the number of the primitive polynomials of degree n over GF (2) and
2
n
− 1. An analysis in [104] shows that this cipher can resist the plain-chosen
attack.
If we use Latin arrays with larger order and if the family of permutations
corresponding to the Latin array satisfies the following condition: for any x
and y,componentsofw with g
w
(x)=y can not satisfy any linear equation,
where w is represented as a vector of dimension log
2
nk over GF (2), then
for the counterpart of the above cipher in the case of (n, k)-Latin array, the
characteristic polynomial of M
a
may be excluded from the key, in other words,
the structure of M
a
can be fixed and the key consists of the Latin array and
the initial state of M
a
. In the following section, we will give the definition
of such a kind Latin arrays, so-called Latin arrays with independence degree
1, and discuss their generation problem by means of invertible Boolean
vector functions with independence degree 1.
8.3 Linearly Independent Latin Arrays
8.3.1 Latin Arrays of Invertible Functions
Let n and k be two positive integers. Denote r = log
2
nk and N =
{1,...,n}.LetA be an (n, k)-Latin array. The vector [u
1
,...,u
r
]overGF (2)
is called the column label of column (u
1
2
r−1
+ u
2
2
r−2
+ ···+ u
r
)+1 of A.Let
x, y ∈ N . If components of column labels of columns of A in which the ele-
ments at row x are y satisfy some nonzero polynomial in r variables of degree
328 8. One Key Cryptosystems and Latin Arrays
c over GF (2), A is said to be c-dependent with respect to (x, y), other-
wise A is said to be c-independent with respect to (x, y). If A is c-dependent
with respect to (x, y) for any x, y ∈ N, A is said to be c-dependent.IfA
is c-independent with respect to (x, y) for any x, y ∈ N , A is said to be
c-independent.IfA is c-dependent and not (c − 1)-dependent, c is called the
dependent degree of A, denoted by c
A
.IfA is c-independent and not (c +1)-
independent, c is called the independent degree of A, denoted by I
A
. Clearly,
c
A
I
A
+1.
Proposition 8.3.1. Let A be an (n, k)-Latin array and r = log
2
nk.Then
we have
c
A
min c [1+
r
1
+ ···+
r
c
>k].
Proof.Letc be a positive integer with 1 +
r
1
+ ···+
r
c
>k. For any
x, y ∈ N, let the element at row x column j
h
of A be y, h =1,...,k. Denote
the column label of column j
h
by [w
h1
,...,w
hr
]. Let α
h
be the row vector
[1,w
h1
,...,w
hr
,w
h1
w
h2
,...,w
h,r−1
w
hr
,
......,w
h1
...w
hc
,...,w
h,r−c+1
...w
hr
],
for h =1,...,k.LetC be a matrix of which the h-th row is α
h
, h =1,...,k.
Since the number of C’scolumnsisgreaterthanthenumberofC’s rows,
columns of C are linearly dependent. Thus there is a nonzero column vector
γ such that Cγ = 0. It follows that A is c-dependent with respect to (x, y).
Thus A is c-dependent. Therefore, c
A
c.
We use R
r
2
to denote the row vector space of dimension r over GF (2). For
any positive integer m,letf
m
be a one-to-one mapping from R
m
2
onto {0,
1, ...,2
m
− 1} defined by f
m
(x
1
,...,x
m
)=x
1
2
m−1
+ x
2
2
m−2
+ ···+ x
m
.
Let ϕ
1
and ϕ
2
be two permutations on R
r
2
,andϕ a transformation on R
r
2
.
Denote Φ =(ϕ
1
,ϕ,ϕ
2
). Construct a 2
r
× 2
2r
matrix A
Φ
over {1,...,2
r
} as
follows: for any x, w
1
,w
2
∈ R
r
2
, the element at row f
r
(x)+1 and column
f
2r
(w
1
,w
2
)+1 is f
r
(ϕ
1
(w
1
) ⊕ ϕ(ϕ
2
(w
2
) ⊕ x)) + 1, where ⊕ stands for the
vector addition over GF (2).
Proposition 8.3.2. A
Φ
is a (2
r
, 2
r
)-Latin array if and only if ϕ is a per-
mutation.
Proof. Whenever ϕ is a permutation, it is easy to prove that each column
of A
Φ
is a permutation on N and that for any x, y ∈ N,anyw
2
∈ R
r
2
there
exists uniquely w
1
∈ R
r
2
such that the element at row x column f(w
1
,w
2
)+1
of A
Φ
is y.ThusA
Φ
is a (2
r
, 2
r
)-Latin array.
Whenever ϕ is not a permutation, it is easy to prove that each column of
A
Φ
is not a permutation on N.ThusA
Φ
is not a (2
r
, 2
r
)-Latin array.
8.3 Linearly Independent Latin Arrays 329
Whenever ϕ is a permutation, A
Φ
is called the (2
r
, 2
r
)-Latin array of Φ.
Let ϕ be a transformation on R
r
2
with component functions ϕ
1
,...,ϕ
r
.
For any nonnegative integer c, if there is a nonzero polynomial h of degree
c in 2r variables over GF (2) such that
h(x
1
,...,x
r
,ϕ
1
(x
1
,...,x
r
),...,ϕ
r
(x
1
,...,x
r
)) = 0,x
1
,...,x
r
∈ GF (2),
ϕ is said to be c-dependent,andh is called a dependent polynomial of ϕ.If
ϕ is not c-dependent, ϕ is said to be c-independent.Ifϕ is c-dependent and
(c − 1)-independent, c is called the dependent degree of ϕ, denoted by c
ϕ
,and
c − 1 is called the independent degree of ϕ, denoted by I
ϕ
. In the case where
ϕ is 1-dependent, ϕ is said to be linearly dependent. In the case where ϕ is
1-independent, ϕ is said to be linearly independent.
An affine transformation on R
r
2
means a mapping xC ⊕ b,whereC is an
r × r matrix over GF (2), b is a row vector of dimension r over GF (2).
Lemma 8.3.1. Let ϕ be a transformation on R
r
2
,andp and q two invertible
affine transformations on R
r
2
.Letϕ
(x)=p(ϕ(q(x))), x ∈ R
r
2
. Then we have
c
ϕ
= c
ϕ
and I
ϕ
= I
ϕ
.
Proof. Suppose that h is a dependent polynomial of ϕ.Sincep and q are
invertible affine transformations, p
−1
and q
−1
areinvertibleaffinetransfor-
mations. Let
h
(x, y)=h(q(x),p
−1
(y)),x,y∈ R
r
2
.
Since h is a dependent polynomial of ϕ and q is invertible, it is easy to verify
that h
is a dependent polynomial of ϕ
.Sinceq and p
−1
are affine transfor-
mations, the degree of h
is not greater than the degree of h. Therefore, we
have c
ϕ
c
ϕ
.Sincep
−1
and q
−1
are invertible affine transformations and
ϕ(x)=p
−1
(ϕ
(q
−1
(x))), from symmetry, we have c
ϕ
c
ϕ
.Thusc
ϕ
= c
ϕ
.
From I
ϕ
= c
ϕ
− 1andI
ϕ
= c
ϕ
− 1, we have I
ϕ
= I
ϕ
.
Theorem 8.3.1. Let ϕ be a transformation on R
r
2
,andϕ
1
and ϕ
2
two
invertible affine transformations on R
r
2
.LetΦ =(ϕ
1
,ϕ,ϕ
2
),andA
Φ
be the
(2
r
, 2
r
)-Latin array of Φ. Then we have c
A
Φ
= c
ϕ
, I
A
Φ
= I
ϕ
,andc
A
Φ
=
I
A
Φ
+1.
Proof. For any x, y, w
1
,w
2
∈ R
r
2
, from the definition of A
Φ
, the element
of A
Φ
at row f
r
(x)+1 column f
2r
(w
1
,w
2
)+1 is f
r
(y) + 1 if and only if
y = ϕ
1
(w
1
) ⊕ ϕ(ϕ
2
(w
2
) ⊕ x), if and only if w
1
= ϕ
xy
(w
2
), where ϕ
xy
(u)=
p
y
(ϕ(q
x
(u))), p
y
(u)=ϕ
−1
1
(u ⊕ y), q
x
(u)=ϕ
2
(u) ⊕ x, u ∈ R
r
2
. It follows
that A
Φ
is c
ϕ
xy
-dependent with respect to (f
r
(x)+1,f
r
(y) + 1) and that A
Φ
is I
ϕ
xy
-independent with respect to (f
r
(x)+1,f
r
(y)+1).Sinceϕ
1
and ϕ
2
are invertible affine transformations on R
r
2
, p
y
and q
x
areinvertibleaffine
330 8. One Key Cryptosystems and Latin Arrays
transformations on R
r
2
. From Lemma 8.3.1, we have c
ϕ
xy
= c
ϕ
.ThusI
ϕ
xy
=
I
ϕ
. Therefore, A
Φ
is c
ϕ
-dependent and I
ϕ
-independent. Since c
ϕ
= I
ϕ
+1,
we have c
A
Φ
= c
ϕ
, I
A
Φ
= I
ϕ
and c
A
Φ
= I
A
Φ
+1.
Denote c(r)=minc [1+
2r
1
+ ···+
2r
c
> 2
r
]. We have the following.
Proposition 8.3.3. For any transformation ϕ on R
r
2
, we have c
ϕ
c(r).
Proof. We give a proof analogous to Proposition 8.3.1. For any x ∈ R
r
2
,
let α
x
be the row vector
[1,w
1
,...,w
2r
,w
1
w
2
,...,w
2r−1
w
2r
,...,w
1
...w
c(r)
,...,w
2r−c(r)+1
...w
2r
],
where [ x, ϕ(x)]=[w
1
,...,w
2r
], w
1
,...,w
2r
∈ GF (2). Let C be a matrix
of which row f
r
(x)+1 is α
x
, x ∈ R
r
2
.SincethenumberofC’s columns is
greater than the number of C’s rows, columns of C are linearly dependent.
Thus there is a nonzero column vector γ such that Cγ = 0. It follows that ϕ
is c(r)-dependent. Therefore, c
ϕ
c(r).
Theorem 8.3.2. Let r 3. Then there is a permutation ϕ on R
r
2
such that
c
ϕ
2.
Proof. Denote t
i
= x
1
...x
i−1
x
i+1
...x
r
, i =1,...,r. Define a function ϕ
on R
r
2
so that ϕ(x
1
,...,x
r
)=[y
1
,...,y
r
], where
y
1
= x
1
⊕ t
1
⊕ t
2
,
y
2
= x
2
⊕ t
2
⊕ t
3
,
........., (8.2)
y
r−1
= x
r−1
⊕ t
r−1
⊕ t
r
,
y
r
= x
r
⊕ t
r
.
It is easy to verify that if the weight (number of 1) of [x
1
,...,x
r
] is less than
r −1thenϕ(x
1
,...,x
r
)=[x
1
,...,x
r
], and that on the points of weights r −1
and r, ϕ is the cyclic permutation
(11 ...110, 11 ...101,...,101 ...11, 011 ... 11, 111 ...11).
Therefore, ϕ is invertible. We prove that ϕ is linearly independent. Suppose
to the contrary that ϕ is linearly dependent. Then there exist c
0
, ..., c
r
,
d
1
,..., d
r
∈ GF (2)suchthatatleastoneofthemisnonzeroand
c
0
⊕ c
1
x
1
⊕···⊕c
r
x
r
⊕ d
1
y
1
⊕···⊕d
r
y
r
=0
holds for any x
1
,...,x
r
in GF (2), where y
1
,...,y
r
are defined by (8.2). No-
tice that for the zero Boolean function all the coefficients of its polynomial
8.3 Linearly Independent Latin Arrays 331
expression are zero. From the coefficients of t
1
,wehaved
1
=0.Fromthe
coefficients of t
2
,wehaved
2
= 0. And so forth, from the coefficients of t
r
,we
have d
r
= 0. It follows that c
0
= ···= c
r
= 0. This is a contradiction. So ϕ
is linearly independent.
Corollary 8.3.1. For any r, 1 r 6, there is a permutation ϕ on R
r
2
such that c
ϕ
= c(r).
Proof. Whenever r =1, 2, we have c(r) = 1. Since any permutation ϕ on
R
r
2
is 0-independent, from Proposition 8.3.3, c
ϕ
= c(r)holds.
Whenever r =3,...,6, we have c(r) = 2. From Theorem 8.3.2, there is
a permutation ϕ on R
r
2
such that c
ϕ
2. From Proposition 8.3.3, we have
c
ϕ
c(r) = 2. Therefore, c
ϕ
=2holds.
8.3.2 Generation of Linearly Independent Permutations
Truth Table
Given r>0, let ϕ be a transformation on R
r
2
.LetW
i
be a
r
i
× r matrix
over GF (2) of which rows consist of all difference vectors of dimension r with
weight i, i =0,1,..., r.WeuseI
t
to denote the column vector of dimension
r
t
of which each component is 1. For any i,0 i r, define a
r
i
×r matrix
U
i
over GF (2) of which row j is the value of ϕ at row j of W
i
,1 j
r
i
.
Define a 2
r
× (1 + 2r)matrix
Φ =
⎡
⎢
⎢
⎢
⎣
I
0
W
0
U
0
I
1
W
1
U
1
.
.
.
.
.
.
.
.
.
I
r
W
r
U
r
⎤
⎥
⎥
⎥
⎦
.
In this section, we refer to Φ as the truth table of ϕ, and denote the submatrix
of the last r columns of Φ by U
ϕ
. Notice that W
0
= 0. For convenience, we
arrange rows of W
1
so that it is the identity matrix.
From the definitions, we have the following.
Proposition 8.3.4. (a) c
ϕ
> 1 if and only if columns of Φ are linearly
independent.
(b) ϕ is invertible if and only if rows of U
ϕ
are distinct.
By E
t
denote the
r
t
×
r
t
identity matrix. Let the 2
r
× 2
r
matrix
332 8. One Key Cryptosystems and Latin Arrays
P =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
I
0
W
0
I
1
W
1
I
2
W
2
E
2
0 W
3
0 E
3
I
4
W
4
00E
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
I
r−1
W
r−1
000... E
r−1
I
r
W
r
000... 0 E
r
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
where I
j
= I
j
if j is even, I
j
= 0 otherwise. It is easy to verify that P is
nonsingular and
P
−1
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
I
0
W
0
I
1
W
1
I
2
W
2
E
2
I
3
W
3
0 E
3
I
4
W
4
00E
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
I
r−1
W
r−1
000... E
r−1
I
r
W
r
000... 0 E
r
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
Noticing that the first 1 + r columns of P
−1
and of Φ arethesame,wehave
the following.
Lemma 8.3.2. PΦ is in the form
PΦ =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
I
0
0 V
0
0 E
1
V
1
00 V
2
.
.
.
.
.
.
.
.
.
00 V
r
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
where V
0
= U
0
, V
i
is a
r
i
× r matrix, i =1, ..., r.
Let
V
ϕ
=
⎡
⎢
⎣
V
0
.
.
.
V
r
⎤
⎥
⎦
,V
ϕ−
=
⎡
⎢
⎣
V
2
.
.
.
V
r
⎤
⎥
⎦
.
Since P is nonsingular, columns of Φ are linearly independent if and only if
columns of PΦ are linearly independent. Using Lemma 8.3.2, columns of PΦ
are linearly independent if and only if columns of V
ϕ−
are linearly indepen-
dent. From Proposition 8.3.4 (a), we obtain the following proposition.
8.3 Linearly Independent Latin Arrays 333
Proposition 8.3.5. c
ϕ
> 1 if and only if columns of V
ϕ−
are linearly in-
dependent.
Lemma 8.3.3. For any i, 1 i r,andanyr × r permutation matrix Q
over GF (2), there exists uniquely a
r
i
×
r
i
permutation matrix P
iQ
such
that P
iQ
W
i
= W
i
Q.
Proof.NoticethatrowsofW
i
consist of all row vectors of dimension r
with weight i. Since arranging columns of W
i
keeps the weight of each row
and sameness between rows unchanged, rows of W
i
Q consist of all row vectors
of dimension r with weight i. Therefore, there exists uniquely a permutation
matrix P
iQ
such that P
iQ
W
i
= W
i
Q.
For any r × r permutation matrix Q over GF (2), let
D
Q
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
I
0
Q
P
2Q
.
.
.
P
rQ
⎤
⎥
⎥
⎥
⎥
⎥
⎦
.
Let G
r
= {D
Q
| Q is an r×r permutation matrix over GF (2)}. Clearly, in the
case where Q is the identity matrix, P
iQ
is the identity matrix. In the case of
P
iQ
W
i
= W
i
Q,wehaveW
i
Q
−1
= P
−1
iQ
(P
iQ
W
i
)Q
−1
= P
−1
iQ
(W
i
Q)Q
−1
=
P
−1
iQ
W
i
; therefore, P
iQ
−1
= P
−1
iQ
. In the case of P
iQ
W
i
= W
i
Q
and
P
iQ
W
i
= W
i
Q,wehaveP
iQ
P
iQ
W
i
= P
iQ
W
i
Q
= W
i
QQ
; therefore,
P
iQ
P
iQ
= P
i(QQ
)
.ThusG
r
is a group.
Let G
r
= {D
Q
,δ,C|Q is an r × r permutation matrix over GF (2), δ
is a row vector of dimension r over GF (2), C is an r × r nonsingular matrix
over GF (2) }.
For any 2
r
× r matrix V , partition it into blocks
V =
⎡
⎢
⎢
⎢
⎣
V
0
V
1
.
.
.
V
r
⎤
⎥
⎥
⎥
⎦
,
where V
i
has
r
i
rows, i =0, 1,...,r. For any D
Q
,δ,C in G
r
, define
V
D
Q
,δ,C
= D
Q
(V ⊕
⎡
⎢
⎢
⎢
⎣
δ
0
.
.
.
0
⎤
⎥
⎥
⎥
⎦
)C = D
Q
VC⊕
⎡
⎢
⎢
⎢
⎣
δC
0
.
.
.
0
⎤
⎥
⎥
⎥
⎦
.
334 8. One Key Cryptosystems and Latin Arrays
For any 2
r
× r matrices V and V
over GF (2), V and V
are said to be
equivalent if there is D
Q
,δ,C in G
r
such that V
D
Q
,δ,C
= V
.Itiseasyto
verify that the equivalence relation is reflexive, symmetric and transitive.
Lemma 8.3.4. Assume that V
D
Q
,δ,C
= V
. Then we have
P
−1
V
= D
Q
(P
−1
V )C ⊕
⎡
⎢
⎢
⎢
⎣
δC
δC
.
.
.
δC
⎤
⎥
⎥
⎥
⎦
.
Proof.SinceP
iQ
is a permutation matrix, we have P
iQ
I
i
= I
i
.Using
P
iQ
W
i
= W
i
Q, it follows that
P
−1
D
Q
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
I
0
I
1
Q
I
2
W
2
QP
2Q
.
.
.
.
.
.
.
.
.
.
.
.
I
r
W
r
Q 0 ... P
rQ
⎤
⎥
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
I
0
I
1
Q
I
2
P
2Q
W
2
P
2Q
.
.
.
.
.
.
.
.
.
.
.
.
I
r
P
rQ
W
r
0 ... P
rQ
⎤
⎥
⎥
⎥
⎥
⎥
⎦
= D
Q
P
−1
.
Since V
= V
D
Q
,δ,C
,wehave
V
= D
Q
VC⊕
⎡
⎢
⎢
⎢
⎣
δC
0
.
.
.
0
⎤
⎥
⎥
⎥
⎦
.
Therefore,
P
−1
V
= P
−1
D
Q
VC⊕ P
−1
⎡
⎢
⎢
⎢
⎣
δC
0
.
.
.
0
⎤
⎥
⎥
⎥
⎦
= D
Q
(P
−1
V )C ⊕
⎡
⎢
⎢
⎢
⎣
δC
δC
.
.
.
δC
⎤
⎥
⎥
⎥
⎦
.
For any 2
r
× r matrices V and V
, denote the submatrices of V and of V
obtained by deleting their first 1 + r rows by V
−
and V
−
, respectively.