The K-Error Linear Complexity Distribution Of Periodic Unbalanced Binary Sequences

The development of computers and Internet bring human beings into the information age.Information has become one of the most important resources in our daily life. As a double-edgedsword, information brings us great convenience while producing a series of safety problems.Cryptography as the core technology of information security has become the focus in this field.With the development of cryptography and the improvement of hardware, stream ciphers haveattracted the most widely attention. Stream ciphers are generated by certain algorithms, they areactually periodic sequences. In order to measure the randomness of them, there are a number ofassumptions. Ultimately, linear complexity and k-error linear complexity became the two importantsecurity indicators for stream ciphers.Linear complexity（LC） is the stage of the shortest linear-feedback-shift-register whichgenerates the keystream. According to B-M algorithm, the entire keystream can be obtained if2LC consecutive bits are known. So a safer keystream can be got by improving its linear complexity.However, for some keystream when a small number of bits are changed, the linear complexity willdecline sharply. Obviously, this kind of keystream is unsafe. So foreign scholars Stamp and Martinintroduced the concept of k-error linear complexity as the stability indicators for keystream. Thus,Linear complexity and k-error linear complexity became the heatest research spot.In order to investigate the safety performance of keystream sequence further, Kurosawa, etc.proposed the concept of the error sequences. On this basis, Chinese scholars put forward thedefinition of k-error sequences. Easy to know that, the more k-error sequences a keystream has, themore likely that its linear complexity to decline. Therefore, research the number of k-error sequenceis also significant.In this paper, based on the existing achievements, k-error linear complexity and k-errorsequence of2n-periodic binary sequences are studied. The k-error linear complexity of pn-periodicbinary sequences is discussed as well. The main research content and results are as follows:1.Based on the Games-Chan algorithm, the k-error linear complexity for binary sequences arediscussed. While linear complexity and k-error linear complexity are2n, counting functions when5-error linear complexity equals to2n-3+x,2n-2₂n-m,2n-1₂n-3and7-error linear complexity equalsto2n₂r+c,2n-3,2n-3+x are derived.2.According to the concept of k-error sequences and associated lemma, counting functions of5-error sequences while5-error linear complexity up to2n-3or equal to2n-3+x,2n-2,2n-2+x,2n-2-2m,2n-2-2m+x are derived. 3.Based on XWLI algorithm, counting functions of k-error linear complexity for pn-periodicbinary sequences when k-error linear complexity is not greater than pn-2are derived, where k=3,4,p=3.