Research On The Complexity Of Two Classes Of The Rudin-Shapiro-Like Sequence

Symmetric cryptography include stream cipher(also called sequence cipher)and block cipher.Compared with block cipher,stream cipher is more suitable to resourceconstrained environment.The security feature of stream cipher is often depend on the key stream,both the nonlinear complexity and the expansion complexity are important criteria to measure a given sequence.The Rudin-Shapiro sequence is one of the famous automatic sequences,which has large nonlinear complexity while its expansion complexity is small,such sequences can be easily predicted,there are much risks when they are used as key stream.The Rudin-Shapiro sequence is risky for cryptographic applications,which motivated us to exploring whether modifying the Rudin-Shapiro sequence in some manner will give rise to cryptographically strong sequences or not.In this paper,we determine the nonlinear complexity of the Rudin-Shapiro-Like sequence based on its definition and the properties of nonlinear complexity.Meanwhile,we also give the upper bound of the expansion complexity of the Rudin-Shapiro-Like sequence by applying the definition of expansion complexity and the recursive properties of the Rudin-Shapiro-Like sequence.Moreover,we analyse the relationship of the nonlinear complexity between the Rudin-Shapiro-Like sequence and Rudin-Shapiro sequence,as well as the correlation between the nonlinear complexity and the expansion complexity of the Rudin-Shapiro-Like sequence.