Almost Perfect Nonlinear (APN) Functions

Background and definition

Almost perfect nonlinear (APN) functions are the class of (𝑛,𝑛) Vectorial Boolean Functions that provide optimum resistance to against differential attack. Intuitively, the differential attack against a given cipher incorporating a vectorial Boolean function 𝐹 is efficient when fixing some difference 𝛿 and computing the output of 𝐹 for all pairs of inputs (𝑥₁,𝑥₂) whose difference is 𝛿 produces output pairs with a difference distribution that is far away from uniform.

The formal definition of an APN function 𝐹 : 𝔽_2^𝑛 → 𝔽_2^𝑛 is usually given through the values

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta_F(a,b) = | \{ x \in \mathbb{F}_{2^n} : F(x) + F(a+x) = b \}|}

which, for 𝑎≠0, express the number of input pairs with difference 𝑎 that map to a given 𝑏. The existence of a pair Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a,b) \in \mathbb{F}_{2^n}^* \times \mathbb{F}_{2^n}} with a high value of Δ_{𝐹(𝑎,𝑏)} makes the function 𝐹 vulnerable to differential cryptanalysis. This motivates the definition of differential uniformity as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta_F = \max \{ \Delta_F(a,b) : a \in \mathbb{F}_{2^n}^*, b \in \mathbb{F}_{2^n} \}}

which clearly satisfies Δ_𝐹 ≥ 2 for any function 𝐹. The functions meeting this lower bound are called almost perfect nonlinear (APN).

The characterization by means of the derivatives below suggests the following definition: a v.B.f. 𝐹 is said to be strongly-plateuaed if, for every 𝑎 and every 𝑣, the size of the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ b \in \mathbb{F}_2^n : D_aD_bF(x) = v \}} does not depend on 𝑥, or, equivalently, the size of the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ b \in \mathbb{F}_2^n : D_aF(b) = D_aF(x) + v \}} does not depend on 𝑥.

Characterizations

Walsh transform

Any (𝑛,𝑚)-function 𝐹 satisfies

$\sum _{a\in \mathbb {F} _{2^{n}},b\in \mathbb {F} _{2^{m}}^{*}}W_{F}^{4}(a,b)\geq 2^{2n}(3\cdot 2^{n+m}-2^{m+1}-2^{2n})$

with equality characterizing APN functions.

In particular, for (𝑛,𝑛)-functions we have

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^n}^*} W_F^4(a,b) \ge 2^{3n+1}(2^n-1)}

with equality characterizing APN functions.

Sometimes, it is more convenient to sum through all 𝑏 ∈ 𝔽_2^𝑚 instead of just the nonzero ones. In this case, the inequality for (𝑛,𝑚)-functions becomes

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^m}} W_F^4(a,b) \ge 2^{2n + m}(3 \cdot 2^n - 2)}

and the particular case for (𝑛,𝑛)-functions becomes

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{a,b \in \mathbb{F}_{2^n}} W_F^4(a,b) \ge 2^{3n+1}(3 \cdot 2^{n-1} - 1)}

with equality characterizing APN functions in both cases.

Autocorrelation functions of the directional derivatives

Given a Boolean function 𝑓 : 𝔽_2^𝑛 → 𝔽₂, the autocorrelation function of 𝑓 is defined as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{F}(f) = \sum_{x \in \mathbb{F}_{2^n}} (-1)^{f(x)} = 2^n - 2wt(f).}

Any (𝑛,𝑛)-function 𝐹 satisfies

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{\lambda \in \mathbb{F}_{2^n}} \mathcal{F}(D_af_\lambda) = 2^{2n+1}}

for any 𝑎 ∈ 𝔽*_2^𝑛 . Equality occurs if and only if $F$ is APN.

This allows APN functions to be characterized in terms of the sum-of-square-indicator Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu(f)} defined as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu(f) = \sum_{a \in \mathbb{F}_{2^n}} \mathcal{F}^2(D_aF) = 2^{-n} \sum_{a \in \mathbb{F}_{2^n}} \mathcal{F}^4(f + \varphi_a)}

for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_a(x) = {\rm Tr}(ax)} .

Then any (𝑛,𝑛) function 𝐹 satisfies

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{\lambda \in \mathbb{F}_{2^n}^*} \nu(f_\lambda) \ge (2^n-1)2^{2n+1}}

and equality occurs if and only if 𝐹 is APN.

Similar techniques can be used to characterize permutations and APN functions with plateaued components.