On the computation of the Walsh-Hadamard Transform using Binomial Trees

Abstract

The Walsh-Hadamard Transform is a fundamental tool to characterize several cryptographic properties of Boolean functions $f: \mathbb{F}_2^n \to \mathbb{F}_2$. It is well-known that this transform can be efficiently computed in $O(n2^n)$ steps by using the Fast Walsh Transform (FWT) algorithm, while the naive implementation requires $O(2^{2n})$ steps. In this talk, we investigate a new approach to compute the Walsh-Hadamard transform. The main data structure underlying this method is a binomial tree, where the path back to the root of each node represents a Walsh-Hadamard coefficient, and inductively defines the related scalar product. We show that the Walsh-Hadamard transform is obtained by visiting such a binomial tree, and consider both a depth-first and a breadth-first search strategy to perform this task. Although the resulting algorithms yield the same $\mathcal{O}(2^{2n})$ time complexity of the naive Walsh-Hadamard transform, we experimentally observe that they are faster in practice. We then show how to adapt the BFS-based algorithm to check a Boolean function’s correlation immunity order by requiring only its support as an input. Interestingly, this modified algorithm gives an efficient way to check whether a binary matrix of a large number of columns is an orthogonal array. Such a task cannot be practically accomplished with the Fast Walsh-Hadamard Transform procedure, due to the amount of memory required to hold the truth table of the associated Boolean function.