On The K-Error Linear Complexity Of Pseudorandom Sequences

Research on the pseudorandom properties of keystream sequences is very important indesign and analysis of stream ciphers. Linear complexity and k-error linear complexity are twoimportant measures to characterize the pseudorandom properties of keystream sequences. Acryptographically secure sequence should possess large linear complexity to resist the attack byBerlekamp-Massey synthesis algorithm. However, a cryptographically strong sequence shouldnot only have a large linear complexity, but also the change of a few terms should not causesignificant decrease of the linear complexity. This leads to the concept of the k-error linearcomplexity, that is, the smallest linear complexity that can be obtained by altering up to k termsof the sequence, and then continuing the changes periodically. The k-error linear complexity is animportant measure on the stability of the linear complexity of sequences.In this thesis, we first study the asymptotic behavior of the k-error linear complexity ofrandom sequences, and then discuss the stability of the linear complexity of several classes ofpseudorandom sequences. The main results are as follows:1. The asymptotic behavior of the normalized k-error linear complexity Ln, k(s)/n of randomsequence is studied in two ways. For k and n tending to∞at a fixed ratio, the lower and upperbounds on the accumulation points of Ln, k(s)/n are derived, which hold with probability1. Onthe other hand, for any fixed k it is shown that nliâ†'m∞Ln, k(s)/n=1/2holds with probability1. Theasymptotic bounds on the expected value of the normalized k-error linear complexity are alsopresented. These results are based on the research of one of H. Niederreiter’s open problems, andadvance the solution of the open problem.2. The distribution of1-error linear complexity of binary sequences with arbitrary primeperiod is studied. For any odd prime N, the exact formulas to count the number of N-periodicbinary sequences with any given1-error linear complexity and given linear complexity arepresented. The exact formulas to count the number of N-periodic binary sequences with anygiven1-error linear complexity are also derived. Compared with the results on the k-error linearcomplexity of prime periodic sequences derived by W. Meidl and H. Niederreiter, the period ofsequences is generalized to arbitrary odd prime number for the case of k=1in this thesis.3. The stability of the linear complexity of the maximal length feedback with carry shiftregisters sequences(l-sequences) is discussed. For an l-sequence s with linear complexityattaining the maximum value: per(s)/2+1, a tight lower bound and an upper bound on theminimal value of k, for which the k-error linear complexity of s is strictly less than its linearcomplexity, are given. In particular, for the l-sequences based on strong2-prime numbers, it isshown that they possess the maximal linear complexity and their linear complexity are verystable. In addition, the element distribution property of the decimations of l-sequences isestimated. It is shown that when the connection integer is large enough, the proportion of1’s(resp.,0’s) in a period of any decimation of l-sequences approximates50%.4. For two generalized cyclotomic binary sequences of period2p~mconstructed recently, their distribution properties, k-error linear complexity and autocorrelation are studied. Thenon-pseudorandomness of their distribution properties is first presented. Then it is shown that,although these sequences have large linear complexity, the k-error linear complexity are far lessthan their linear complexity even for some small values of k. Furthermore, it is shown thatautocorrelation values at some shifts of these sequences are very large, even close to the period.These results imply that there exist many serious drawbacks in the application of these twosequences.