Information Technology Reference
In-Depth Information
2
n
-Periodic Binary Sequences with Fixed
k
=2or3
-Error Linear Complexity for
k
Ramakanth Kavuluru
Department of Computer Science, University of Kentucky,
Lexington, KY 40506, USA
ramakanth.kavuluru@uky.edu
Abstract.
The linear complexity of sequences is an important mea-
sure to gauge the cryptographic strength of key streams used in stream
ciphers. The instability of linear complexity caused by changing a few
symbols of sequences can be measured using
k
-error linear complexity. In
their SETA 2006 paper, Fu, Niederreiter, and Su [3] studied linear com-
plexity and 1-error linear complexity of 2
n
-periodic binary sequences to
characterize such sequences with fixed 1-error linear complexity. In this
paper we study the linear complexity and the
k
-error linear complexity of
2
n
-periodic binary sequences in a more general setting using a combina-
tion of algebraic, combinatorial, and algorithmic methods. This approach
allows us to characterize 2
n
-periodic binary sequences with fixed 2-error
or 3-error linear complexity
L
, when the Hamming weight of the binary
representation of 2
n
−
L
is
w
H
(2
n
−
L
)
= 2. Using this characterization
we obtain the counting function for the number of 2
n
-periodic binary
sequences with fixed
k
-error linear complexity
L
for
k
=2and3when
w
H
(2
n
−
L
)
=2.
Keywords:
Periodic
sequence,
linear
complexity,
k
-error
linear
complexity.
1
Introduction
The linear complexity of a sequence is the length of the shortest linear feedback
shift register (LFSR) that can generate the sequence. The LFSR that generates a
given sequence can be determined using the Berlekamp-Massey algorithm using
only the first 2
L
elements of the sequence, where
L
is the linear complexity
of the sequence. Hence for cryptographic purposes sequences with high linear
complexity are essential as an adversary would then need large initial segments
of the sequences to recover the LFSRs that generate them using the Berlekamp-
Massey algorithm.
