Pseudo-Hadamard transform

The psuedo-Hadamard transform, or PHT, is a technique used in cryptography, primarily block cipher design. It was introduced in the SAFER ciphers and has been used in others such as Twofish. For cryptography, a reversible transform is required so that decryption can be the inverse of encryption. The Walsh-Hadamard transform does not have that property when modular arithmetic is involved, but the PHT variant does.

A two-element transform can be applied to any bit string of even length. Split it into two bit strings a and b of equal lengths, each of n bits. Then, with all arithmetic mod 2ⁿ, compute:

 a' = a + b
 b' = a + 2b

To reverse this, clearly:

 b = b' - a'
 a = 2a' - b'

Generally, the transform is done in place, so it becomes:

 x = a + b
 y = a + 2b
 a = x
 b = y

This can be applied recursively to get a transform for any size with 2ⁿ blocks. For example, if pht(ab,) does an in-place PHT of two blocks, then the in-place PHT for an array x[] of four blocks is:

  pht(x[0],x[1])
  pht(x[2],x[3])
  pht(x[0],x[2])
  pht(x[1],x[3])

For an 8-element transform, apply the 4-element one to the two halves then mix the halves with eight two-element transforms: pht(x[0],x[8]), .... pht(x[7],x[15]). This can be extended to 16, 32 ... 2ⁿ elements.

This has two very desirable properties for cryptography. First, since the two-element transform is reversible, so are all the higher-level transforms constructed from it. Second, for any level of ansform, it is clear that all output blocks are made to depend on all input blocks. This is a very useful property in terms of cryptographic diffusion.

The transform can also be expressed as a matrix multiplication involving a recursively-defined set of matrices.