Almost Perfect Nonlinear (APN) Functions

Background and definition

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

The formal definition of an APN function $F:{𝔽}_{2^n}\to {𝔽}_{2^n}$ is usually given through the values

${\Delta }_F(a,b)=|\{x\in {𝔽}_{2^n}:F(x)+F(a+x)=b\}|$

which, for $a\ne 0$, express the number of input pairs with difference $a$ that map to a given $b$. The existence of a pair $(a,b)\in {𝔽}_{2^n}^{\ast }\times {𝔽}_{2^n}$ with a high value of ${\Delta }_F(a,b)$ makes the function $F$ vulnerable to differential cryptanalysis. This motivates the definition of differential uniformity as

${\Delta }_F=max\{{\Delta }_F(a,b):a\in {𝔽}_{2^n}^{\ast },b\in {𝔽}_{2^n}\}$

which clearly satisfies ${\Delta }_F\ge 2$ for any function $F$. 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. $F$ is said to be strongly-plateuaed if, for every $a$ and every $v$, the size of the set $\{b\in {𝔽}_2^n:D_a{D}_{b}F(x)=v\}$ does not depend on $x$, or, equivalently, the size of the set $\{b\in {𝔽}_2^n:D_{a}F(b)=D_{a}F(x)+v\}$ does not depend on $x$.

Characterizations

Walsh transform

Any $(n,m)$-function $F$ satisfies

$\sum _{a\in {𝔽}_{2^n},b\in {𝔽}_{2^m}^{\ast }}{W}_F^4(a,b)\ge 2^{2n}(3\cdot 2^{n+m}-2^{m+1}-2^{2n})$

with equality characterizing APN functions.

In particular, for $(n,n)$-functions we have

$\sum _{a\in {𝔽}_{2^n},b\in {𝔽}_{2^n}^{\ast }}{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 $b\in {𝔽}_{2^m}$ instead of just the nonzero ones. In this case, the inequality for $(n,m)$-functions becomes

$\sum _{a\in {𝔽}_{2^n},b\in {𝔽}_{2^m}}{W}_F^4(a,b)\ge 2^{2n+m}(3\cdot 2^n-2)$

and the particular case for $(n,n)$-functions becomes

$\sum _{a,b\in {𝔽}_{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 $f:{𝔽}_{2^n}\to {𝔽}_2$, the autocorrelation function of $f$ is defined as

$ℱ(f)=\sum _{x\in {𝔽}_{2^n}}(-1{)}^{f(x)}=2^n-2wt(f).$

Any $(n,n)$-function $F$ satisfies

$\sum _{\lambda \in {𝔽}_{2^n}}ℱ(D_a{f}_{\lambda })=2^{2n+1}$

for any $a\in {𝔽}_{2^n}^{\ast }$. Equality occurs if and only if $F$ is APN.

This allows APN functions to be characterized in terms of the sum-of-square-indicator $\nu (f)$ defined as

$\nu (f)=\sum _{a\in {𝔽}_{2^n}}{ℱ}^2(D_{a}F)=2^{-n}\sum _{a\in {𝔽}_{2^n}}{ℱ}^4(f+{\phi }_a)$

for ${\phi }_a(x)=\mathrm{T}\mathrm{r}(ax)$.

Then any $(n,n)$ function $F$ satisfies

$\sum _{\lambda \in {𝔽}_{2^n}^{\ast }}\nu (f_{\lambda })\ge (2^n-1)2^{2n+1}$

and equality occurs if and only if $F$ is APN.

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