Almost Perfect Nonlinear (APN) Functions: Difference between revisions

From Boolean
No edit summary
No edit summary
Line 13: Line 13:
== 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> ==
== 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
Any <math>(n,m)</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>
<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.
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> ==
== 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 09:01, 18 January 2019

Background and definition

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

The formal definition of an APN 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^n}} is usually given through the values

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 \Delta_F(a,b) = | \{ x \in \mathbb{F}_{2^n} : F(x) + F(a+x) = b \}|}

which, 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 a \ne 0} , express the number of input pairs with difference 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} that map to a given 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 b} . The existence of a pair 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,b) \in \mathbb{F}_{2^n}^* \times \mathbb{F}_{2^n}} with a high value 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 \Delta_F(a,b)} makes the 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} vulnerable to differential cryptanalysis. This motivates the definition of differential uniformity 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 \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 (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 \Delta_F \ge 2} for any 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} . The functions meeting this lower bound are called almost perfect nonlinear (APN).

Characterizations

Walsh transform[1]

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,m)} -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_{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})}

with equality characterizing APN functions.

In particular, 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 we have

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^n}^*} W_F^4(a,b) \ge 2^{3n+1}(2^n-1)}

with equality characterizing APN functions.

Sometimes, it is more convenient to sum through all 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 b \in \mathbb{F}_{2^m}} instead of just the nonzero ones. In this case, the inequality 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,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 [2]

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.

  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
Retrieved from "http://boolean.wiki.uib.no/index.php?title=Almost_Perfect_Nonlinear_(APN)_Functions&oldid=119"