Research On Several Key Problems Of Algebraic Attacks On Stream Ciphers

Recently, algebraic attack is considered as one of the most powerful tools for cryptanalysis. To measure the resistance to algebraic attacks, a new cryptographic property of Boolean functions, called algebraic immunity, has been proposed. In order to resist algebraic attacks, the Boolean functions employed in cryptosystems should possess high algebraic immunity (even optimum algebraic immunity). Solving an over-defined nonlinear equation system is a key step for algebraic attack. Grobner bases theory is an important method to solve the systems. XL algorithm, which is used widely in algebraic attacks, is proved to be a redundant version of F4 algorithm (one of the efficient computing algorithms for Grobner bases).In this dissertation, we firstly investigate the recursive constructions of Boolean functions with optimum algebraic immunity. Moreover, we discuss two classes of symmetric Boolean functions with regard to algebraic immunity, algebraic degree and nonlinearity. Finally, we study the fast computing for Grobner bases. The main results are given as follows:1) The recursive constructions of Boolean functions with optimum algebraic immunity. Firstly, we provide a second-order recursive construction of Boolean functions with optimum algebraic immunity. The constructed Boolean functions have not only optimum algebraic immunity but also high algebraic degree and nonlinearity. Compared with the former recursive construction, they are much more balance. Secondly, we propose a first-order recursive construction of Boolean functions with optimum algebraic immunity. The constructed Boolean functions are completely balanced. Especially, to the best of our knowledge, it's the first time to present such a first-order recursive construction. Thirdly, based on the transformation theory of Boolean functions, we make some generalizations for the two constructions above.2) Research on two classes of symmetric Boolean functions. For each class, we prove the necessary and sufficient condition for having optimum algebraic immunity. Then we enumerate all the Boolean functions with optimum algebraic immunity in the two classes. The algebraic degree and nonlinearity of the two classes are completely determined. Based on these results, we prove several of Braeken's conjectures about the algebraic degree and nonlinearity of the symmetric Boolean functions with optimum algebraic immunity in the two classes.3) Fast computation of Grobner bases. We propose a fast computing algorithm for Grobner bases of polynomial ideals in two variables. We show that only the S-polynomials of neighbor pairs of a strictly ordered finite generating set are needed while computing the Grobner bases. Therefore, the number of S-polynomials needed decreases dramatically from 1/2r(r-1) to(r-1), where r is the number of generating polynomials for the current computing round.