I've read that the fast Walsh–Hadamard transform is a way to efficiently calculate the linearity/non-linearity of an S-box. Can I get a description of it in simple steps or pseudocode that is restricted to simpler notation and terminology?

  • $\begingroup$ Maybe you could take this inquiry as motivation to study and figure out how to work with linear algebra in finite fields? $\endgroup$ Dec 29 '17 at 4:18

The fast Walsh-Hadamard transform algorithm generally applies to Hadamard matrices $H_n$ which are of dimension $2^n\times 2^n, n\geq 1$. Using row and column transpositions, $H_n$ can be arranged so that it is of the form $$H_n = \left[\begin{matrix}H_{n-1}& H_{n-1}\\H_{n-1}& -H_{n-1}\end{matrix}\right].$$ As a special case, note that $$H_1 = \left[\begin{matrix}+1& +1\\+1& -1\end{matrix}\right].$$

Now, the Hadamard transform of the (row) vector $\mathbf x$ of length $2^n$ is the row vector $\mathbf xH$ where, if we partition $\mathbf x$ as the concatenation of $2^{n-1}$-vectors $\mathbf x_L$ and $\mathbf x_R$ $\bigr($that is, $\mathbf x = \big[\mathbf x_L, \mathbf x_R\big]\bigr)$, then we can write $$\mathbf xH = \big[\mathbf x_L, \mathbf x_R\big]\left[\begin{matrix}H_{n-1}& H_{n-1}\\H_{n-1}& -H_{n-1}\end{matrix}\right] = \big[\mathbf x_LH_{n-1}+\mathbf x_RH_{n-1}, \mathbf x_LH_{n-1} - \mathbf x_RH_{n-1}\big].$$ This suggests that if we have already computed $\mathbf x_LH_{n-1}$ and $\mathbf x_RH_{n-1}$, we can compute $\mathbf xH$ in $2^n$ more additions/subtractions. So, we can proceed recursively, partitioning $\mathbf x_L$ into $\big[\mathbf x_{LL}, \mathbf x_{LR}\big]$ and $\mathbf x_R$ into $\big[\mathbf x_{RL}, \mathbf x_{RR}\big]$, and repeat the above calculations with shorter vectors,....

Pseudocode would be something like

recursive function FHT$(\mathbf x)$
partition $\mathbf x$ into two equal-length parts $\mathbf x_L$ and $\mathbf x_R$
$\mathbf y_L$ = FHT$(\mathbf x_L)$; $\mathbf y_R$ = FHT$(\mathbf x_R)$
return $\big[\mathbf y_L+\mathbf y_R,\mathbf y_L-\mathbf y_R\big]$.

The total number of additions/subtractions is $n2^n$; there are no multiplications needed

  • 1
    $\begingroup$ I probably should have qualified "simple" to exclude matrices. $\endgroup$
    – Melab
    Dec 22 '17 at 5:53
  • $\begingroup$ @Melab OK. Don’t read the first part of my answer (everything before the sentence beginning with “Pseudocode”). What is left has no mention of matrices whatsoever. Oh, you don’t understand vectors or arrays or the concept of dividing an array into a left half and a right half either? Well, in that case, ignore my entire answer and wait for someone else to give you the answer in terms that suit you. $\endgroup$ Dec 22 '17 at 15:33
  • $\begingroup$ Sorry if I offended you. I understand arrays. I also understand matrices, but not the ways they are typically used in cryptography. $\endgroup$
    – Melab
    Dec 22 '17 at 18:07
  • $\begingroup$ Is this the same as only evaluating for equal input and output masks? $\endgroup$
    – Melab
    Dec 22 '17 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.