Computing Partial Walsh Transform From the Algebraic Normal Form of a Boolean Function
Kishan Chand Gupta, Palash Sarkar · IEEE Transactions on Information Theory · 2009
We study the relationship between the Walsh transform and the algebraic normal form (ANF) of a Boolean function. In the first part of the paper, we obtain a formula for the Walsh transform at a certain point in terms of parameters derived from the algebraic normal form. We use previous results by Carlet and Guillot to obtain an explicit expression for the Walsh transform at a point in terms of parameters derived from the ANF. The second part of the paper is devoted to simplify this formula and develop an algorithm to evaluate it. This algorithm can be applied in situations where it is practically impossible to use the fast Walsh transform algorithm. Experimental results show that under certain conditions it is possible to execute our algorithm to evaluate the Walsh transform (at a small set of points) of functions on a few scores of variables having a few hundred terms in the algebraic normal form.