Constructions Of Finite-length Sequences With Large Nonlinear Complexity

Stream cipher is a class of important symmetric cryptosystems,having the advan-tages of fast encryption and easy hardware implementation.It has been widely used in recent years.The security of stream cipher depends largely on the characteristics of the keystream,and pseudorandom sequences are usually utilized for keystreams in stream cipher.In practical applications,some properties such as randomness,long pe-riod,balance,low correlation of a key-stream sequence are requried.In general,the nonlinear complexity is one of the important criteria used to measure the randomness of a sequence.The nonlinear complexity of a sequence is defined to be the length of the shortest nonlinear feedback shift registers(NFSRs)that can generate the sequence.The eSTREAM project greatly promoted the development of stream cipher,in the third round candidate algorithms,Trivium and Grain,the hardware-oriented algorithms,both use NFSRs as their main components.It shows that NFSR has been an important bu-liding block in keystream generators.Therefore,it is of great practical significance to investigate the nonlinear complexity of sequences.In the study of nonlinear complexity,a important problem is to construct se-quences with large nonlinear complexity.For finite length sequences of length n,the maximal nonlinear complexity is n-1,and these sequences are completely determined by Jansen.We construct sequences with length n having nonlinear complexity n-2,n-3 and n-4.Specifically,all sequences with length n having nonlinear complexity n-j are constructed for n ? 2j and j ? 2,3.Furthermore,for n>8,binary sequences with length n having nonlinear complexity n-4 are obtained.Finally,based on the forms of the constructed sequences,the numbers of these sequences are determined.