# Using Hadamard Form of a Matrix in the Block Cipher

Definition: A matrix A of size $2^n$ is a Hadamard matrix, if has the following form $$A= \left( \begin{array}{cc} U & V \\ V & U \end{array} \right)_{2^n\times 2^n}\, ,$$ where $U$ and $V$ are also Hadamard matrices.

Example: A Hadamard matrix A of size $2^2$ is as follows $$A= \left( \begin {array}{cccc} a_{{0}}&a_{{1}}&a_{{2}}&a_{{3}} \\ a_{{1}}&a_{{0}}&a_{{3}}&a_{{2}} \\ a_{{2}}&a_{{3}}&a_{{0}}&a_{{1}} \\ a_{{3}}&a_{{2}}&a_{{1}}&a_{{0}}\end {array} \right)\, ,$$ Where $a_i$, $0\leq i \leq 3$ are from any arbitrary field.

Consider B is a $2^n\times 2^n$ matrix such that the $(i,j)$the entry of B, denoted B$[i,j]$, is defined by B$[i,j]=a_{i \oplus j}$ where $i,j \in \{0,1,\cdots , 2^{n}-1\}$ and $i \oplus j$ means Xor between two numbers $i$ and $j$(for example $2 \oplus 3=1$ since $10 \oplus 11=01$).

Example: A matrix B of size $2^3$ is $$B= \left( \begin {array}{cccccccc} a_{{0}}&a_{{1}}&a_{{2}}&a_{{3}}&a_{{4 }}&a_{{5}}&a_{{6}}&a_{{7}}\\ a_{{1}}&a_{{0}}&a_{{3}} &a_{{2}}&a_{{5}}&a_{{4}}&a_{{7}}&a_{{6}}\\ a_{{2}}&a _{{3}}&a_{{0}}&a_{{1}}&a_{{6}}&a_{{7}}&a_{{4}}&a_{{5}} \\ a_{{3}}&a_{{2}}&a_{{1}}&a_{{0}}&a_{{7}}&a_{{6}}&a _{{5}}&a_{{4}}\\ a_{{4}}&a_{{5}}&a_{{6}}&a_{{7}}&a_{ {0}}&a_{{1}}&a_{{2}}&a_{{3}}\\ a_{{5}}&a_{{4}}&a_{{7 }}&a_{{6}}&a_{{1}}&a_{{0}}&a_{{3}}&a_{{2}}\\a_{{6}} &a_{{7}}&a_{{4}}&a_{{5}}&a_{{2}}&a_{{3}}&a_{{0}}&a_{{1}} \\ a_{{7}}&a_{{6}}&a_{{5}}&a_{{4}}&a_{{3}}&a_{{2}}&a _{{1}}&a_{{0}}\end {array} \right)=a_{i \oplus j}\qquad 0\leq i,j \leq 7 \, .$$

My question: Why the matrix B=$(a_{i \oplus j})$, $0\leq i,j \leq 2^{n}-1$, is an $2^n\times 2^n$ Hadamard matrix?

My Try: I can proof it by induction on $n$, but I would like to see its proof with other method.

Background: When entries of a Hadamard matrix come from the finite field $GF(2^q)$ and be an MDS matrix, then the Hadamard matrix can be used in the diffusion layer of block cipher such as Khazad block cipher

This is evident. Let $B$ be a $2^n \times 2^n$ matrix. We have:
$$a_{i\oplus (j+2^{n-1})}=a_{(2^{n-1}+i)\oplus j},a_{i\oplus j}=a_{(2^{n-1}+i)\oplus (2^{n-1}+j)}.$$
So, $B$ has the following form and therefore is a Hadamard matrix as follows $$B= \left( \begin{array}{cc} U & V \\ V & U \end{array} \right)_{2^n\times 2^n}\,$$
• Meysam, I suggest to add the condition $i,j \in \{0,1,\cdots, 2^{n-1}-1\}$ in your answer, since in the posted question it is assumed that $i,j \in \{0,1,\cdots, 2^{n}-1\}$. In fact, I wrote the values of $i$ and $j$ incorrectly and after that I edited the question and I modified it. Thanks – Amin235 Oct 30 '17 at 19:16