**Computing Partial Walsh Transform from the Algebraic Normal Form of a Boolean Function
**

*Kishan Chand Gupta and 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.

**Category / Keywords: **secret-key cryptography / Boolean function, Walsh transform, algebraic normal form

**Date: **received 3 Mar 2003, last revised 11 Sep 2003

**Contact author: **palash at isical ac in

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20030911:104644 (All versions of this report)

**Short URL: **ia.cr/2003/040

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]