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

(Created page with "= Background and definition = Almost perfect nonlinear (APN) functions are the class of <math>(n,n)</math> Vectorial Boolean Functions that provide optimum resistance to...") |
|||

Line 10: | Line 10: | ||

= Characterizations = | = Characterizations = | ||

+ | |||

+ | == Autocorrelation functions of the directional derivatives == | ||

+ | |||

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

+ | <div><math>\mathcal{F}(f) = \sum_{x \in \mathbb{F}_{2^n}} (-1)^{f(x)} = 2^n - 2wt(f).</math></div> | ||

+ | |||

+ | Any <math>(n,n)</math>-function <math>F</math> satisfies | ||

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

## Revision as of 11:00, 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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.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 for any function . The functions meeting this lower bound are called *almost perfect nonlinear (APN)*.

# Characterizations

## Autocorrelation functions of the directional derivatives

Given a Boolean function , the *autocorrelation function* of **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f}**
is defined as

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal{F}(f) = \sum_{x \in \mathbb{F}_{2^n}} (-1)^{f(x)} = 2^n - 2wt(f).}**

Any -function **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F}**
satisfies

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{\lambda \in \mathbb{F}_{2^n}} \mathcal{F}(D_af_\lambda) = 2^{2n+1}}**

for any . Equality occurs if and only if **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F}**
is APN.