2013/09/07 by Jianqin Zhou, Wanquan Liu, Zhou, Jianqin +1 · 3 citations
Computer Science · Engineering · Mathematics · #11B50 #94A55 #94A60 #Coding theory and cryptography #Cryptographic Implementations and Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.CR #cs.IT #graph theory and CDMA systems #math.IT #msc:11B50 #msc:94A55 #msc:94A60
paper · pdf · doi:10.48550/arxiv.1309.1829
11 pages. arXiv admin note: substantial text overlap with arXiv:1109.4455, arXiv:1108.5793, arXiv:1112.6047
arxiv created 2013/09/07 · openalex publication_date 2013/09/07 · arxiv updated 2013/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The linear complexity and k-error linear complexity of a sequence have been used as important measures of keystream strength, hence designing a sequence with high linear complexity and k-error linear complexity is a popular research topic in cryptography. In this paper, the concept of stable k-error linear complexity is proposed to study sequences with stable and large k-error linear complexity. In order to study k-error linear complexity of binary sequences with period 2n, a new tool called cube theory is developed. By using the cube theory, one can easily construct sequences with the maximum stable k-error linear complexity. For such purpose, we first prove that a binary sequence with period 2n can be decomposed into some disjoint cubes and further give a general decomposition approach. Second, it is proved that the maximum k-error linear complexity is 2n-(2l-1) over all 2n-periodic binary sequences, where 2l-1≤ k<2l. Thirdly, a characterization is presented about the tth (t>1) decrease in the k-error linear complexity for a 2n-periodic binary sequence s and this is a continuation of Kurosawa et al. recent work for the first decrease of k-error linear complexity. Finally, A counting formula for m-cubes with the same linear complexity is derived, which is equivalent to the counting formula for k-error vectors. The counting formula of 2n-periodic binary sequences which can be decomposed into more than one cube is also investigated, which extends an important result by Etzion et al..