Information Technology Reference
In-Depth Information
A system is insecure if all but a few symbols of the key stream can be ex-
tracted. Hence for a cryptographically strong sequence, the linear complexity
should not decrease drastically if a few symbols are changed. If it did, an at-
tacker could modify the known prefix of the key stream and try to decrypt the
result using the Berlekamp-Massey algorithm. If the resulting sequence differed
from the actual key stream by only a few symbols, the attacker could extract
most of the message. This observation gives rise to
k
-error linear complexity of se-
quences introduced in [8] based on the earlier concepts of sphere complexity and
weight complexity, see [2]. The
k
-error linear complexity of a periodic sequence
is the smallest linear complexity achieved by making
k
or fewer changes per pe-
riod. Besides having large linear complexity, cryptographically strong sequences
should, thus, also have large
k
-error linear complexity at least for small
k
.
Let
S
=(
s
0
,s
1
,
,s
T−
1
)
∞
be a periodic binary sequence with period
T
.We
associate the polynomial
S
(
x
)=
s
0
+
s
1
x
+
···
+
s
T−
1
x
T−
1
and the correspond-
···
ing
T
-tuple
S
(
T
)
=(
s
0
,s
1
,
,s
T−
1
)to
S
. The relationship between the linear
complexity, denoted
L
(
S
), of
S
and the associated polynomial
S
(
x
)isgivenby
···
deg(gcd(
x
T
L
(
S
)=
T
−
−
1
,
S
(
x
)))
,
(1)
see e.g. [1], Lemma 8.2.1. Let
w
H
(
S
) denote the Hamming weight of the
T
-tuple
S
(
T
)
.For0
≤
k
≤
T
,the
k
-error linear complexity of
S
, denoted
L
k
(
S
), is
given by
L
k
(
S
)=min
E
L
(
S
+
E
)
,
where the minimum is over all
T
-periodic binary sequences
E
with
w
H
(
E
)
k
.
Since we consider only 2
n
-periodic sequences, we use
T
=2
n
and the observation
≤
1=
x
2
n
1)
2
n
x
T
−
−
1=(
x
−
(2)
for the rest of the paper.
Let
merr
(
S
) denote the minimum value
k
such that the
k
-error linear com-
plexity of a 2
n
-periodic sequence
S
is strictly less than its linear complexity.
That is
.
Kurosawa et al. [5] derived the formula for the exact value of
merr
(
S
).
merr
(
S
)=min
{
k
:
L
k
(
S
)
<L
(
S
)
}
Lemma 1.
For any nonzero
2
n
-periodic sequence
S
, we have
merr
(
S
)=2
w
H
(2
n
−L
(
S
))
,
2
n
where
w
H
(
j
)
,
0
≤
j
≤
−
1
, denotes the Hamming weight of the binary repre-
sentation of
j
.
The counting function of a sequence complexity measure gives the number of
sequences with a given complexity measure value. Rueppel [7] determined the
counting function of linear complexity for 2
n
-periodic binary sequences. Using
equations (1) and (2) it is straightforward to characterize the 2
n
-periodic se-
quences with fixed linear complexity.
