2 n -Periodic binary sequences with fixed k-error linear complexity for k = 2 or 3

Ramakanth Kavuluru

doi:10.1007/978-3-540-85912-3_23

2 ⁿ -Periodic binary sequences with fixed k-error linear complexity for k = 2 or 3

Ramakanth Kavuluru

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

7 Scopus citations

Abstract

The linear complexity of sequences is an important measure 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 complexity and 1-error linear complexity of 2 ⁿ -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 ⁿ -periodic binary sequences in a more general setting using a combination of algebraic, combinatorial, and algorithmic methods. This approach allows us to characterize 2 ⁿ -periodic binary sequences with fixed 2-error or 3-error linear complexity L, when the Hamming weight of the binary representation of 2 ⁿ - L is . Using this characterization we obtain the counting function for the number of 2 ⁿ -periodic binary sequences with fixed k-error linear complexity L for k = 2 and 3 when .

Original language	English
Title of host publication	Sequences and Their Applications - SETA 2008 - 5th International Conference, Proceedings
Pages	252-265
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-540-85912-3_23
State	Published - 2008
Event	5th International Conference on Sequences and Their Applications, SETA 2008 - Lexington, KY, United States Duration: Sep 14 2008 → Sep 18 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5203 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	5th International Conference on Sequences and Their Applications, SETA 2008
Country/Territory	United States
City	Lexington, KY
Period	9/14/08 → 9/18/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 author and do not necessarily reflect the views of the National Science Foundation.

Keywords

K-error linear complexity
Linear complexity
Periodic sequence

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science (all)

Access to Document

10.1007/978-3-540-85912-3_23

Cite this

Kavuluru, R. (2008). 2 ⁿ -Periodic binary sequences with fixed k-error linear complexity for k = 2 or 3. In Sequences and Their Applications - SETA 2008 - 5th International Conference, Proceedings (pp. 252-265). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5203 LNCS). https://doi.org/10.1007/978-3-540-85912-3_23

@inproceedings{7e0c3133fb8c4b658a38d94f2a0d6395,

title = "2 n -Periodic binary sequences with fixed k-error linear complexity for k = 2 or 3",

abstract = "The linear complexity of sequences is an important measure 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 complexity 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 combination 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 . 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 = 2 and 3 when .",

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

author = "Ramakanth Kavuluru",

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 author and do not necessarily reflect the views of the National Science Foundation.; 5th International Conference on Sequences and Their Applications, SETA 2008 ; Conference date: 14-09-2008 Through 18-09-2008",

year = "2008",

doi = "10.1007/978-3-540-85912-3_23",

language = "English",

isbn = "354085911X",

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

pages = "252--265",

booktitle = "Sequences and Their Applications - SETA 2008 - 5th International Conference, Proceedings",

}

Kavuluru, R 2008, 2 ⁿ -Periodic binary sequences with fixed k-error linear complexity for k = 2 or 3. in Sequences and Their Applications - SETA 2008 - 5th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5203 LNCS, pp. 252-265, 5th International Conference on Sequences and Their Applications, SETA 2008, Lexington, KY, United States, 9/14/08. https://doi.org/10.1007/978-3-540-85912-3_23

2 ⁿ -Periodic binary sequences with fixed k-error linear complexity for k = 2 or 3. / Kavuluru, Ramakanth.
Sequences and Their Applications - SETA 2008 - 5th International Conference, Proceedings. 2008. p. 252-265 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5203 LNCS).

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

TY - GEN

T1 - 2 n -Periodic binary sequences with fixed k-error linear complexity for k = 2 or 3

AU - Kavuluru, Ramakanth

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 author and do not necessarily reflect the views of the National Science Foundation.

PY - 2008

Y1 - 2008

N2 - The linear complexity of sequences is an important measure 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 complexity 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 combination 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 . 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 = 2 and 3 when .

AB - The linear complexity of sequences is an important measure 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 complexity 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 combination 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 . 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 = 2 and 3 when .

KW - K-error linear complexity

KW - Linear complexity

KW - Periodic sequence

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

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

U2 - 10.1007/978-3-540-85912-3_23

DO - 10.1007/978-3-540-85912-3_23

M3 - Conference contribution

AN - SCOPUS:56449110628

SN - 354085911X

SN - 9783540859116

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

SP - 252

EP - 265

BT - Sequences and Their Applications - SETA 2008 - 5th International Conference, Proceedings

T2 - 5th International Conference on Sequences and Their Applications, SETA 2008

Y2 - 14 September 2008 through 18 September 2008

ER -

Kavuluru R. 2 ⁿ -Periodic binary sequences with fixed k-error linear complexity for k = 2 or 3. In Sequences and Their Applications - SETA 2008 - 5th International Conference, Proceedings. 2008. p. 252-265. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-85912-3_23