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

<math>\Delta_F(a,b) = | \{ x \in \mathbb{F}_{2^n} : F(x) + F(a+x) = b \}|</math>

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

<math>\Delta_F = \max \{ \Delta_F(a,b) : a \in \mathbb{F}_{2^n}^*, b \in \mathbb{F}_{2^n} \}</math>

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).