Almost Perfect Nonlinear (APN) Functions: Difference between revisions

From Boolean
Jump to navigation Jump to search
No edit summary
No edit summary
Line 11: Line 11:
= Characterizations =
= Characterizations =


== Autocorrelation functions of the directional derivatives ==
== 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
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
Line 19: Line 19:
<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}} \mathcal{F}(D_af_\lambda) = 2^{2n+1}</math></div>
<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.
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.

Revision as of 10:50, 15 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

Autocorrelation functions of the directional derivatives [1]

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