Algebraic Structures And Distribution Properties Of Sequences Based On T-functions

Recently, new classes of cryptographic primitives called T-functions were introduced by Klimov and Shamir. They are well-suited for use in the design of efficient software-oriented stream ciphers, and their efficiency is based on operating in bytes and using operations available in modern processors, including algebraic and logical operations. Since T-functions combine algebraic and non-algebraic operations, it is difficult to mount an algebraic attack against stream ciphers based on T-functions. Now, T-functions have been an important research subject of stream ciphers design and analysis.In this dissertation, we investigate the algebraic structures of Klimov-Shamir T-functions and some cryptographic properties of single word T-functions and sequences generated by them. The main results are as follows.1. Three main quadratic equations over the binaries for Klimov-Shamir T-functions are presented. Based on these quadratic equations, the autocorrelation value of the jth bit sequence generated by Klimov-Shamir T-functions with Cj = Cj?1 for the shift equal to one eighth period is completely solved. Moreover, how to choose C used in Klimov-Shamir T-functions to avoid simple algebraic structures is discussed.2. Pattern distributions of truncated sequences of single cycle T-functions are studied. The result shows that these sequences have ideal pattern distributions.3. Linear complexity of truncated sequences generated by single word single-cycle T-functions is studied, and both the upper bound and the lower bound are given. Moreover, k-error linear complexity of the truncated sequences generated by the 2t most significant bits of every word of single-cycle T-functions is also studied.4. Based on the above results of linear complexity, all the de Bruijn sequences generated by single word single-cycle T-functions are compeletely determined.