On the $k$-error linear complexity for $p^n$-periodic binary sequences via hypercube theory
This work addresses security analysis for stream ciphers in cryptography, but it is incremental as it builds on prior methods to enhance specific theoretical results.
The authors tackled the problem of analyzing the linear complexity and k-error linear complexity for p^n-periodic binary sequences, which are key security measures in stream ciphers, by developing hypercube theory based on sequence decomposition, and they achieved a complete characterization for the first decrease in linear complexity, significantly improving existing results.
The linear complexity and the $k$-error linear complexity of a binary sequence are important security measures for key stream strength. By studying binary sequences with the minimum Hamming weight, a new tool named as hypercube theory is developed for $p^n$-periodic binary sequences. In fact, hypercube theory is based on a typical sequence decomposition and it is a very important tool in investigating the critical error linear complexity spectrum proposed by Etzion et al. To demonstrate the importance of hypercube theory, we first give a standard hypercube decomposition based on a well-known algorithm for computing linear complexity and show that the linear complexity of the first hypercube in the decomposition is equal to the linear complexity of the original sequence. Second, based on such decomposition, we give a complete characterization for the first decrease of the linear complexity for a $p^n$-periodic binary sequence $s$. This significantly improves the current existing results in literature. As to the importance of the hypercube, we finally derive a counting formula for the $m$-hypercubes with the same linear complexity.