A High Efficient Boolean Polynomial Representation

Solving Boolean equations for cryptanalysis has important practical significance. However, the contradiction of limited computer storage space and solving demand growth of existing algorithms is the major bottleneck for getting more progresses. This paper presents a high efficient Boolean polynomial representation, BanYan. BanYan is designed for Boolean equations solving algorithms based on leading-term eliminating, such as F4,F5,XLs.The essence of BanYan is that it only stores the information about how to generate intermediate polynomials, but not the intermediate polynomials themselves. The original polynomials in the polynomial ring for Grnbner bases computation are called root polynomials. The new generated polynomials come from root polynomials by terms multiplication and polynomials addition. So we only store the corresponding terms and polynomials connected with the root polynomials. As the intermediate polynomials grow, the whole storage structure is getting just like a tree. That is why we call this method BanYan. Although the scale of intermediate polynomials grows exponentially in the process of Grnbner bases computation, the generation information is becoming much more simpler, so BanYan can greatly reduce the space requirement and then improve the solving ability. Analysis and experiments show that compared with traditional representations based on terms, in average case and worst case the space requirement of BanYan has l-fold reduction. Here l is the average length of intermediate polynomials.