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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (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

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (a,b)\in \mathbb {F} _{2^{n}}^{*}\times \mathbb {F} _{2^{n}}} with a high value of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \Delta _{F}(a,b)} makes the function $F$ vulnerable to differential cryptanalysis. This motivates the definition of differential uniformity as

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \Delta _{F}=\max\{\Delta _{F}(a,b):a\in \mathbb {F} _{2^{n}}^{*},b\in \mathbb {F} _{2^{n}}\}}

which clearly satisfies Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \Delta _{F}\geq 2} for any function $F$. The functions meeting this lower bound are called almost perfect nonlinear (APN).

Characterizations

Walsh transform

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

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 $(n,n)$-functions we have

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \sum _{a\in \mathbb {F} _{2^{n}},b\in \mathbb {F} _{2^{n}}^{*}}W_{F}^{4}(a,b)\geq 2^{3n+1}(2^{n}-1)}

with equality characterizing APN functions.

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

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \sum _{a\in \mathbb {F} _{2^{n}},b\in \mathbb {F} _{2^{m}}}W_{F}^{4}(a,b)\geq 2^{2n+m}(3\cdot 2^{n}-2)}

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

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \sum _{a,b\in \mathbb {F} _{2^{n}}}W_{F}^{4}(a,b)\geq 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \nu (f)} defined as

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \varphi _{a}(x)={\rm {Tr}}(ax)} .

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

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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.

Characterization of Plateaued Functions

Characterization by the Derivatives

First characterization

Using the fact that two integer-valued functions over $\mathbb {F} _{2}^{m}$ are equal precisely when their Fourier transforms are equal, one can obtain the following characterization.

Let $F$ be an $(n,m)$-function. Then:

- $F$ is plateaued if and only if, for every Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v\in \mathbb {F} _{2}^{m}} , the size of the set

$\{(a,b)\in (\mathbb {F} _{2}^{n})^{2}:D_{a}D_{b}F(x)=v\}$

does not depend on $x$;

- $F$ is plateaued with single amplitude if and only if the size of the above set depends neither on $x$ nor on $v$ when Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v\neq 0} .

Moreover:

- for any $(n,m)$-function $F$, the value distribution of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle D_{a}D_{b}F(x)} equals the value distribution of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle D_{a}F(b)+D_{a}F(x)} as Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (a,b)} ranges over Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (\mathbb {F} _{2}^{n})^{2}} ;

- if two plateuaed functions have the same distribution, then for every $u$, their component functions at $u$ have the same amplitude.

Characterization in the Case of Unbalanced Components

Let $F$ be an $(n,m)$-function. Then $F$ is plateuaed with all components unbalanced if and only if, for every $v,x\in \mathbb {F} _{2}^{n}$, we have

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |\{(a,b)\in (\mathbb {F} _{2}^{n})^{2}:D_{a}D_{b}F(x)=v\}|=|\{(a,b)\in (\mathbb {F} _{2}^{n})^{2}:F(a)+F(b)=v\}|.}

Moreover, $F$ is plateuaed with single amplitude if and only if, in addition, this value does not depend on $v$ for Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v\neq 0} .