Linear Approximations of Pseudo-Hadamard Transform

In FSE 2003, Johan Wall′en proposed efficient log-time algorithms for computing linear approximations of addition modulo 2ⁿ. They posed that his algorithms can be generalized to more complex functions such as Pseudo-Hadamard Transform, but didn’t to the readers. In this paper, we present a formula for computing linear correlation of Pseudo-Hadamard Transform.