View source for Almost Perfect Nonlinear (APN) Functions

= Background and definition =

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

The formal definition of an APN function <math>F : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_{2^n}</math> is usually given through the values
<div><math>\Delta_F(a,b) = | \{ x \in \mathbb{F}_{2^n} : F(x) + F(a+x) = b \}|</math></div>
which, for <math>a \ne 0</math>, express the number of input pairs with difference <math>a</math> that map to a given <math>b</math>. The existence of a pair <math>(a,b) \in \mathbb{F}_{2^n}^* \times \mathbb{F}_{2^n}</math> with a high value of <math>\Delta_F(a,b)</math> makes the function <math>F</math> vulnerable to differential cryptanalysis. This motivates the definition of ''differential uniformity'' as
<div><math>\Delta_F = \max \{ \Delta_F(a,b) : a \in \mathbb{F}_{2^n}^*, b \in \mathbb{F}_{2^n} \}</math></div>
which clearly satisfies <math>\Delta_F \ge 2</math> for any function <math>F</math>. The functions meeting this lower bound are called ''almost perfect nonlinear (APN)''.

= Characterizations =

== Walsh transform<ref name="chavau1994">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</ref> ==

Any <math>(n,m)</math>-function <math>F</math> satisfies

<div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^m}^*} W_F^4(a,b) \ge 2^{2n}(3 \cdot 2^{n+m} - 2^{m+1} - 2^{2n})</math></div>

with equality characterizing APN functions.

In particular, for <math>(n,n)</math>-functions we have

<div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^n}^*} W_F^4(a,b) \ge 2^{3n+1}(2^n-1)</math></div>

with equality characterizing APN functions.

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

<div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^m}} W_F^4(a,b) \ge 2^{2n + m}(3 \cdot 2^n - 2)</math></div>

and the particular case for <math>(n,n)</math>-functions becomes

<div><math>\sum_{a,b \in \mathbb{F}_{2^n}} W_F^4(a,b) \ge 2^{3n+1}(3 \cdot 2^{n-1} - 1)</math></div>

with equality characterizing APN functions in both cases.

== Autocorrelation functions of the directional derivatives <ref name="bercanchalai2006"> 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</ref> ==

Given a Boolean function <math>f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2</math>, the ''autocorrelation function'' of <math>f</math> is defined as
<div><math>\mathcal{F}(f) = \sum_{x \in \mathbb{F}_{2^n}} (-1)^{f(x)} = 2^n - 2wt(f).</math></div>

Any <math>(n,n)</math>-function <math>F</math> satisfies
<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}} \mathcal{F}(D_af_\lambda) = 2^{2n+1}</math></div>
for any <math>a \in \mathbb{F}_{2^n}^*</math>. Equality occurs if and only if <math>F</math> is APN.

This allows APN functions to be characterized in terms of the ''sum-of-square-indicator'' <math>\nu(f)</math> defined as
<div><math>\nu(f) = \sum_{a \in \mathbb{F}_{2^n}} \mathcal{F}^2(D_aF) = 2^{-n} \sum_{a \in \mathbb{F}_{2^n}} \mathcal{F}^4(f + \varphi_a)</math></div>
for <math>\varphi_a(x) = {\rm Tr}(ax)</math>.

Then any <math>(n,n)</math> function <math>F</math> satisfies
<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}^*} \nu(f_\lambda) \ge (2^n-1)2^{2n+1}</math></div>
and equality occurs if and only if <math>F</math> is APN.

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

= Characterization of Plateaued Functions =

== Characterization by the Derivatives <ref name="carletPlateaued">Carlet C. Boolean and vectorial plateaued functions and APN functions. IEEE Transactions on Information Theory. 2015 Nov;61(11):6272-89.</ref> ==

=== First characterization ===

Using the fact that two integer-valued functions over <math>\mathbb{F}_2^m</math> are equal precisely when their Fourier transforms are equal, one can obtain the following characterization.

Let <math>F</math> be an <math>(n,m)</math>-function. Then:

- <math>F</math> is plateaued if and only if, for every <math>v \in \mathbb{F}_2^m</math>, the size of the set

<div><math> \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \}</math></div>

does not depend on <math>x</math>;

- <math>F</math> is plateaued with single amplitude if and only if the size of the above set depends neither on <math>x</math> nor on <math>v</math> when <math>v \ne 0</math>.

Moreover:

- for any <math>(n,m)</math>-function <math>F</math>, the value distribution of <math>D_aD_bF(x)</math> equals the value distribution of <math>D_aF(b) + D_aF(x)</math> as <math>(a,b)</math> ranges over <math>(\mathbb{F}_2^n)^2</math>;

- if two plateuaed functions have the same distribution, then for every <math>u</math>, their component functions at <math>u</math> have the same amplitude.

=== Characterization in the Case of Unbalanced Components ===

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

<div><math> | \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \} | = | \{ (a,b) \in (\mathbb{F}_2^n)^2 : F(a) + F(b) = v \} |.</math></div>

Moreover, <math>F</math> is plateuaed with single amplitude if and only if, in addition, this value does not depend on <math>v</math> for <math>v \ne 0</math>.