Pseudo-Hadamard Transform

The pseudo-Hadamard transform is a reversible transformation of a bit string that provides cryptographic diffusion. See Hadamard transform.

The bit string must be of even length so that it can be split into two bit strings ''a'' and ''b'' of equal lengths, each of ''n'' bits. To compute the transform, ''a''' and ''b''', from these we use the equations:

:$a' = a + b \, \pmod$

:$b' = a + 2b\, \pmod$

To reverse this, clearly:

:$b = b' - a' \, \pmod$

:$a = 2a' - b' \, \pmod$

Generalization

The above equations can be expressed in matrix algebra, by considering ''a'' and ''b'' as two elements of a vector, and the transform itself as multiplication by a matrix of the form:

:$H_1 = \begin 2 & 1 \\ 1 & 1 \end$

The inverse can then be derived by inverting the matrix.

However, the matrix can be generalised to higher dimensions, allowing vectors of any power-of-two size to be transformed, using the following recursive rule:

:$H_n = \begin 2 \times H_ & H_ \\ H_ & H_ \end$

For example:

:$H_2 = \begin 4 & 2 & 2 & 1 \\ 2 & 2 & 1 & 1 \\ 2 & 1 & 2 & 1 \\ 1 & 1 & 1 & 1 \end$

See also

* SAFER
* Twofish
This is the Kronecker product of an Arnold Cat Map matrix with a Hadamard matrix.

References

* James Massey, "On the Optimality of SAFER+ Diffusion", 2nd AES Conference, 1999

* Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, "Twofish: A 128-Bit Block cipher, Block Cipher", 1998

* Helger Lipmaa. On Differential Properties of Pseudo-Hadamard Transform and Related Mappings. INDOCRYPT 2002, LNCS 2551, pp 48-61, 200


{{crypto-stub

External links

Fast Pseudo-Hadamard Transforms

Theory of cryptography
Transforms