Construction And Analysis Of The Extended Welch-Gong(WG) Sequences

Pseudorandom sequences are the core of the stream cipher system, which are essential components in key stream and pseudorandom number generators, having a very wide application. Welch-Gong(WG) sequences that were discovered by Golomb, Gong, and Gaal have good randomness, including long period, balance property, ideal 2-tuple distribution, two-level autocorrelation, three-level cross correlation with m-sequences, and linear span increasing exponentially in n. Synchronous stream cipher based on WG transformation which is one of the candidates for eSTREAM project not only has good randomness, but also can resist some attacks to ensure safety. WG sequences have been used in many fields, causing further study by domestic and foreign scholars due to the good cryptographic properties.The original WG sequences are generated by a specific five-term function through WG transformation. For the WG transformation, the general research on polynomial function is odd term. Considering the complexity of polynomial function by WG transform, we extend the specific five-term function to general three-term function in WG transformation, having proved that the new sequences still have good randomness (long period, balance property, ideal 2-tuple distribution, two-level autocorrelation, three-level cross correlation withh-sequences) and large linear span. The linear span of the original sequences is n(2[n/3]-3), increasing exponentially in n. For the new sequences based on general three-term function, the growth of linear span is related to the indexes of three-term function, which can increase exponentially in n by selecting good indexes. We study comprehensively on the linear span of WG sequences based on three-term function and have found some general forms of the indexes, which can make linear span increase exponentially. This provides a variety of options for the application of three-term function in the WG transformation. In addition, we select a specific instance to analyze the hardware implementation of the WG cipher based on the three-term function, giving a certain reference value for the design of the algorithm. Three-term function is simpler than five-term function, so the results of this paper provide theoretical basis for more efficient implementation of WG sequences.