Almost Perfect Nonlinear (APN) Functions

Background and definition

Almost perfect nonlinear (APN) functions are the class of [math]\displaystyle{ (n,n) }[/math] Vectorial Boolean Functions that provide optimum resistance to against differential attack. Intuitively, the differential attack against a given cipher incorporating a vectorial Boolean function [math]\displaystyle{ F }[/math] is efficient when fixing some difference [math]\displaystyle{ \delta }[/math] and computing the output of [math]\displaystyle{ F }[/math] for all pairs of inputs [math]\displaystyle{ (x_1,x_2) }[/math] whose difference is [math]\displaystyle{ \delta }[/math] produces output pairs with a difference distribution that is far away from uniform.

The formal definition of an APN function [math]\displaystyle{ F : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_{2^n} }[/math] is usually given through the values

[math]\displaystyle{ \Delta_F(a,b) = | \{ x \in \mathbb{F}_{2^n} : F(x) + F(a+x) = b \}| }[/math]

which, for [math]\displaystyle{ a \ne 0 }[/math], express the number of input pairs with difference [math]\displaystyle{ a }[/math] that map to a given [math]\displaystyle{ b }[/math]. The existence of a pair [math]\displaystyle{ (a,b) \in \mathbb{F}_{2^n}^* \times \mathbb{F}_{2^n} }[/math] with a high value of [math]\displaystyle{ \Delta_F(a,b) }[/math] makes the function [math]\displaystyle{ F }[/math] vulnerable to differential cryptanalysis. This motivates the definition of differential uniformity as

[math]\displaystyle{ \Delta_F = \max \{ \Delta_F(a,b) : a \in \mathbb{F}_{2^n}^*, b \in \mathbb{F}_{2^n} \} }[/math]

which clearly satisfies [math]\displaystyle{ \Delta_F \ge 2 }[/math] for any function [math]\displaystyle{ F }[/math]. 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. [math]\displaystyle{ F }[/math] is said to be strongly-plateuaed if, for every [math]\displaystyle{ a }[/math] and every [math]\displaystyle{ v }[/math], the size of the set [math]\displaystyle{ \{ b \in \mathbb{F}_2^n : D_aD_bF(x) = v \} }[/math] does not depend on [math]\displaystyle{ x }[/math], or, equivalently, the size of the set [math]\displaystyle{ \{ b \in \mathbb{F}_2^n : D_aF(b) = D_aF(x) + v \} }[/math] does not depend on [math]\displaystyle{ x }[/math].

Characterizations

Walsh transform

Any [math]\displaystyle{ (n,m) }[/math]-function [math]\displaystyle{ F }[/math] satisfies

[math]\displaystyle{ \sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^m}^*} W_F^4(a,b) \ge 2^{2n}(3 \cdot 2^{n+m} - 2^{m+1} - 2^{2n}) }[/math]

with equality characterizing APN functions.

In particular, for [math]\displaystyle{ (n,n) }[/math]-functions we have

[math]\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) }[/math]

with equality characterizing APN functions.

Sometimes, it is more convenient to sum through all [math]\displaystyle{ b \in \mathbb{F}_{2^m} }[/math] instead of just the nonzero ones. In this case, the inequality for [math]\displaystyle{ (n,m) }[/math]-functions becomes

[math]\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) }[/math]

and the particular case for [math]\displaystyle{ (n,n) }[/math]-functions becomes

[math]\displaystyle{ \sum_{a,b \in \mathbb{F}_{2^n}} W_F^4(a,b) \ge 2^{3n+1}(3 \cdot 2^{n-1} - 1) }[/math]

with equality characterizing APN functions in both cases.

Autocorrelation functions of the directional derivatives

Given a Boolean function [math]\displaystyle{ f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2 }[/math], the autocorrelation function of [math]\displaystyle{ f }[/math] is defined as

[math]\displaystyle{ \mathcal{F}(f) = \sum_{x \in \mathbb{F}_{2^n}} (-1)^{f(x)} = 2^n - 2wt(f). }[/math]

