Almost Perfect Nonlinear (APN) Functions: Difference between revisions

From Boolean
Jump to navigation Jump to search
No edit summary
No edit summary
Line 10: Line 10:


= Characterizations =
= 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>(p,q)</math>-function <math>F</math> satisfies
<div><math>\sum_{a \in \mathbb{F}_{2^p}, b \in \mathbb{F}_{2^q}^*} W_F^4(a,b) \ge 2^{2p}(3 \cdot 2^{p+q} - 2^{q+1} - 2^{2p})</math></div>
with equality characterizing APN functions.


== 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> ==
== 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> ==

Revision as of 08:42, 18 January 2019

Background and definition

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

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

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

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

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

which clearly satisfies [math]\displaystyle{ \Delta_F \ge 2 }[/math] for any function [math]\displaystyle{ F }[/math]. The functions meeting this lower bound are called almost perfect nonlinear (APN).

Characterizations

Walsh transform[1]

Any [math]\displaystyle{ (p,q) }[/math]-function [math]\displaystyle{ F }[/math] satisfies

[math]\displaystyle{ \sum_{a \in \mathbb{F}_{2^p}, b \in \mathbb{F}_{2^q}^*} W_F^4(a,b) \ge 2^{2p}(3 \cdot 2^{p+q} - 2^{q+1} - 2^{2p}) }[/math]

with equality characterizing APN functions.


Autocorrelation functions of the directional derivatives [2]

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

[math]\displaystyle{ \mathcal{F}(f) = \sum_{x \in \mathbb{F}_{2^n}} (-1)^{f(x)} = 2^n - 2wt(f). }[/math]

Any [math]\displaystyle{ (n,n) }[/math]-function [math]\displaystyle{ F }[/math] satisfies

[math]\displaystyle{ \sum_{\lambda \in \mathbb{F}_{2^n}} \mathcal{F}(D_af_\lambda) = 2^{2n+1} }[/math]

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

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

[math]\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) }[/math]

for [math]\displaystyle{ \varphi_a(x) = {\rm Tr}(ax) }[/math].

Then any [math]\displaystyle{ (n,n) }[/math] function [math]\displaystyle{ F }[/math] satisfies

[math]\displaystyle{ \sum_{\lambda \in \mathbb{F}_{2^n}^*} \nu(f_\lambda) \ge (2^n-1)2^{2n+1} }[/math]

and equality occurs if and only if [math]\displaystyle{ F }[/math] 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