The Research On K-Error Linear Complexity Of 2p~2-Periodic Binary Sequences And Sequences Generated From HWBF

Pseudorandom sequences play an important role in cryptography.The security of stream cipher depends entirely on the randomness and unpredictability of pseudorandom sequences.So the design of pseudorandom sequences and their cryptographic indicators are the critical research directions.The linear complexity and k-error linear complexity of periodic sequences are important metrics for the evaluation in stream cipher.In this paper,the k-error linear complexity of binary periodic sequences is studied.A new matrix method is used to calculate the k-error linear complexity of 2p~2-periodic binary sequences,and the k-error linear complexity of 2n-periodic binary sequences generated from HWBF(high weighted bit function)is preliminarily explored.The main research contents are as follows:(1)Research on the k-error linear complexity of 2p~2-periodic binary sequences.We use a new matrix method to determine the linear complexity and k-error linear complexity of the sequence by arranging the sequence into three matrix forms(matrices of size p×2p,2px p and px p)and calculating the parameters related to the weight of matrix columns.Firstly,we analyze the lower bounds on linear complexity and conclude that there are two cases,p~2-p<LC(s)?p~2+p and LC(s)>2(p~2-p).Then according to these two cases,we discuss the values of k-error linear complexity and the corresponding range of k by using this matrix method,and the proof is given in theory.Finally,a numerical example is given for verification.(2)Research on the k-error linear complexity of Ding-generalized cyclotomic sequences of order two.We first introduce the Ding-generalized cyclotomic sequences of order two with period 2p~2,and then apply the matrix method to the calculation of the k-error linear complexity of the sequences.The results show that the linear complexity of the sequences will decrease from p~2+1 to less than 2p by changing k=p-1 terms.Finally,a numerical example is given for verification(3)Research on the k-error linear complexity of 2n-periodic binary sequences generated from HWBF.Firstly,we introduce the generation method of the sequences,and then prove that the linear complexity of the sequences is 2n-1 by using the Hasse derivative.Finally,we calculate the k-error linear complexity of the sequences by using the Stamp-Martin algorithm,and the error sequence corresponding to the 2-error linear complexity by the exhaustive method.By analyzing the results of numerical experiments,we find that the k-error linear complexity(4?n?23,0?k?6)and the error sequence corresponding to the 2-error linear complexity(4?n?23)of the sequences show some regularity,and we give the related speculations.