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:\mathbb {F} _{2^{n}}\rightarrow \mathbb {F} _{2^{n}}$ is usually given through the values

$\Delta _{F}(a,b)=|\{x\in \mathbb {F} _{2^{n}}:F(x)+F(a+x)=b\}|$ which, for $a\neq 0$ , express the number of input pairs with difference $a$ that map to a given $b$ . The existence of a pair $(a,b)\in \mathbb {F} _{2^{n}}^{*}\times \mathbb {F} _{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 \mathbb {F} _{2^{n}}^{*},b\in \mathbb {F} _{2^{n}}\}$ which clearly satisfies $\Delta _{F}\geq 2$ for any function $F$ . The functions meeting this lower bound are called almost perfect nonlinear (APN).

Characterizations

Autocorrelation functions of the directional derivatives 

Given a Boolean function $f:\mathbb {F} _{2^{n}}\rightarrow \mathbb {F} _{2}$ , the autocorrelation function of $f$ is defined as

${\mathcal {F}}(f)=\sum _{x\in \mathbb {F} _{2^{n}}}(-1)^{f(x)}=2^{n}-2wt(f).$ Any $(n,n)$ -function $F$ satisfies

$\sum _{\lambda \in \mathbb {F} _{2^{n}}}{\mathcal {F}}(D_{a}f_{\lambda })=2^{2n+1}$ for any $a\in \mathbb {F} _{2^{n}}^{*}$ . 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 \mathbb {F} _{2^{n}}}{\mathcal {F}}^{2}(D_{a}F)=2^{-n}\sum _{a\in \mathbb {F} _{2^{n}}}{\mathcal {F}}^{4}(f+\varphi _{a})$ for $\varphi _{a}(x)={\rm {Tr}}(ax)$ .

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

$\sum _{\lambda \in \mathbb {F} _{2^{n}}^{*}}\nu (f_{\lambda })\geq (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.

1. Thierry Berger, Anne Canteaut, Pascale Charpin, Yann Laigle-Chapuy, On Almost Perfect Nonlinear Functions Over GF(2^n), IEEE Transactions on Information Theory, 2006 Sep,52(9),4160-70