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

The characterization by means of the derivatives below suggests the following definition: a v.B.f. $F$ is said to be strongly-plateuaed if, for every $a$ and every $v$, the size of the set Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \{b\in \mathbb {F} _{2}^{n}:D_{a}D_{b}F(x)=v\}} does not depend on $x$, or, equivalently, the size of the set Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \{b\in \mathbb {F} _{2}^{n}:D_{a}F(b)=D_{a}F(x)+v\}} does not depend on $x$.

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 (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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)}

and the particular case for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,n)} -functions becomes

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{a,b \in \mathbb{F}_{2^n}} W_F^4(a,b) \ge 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 (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2} , the autocorrelation function of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} is defined as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{F}(f) = \sum_{x \in \mathbb{F}_{2^n}} (-1)^{f(x)} = 2^n - 2wt(f).}

Any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,n)} -function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} satisfies

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{\lambda \in \mathbb{F}_{2^n}} \mathcal{F}(D_af_\lambda) = 2^{2n+1}}

for any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in \mathbb{F}_{2^n}^*} . Equality occurs if and only if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is APN.

This allows APN functions to be characterized in terms of the sum-of-square-indicator Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu(f)} defined as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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)}

for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi_a(x) = {\rm Tr}(ax)} .

Then any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,n)} function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} satisfies

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{\lambda \in \mathbb{F}_{2^n}^*} \nu(f_\lambda) \ge (2^n-1)2^{2n+1}}

and equality occurs if and only if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is APN.

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