A characteristic set method for solving boolean equations and applications in cryptanalysis of stream ciphers* |
| |
Authors: | Fengjuan CHAI Xiao-Shan GAO Chunming YUAN |
| |
Institution: | (1) Key Laboratory of Mathematics Mechanization, Institute of Systems Science, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190, China |
| |
Abstract: | This paper presents a characteristic set method for solving Boolean equations, which is more efficient and has better properties
than the general characteristic set method. In particular, the authors give a disjoint and monic zero decomposition algorithm
for the zero set of a Boolean equation system and an explicit formula for the number of solutions of a Boolean equation system.
The authors also prove that a characteristic set can be computed with a polynomial number of multiplications of Boolean polynomials
in terms of the number of variables. As experiments, the proposed method is used to solve equations from cryptanalysis of
a class of stream ciphers based on nonlinear filter generators. Extensive experiments show that the method is quite effective.
*This research is partially supported by a National Key Basic Research Project of China under Grant No. 2004CB318000. |
| |
Keywords: | Boolean equation characteristic set method cryptanalysis finite field stream ciphers |
本文献已被 维普 SpringerLink 等数据库收录! |