Paper 2016/1025

An Algorithm for Counting the Number of $2^n$-Periodic Binary Sequences with Fixed $k$-Error Linear Complexity

Wenlun Pan, Zhenzhen Bao, Dongdai Lin, and Feng Liu

Abstract

The linear complexity and $k$-error linear complexity of sequences are important measures of the strength of key-streams generated by stream ciphers. The counting function of a sequence complexity measure gives the number of sequences with given complexity measure value and it is useful to determine the expected value and variance of a given complexity measure of a family of sequences. Fu et al. studied the distribution of $2^n$-periodic binary sequences with 1-error linear complexity in their SETA 2006 paper and peoples have strenuously promoted the solving of this problem from $k=2$ to $k=4$ step by step. Unfortunately, it still remains difficult to obtain the solutions for larger $k$ and the counting functions become extremely complex when $k$ become large. In this paper, we define an equivalent relation on error sequences. We use a concept of \textit{cube fragment} as basic modules to construct classes of error sequences with specific structures. Error sequences with the same specific structures can be represented by a single \textit{symbolic representation}. We introduce concepts of \textit{trace}, \textit{weight trace} and \textit{orbit} of sets to build quantitative relations between different classes. Based on these quantitative relations, we propose an algorithm to automatically generate symbolic representations of classes of error sequences, calculate \textit{coefficients} from one class to another and compute \textit{multiplicity} of classes defined based on specific equivalence on error sequences. This algorithm can efficiently get the number of sequences with given $k$-error linear complexity. The time complexity of this algorithm is $O(2^{k\log k})$ in the worst case which does not depend on the period $2^n$.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
SequenceLinear Complexity$k$-Error Linear ComplexityCounting FunctionCube Theory
Contact author(s)
wylbpwl @ gmail com
History
2016-11-01: received
Short URL
https://ia.cr/2016/1025
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1025,
      author = {Wenlun Pan and Zhenzhen Bao and Dongdai Lin and Feng Liu},
      title = {An Algorithm for Counting the Number of $2^n$-Periodic Binary Sequences with Fixed $k$-Error Linear Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1025},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1025}},
      url = {https://eprint.iacr.org/2016/1025}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.