Pseudo-Hadamard transform

The pseudo-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. Its main function is to provide cryptographic diffusion.

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 conceptually:

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

The actual implementation often dispenses with the intermediate variables giving:

 a += b
 b += a

This can be applied recursively to get a transform for any number of blocks that is a power of two. For example, if pht(a,b) does an in-place PHT of two blocks, then the in-place PHT for an array of four blocks is:

  pht(0,1)
  pht(2,3)
  pht(0,3)
  pht(2,4)

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

Matrix version

The transform can also be expressed as a matrix multiplication of a data vector by the appropriate member of a recursively-defined set of matrices.

The first matrix is:

$H_{1}={\begin{bmatrix}2&1\\1&1\end{bmatrix}}$

and the recursion rule is:

$H_{n}={\begin{bmatrix}2\times H_{n-1}&H_{n-1}\\H_{n-1}&H_{n-1}\end{bmatrix}}$

To reverse the transform, multiply by the inverse of the matrix.

Cryptographic properties

This has two very desirable properties for cryptographic use.

First, since the two-element transform is reversible, so are all the higher-level transforms constructed from it. For cryptography, a reversible transform is required so that decryption can be the inverse of encryption. The Walsh-Hadamard transform (same recursive structure but using a' = a+b, b' = a-b) does not have that property when modular arithmetic is involved, but the PHT variant does.

Second, for any level of the transform, it is clear that every output block depends on all input blocks. This is a very useful property in terms of cryptographic diffusion