# Difference between revisions of "Almost Perfect Nonlinear (APN) Functions"

Jump to: navigation, search

# Background and definition

Almost perfect nonlinear (APN) functions are the class of ${\displaystyle (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 ${\displaystyle F}$ is efficient when fixing some difference ${\displaystyle \delta }$ and computing the output of ${\displaystyle F}$ for all pairs of inputs ${\displaystyle (x_{1},x_{2})}$ whose difference is ${\displaystyle \delta }$ produces output pairs with a difference distribution that is far away from uniform.

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

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

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

${\displaystyle \Delta _{F}=\max\{\Delta _{F}(a,b):a\in \mathbb {F} _{2^{n}}^{*},b\in \mathbb {F} _{2^{n}}\}}$

which clearly satisfies ${\displaystyle \Delta _{F}\geq 2}$ for any function ${\displaystyle F}$. The functions meeting this lower bound are called almost perfect nonlinear (APN).

# Characterizations

## Autocorrelation functions of the directional derivatives [1]

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

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

Any ${\displaystyle (n,n)}$-function ${\displaystyle F}$ satisfies

${\displaystyle \sum _{\lambda \in \mathbb {F} _{2^{n}}}{\mathcal {F}}(D_{a}f_{\lambda })=2^{2n+1}}$

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

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

${\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 ${\displaystyle \varphi _{a}(x)={\rm {Tr}}(ax)}$.

Then any ${\displaystyle (n,n)}$ function ${\displaystyle F}$ satisfies

${\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 ${\displaystyle 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