Welcome to the resource topic for 2003/040
Title:
Computing Partial Walsh Transform from the Algebraic Normal Form of a Boolean Function
Authors: Kishan Chand Gupta, Palash Sarkar
Abstract:We study the relationship between the Walsh transform and the algebraic normal form of
a Boolean function. In the first part of the paper, we carry out a combinatorial analysis
to obtain a formula for the Walsh transform at a certain point in terms of parameters derived
from the algebraic normal form. The second part of the paper is devoted to simplify this
formula and develop an algorithm to evaluate it. Our 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.
ePrint: https://eprint.iacr.org/2003/040
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .