## Abstract

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 2^{n}-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 2^{n}-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 2^{n}-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 2^{n}-periodic binary sequences.

Original language | English |
---|---|

Title of host publication | Selected Areas in Cryptography - 15th International Workshop, SAC 2008, Revised Selected Papers |

Pages | 151-164 |

Number of pages | 14 |

DOIs | |

State | Published - 2008 |

Event | 15th International Workshop on Selected Areas in Cryptography, SAC 2008 - Sackville, NB, Canada Duration: Aug 14 2008 → Aug 15 2008 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 5381 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 15th International Workshop on Selected Areas in Cryptography, SAC 2008 |
---|---|

Country/Territory | Canada |

City | Sackville, NB |

Period | 8/14/08 → 8/15/08 |

### Bibliographical note

Funding Information:This material is based upon work supported by the National Science Foundation under Grant No. CCF-0514660. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

## Keywords

- Linear complexity
- Periodic sequence
- k-error linear complexity

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science

## Fingerprint

Dive into the research topics of 'Counting functions for the k-error linear complexity of 2^{n}-periodic binary sequences'. Together they form a unique fingerprint.