A Characteristic Set Method For Solving Boolean Equations And Applications In Cryptanalysis Of Stream Ciphers

In this paper, we present a characteristic set method for solving Boolean equations, which is equivalent to polynomial equation solving in the finite field F₂. Due to the special property of F₂, the given characteristic set methods are much more efficient and simpler than the general characteristic set method.The first major improvement is that we could decompose the zero set of a Boolean equation system as the disjoint union of the zero sets of ascending chains consisting of monic polynomials. As a consequence, we could give an explicit formula for the number of solutions of the equation system.The well-ordering principle is a basic step of the CS method, which can be used to compute a so called Wu-CS for an equation system. If the Wu-CS satisfies certain properties, it provides at least one solution to the original equation system. The second improvement is that we design well-ordering principles which can be executed in n steps and use a polynomial number of polynomial multiplications, where n is the number of variables. Thirdly, we also design an algorithm, where the degrees of the polynomials occurring in the algorithm do not increase. This allows us to control the size of the polynomials effectively.We implement our algorithm with the C language. We introduce the Principle of Balance Between Sizes and Branches: try to produce as less branches as possible under the constraint that the memory of the computers be sufficiently used. In order to save space, we use SZDD to represent Boolean polynomials. Experiments show that this could speed up the program significantly. We also give a parallel implementation of our methods. Based on these strategies, we could give a very efficient implementation for the characteristic set method.We use our methods to solve equations from cryptanalysis of a class of stream ciphers based on nonlinear filter generators. Extensive experiments have been done for equation systems with variables ranging from 40 to 128. Comparisons with the Grobner basis method are given. Experiments show that our algorithms provide an effective tool for solving equations over F₂.