Differential and Linear trail propagation in Noekeon

Question

In the Noekeon Cipher Specification they write the following :

The propagation through Lambda is denoted by $(a \rightarrow A)$, also called a step. Because of the linearity of Lambda it is fully deterministic: both for LC and DC patterns, we have: $A = \operatorname{Lambda}(a)$. The fact that the relation is the same for LC and DC is thanks to the fact that the Lambda is an orthogonal function. If represented in a matrix, its inverse is its transpose.

I'm having a hard time understanding why the orthogonality of Lambda affects the relation with regards to selection patterns (LC).

Why does the orthogonality of Lambda make it so that the relationship is the same as for DC ? How would the selection pattern propagate through the linear layer if Lambda was not orthogonal ?

Answer 1

This is due to the duality between linear and differential trails. Let $L$ be an invertible linear map on $\mathbb{F}_2^n$, think of it as a matrix for convenience. In general, a nonzero differential $\Delta_1 \to \Delta_2$ over $L$ must satisfy

$$\Delta_2 = L\,\Delta_1.$$

A nonzero linear approximation $u_1 \to u_2$, however, must satisfy

$$u_2 = L^{-\top}\,u_1$$

An elementary way to see this is to observe that $u_1^\top x = u_2^\top (Lx)$ is equivalent to $u_1^\top x = (L^\top\,u_2)^\top x$. This holds for all $x \in \mathbb{F}_2^n$ whenever $u_2 = L^{-\top}\,u_1$, and otherwise for half (some hyperplane) the $x$.

If $L$ is orthogonal, then $L^{-T} = L$. So then we have both $\Delta_2 = L\Delta_1$ and $u_2 = L u_1$.