Characterization of 2 n -periodic binary sequences with fixed 2-error or 3-error linear complexity

Ramakanth Kavuluru

doi:10.1007/s10623-009-9295-x

Characterization of 2 ⁿ -periodic binary sequences with fixed 2-error or 3-error linear complexity

Ramakanth Kavuluru

Internal Medicine

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

The linear complexity of sequences is an important measure of 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 et al. (SETA, pp. 88-103, 2006) studied the linear complexity and the 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- or 3-error linear complexity. Using this characterization we obtain the counting function for the number of 2 ⁿ -periodic binary sequences with fixed k-error linear complexity for k = 2 and 3.

Original language	English
Pages (from-to)	75-97
Number of pages	23
Journal	Designs, Codes, and Cryptography
Volume	53
Issue number	2
DOIs	https://doi.org/10.1007/s10623-009-9295-x
State	Published - Nov 2009

Bibliographical note

Funding Information:
A portion of this paper has appeared in the proceedings of the 5th international conference on Sequences and their Applications (SETA 2008). 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.

Funding

A portion of this paper has appeared in the proceedings of the 5th international conference on Sequences and their Applications (SETA 2008). 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.

Funders	Funder number
National Science Foundation (NSF)

Keywords

K-error linear complexity
Linear complexity
Periodic sequence

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science Applications
Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1007/s10623-009-9295-x

Cite this

@article{9d2fb993facb47e1835ac1e316ea2bbd,

title = "Characterization of 2 n -periodic binary sequences with fixed 2-error or 3-error linear complexity",

abstract = "The linear complexity of sequences is an important measure of 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 et al. (SETA, pp. 88-103, 2006) studied the linear complexity and the 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- or 3-error linear complexity. Using this characterization we obtain the counting function for the number of 2 n -periodic binary sequences with fixed k-error linear complexity for k = 2 and 3.",

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

author = "Ramakanth Kavuluru",

note = "Funding Information: A portion of this paper has appeared in the proceedings of the 5th international conference on Sequences and their Applications (SETA 2008). 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.",

year = "2009",

month = nov,

doi = "10.1007/s10623-009-9295-x",

language = "English",

volume = "53",

pages = "75--97",

number = "2",

}

TY - JOUR

T1 - Characterization of 2 n -periodic binary sequences with fixed 2-error or 3-error linear complexity

AU - Kavuluru, Ramakanth

N1 - Funding Information: A portion of this paper has appeared in the proceedings of the 5th international conference on Sequences and their Applications (SETA 2008). 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 - 2009/11

Y1 - 2009/11

N2 - The linear complexity of sequences is an important measure of 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 et al. (SETA, pp. 88-103, 2006) studied the linear complexity and the 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- or 3-error linear complexity. Using this characterization we obtain the counting function for the number of 2 n -periodic binary sequences with fixed k-error linear complexity for k = 2 and 3.

AB - The linear complexity of sequences is an important measure of 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 et al. (SETA, pp. 88-103, 2006) studied the linear complexity and the 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- or 3-error linear complexity. Using this characterization we obtain the counting function for the number of 2 n -periodic binary sequences with fixed k-error linear complexity for k = 2 and 3.

KW - K-error linear complexity

KW - Linear complexity

KW - Periodic sequence

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

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

U2 - 10.1007/s10623-009-9295-x

DO - 10.1007/s10623-009-9295-x

M3 - Article

AN - SCOPUS:69949088971

SN - 0925-1022

VL - 53

SP - 75

EP - 97

JO - Designs, Codes, and Cryptography

JF - Designs, Codes, and Cryptography

IS - 2

ER -