Polynomial algorithms for constructing local affinities of quadratic Boolean functions

Due to the affine normal form, one can consider a Boolean function as affine on certain flats in its domain — so-called local affinities. This Boolean function representation — affine approximation — could be useful for solving systems of nonlinear equations over two-element field. The problem of solving these systems (of a special sort) arises, in particular, in some methods of the information security tools design and analysis. The paper describes an approach to finding local affinities for quadratic Boolean functions which is based on Dickson's*theorem. By this, one obtains affine normal forms for such functions. Besides, the paper concerns the efficiency of corresponding algorithms. This approach can be profitable for constructing efficient methods of solving systems of quadratic Boolean equations via “approximation” of corresponding Boolean functions by their affine normal forms.