# 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 (π,π) Vectorial Boolean Functions that provide optimum resistance to against differential attack. Intuitively, the differential attack against a given cipher incorporating a vectorial Boolean function πΉ is efficient when fixing some difference πΏ and computing the output of πΉ for all pairs of inputs (π₯β,π₯β) whose difference is πΏ produces output pairs with a difference distribution that is far away from uniform.

The formal definition of an APN function πΉ : π½2π β π½2π 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 πβ 0, express the number of input pairs with difference π that map to a given π. The existence of a pair ${\displaystyle (a,b)\in \mathbb {F} _{2^{n}}^{*}\times \mathbb {F} _{2^{n}}}$ with a high value of ΞπΉ(π,π) makes the function πΉ 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 ΞπΉ β₯ 2 for any function πΉ. 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. πΉ is said to be strongly-plateuaed if, for every π and every π£, the size of the set ${\displaystyle \{b\in \mathbb {F} _{2}^{n}:D_{a}D_{b}F(x)=v\}}$ does not depend on π₯, or, equivalently, the size of the set ${\displaystyle \{b\in \mathbb {F} _{2}^{n}:D_{a}F(b)=D_{a}F(x)+v\}}$ does not depend on π₯.

# Characterizations

## Walsh transform[1]

Any (π,π)-function πΉ satisfies

${\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 (π,π)-functions we have

${\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 π β π½2π instead of just the nonzero ones. In this case, the inequality for (π,π)-functions becomes

${\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 (π,π)-functions becomes

${\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 [2]

Given a Boolean function π : π½2π β π½2, the autocorrelation function of π is defined as

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

Any (π,π)-function πΉ satisfies

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

for any π β π½*2π . 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 (π,π) function πΉ 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 πΉ is APN.

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

1. β Florent Chabaud, Serge Vaudenay, Links between differential and linear cryptanalysis, Workshop on the Theory and Application of Cryptographic Techniques, 1994 May 9, pp. 356-365, Springer, Berlin, Heidelberg
2. β 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