# LAT of an SBox, values are even

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.

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$$.

• " (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!
– hola
Sep 14, 2020 at 4:42
• fixed! it should be $n=1$ Sep 14, 2020 at 7:21