Any [math]\displaystyle{ (n,n) }[/math]-function [math]\displaystyle{ F }[/math] satisfies

[math]\displaystyle{ \sum_{\lambda \in \mathbb{F}_{2^n}} \mathcal{F}(D_af_\lambda) = 2^{2n+1} }[/math]

for any [math]\displaystyle{ a \in \mathbb{F}_{2^n}^* }[/math]. Equality occurs if and only if [math]\displaystyle{ F }[/math] is APN.

This allows APN functions to be characterized in terms of the sum-of-square-indicator [math]\displaystyle{ \nu(f) }[/math] defined as

[math]\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) }[/math]

for [math]\displaystyle{ \varphi_a(x) = {\rm Tr}(ax) }[/math].

Then any [math]\displaystyle{ (n,n) }[/math] function [math]\displaystyle{ F }[/math] satisfies

[math]\displaystyle{ \sum_{\lambda \in \mathbb{F}_{2^n}^*} \nu(f_\lambda) \ge (2^n-1)2^{2n+1} }[/math]

and equality occurs if and only if [math]\displaystyle{ F }[/math] is APN.

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

Characterization of Plateaued Functions

Characterization by the Derivatives

First characterization

Using the fact that two integer-valued functions over [math]\displaystyle{ \mathbb{F}_2^m }[/math] are equal precisely when their Fourier transforms are equal, one can obtain the following characterization.

Let [math]\displaystyle{ F }[/math] be an [math]\displaystyle{ (n,m) }[/math]-function. Then:

- [math]\displaystyle{ F }[/math] is plateaued if and only if, for every [math]\displaystyle{ v \in \mathbb{F}_2^m }[/math], the size of the set

[math]\displaystyle{ \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \} }[/math]

does not depend on [math]\displaystyle{ x }[/math];

- [math]\displaystyle{ F }[/math] is plateaued with single amplitude if and only if the size of the above set depends neither on [math]\displaystyle{ x }[/math] nor on [math]\displaystyle{ v }[/math] when [math]\displaystyle{ v \ne 0 }[/math].

Moreover:

- for any [math]\displaystyle{ (n,m) }[/math]-function [math]\displaystyle{ F }[/math], the value distribution of [math]\displaystyle{ D_aD_bF(x) }[/math] equals the value distribution of [math]\displaystyle{ D_aF(b) + D_aF(x) }[/math] as [math]\displaystyle{ (a,b) }[/math] ranges over [math]\displaystyle{ (\mathbb{F}_2^n)^2 }[/math];

- if two plateuaed functions have the same distribution, then for every [math]\displaystyle{ u }[/math], their component functions at [math]\displaystyle{ u }[/math] have the same amplitude.

Characterization in the Case of Unbalanced Components

Let [math]\displaystyle{ F }[/math] be an [math]\displaystyle{ (n,m) }[/math]-function. Then [math]\displaystyle{ F }[/math] is plateuaed with all components unbalanced if and only if, for every [math]\displaystyle{ v,x \in \mathbb{F}_2^n }[/math], we have

[math]\displaystyle{ | \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \} | = | \{ (a,b) \in (\mathbb{F}_2^n)^2 : F(a) + F(b) = v \} |. }[/math]

Moreover, [math]\displaystyle{ F }[/math] is plateuaed with single amplitude if and only if, in addition, this value does not depend on [math]\displaystyle{ v }[/math] for [math]\displaystyle{ v \ne 0 }[/math].

Properties of Strongly-Plateaued Functions

A Boolean function is strongly-plateaued if and only if its partially-bent. A v.B.f. is strongly-plateaued if and only if all of its component functions are partially-bent. In particular, bent and quadratic Boolean and vectorial functions are strongly-plateaued.

The image set [math]\displaystyle{ {\rm Im}(D_aF) }[/math] of any derivative of a strongly-plateaued function [math]\displaystyle{ F }[/math] is an affine space.