Construction And Analysis Of Sequences Derived From Single Cycle T-functions

The sequences derived from T-functions are a type of sequences suitable for stream cipherdesign. As T-functions combine algebraic and logical operations, the sequences generated bythem have very good nonlinear properties. T-functions are well-suited for use in the design ofefficient software-oriented stream ciphers, and their efficiency is based on operating in bytes. Asa result, since T-functions are proposed, they have gained much attention and are rapidly appliedto stream cipher design. The research performed so far focuses on single cycle T-functions.The periods of the coordinate sequences generated by single cycle T-functions aredegressive. To avoid this deficiency, this thesis studies several kinds of methods to improve itand then investigates the cryptographic properties of the sequences derived from them. The mainresults are as follows.1. Based on single cycle T-functions overFn2, two classes of pseudorandom sequences areproposed. The periods of all their coordinate sequences can reach the maximal value2n. For thefirst class of sequences, it is shown that the less significant half of the coordinate sequences areuniformly distributed over F2and the exact linear complexities are also derived. However, forthe first proposal, the less significant half of the coordinate sequences are not cryptographicallystrong enough. Therefore, we improve it to obtain the second proposal. For the second class ofsequences, lower bounds on the linear complexities of their coordinate sequences are given.Furthermore, experimental results indicate that all their coordinate sequences are almostuniformly distributed over F2, and their linear complexities are all close to their periods.2. The cryptographic properties of one class of single cycle T-function based sequencesproposed by V. S. Anashin are analyzed. It is proved that the periods of all their coordinatesequences can reach the maximal value2nand the exact linear complexities are also derived. It isalso proved that all their coordinate sequences are uniformly distributed over F2. Then, this thesismakes a conclusion on the sequences derived from single cycle T-functions and puts forward theproblem of constructing single cycle functions over Z/(2n1). It is shown that all the coordinatesequences generated by the single cycle functions over Z/(2n1) are equivalent.3. The construction of single cycle polynomials over Z/(pe) is studied. The polynomialfunctions are a kind of widely investigated functions. Let2n1=p1e1p2e2… pses, then theconstruction of single cycle polynomials over Z/(2n1) can be reduced to the case over eachZ/(piei),1≤i≤s. Moreover, if p≥5, the research of single cycle polynomials over Z/(pe) can bereduced to the case over Z/(p2). Therefore, an exact characterization of single cycle polynomialsover Z/(5) is given in terms of their coefficients, and then a complete characterization of singlecycle polynomials of degree6over Z/(52) is given based on it. The characterization of single cycle polynomials of degree7over Z/(52) is also studied but no uniform results are derived. Inaddition, a partial construction of single cycle polynomials of degree (p1) over Z/(p2) is alsoproposed.2-Adic complexity measures the difficulty of outputting a binary sequence using an FCSR.This thesis studies the2-adic complexities of the coordinate sequences generated by single cycleT-functions.4. The tight upper bounds on the2-adic complexities of the coordinate sequences generatedby single cycle T-functions are given. Let j be an integer such that0≤j≤n1. It is shown thatthe2-adic complexity of the jth coordinate sequence is upper bounded by log2(22j+1). Moreover,1-error2-adic complexity is also studied. It is proved that the1-error2-adic complexity of the jthcoordinate sequence is equal to its2-adic complexity except for j=0.