Loading web-font TeX/Math/Italic
New Results on Periodic Sequences With Large --Error Linear Complexity | IEEE Journals & Magazine | IEEE Xplore

New Results on Periodic Sequences With Large k-Error Linear Complexity


Abstract:

Niederreiter showed that there is a class of periodic sequences which possess large linear complexity and large k-error linear complexity simultaneously. This result disp...Show More

Abstract:

Niederreiter showed that there is a class of periodic sequences which possess large linear complexity and large k-error linear complexity simultaneously. This result disproved the conjecture that there exists a trade-off between the linear complexity and the k-error linear complexity of a periodic sequence by Ding By considering the orders of the divisors of xN-1 over \BBF q, we obtain three main results which hold for much larger k than those of Niederreiter : a) sequences with maximal linear complexity and almost maximal k-error linear complexity with general periods; b) sequences with maximal linear complexity and maximal k -error linear complexity with special periods; c) sequences with maximal linear complexity and almost maximal k-error linear complexity in the asymptotic case with composite periods. Besides, we also construct some periodic sequences with low correlation and large k -error linear complexity.
Published in: IEEE Transactions on Information Theory ( Volume: 55, Issue: 10, October 2009)
Page(s): 4687 - 4694
Date of Publication: 15 September 2009

ISSN Information:


I. Introduction

The linear complexity and the -error linear complexity of periodic sequences over finite fields are important randomness measures for pseudorandom sequence generators employed in stream ciphers (see [10], [15], [30], [34], and [37]). If a sequence has low linear complexity, then it is vulnerable to cryptanalytic attacks based on the Berlekamp-Massey algorithm [23]. Moreover, cryptographically strong sequences should also have large linear complexity under small perturbations. This leads to the concept of the -error linear complexity [8], [10], [13], [36].

References

References is not available for this document.