2
$\begingroup$

This is probably a silly question, but I could not find any reference. For the DDT of an SBox, it is easy to see why all the values are even. Is there any related result for LAT (i.e., all its values are even)?

LAT, for an $n \times n$ SBox, is a $2^n \times 2^n$ matrix with row $\alpha$ and column $\beta$ defined as follows: For all $n$-bit $\alpha$, $\beta$; count how many times $\alpha\cdot x \oplus \beta \cdot y = 0$ holds; and subtract $2^{n-1}$ from it; where $x$ is the vector of input variables, $y$ is the vector of output variables, and $\cdot$ is the dot product.

$\endgroup$
3
$\begingroup$

Let $N(\alpha,\beta)$ be the number of times the equation $$ \alpha\cdot x \oplus \beta \cdot y=0 \tag{0} \label{0} $$ holds. Then the LAT matrix entry is $$ L(\alpha\cdot x \oplus \beta \cdot y )= N(\alpha\cdot x \oplus \beta \cdot y)-2^{n-1} $$ and since the second term is even (can prove $n=1$ case directly) we need to show that $N(\alpha\cdot x \oplus \beta \cdot y)$ is even.

The basic idea is that the set of vectors over $\mathbb{F}_2^n$ of the form $$a\cdot x=c \tag{1} \label{1} $$ has even cardinality for any constant $c\in \mathbb{F}_2.$ Observe that this applied to $\alpha\cdot x$ and $\beta\cdot y$ means that $N(\alpha,\beta)$ is also even if we can prove $\eqref{1}$.

To prove $\eqref{1}$ assume $a\neq 0$ in $\mathbb{F}_2^n,$ since if $a=0,$ the relation holds for all $x\in \mathbb{F}_2^n,$ i.e., for $2^n$ vectors.

If $a\neq 0,$ let $w$ be the Hamming weight of $a$ and let $s_a$ be the support of $a,$ i.e., $s_a=\{i: 1\leq i\leq n, a_i=1\}$. Then, the inner product $a\cdot x$ is invariant when the components $a_i$ in the complement of the support take on all possible $2^n-2^w$ values, since they don't feature in the inner product. Clearly $2^n-2^w$ is even.

Finally note that equation $\eqref{0}$ holds if and only if $\alpha\cdot x$ and $\beta\cdot y$ are both equal to the same constant $c$. So it holds an even number of times.

Remark: This argument also works for an arbitrary $n\times m$ S-box $S:\mathbb{F}_2^n\rightarrow \mathbb{F}_2^m$ for any $m\geq 1$.

$\endgroup$
2
  • $\begingroup$ " (can prove $n=0$ case directly)" -- sorry, don't get it. $n$ is the size of the SBox, so $n=0$ does not mean anything! $\endgroup$ – hola Sep 14 '20 at 4:42
  • $\begingroup$ fixed! it should be $n=1$ $\endgroup$ – kodlu Sep 14 '20 at 7:21

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.