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

Kishan Chand Gupta; Palash Sarkar

Paper 2003/040

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.

Metadata

Available format(s): PS
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Boolean function Walsh transform algebraic normal form
Contact author(s): palash @ isical ac in
History: 2003-09-11: last of 3 revisions; 2003-03-03: received; See all versions
Short URL: https://ia.cr/2003/040
License: CC BY

BibTeX

@misc{cryptoeprint:2003/040,
      author = {Kishan Chand Gupta and Palash Sarkar},
      title = {Computing Partial Walsh Transform from the Algebraic Normal Form of a Boolean Function},
      howpublished = {Cryptology ePrint Archive, Paper 2003/040},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/040}},
      url = {https://eprint.iacr.org/2003/040}
}