An Algorithm for Counting the Number of -Periodic Binary Sequences with Fixed -Error Linear Complexity
Wenlun Pan, Zhenzhen Bao, Dongdai Lin, and Feng Liu
Abstract
The linear complexity and -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 -periodic binary sequences with 1-error linear complexity in their SETA 2006 paper and peoples have strenuously promoted the solving of this problem from to step by step. Unfortunately, it still remains difficult to obtain the solutions for larger and the counting functions become extremely complex when 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 -error linear complexity. The time complexity of this algorithm is in the worst case which does not depend on the period .
@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},
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.