# Differential and Linear trail propagation in Noekeon

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 ?

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

• I suspected it was because of something like that. Could you just give some intuition as to why we want $u^T_1 x = u^T_2(Lx)$ in first place ? If I had to come up with that, I'd think it's the other way around $u^T_2 x = u^T_1 (Lx)$ just like the differential case. – Yuon Mar 17 '19 at 21:43
• @Yuon You can think of the output mask $u_2$ as a selection of some of the output bits, so you want $u_2^\top (Lx)$ because $Lx$ is the output. – Aleph Mar 18 '19 at 10:03