# Difference between revisions of "Almost Perfect Nonlinear (APN) Functions"

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 11:50, 15 January 2019

# Background and definition

Almost perfect nonlinear (APN) functions are the class of Vectorial Boolean Functions that provide optimum resistance to against differential attack. Intuitively, the differential attack against a given cipher incorporating a vectorial Boolean function is efficient when fixing some difference and computing the output of for all pairs of inputs whose difference is produces output pairs with a difference distribution that is far away from uniform.

The formal definition of an APN function is usually given through the values

which, for , express the number of input pairs with difference that map to a given . The existence of a pair with a high value of makes the function vulnerable to differential cryptanalysis. This motivates the definition of *differential uniformity* as

which clearly satisfies for any function . The functions meeting this lower bound are called *almost perfect nonlinear (APN)*.

# Characterizations

## Autocorrelation functions of the directional derivatives ^{[1]}

Given a Boolean function , the *autocorrelation function* of is defined as

Any -function satisfies

for any . Equality occurs if and only if is APN.

This allows APN functions to be characterized in terms of the *sum-of-square-indicator* defined as

for .

Then any function satisfies

and equality occurs if and only if 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