Almost Perfect Nonlinear (APN) Functions: Difference between revisions
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>(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
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
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).
Characterizations
Autocorrelation functions of the directional derivatives [1]
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
Any <math>(n,n)</math>-function <math>F</math> satisfies
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
for <math>\varphi_a(x) = {\rm Tr}(ax)</math>.
Then any <math>(n,n)</math> function <math>F</math> satisfies
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.
- ↑ 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