Counting Functions for the k-Error Linear Complexity of 2 n -Periodic Binary Sequences.

Linear complexity is an important measure of the cryptographic strength of key streams used in stream ciphers. The linear complexity of a sequence can decrease drastically when a few symbols are changed. Hence there has been considerable interest in the k-error linear complexity of sequences which measures this instability in linear complexity. For 2n-periodic sequences it is known that minimum number of changes needed per period to lower the linear complexity is the same for sequences with fixed linear complexity. In this paper we derive an expression to enumerate all possible values for the k-error linear complexity of 2n-periodic binary sequences with fixed linear complexity L, when k equals the minimum number of changes needed to lower the linear complexity below L. For some of these values we derive the expression for the corresponding number of 2n-periodic binary sequences with fixed linear complexity and k-error linear complexity when k equals the minimum number of changes needed to lower the linear complexity. These results are of importance to compute some statistical properties concerning the stability of linear complexity of 2n-periodic binary sequences. [ABSTRACT FROM AUTHOR]
Copyright of Selected Areas in Cryptography (9783642041587) is the property of Springer Nature / Books and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)