Counting functions for the k-error linear complexity of 2 n-periodic binary sequences

Ramakanth Kavuluru; Andrew Klapper

doi:10.1007/978-3-642-04159-4_10

Counting functions for the k-error linear complexity of 2 ⁿ-periodic binary sequences

Ramakanth Kavuluru, Andrew Klapper

Internal Medicine

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

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ⁿ-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ⁿ-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ⁿ-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ⁿ-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	https://doi.org/10.1007/978-3-642-04159-4_10
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

Access to Document

10.1007/978-3-642-04159-4_10

Cite this

Kavuluru, R., & Klapper, A. (2008). Counting functions for the k-error linear complexity of 2 ⁿ-periodic binary sequences. In Selected Areas in Cryptography - 15th International Workshop, SAC 2008, Revised Selected Papers (pp. 151-164). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5381 LNCS). https://doi.org/10.1007/978-3-642-04159-4_10

Kavuluru, Ramakanth ; Klapper, Andrew. / Counting functions for the k-error linear complexity of 2 ⁿ-periodic binary sequences. Selected Areas in Cryptography - 15th International Workshop, SAC 2008, Revised Selected Papers. 2008. pp. 151-164 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d2dc6bfe750448c6bc5c6a7d5a78f94e,

title = "Counting functions for the k-error linear complexity of 2 n-periodic binary sequences",

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 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.",

keywords = "Linear complexity, Periodic sequence, k-error linear complexity",

author = "Ramakanth Kavuluru and Andrew Klapper",

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.; 15th International Workshop on Selected Areas in Cryptography, SAC 2008 ; Conference date: 14-08-2008 Through 15-08-2008",

year = "2008",

doi = "10.1007/978-3-642-04159-4_10",

language = "English",

isbn = "3642041582",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "151--164",

booktitle = "Selected Areas in Cryptography - 15th International Workshop, SAC 2008, Revised Selected Papers",

}

Kavuluru, R & Klapper, A 2008, Counting functions for the k-error linear complexity of 2 ⁿ-periodic binary sequences. in Selected Areas in Cryptography - 15th International Workshop, SAC 2008, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5381 LNCS, pp. 151-164, 15th International Workshop on Selected Areas in Cryptography, SAC 2008, Sackville, NB, Canada, 8/14/08. https://doi.org/10.1007/978-3-642-04159-4_10

Counting functions for the k-error linear complexity of 2 ⁿ-periodic binary sequences. / Kavuluru, Ramakanth; Klapper, Andrew.
Selected Areas in Cryptography - 15th International Workshop, SAC 2008, Revised Selected Papers. 2008. p. 151-164 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5381 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Counting functions for the k-error linear complexity of 2 n-periodic binary sequences

AU - Kavuluru, Ramakanth

AU - Klapper, Andrew

N1 - 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.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Linear complexity

KW - Periodic sequence

KW - k-error linear complexity

UR - http://www.scopus.com/inward/record.url?scp=70350679181&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350679181&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-04159-4_10

DO - 10.1007/978-3-642-04159-4_10

M3 - Conference contribution

AN - SCOPUS:70350679181

SN - 3642041582

SN - 9783642041587

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

SP - 151

EP - 164

BT - Selected Areas in Cryptography - 15th International Workshop, SAC 2008, Revised Selected Papers

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

Y2 - 14 August 2008 through 15 August 2008

ER -

Kavuluru R, Klapper A. Counting functions for the k-error linear complexity of 2 ⁿ-periodic binary sequences. In Selected Areas in Cryptography - 15th International Workshop, SAC 2008, Revised Selected Papers. 2008. p. 151-164. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-04159-4_10