Cryptography Reference
In-Depth Information
where 1
≤
j
≤
φ
(
q
−
1)
/n
,
M
j
is the generator matrix of the sequence and
2. Clearly,
M
j
b
0
is the initial state of the LFSR.
0
≤
k
≤
q
−
2
T
=
T
0
,
where
T
0
is a subset of
T
. We denote these two functions by
f
1
and
f
2
.Then
f
1
differs from
f
2
only when
x
=0and
f
1
=
f
2
+(
x
1
+1)(
x
2
+1)
Let
T
=
F
−{
0
}
. Clearly, there are exactly two
f
∈
B
n
such that 1
f
∩
(
x
n
+1). Given
any LSFR, the keystream generated by using
f
1
or
f
2
as the filter function is the
same. Therefore,
f
1
and
f
2
can be viewed as the same function and we consider
the set
···
B
n
=
B
n
/
{
0
,
(
x
1
+1)(
x
2
+1)
···
(
x
n
+1)
}
.
B
n
can be represented by its support set in the form
Then any
f
∈
M
i
1
j
b
0
,M
i
2
j
b
0
,...,M
i
w
j
1
f
=
{
b
0
}
,
where
M
j
is the generator matrix of the register and 0
≤
i
1
<i
2
< ... < i
w
≤
q
−
2.
4 Equivalence of Boolean Functions
Rønjom and Cid put forward nonlinear equivalence of Boolean functions in [17],
which can be defined as follows.
Definition 1.
Let
z
be a keystream generated by a filter generator where the
LFSR has primitive feedback polynomial
g
1
(
x
)
and the filter function is
f
1
.
f
2
∈
B
n
f
2
) if there exists an LFSR which filtered
by
f
2
will generate the same keystream. Particularly, if the two LFSRs have
the same generator polynomial, we say that
f
1
and
f
2
are linear equivalent and
denote it by
f
1
∼
L
f
2
.Otherwise,
f
1
and
f
2
are said to be nonlinear equivalent
which is denoted by
f
1
∼
N
f
2
.
Example 1.
Let the generator polynomial be
m
1
(
x
)=
x
5
+
x
2
+ 1, the initial
statebe(1
,
0
,
0
,
0
,
0)
T
, and the filter function be
f
1
(
x
)=
x
1
x
3
+
x
1
x
4
+
x
2
x
4
+
x
3
x
4
+
x
4
x
5
+
x
5
.Thenafullperiodofkeystreamis
is said to be equivalent to
f
1
(
f
1
∼
(0100111110111000101011010000110)
.
Let the generator polynomial of another LFSR be
m
2
(
x
)=
x
5
+
x
4
+
x
3
+
x
2
+1,
theinitialstatebe(1
,
0
,
0
,
0
,
0)
T
, and the filter function be
f
2
(
x
)=
x
3
+
x
4
+
x
5
.
Then the keystream generated will be the same as the above one. Therefore,
f
1
∼
N
f
2
. Clearly, deg(
f
1
)=2,
AI
(
f
1
)=2and
nl
(
f
1
) = 12, while
f
2
is a linear
function.
B
n
,let
Theorem 1.
Given an LFSR and the filter function
f
∈
|
1
f
|
=
w
,where
B
n
w
1
≤
w<q
−
1
. Then the number of
g
∈
such that
g
∼
L
f
is
q
−
m
,where
m
w
is a positive divisor of
w
and
(
w,q−
1)
|
m
.
Search WWH ::
Custom Search