Boolean Functions with Affine Annihilators

Abstract

In the article we study boolean functions with affine annihilators. We have obtained results in both, estimating the number of functions under study and defining the relationship between Walsh-Hadamard coefficients of an arbitrary boolean function and its affine annihilator available. The second section of this article focuses on estimating the number of boolean functions with affine annihilators. The value has top and bottom bound. Besides, we have obtained the asymptotic estimate of the number of boolean functions with affine annihilators. The third section studies the Walsh-Hadamard coefficients of boolean functions with affine annihilators. First, we have derived the dependence of the Walsh-Hadamard coefficient on the distance between an arbitrary boolean function and a vector space of the affine function’s annihilators. Based on this result, we have obtained the dependence of distance between an arbitrary boolean function and a set of functions with affine annihilators on the spectrum of given function. Also we have defined the necessary and sufficient condition for the arbitrary boolean function to be with an affine annihilator available. Using the results obtained we bounded an absolute value of Walsh-Hadamard coefficients.Also we suggested a method for boolean equations analysis, which is based on two known methods. Namely, we used an analysis using annihilators and an analysis using linear analogs. We have obtained an estimate of the success probability of the suggested method for an arbitrary boolean function. Also we proved that bent functions are the most resistant to this analysis.The results obtained can be used in analysis of boolean equations. Also obtained dependences can be used, for instance, to study bent functions and algebraic immunity of boolean functions.

Keywords

• boolean functions
• annihilator
• affine function
• linear function
• walsh-hadamard coefficients
• bent functions